Ramsey Number

The Ramsey number $R(m,n)$ gives the solution to the Party Problem, which asks the minimum number of guests $R(m,n)$ that must be invited so that at least $m$ will know each other (i.e., there exists a Clique of order $m$) or at least $n$ will not know each other (i.e., there exists an independent set of order $n$). By symmetry, it is true that

$$R(m,n)=R(n,m).$$ (1)

It also must be true that

$$R(2,m)=m.$$ (2)

A generalized Ramsey number is written

$$R(m_1, \ldots, m_k; n)$$ (3)

and is the smallest Integer $r$ such that, no matter how each $n$-element Subset of an $r$-element Set is colored with $k$ colors, there exists an $i$ such that there is a Subset of size $m_i$, all of whose $n$-element Subsets are color $i$. The usual Ramsey numbers are then equivalent to $R(m,n)=R(m, n; 2)$.

Bounds are given by

$$R(k,l)\leq \cases{ R(k-1,l)+R(k,l-1)-1\cr \hfill {\rm for\ ... ...\rm\ even}\cr R(k-1,l)+R(k,l-1)\cr \hfill {\rm otherwise}\cr}$$ (4)

and

$$R(k,k)\leq 4R(k-2,k)+2$$ (5)

(Chung and Grinstead 1983). Erdös proved that for diagonal Ramsey numbers $R(k,k)$,

$${k2^{k/2}\over e\sqrt{2}} < R(k,k).$$ (6)

This result was subsequently improved by a factor of 2 by Spencer (1975). $R(3,k)$ was known since 1980 to be bounded from above by $c_2k^2/\ln k$, and Griggs (1983) showed that $c_2=5/12$ was an acceptable limit. J.-H. Kim (Cipra 1995) subsequently bounded $R(3,k)$ by a similar expression from below, so

$$c_1 {k^2\over \ln k} \leq R(3,k) \leq c_2 {k^2\over\ln k}.$$ (7)

Burr (1983) gives Ramsey numbers for all 113 graphs with no more than 6 Edges and no isolated points.

A summary of known results up to 1983 for $R(m,n)$ is given in Chung and Grinstead (1983). Radziszowski maintains an up-to-date list of the best current bounds, reproduced in part in the following table for $R(m,n;2)$.

$m$	$n$	$R(m,n)$	Reference
3	3	6	Greenwood and Gleason 1955
3	4	9	Greenwood and Gleason 1955
3	5	14	Greenwood and Gleason 1955
3	6	18	Graver and Yackel 1968
3	7	23	Kalbfleisch 1966
3	8	28	McKay and Min 1992
3	9	36	Grinstead and Roberts 1982
3	10	[40, 43]	Exoo 1989, Radziszowski and Kreher 1988
3	11	[46, 51]	Radziszowski and Kreher 1988
3	12	[52, 60]	Exoo 1993, Radziszowski and Kreher 1988, Exoo 1998
3	13	[60, 69]	XZ, Radziszowski and Kreher 1988
3	14	[66, 78]	Exoo (unpub.), Radziszowski and Kreher 1988
3	15	[73, 89]	Wang and Wang 1989, Radziszowski (unpub.)
3	16	[79, $\infty$]	Wang and Wang 1989
3	17	[92, $\infty$]	WWY
3	18	[98, $\infty$]	WWY
3	19	[106, $\infty$]	WWY
3	20	[109, $\infty$]	WWY
3	21	[122, $\infty$]	WWY
3	22	[125, $\infty$]	WWY
3	23	[136, $\infty$]	WWY
4	4	18	Greenwood and Gleason 1955
4	5	25	Mckay and Radziszowski 1995
4	6	[35, 41]	Ex8, MR4
4	7	[49, 62]
4	8	[55, 85]	Exoo 1998
4	9	[69, 116]
4	10	[80, 151]
4	11	[93, 191]
4	12	[98, 238]
4	13	[112, 291]
4	14	[119, 349]
4	15	[128, 417]
5	5	[43, 49]	Ex4, MR4
5	6	[58, 87]	Exoo 1993, Walker 1971
5	7	[80, 143]
5	8	[95, 216]
5	9	[116, 371]	Exoo 1998
5	10	[1, 445]
6	6	[102, 165]	Kalbfleisch 1965, Mac
6	7	[109, 300]	Exoo 1998
6	8	[122, 497]	Exoo 1998
6	9	[153, 784]
6	10	[167, 1180]
7	7	[205, 545]	Hill and Irving 1982, Giraud 1973
7	8	[1, 1035]
7	9	[1, 1724]
7	10	[1, 2842]
8	8	[282, 1874]
8	9	[1, 3597]
8	10	[1, 6116]
9	9	[565, 6680]
9	10	[1, 12795]
10	10	[798, 23981]	Guldan and Tomasta ?
11	11	[522, $\infty$]	Guldan and Tomasta ?

Known values for generalized Ramsey numbers are given in the following table.

$R(\ldots; 2)$	Bounds	Reference
$R(3, 3, 3; 2)$	17	Greenwood and Gleason 1955
$R(3, 3, 4; 2)$	[30, 32]
$R(3, 3, 5; 2)$	[45, 59]
$R(3, 4, 5; 2)$	$\geq 80$	Exoo 1998
$R(3, 4, 4; 2)$	[55, 81]
$R(4, 4, 4; 2)$	[128, 242]	Hill and Irving 1982, Giraud 1973
$R(3, 3, 3, 3; 2)$	[51, 64]	Chung 1973, Sanchez-Flores 1995
$R(3, 3, 3, 4; 2)$	[87, 159]	Exoo 1998
$R(3, 3, 3, 3, 3; 2)$	[162, 317]
$R(3, 3, 3, 3, 3, 3; 2)$	[1, 500]

