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 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


It also must be true that


A generalized Ramsey number is written


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



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


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


Burr (1983) gives Ramsey numbers for all 113 graphs with no more than 6 graph 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 (2004) maintains an up-to-date list of the best current bounds. Results from Tables I and II of Radziszowski (2004) are reproduced below in a slightly less cramped format than in the original. Known bounds for generalized Ramsey numbers (multicolor graph numbers), hypergraph Ramsey numbers, and many other types of Ramsey numbers may be found in Radziszowski (2004). In the absence of a published upper bound, the theorem of Erdős-Szekeres stating that R(k,l)<(k+l-2; l-1) is used to provide one.

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
310[40, 43]Exoo 1989c, Radziszowski and Kreher 1988
311[46, 51]Radziszowski and Kreher 1988
312[52, 59]Exoo 1993, Radziszowski and Kreher 1988, Exoo 1998, Lesser 2001
313[59, 69]Piwakowski 1996, Radziszowski and Kreher 1988
314[66, 78]Exoo (unpub.), Radziszowski and Kreher 1988
315[73, 88]Wang and Wang 1989, Radziszowski (unpub.), Lesser 2001
316[79, 135]Wang and Wang 1989
317[92, 152]Wang et al. 1994
318[98, 170]Wang et al. 1994
319[106, 189]Wang et al. 1994
320[109, 209]Wang et al. 1994
321[122, 230]Wang et al. 1994
322[125, 252]Wang et al. 1994
323[136, 275]Wang et al. 1994
4418Greenwood and Gleason 1955
4525McKay and Radziszowski 1995
46[35, 41]Exoo (unpub.), McKay and Radziszowski 1995
47[49, 61]Exoo 1989a, Mackey 1994
48[56, 84]Exoo 1998, Exoo 2002
49[73, 115]Radziszowski 1988, Mackey 1994
410[92, 149]Piwakowski 1996, Mackey 1994, Harboth and Krause 2003
411[97, 191]Piwakowski 1996, Spencer 1994, Burr et al. 1989
412[128, 238]Su et al. 1998, Spencer 1994
413[133, 291]Xu and Xie 2002
414[141, 349]Xu and Xie 2002
415[153, 417]Xu and Xie 2002
416[153, 815]
417[182, 968]Luo et al. 2001
418[182, 1139]
419[198, 1329]Luo et al. 2002
420[230, 1539]Su et al. 1999
421[242, 1770]Su et al. 1999
422[282, 2023]Su et al. 1999
55[43, 49]Exoo 1989b, McKay and Radziszowski 1995
56[58, 87]Exoo 1993, Walker 1971
57[80, 143]CET, Spencer 1994
58[101, 216]Piwakowski 1996, Spencer 1994, Harborth and Krause 2003
59[125, 316]Exoo 1998, Haanpää 2000
510[143, 442]Exoo 1998, Mackey 1994
511[157, 1000]Exoo 1998, Xiaodong et al. 2004
512[181, 1364]Exoo 1998
513[205, 1819]Exoo 1998, Xiaodong et al. 2004
514[233, 2379]Exoo 1998, Xiaodong et al. 2004
515[261, 3059]Su et al. 2002, Xiaodong et al. 2004
516[278, 3875]Luo et al. 2001
517[284, 4844]Exoo 2002
518[284, 5984]
519[338, 7314]Su et al. 1999
520[380, 8854]Luo et al. 2001
521[380, 10625]
522[422, 12649]Luo et al. 2000
523[434, 14949]Luo et al. 2000
524[434, 17549]
525[434, 20474]
526[464, 23750]
66[102, 165]Kalbfleisch 1965, Mackey 1994
67[113, 298]Exoo 1998, Xu and Xie 2002
68[127, 495]Exoo 1998, Xu and Xie 2002
69[169, 780]Exoo 1998, Mackey 1994, Xiaodong et al. 2004
610[179, 1171]Xu and Xie 2002
611[253, 3002]Xu and Xie 2002
612[262, 4367]Xu and Xie 2002
613[317, 6187]Xu and Xie 2002, Xiaodong et al. 2004
614[317, 8567]Xu and Xie 2002
615[401, 11627]Su et al. 2002, Xiaodong et al. 2004
616[434, 15503]Su et al. 2002
617[548, 20348]Su et al. 2002
618[614, 26333]Su et al. 2002
619[710, 33648]Su et al. 2002
620[878, 42503]Su et al. 2002
621[878, 53129]
622[1070, 65779]Su et al. 2002
77[205, 540]Hill and Irving 1982, Giraud 1973
78[216, 1031]Xu and Xie 2002
79[233, 1713]Huang and Zhang 1998, Xiaodong and Zheng 2002
710[232, 2826]Mackey 1994
711[405, 8007]Xu and Xie 2002, Xiaodong and Zheng 2002
712[416, 12375]Xu and Xie 2002
713[511, 18563]Xu and Xie 2002
714[511, 27131]
715[511, 38759]
716[511, 54263]
717[628, 74612]Xu and Xie 2002
718[722, 100946]Xu and Xie 2002
719[908, 134595]Su et al. 2002
720[908, 177099]
721[1214, 230229]Su et al. 2002
88[282, 1870]Burling and Reyner 1972, Mackey 1994
89[317, 3583]Radziszowski 2002, Xiaodong et al. 2004
810[377, 6090]Xu and Xie 2002, Huang and Zhang 1998, Xiaodong et al. 2004
811[377, 19447]
812[377, 31823]
813[817, 50387]Xu and Xie 2002, Xiaodong et al. 2004
814[817, 77519]
815[861, 116279]Xu and Xie 2002, Xiaodong et al. 2004
816[861, 170543]
817[861, 245156]Xu and Xie 2002
818[871, 346103]Xu and Xie 2002
819[1054, 480699]Xu and Xie 2002
820[1094, 657799]Su et al. 2002
821[1328, 888029]Su et al. 2002
99[565, 6588]Shearer 1986, Shi and Zheng 2001
910[580, 12677]Xu and Xie 2002
1010[798, 23556]Shearer 1986, Shi 2002
1111[1597, 184755]Mathon 1987
1212[1637, 705431]Xu and Xie 2002
1313[2557, 2704155]Mathon 1987
1414[2989, 10400599]Mathon 1987
1515[5485, 40116599]Mathon 1987
1616[5605, 155117519]Mathon 1987
1717[8917, 601080389]Luo et al. 2002
1818[11005, 2333606219]Luo et al. 2002
1919[17885, 9075135299]Luo et al. 2002

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


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., G. "Some New Ramsey Colorings." Electronic J. Combinatorics 5, No. 1, R29, 1-5, 1998., 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.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., S. P. "Small Ramsey Numbers." Electronic J. Combinatorics Dynamical Survey DS1, 1-42, Jul. 4, 2004., 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., 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.

Referenced on Wolfram|Alpha

Ramsey Number

Cite this as:

Weisstein, Eric W. "Ramsey Number." From MathWorld--A Wolfram Web Resource.

Subject classifications