TOPICS
Search

Ramsey Number


The Ramsey number R(m,n), sometimes also denoted r(s,t) (e.g., Mattheus and Verstraete 2023), 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 or at least n will not know each other. In the language of graph theory, the Ramsey number is the minimum number of vertices v=R(m,n) such that all undirected simple graphs of order v contain a clique of order m or an independent set of order n. Ramsey's theorem states that such a number exists for all m and n.

By symmetry, it is true that

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

It also must be true that

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

A generalized Ramsey number is written

 R(m_1,...,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)<={R(k-1,l)+R(k,l-1)-1   for  R(k-1,l)  and  R(k,l-1)  even; R(k-1,l)+R(k,l-1)   otherwise
(4)

and

 R(k,k)<=4R(k-2,k)+2
(5)

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

 (k2^(k/2))/(esqrt(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/lnk, 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)/(lnk)<=R(3,k)<=c_2(k^2)/(lnk).
(7)

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

Mattheus and Verstraete (2023) proved that

 R(4,t)=Omega((t^3)/(ln^4t))
(8)

as t->infty, where Omega is big-omega notation. This determines R(4,t) up to a factor of order ln^2t.

A summary of known results up to 1983 for R(m,n) is given in Chung and Grinstead (1983). Radziszowski (2021) maintains an up-to-date list of the best current bounds. The numbers whose exact values are known are summarized below.

mnR(m,n)Reference
336Greenwood and Gleason (1955)
349Greenwood and Gleason (1955)
3514Greenwood and Gleason (1955)
3618Graver and Yackel (1968)
3723Kalbfleisch (1966)
3828McKay and Min (1992)
3936Grinstead and Roberts 1982
4418Greenwood and Gleason (1955)
4525McKay and Radziszowski (1995)

See also

Clique, Clique Number, Complete Graph, Extremal Graph, Independence Number, Independent Set, Irredundant Ramsey Number, Ramsey's Theorem, Ramsey Theory, Schur Number

Explore with Wolfram|Alpha

References

Burling, J. P. and Reyner, S. W. "Some Lower Bounds of the Ramsey Numbers n(k,k)." J. Combin. Th. Ser. B 13, 168-169, 1972.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, 1974.Burr, S. A. "Diagonal Ramsey Numbers for Small Graphs." J. Graph Th. 7, 57-69, 1983.Burr, S. A.; Erdős, P.; Faudree, R. J.; and Schelp, R. H. "On the Difference between Consecutive Ramsey Numbers." Util. Math. 35, 115-118, 1989.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,...,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. "Applying Optimization Algorithm to Ramsey Problems." In Graph Theory, Combinatorics, Algorithms, and Applications (Ed. Y. Alavi). Philadelphia: SIAM, pp. 175-179, 1989a.Exoo, G. "A Lower Bound for R(5,5)." J. Graph Th. 13, 97-98, 1989.Exoo, G. "On Two Classical Ramsey Numbers of the Form R(3,n)." SIAM J. Discrete Math. 2, 488-490, 1989c.Exoo, G. "Announcement: On the Ramsey Numbers R(4,6), R(5,6) and R(3,12)." Ars Combin. 35, 85, 1993.Exoo, G. "A Lower Bound for Schur Numbers and Multicolor Ramsey Numbers of K_3." Electronic J. Combinatorics 1, No. 1, R8, 1-3, 1994. http://www.combinatorics.org/Volume_1/Abstracts/v1i1r8.html.Exoo, G. "Some New Ramsey Colorings." Electronic J. Combinatorics 5, No. 1, R29, 1-5, 1998. http://www.combinatorics.org/Volume_5/Abstracts/v5i1r29.html.Exoo, G. "Some Applications of pq-Groups in Graph Theory." Preprint. 2002.Folkmann, J. "Notes on the Ramsey Number N(3,3,3,3)." J. Combinat. Theory. Ser. A 16, 371-379, 1974.Fredricksen, H. "Schur Numbers and the Ramsey Numbers N(3,3,...,3;2)." J. Combin. Theory Ser. A 27, 376-377, 1979.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.Haanpää, H. "A Lower Bound for a Ramsey Number." Congr. Numer. 144, 189-191, 2000.Hanson, D. "Sum-Free Sets and Ramsey Numbers." Discrete Math. 14, 57-61, 1976.Harary, F. "Recent Results on Generalized Ramsey Theory for Graphs." In Graph Theory and Applications: Proceedings of the Conference at Western Michigan University, Kalamazoo, Mich., May 10-13, 1972 (Ed. Y. Alavi, D. R. Lick, and A. T. White). New York: Springer-Verlag, pp. 125-138, 1972.Harborth, H. and Krause, S. "Ramsey Numbers for Circulant Colorings." Congr. Numer. 161, 139-150, 2003.Hill, R. and Irving, R. W. "On Group Partitions Associated with Lower Bounds for Symmetric Ramsey Numbers." European J. Combin. 3, 35-50, 1982.Hoffman, P. The Man Who Loved Only Numbers: The Story of Paul Erdős and the Search for Mathematical Truth. New York: Hyperion, pp. 52-53, 1998.Huang, Y. R. and Zhang, K. M. "An New Upper Bound Formula for Two Color Classical Ramsey Numbers." J. Combin. Math. Combin. Comput. 28, 347-350, 1998.Kalbfleisch, J. G. Chromatic Graphs and Ramsey's Theorem. Ph.D. thesis, University of Waterloo, January 1966.Lesser, A. "Theoretical and Computational Aspects of Ramsey Theory." Examensarbeten i Matematik, Matematiska Institutionen, Stockholms Universitet 3, 2001.Luo, H.; Su, W.; and Li, Z. "The Properties of Self-Complementary Graphs and New Lower Bounds for Diagonal Ramsey Numbers." Australasian J. Combin. 25, 103-116, 2002.Luo, H.; Su, W.; and Shen, Y.-Q. "New Lower Bounds of Ten Classical Ramsey Numbers." Australasian J. Combin. 24, 81-90, 2001.Luo, H.; Su, W.; Zhang, Z.; and Li, G. "New Lower Bounds for Twelve Classical 2-Color Ramsey Numbers R(k,l)." Guangxi Sci. 7, 120-121, 2000.Mackey, J. Combinatorial Remedies. Ph.D. thesis. Department of Mathematics, University of Hawaii, 1994.Mathon, R. "Lower Bounds for Ramsey Numbers and Association Schemes." J. Combin. Th. Ser. B 42, 122-127, 1987.Mattheus, S. and Verstraete, J. "The asymptotics of r(r,t)." https://arxiv.org/abs/2306.04007. 7 Jun 2023.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, No. 1, R6, 1-4, 1996. http://www.combinatorics.org/Volume_3/Abstracts/v3i1r6.html.Radziszowski, S. P. "Small Ramsey Numbers." Electronic J. Combinatorics Dynamical Survey DS1, 1-116, Jan. 15, 2021. http://www.combinatorics.org/Surveys/#DS1.Radziszowski, S. and Kreher, D. L. "Search Algorithm for Ramsey Graphs by Union of Group Orbits." J. Graph Th. 12, 59-72, 1988a.Radziszowski, S. and Kreher, D. L. "Upper Bounds for Some Ramsey Numbers R(3,k)." J. Combinat. Math. Combin. Comput. 4, 207-212, 1988b.Robertson, A. "New Lower Bounds for Some Multicolored Ramsey Numbers." Electronic J. Combinatorics 6, No. 1, R3, 1-6, 1999. http://www.combinatorics.org/Volume_6/Abstracts/v6i1r3.html.Shearer, J. B. "Lower Bounds for Small Diagonal Ramsey Numbers." J. Combin. Th. Ser. A 42, 302-304, 1986.Shi, L. S. "Upper Bounds for Ramsey Numbers." Preprint. 2002.Shi, L. S. and Zhang, K. M. "An Upper Bound Formula for Ramsey Numbers" Preprint. 2001.Spencer, J. H. "Ramsey's Theorem--A New Lower Bound." J. Combinat. Theory Ser. A 18, 108-115, 1975.Spencer, T. "Upper Bounds for Ramsey Numbers via Linear Programming." Preprint. 1994.Su, W.; Luo, H.; Li, G.; and Li, Q. "Lower Bounds of Ramsey Numbers Based on Cubic Residues." Disc. Math. 250, 197-209, 2002.Su, W.; Luo, H.; Li, G.; and Li, Q. "New Lower Bounds of Classical Ramsey Numbers R(4,12), R(5,11), and R(5,12)." Chinese Sci. Bull. 43, 528, 1998.Su, W.; Luo, H.; Zhang, Z.; and Li, G. "New Lower Bounds of Fifteen Classical Ramsey Numbers." Australasian J. Combin. 19, 91-99, 1999.Wang, Q. and Wang, G. "New Lower Bounds for the Ramsey Numbers R(3,q)." Beijing Daxue Xuebao 25, 117-121, 1989.Wang, Q.; Wang, G.; and Yan, S. "A Search Algorithm and New Lower Bounds for Ramsey Numbers r(3,q)." Preprint. 1994.Whitehead, E. G. "The Ramsey Number N(3,3,3,3;2)." Discrete Math. 4, 389-396, 1973.Xiaodong, X. and Zheng, X. "A Constructive Approach for the Lower Bounds on the Ramsey Numbers r(k,l)." Unpublished manuscript, 2002.Xiaodong, X.; Zheng, X.; Exoo, G.; and Radziszowski, S. P. "Constructive Lower Bounds on Classical Multicolor Ramsey Numbers." Elec. J. Combin. 11, 2004. http://www.combinatorics.org/Volume_11/PDF/v11i1r35.pdf.

Referenced on Wolfram|Alpha

Ramsey Number

Cite this as:

Weisstein, Eric W. "Ramsey Number." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/RamseyNumber.html

Subject classifications