$R(\ldots; 3)$	Bounds
$R(4, 4; 3)$	[14, 15]

See also Clique, Complete Graph, Extremal Graph, Irredundant Ramsey Number, Schur Number

References

Burr, S. A. ``Generalized Ramsey Theory for Graphs--A Survey.'' In Graphs and Combinatorics (Ed. R. A. Bari and F. Harary). New York: Springer-Verlag, pp. 52-75, 1964.

Burr, S. A. ``Diagonal Ramsey Numbers for Small Graphs.'' J. Graph Th. 7, 57-69, 1983.

Chartrand, G. ``The Problem of the Eccentric Hosts: An Introduction to Ramsey Numbers.'' §5.1 in Introductory Graph Theory. New York: Dover, pp. 108-115, 1985.

Chung, F. R. K. ``On the Ramsey Numbers $N(3, 3, \ldots, 3;2)$.'' Discrete Math. 5, 317-321, 1973.

Chung, F. and Grinstead, C. G. ``A Survey of Bounds for Classical Ramsey Numbers.'' J. Graph. Th. 7, 25-37, 1983.

Cipra, B. ``A Visit to Asymptopia Yields Insights into Set Structures.'' Science 267, 964-965, 1995.

Exoo, G. ``On Two Classical Ramsey Numbers of the Form $R(3,n)$.'' SIAM J. Discrete Math. 2, 488-490, 1989.

Exoo, G. ``Announcement: On the Ramsey Numbers $R(4,6)$, $R(5,6)$ and $R(3,12)$.'' Ars Combin. 35, 85, 1993.

Exoo, G. ``Some New Ramsey Colorings.'' Electronic J. Combinatorics 5, No. 1, R29, 1-5, 1998. http://www.combinatorics.org/Volume_5/v5i1toc.html.

Folkmann, J. ``Notes on the Ramsey Number $N(3,3,3,3)$.'' J. Combinat. Theory. Ser. A 16, 371-379, 1974.

Gardner, M. ``Mathematical Games: In Which Joining Sets of Points by Lines Leads into Diverse (and Diverting) Paths.'' Sci. Amer. 237, 18-28, 1977.

Gardner, M. Penrose Tiles and Trapdoor Ciphers... and the Return of Dr. Matrix, reissue ed. New York: W. H. Freeman, pp. 240-241, 1989.

Giraud, G. ``Une minoration du nombre de quadrangles unicolores et son application a la majoration des nombres de Ramsey binaires bicolors.'' C. R. Acad. Sci. Paris A 276, 1173-1175, 1973.

Graham, R. L.; Rothschild, B. L.; and Spencer, J. H. Ramsey Theory, 2nd ed. New York: Wiley, 1990.

Graver, J. E. and Yackel, J. ``Some Graph Theoretic Results Associated with Ramsey's Theorem.'' J. Combin. Th. 4, 125-175, 1968.

Greenwood, R. E. and Gleason, A. M. ``Combinatorial Relations and Chromatic Graphs.'' Canad. J. Math. 7, 1-7, 1955.

Griggs, J. R. ``An Upper Bound on the Ramsey Numbers $R(3,k)$.'' J. Comb. Th. A 35, 145-153, 1983.

Grinstead, C. M. and Roberts, S. M. ``On the Ramsey Numbers $R(3,8)$ and $R(3,9)$.'' J. Combinat. Th. Ser. B 33, 27-51, 1982.

Guldan, F. and Tomasta, P. ``New Lower Bounds of Some Diagonal Ramsey Numbers.'' J. Graph. Th. 7, 149-151, 1983.

Hanson, D. ``Sum-Free Sets and Ramsey Numbers.'' Discrete Math. 14, 57-61, 1976.

Harary, F. ``Recent Results on Generalized Ramsey Theory for Graphs.'' Graph Theory and Applications (Ed. Y. Alai, D. R. Lick, and A. T. White). New York: Springer-Verlag, pp. 125-138, 1972.

Hill, R. and Irving, R. W. ``On Group Partitions Associated with Lower Bounds for Symmetric Ramsey Numbers.'' European J. Combin. 3, 35-50, 1982.

Kalbfleisch, J. G. Chromatic Graphs and Ramsey's Theorem. Ph.D. thesis, University of Waterloo, January 1966.

McKay, B. D. and Min, Z. K. ``The Value of the Ramsey Number $R(3,8)$.'' J. Graph Th. 16, 99-105, 1992.

McKay, B. D. and Radziszowski, S. P. ``$R(4,5)=25$.'' J. Graph. Th 19, 309-322, 1995.

Piwakowski, K. ``Applying Tabu Search to Determine New Ramsey Numbers.'' Electronic J. Combinatorics 3, R6 1-4, 1996. http://www.combinatorics.org/Volume_3/volume3.html#R6.

Radziszowski, S. P. ``Small Ramsey Numbers.'' Electronic J. Combin. 1, DS1 1-29, Rev. Mar. 25, 1996. http://ejc.math.gatech.edu:8080/Journal/Surveys/ds1.ps.

Radziszowski, S. and Kreher, D. L. ``Upper Bounds for Some Ramsey Numbers $R(3,k)$.'' J. Combinat. Math. Combin. Comput. 4, 207-212, 1988.

Spencer, J. H. ``Ramsey's Theorem--A New Lower Bound.'' J. Combinat. Theory Ser. A 18, 108-115, 1975.

Wang, Q. and Wang, G. ``New Lower Bounds for the Ramsey Numbers $R(3,q)$.'' Beijing Daxue Xuebao 25, 117-121, 1989.

Whitehead, E. G. ``The Ramsey Number $N(3,3,3,3;2)$.'' Discrete Math. 4, 389-396, 1973.