Small Ramsey Numbers
Stanisław P. Radziszowski
Department of Computer Science
Rochester Institute of Technology
Rochester, NY 14623, spr@cs.rit.edu
http://www.cs.rit.edu/~spr
Submitted: June 11, 1994; Accepted: July 3, 1994
Revision #12: August 4, 2009
ABSTRACT: We present data which, to the best of our knowledge,
includes all known nontrivial values and bounds for specific graph,
hypergraph and multicolor Ramsey numbers, where the avoided
graphs are complete or complete without one edge. Many results per-
taining to other more studied cases are also presented. We give refer-
ences to all cited bounds and values, as well as to previous similar
compilations. We do not attempt complete coverage of asymptotic
behavior of Ramsey numbers, but concentrate on their specific values.
Mathematical Reviews Subject Number 05C55.
Revisions
1993, February preliminary version, RIT-TR-93-009 [Ra2]
1994, July 3 accepted to the ElJC, posted on the web
1994, November 7 ElJC revision #1
1995, August 28 ElJC revision #2
1996, March 25 ElJC revision #3
1997, July 11 ElJC revision #4
1998, July 9 ElJC revision #5
1999, July 5 ElJC revision #6
2000, July 25 ElJC revision #7
2001, July 12 ElJC revision #8
2002, July 15 ElJC revision #9
2004, July 4 ElJC revision #10
2006, August 1 ElJC revision #11
2009, August 4 ElJC revision #12
- 1 -
THE ELECTRONIC JOURNAL OF COMBINATORICS (2009), DS1.12
Table of Contents
1. Scope and Notation 3
2. Classical Two Color Ramsey Numbers 4
2.1 Bounds on R (k , l ) for k ≤ 10, l ≤ 15 4
2.2 Bounds on R (k , l ) for l ≥ 15 6
2.3 Other results on R (k , l ) 7
3. Two Colors - Most Studied Cases 9
3.1 Dropping one edge from complete graph 9
3.2 Complete bipartite graphs 11
3.3 Cycles, cycles versus complete graphs 14
3.4 Cycles versus wheels 16
3.5 Cycles versus books 17
4. General Graph Numbers in Two Colors 18
4.1 Paths 18
4.2 Wheels 18
4.3 Books 19
4.4 Trees and forests 19
4.5 Stars, stars versus other graphs 20
4.6 Fans, fans versus other graphs 21
4.7 Paths versus other graphs 21
4.8 Triangle versus other graphs 21
4.9 Cycles versus other graphs 22
4.10 Wheels versus other graphs 23
4.11 Books versus other graphs 23
4.12 Trees and forests versus other graphs 24
4.13 Cases for n (G ), n (H ) ≤ 5 24
4.14 Mixed cases 25
4.15 Multiple copies of graphs, disconnected graphs 26
4.16 General results for sparse graphs 26
4.17 Other general two color results 27
5. Multicolor Ramsey Numbers 29
5.1 Bounds for classical numbers 29
5.2 General results for complete graphs 31
5.3 Cycles 32
5.4 Paths, paths versus other graphs 35
5.5 Special cases 36
5.6 Other general results 36
6. Hypergraph Numbers 38
7. Cumulative Data and Surveys 40
7.1 Cumulative data for two colors 40
7.2 Cumulative data for three colors 41
7.3 Surveys 41
8. Concluding Remarks 42
References 44-72
- 2 -
THE ELECTRONIC JOURNAL OF COMBINATORICS (2009), DS1.12
1. Scope and Notation
There is vast literature on Ramsey type problems starting in 1930 with the original paper
of Ramsey [Ram]. Graham, Rothschild and Spencer in their book [GRS] present an exciting
development of Ramsey Theory. The subject has grown amazingly, in particular with regard
to asymptotic bounds for various types of Ramsey numbers (see the survey papers [GrRo¨,
Nes˘, ChGra2]), but the progress on evaluating the basic numbers themselves has been unsatis-
factory for a long time. In the last three decades, however, considerable progress has been
obtained in this area, mostly by employing computer algorithms. The few known exact values
and several bounds for different numbers are scattered among many technical papers. This
compilation is a fast source of references for the best results known for specific numbers. It
is not supposed to serve as a source of definitions or theorems, but these can be easily
accessed via the references gathered here.
Ramsey Theory studies conditions when a combinatorial object contains necessarily some
smaller given objects. The role of Ramsey numbers is to quantify some of the general existen-
tial theorems in Ramsey Theory.
Let G 1, G 2, . . . , Gm be graphs or s -uniform hypergraphs (s is the number of vertices
in each edge). R ( G 1, G 2, . . . , Gm ; s ) denotes the m -color Ramsey number for s -uniform
graphs/hypergraphs, avoiding Gi in color i for 1 ≤ i ≤ m . It is defined as the least integer n
such that, in any coloring with m colors of the s -subsets of a set of n elements, for some i
the s -subsets of color i contain a sub-(hyper)graph isomorphic to Gi (not necessarily
induced). The value of R ( G 1, G 2, . . . , Gm ; s ) is fixed under permutations of the first m
arguments. If s = 2 (standard graphs) then s can be omitted. If Gi is a complete graph Kk ,
then we can write k instead of Gi , and if Gi = G for all i we can use the abbreviation
Rm (G ; s ) or Rm (G ). For s = 2, Kk − e denotes a Kk without one edge, and for s = 3, Kk − t
denotes a Kk without one triangle (hyperedge).
The graph nG is formed by n disjoint copies of G , and the join G + H of vertex disjoint
graphs G and H is obtained by adding all the edges between vertices of G and H . Pi is a
path on i vertices, Ci is a cycle of length i , and Wi is a wheel with i −1 spokes, i.e. a graph
formed by some vertex x , connected to all vertices of some cycle Ci −1 (thus Wi = K 1 + Ci −1).
Kn ,m is a complete n by m bipartite graph, in particular K 1,n is a star graph. The book
graph Bi = K 2 + Ki = K 1 + K 1,i has i + 2 vertices, and can be seen as i triangular pages attached
to a single edge. The fan graph Fn is defined by Fn = K 1 + nK 2. For a graph G , n (G ) and
e (G ) denote the number of vertices and edges, respectively, and δ(G ) and ∆(G ) minimum
and maximum degree in G . Finally, let χ(G ) be the chromatic number of G . In general we
follow the notation used by West [West].
Section 2 contains the data for the classical two color Ramsey numbers R (k , l ) for com-
plete graphs, and section 3 for the most studied two color cases. Section 4 lists other often
studied two color cases for general graphs. The multicolor and hypergraph cases are gathered
in sections 5 and 6, respectively. Finally, section 7 gives pointers to cumulative data and to
the other surveys.
- 3 -
THE ELECTRONIC JOURNAL OF COMBINATORICS (2009), DS1.12
2. Classical Two Color Ramsey Numbers
2.1. Upper and lower bounds on R (k , l )
l 3 4 5 6 7 8 9 10 11 12 13 14 15
k
40 46 52 59 66 73
3 6 9 14 18 23 28 36
43 51 59 69 78 88
35 49 56 73 92 97 128 133 141 153
4 18 25
41 61 84 115 149 191 238 291 349 417
43 58 80 101 125 143 159 185 209 235 265
5
49 87 143 216 316 442 633 848 1139 1461 1878
102 113 130 169 179 253 262 317 401
6
165 298 495 780 1171 1804 2566 3705 5033 6911
205 216 237 289 405 416 511
7
540 1031 1713 2826 4553 6954 10581 15263 22116
282 317 817 861
8
1870 3583 6090 10630 16944 27490 41525 63620
565 580
9
6588 12677 22325 39025 64871 89203
798 1265
10
23556 81200
Table I. Known nontrivial values and bounds for two color
Ramsey numbers R (k , l ) = R (k , l ; 2).
l 4 5 6 7 8 9 10 11 12 13 14 15
k
Ka2 GR Ka2 Ex5 Ka2 Ex12 Piw1 Ex8 WW
3 GG GG Ke´ry
GY MZ GR RK2 RK2 Les RK2 RK2 Les
Ka1 Ex9 Ex3 Ex15 Ex17 HaKr 2.3.e SLL 2.3.e XXR XXR
4 GG
MR4 MR5 Mac Mac Mac Mac Spe3 Spe3 Spe3 Spe3 Spe3
Ex4 Ex9 CET HaKr Ex17 Ex17 Ex17 Ex17 Ex17 Ex17 Ex17
5
MR5 HZ1 Spe3 Spe3 Mac Mac HW+ HW+ HW+ HW+ HW+
Ka1 Ex17 XSR2 XXER Ex17 XXR 2.3.e XXER 2.3.h
6
Mac Mac Mac Mac Mac HW+ HW+ HW+ HW+ HW+
She1 2.3.e XSR2 2.3.h XXER 2.3.e XXR
7
Mac Mac HZ1 Mac HW+ HW+ HW+ HW+ HW+
BR XXER XXER 2.3.h
8
Mac Ea1 HZ1 HW+ HW+ HW+ HW+ HW+
She1 2.3.e
9
ShZ1 Ea1 HW+ HW+ HW+ HW+
She1 2.3.h
10
Shi2 Yang
References for Table I. HW+ abbreviates HWSYZH.
- 4 -
THE ELECTRONIC JOURNAL OF COMBINATORICS (2009), DS1.12
We split the data into the table of values and a table with corresponding references. In
Table I, known exact values appear as centered entries, lower bounds as top entries, and upper
bounds as bottom entries. For some of the exact values two references are given when the
lower and upper bound credits are different.
The task of proving R (3, 3) ≤ 6 was the second problem in Part I of the William Lowell
Putnam Mathematical Competition held in March 1953 [Bush]. Greenwood and Gleason [GG]
in 1955 established the initial values R (3,4)=9, R (3,5)=14 and R (4,4)=18. Ke´ry [Ke´ry] in
1964 found R (3,6)=18, but only recently an elementary and self-contained proof of this result
appeared in English [Car].
All the critical graphs for the numbers R (k , l ) (graphs on R (k , l ) − 1 vertices without Kk
and without Kl in the complement) are known for k = 3 and l = 3, 4, 5 [Ke´ry], 6 [Ka2], 7
[RK3, MZ], and there are 1, 3, 1, 7 and 191 of them, respectively. All (3, k )-graphs, for
k ≤ 6, were enumerated in [RK3], and all (4,4)-graphs in [MR2]. There exists a unique criti-
cal graph for R (4,4) [Ka2]. There are 430215 such graphs known for R (3,8) [McK], 1 for
R (3,9) [Ka2] and 350904 for R (4, 5) [MR4], but there might be more of them. In [MR5] evi-
dence is given for the conjecture that R (5, 5) = 43 and that there exist 656 critical graphs on
42 vertices. The graphs constructed by Exoo in [Ex9, Ex12, Ex13, Ex14, Ex15, Ex16, Ex17],
and some others, are available electronically from http://ginger.indstate.edu/ge/RAMSEY.
The construction by Mathon [Mat] and Shearer [She1] (see also sections 2.3.i, 5.2.h and
5.2.i), using data obtained by Shearer [She3] for primes up to 7000, gives the following lower
bounds for higher diagonal numbers: R (11,11) ≥ 1597, R (13,13) ≥ 2557, R (14,14) ≥ 2989,
R (15,15) ≥ 5485, and R (16,16) ≥ 5605. Similarly, R (17,17) ≥ 8917, R (18,18) ≥ 11005 and
R (19,19) ≥ 17885 were obtained in [LSL], though the first two of these bounds follow also
from the data in [She3]. The same approach does not improve on an easy bound
R (12,12) ≥ 1637 [XXR], which can be obtained by applying twice 2.3.e. Only some of the
higher bounds implied by 2.3.* are shown, and more similar bounds could be easily derived.
In general, we show bounds beyond the contiguous small values if they improve on results
previously reported in this survey or published elsewhere. Some easy upper bounds implied
by 2.3.a are marked as [Ea1].
Cyclic (or circular ) graphs are often used for Ramsey graph constructions. Several
cyclic graphs establishing lower bounds were given in the Ph.D. dissertation by J.G.
Kalbfleisch in 1966, and many others were published in the next few decades (see [RK1]).
Only recently Harborth and Krause [HaKr] presented all best lower bounds up to 102 from
cyclic graphs avoiding complete graphs. In particular, no lower bound in Table I can be
improved with a cyclic graph on less than 102 vertices. See also item 2.3.k and section 4.16
[HaKr].
The claim that R (5, 5) = 50 posted on the web [Stone] is in error, and despite being
shown to be incorrect more than once, this value is still being cited by some authors. The
bound R (3, 13) ≥ 60 [XieZ] cited in the 1995 version of this survey was shown to be
incorrect in [Piw1]. Another incorrect construction for R (3, 10) ≥ 41 was described in
[DuHu].
- 5 -
THE ELECTRONIC JOURNAL OF COMBINATORICS (2009), DS1.12
There are really only two general upper bound inequalities useful for small parameters,
namely 2.3.a and 2.3.b. Stronger upper bounds for specific parameters were difficult to
obtain, and they often involved massive computations, like those for the cases of (3,8) [MZ],
(4,5) [MR4], (4,6) and (5,5) [MR5]. The bound R (6, 6) ≤ 166, only 1 more than the best
known [Mac], is an easy consequence of a theorem in [Walk] (2.3.b) and R (4, 6) ≤ 41. T.
Spencer [Spe3], Mackey [Mac], and Huang and Zhang [HZ1], using the bounds for minimum
and maximum number of edges in (4,5) Ramsey graphs listed in [MR3, MR5], were able to
establish new upper bounds for several higher Ramsey numbers, improving on all of the pre-
vious longstanding results by Giraud [Gi3, Gi5, Gi6].
We have recomputed the upper bounds in Table I marked [HZ1] using the method from
the paper [HZ1], because the bounds there relied on an overly optimistic personal communica-
tion from T. Spencer. Further refinements of this method are studied in [HZ2, ShZ1, Shi2].
The paper [Shi2] subsumes the main results of the manuscripts [ShZ1, Shi2]. The upper
bound marked in Table I [Yang] was obtained by Yang using the method of [HWSYZH]
(abbreviated in the table as HW+).
2.2. Bounds on R (k , l ), higher parameters
l 15 16 17 18 19 20 21 22 23
k
73 79 92 99 106 111 122 131 137
3
WW WW WWY1 Ex17 WWY1 Ex17 WWY1 WSLX2 WSLX2
153 163 182 187 213 234 242 282
4
XXR Ex17 LSS1 2.3.e 2.3.g Ex17 SLZL SL
265 289 388 395 407 421 441 485 521
5
Ex17 2.3.h XSR2 2.3.e XSR2 2.3.h 2.3.h 2.3.h 2.3.h
401 434 548 614 710 878 1070
6
2.3.h SLLL SLLL SLLL SLLL SLLL SLLL
711 725 908 1214
7
2.3.g 2.3.h SLLL SLLL
861 937 1045 1236 1617
8
2.3.h ShaXP 2.3.g 2.3.g 2.3.h
l 24 25 26 27 28 29 30 31
k
143 154 159 167 173 184 190 199
3
WSLX1 WSLX2 WSLX1 WSLX1 WSLX2 WSLX2 WSLX2 WSLX2
l 32 33 34 35 36 37 38 39
k
214 218 226 231 239 244 256
3
WSLX2 WuCXS WuCXS WuCXS WuCXS WuCXS WuCXS
Table II. Known nontrivial lower bounds for higher two color
Ramsey numbers R (k , l ), with references.
- 6 -
THE ELECTRONIC JOURNAL OF COMBINATORICS (2009), DS1.12
The upper bounds of 88, 99, 110, 121 133, 145, 158 on R (3, k ) for 15 ≤ k ≤ 21, respec-
tively, were obtained in [Les]. The lower bounds marked [XXR], [XXER], 2.3.e and 2.3.h
need not be cyclic. Several of the Cayley colorings from [Ex17] are also non-cyclic. All other
lower bounds listed in Table II were obtained by construction of cyclic graphs. The graphs
establishing lower bounds marked 2.3.g can be constructed by using appropriately chosen
graphs G and H with a common m -vertex induced subgraph, similarly as it was done in
several cases in [XXR].
Yu [Yu2] constructed a special class of triangle-free cyclic graphs establishing several
lower bounds for R (3, k ), for k ≥ 61. Only one of these bounds, R (3, 61) ≥ 479, cannot be
easily improved by the inequality R (3, 4k + 1) ≥ 6R (3, k + 1) − 5 from [CCD] (2.3.c) and data
from Tables I and II. Finally, for higher parameters we mention two more cases which
improve on bounds listed in earlier revisions: R (9, 17) ≥ 1411 is given in [XXR] and
R (10, 15) ≥ 1265 can be obtained by using 2.3.h.
In general, one can except that the lower bounds in Table II are weaker than those in
Table I, in the sense that with some work many of them should not be hard to improve, in
contrast to the bounds in Table I, especially smaller ones.
2.3. Other results on R (k , l )
(a) R (k , l ) ≤ R (k −1, l ) + R (k , l −1), with strict inequality when both terms on the right hand
side are even [GG]. There are obvious generalizations of this inequality for avoiding
graphs other than complete.
(b) R (k , k ) ≤ 4R (k , k − 2) + 2 [Walk].
(c) Explicit construction for R (3, 4k + 1) ≥ 6R (3, k + 1) − 5, for all k ≥ 1 [CCD].
(d) Constructive results on triangle-free graphs in relation to the case of R (3, k ) [BBH1,
BBH2, Fra1, Fra2, FrLo, Gri, KM1, Loc, RK3, RK4, Stat, Yu1].
(e) Bounds for the difference between consecutive Ramsey numbers, in particular the bound
R (k , l ) ≥ R (k , l − 1) + 2k − 3 for k , l ≥ 3 [BEFS].
(f) By taking a disjoint union of two critical graphs one can easily see that R (k , p ) ≥ s and
R (k , q ) ≥ t imply R (k , p + q −1) ≥ s + t −1. Xu and Xie [XX1] improved this construc-
tion to yield better general lower bounds, in particular R (k , p + q −1) ≥ s + t + k − 3.
(g) For 2 ≤ p ≤ q and 3 ≤ k , if (k , p )-graph G and (k , q )-graph H have a common induced
subgraph on m vertices without Kk −1, then R (k , p + q − 1) > n (G ) + n (H ) + m . In partic-
ular, this implies the bounds R (k , p + q − 1) ≥ R (k , p ) + R (k , q ) + k − 3 and
R (k , p + q − 1) ≥ R (k , p ) + R (k , q ) + p − 2 [XX1, XXR].
(h) R (2k − 1, l ) ≥ 4R (k , l − 1) −3 for l ≥ 5 and k ≥ 2, and in particular for k = 3 we obtain
R (5, l ) ≥ 4R (3, l − 1) −3 [XXER].
(i) If the quadratic residues Paley graph Qp of prime order p = 4t + 1 contains no Kk , then
R (k , k ) ≥ p + 1 and R (k + 1, k + 1) ≥ 2p + 3 [She1, Mat]. Data for larger p was
obtained in [LSL]. See also 3.1.c, and items 5.2.h and 5.2.i for similar multicolor results.
- 7 -
THE ELECTRONIC JOURNAL OF COMBINATORICS (2009), DS1.12
(j) Study of Ramsey numbers for large disjoint unions of graphs [Bu1, Bu9], in particular
R (nKk , nKl ) = n (k + l − 1) + R (Kk −1, Kl −1) − 2, for n large enough [Bu8].
(k) R (k , l ) ≥ L (k , l ) + 1, where L (k , l ) is the maximal order of any cyclic (k , l )-graph.
A compilation of many best cyclic bounds was presented in [HaKr].
(l) The graphs critical for R (k , l ) are k − 1 vertex connected and 2k − 4 edge connected, for
k , l ≥ 3 [BePi].
(m) Two color lower bounds can be obtained by using items 5.2.k, 5.2.l and 5.2.m with
r = 2. Some generalizations of these were obtained in [ZLLS].
In the last six items of this section we only briefly mention some pointers to the litera-
ture dealing with asymptotics of Ramsey numbers. This survey was designed mostly for small,
finite, and combinatorial results, but still we wish to give the reader some useful and represen-
tative references to more traditional papers looking first of all at the infinite.
(n) In a 1995 breakthrough Kim proved that R (3, k ) = Θ(k 2/ log k ) [Kim].
(o) Explicit triangle-free graphs with independence k on Ω(k 3/ 2 ) vertices [Alon2, CPR].
(p) Other general and asymptotic results on triangle-free graphs in relation to the case of
R (3, k ) [AKS, Alon2, CCD, CPR, Gri, FrLo, Loc, She2].
(q) In 1947, Erdo¨s gave an amazingly simple probabilistic proof that R (k , k ) ≥ c .k 2 k / 2
[Erd1]. Spencer [Spe1] improved the constant in the last result. More probabilistic
asymptotic lower bounds for other Ramsey numbers were obtained in [Spe1, Spe2,
AlPu].
(r) Other asymptotic bounds for R (k , k ) can be found, for example, in [Chu3, McS] (lower
bound) and [Tho, Con1] (upper bound), and for many other bounds in the general case
of R (k , l ) consult [Spe2, GRS, GrRo¨, Chu4, ChGra2, LiRZ1, AlPu, Kriv].
(s) Explicit construction of a graph with clique and independence k on 2c log2k / log log k ver-
tices by Frankl and Wilson [FraWi]. Further constructions by Chung [Chu3] and Grol-
musz [Grol1, Grol2]. Explicit constructions like these are usually weaker than known
probabilistic results.
- 8 -
THE ELECTRONIC JOURNAL OF COMBINATORICS (2009), DS1.12
3. Two Colors - Most Studied Cases
3.1. Dropping one edge from complete graph
This section contains known values and nontrivial bounds for the two color case when the
avoided graphs are complete or have the form Kk − e , but not both are complete.
H K 3 − e K 4 − e K 5 − e K 6 − e K 7 − e K 8 − e K 9 − e K 10 − e K 11 − e
G
K 3 − e 3 5 7 9 11 13 15 17 19
37 42K 3 5 7 11 17 21 25 31 38 47
29 34 41K 4 − e 5 10 13 17 28 38
27 37K 4 7 11 19 36 52
31 40K 5 − e 7 13 22 39 66
30 43K 5 9 16 34 67 112
31 45 59K 6 − e 9 17 39 70 135
37K 6 11 21 55 116 205
40 59K 7 − e 11 28 66 135 251
28 51K 7 13 34 88 202
Table III. Two types of Ramsey numbers R (G , H ),
includes all known nontrivial values.
(a) The exact values in Table III involving K 3 − e are obvious, since one can easily see that
R (K 3 − e , Kk ) = R (K 3 − e , Kk +1 − e ) = 2k − 1, for all k ≥ 2.
(b) The bound R (K 4 − e , K 8) ≤ 45 is given in [LinMac], and R (K 3, K 12 − e ) ≥ 46 in [MPR].
Wang, Wang and Yan [WWY2] constructed cyclic graphs showing R (K 3, K 13 − e ) ≥ 54,
R (K 3, K 14 − e ) ≥ 59 and R (K 3, K 15 − e ) ≥ 69. It is known that R (K 4, K 12 − e ) ≥ 128
[Shao] using one color of the (4,4,4;127)-coloring defined in [HiIr].
(c) If the quadratic residues Paley graph Qp of prime order p = 4t + 1 contains no Kk − e ,
then R (Kk +1 − e , Kk +1 − e ) ≥ 2p + 1. In particular, R (K 14 − e , K 14 − e ) ≥ 2987 [LiShen].
See also item 2.3.i.
- 9 -
THE ELECTRONIC J