OFFSET
0,1
COMMENTS
See A212954 for another version of this table. The present entry is the main one for these Ramsey numbers R(n,k).
From Jianglin Luo, Jan 08 2024: (Start)
Fence conjecture: R(m,n) <= (2m-1)*A008284_T(2m-6+n,m) + m + 1 for n >= m >= 3.
R(3,n) == 1,3,4 (mod 5) for n >= 1. (End)
REFERENCES
G. Berman and K. D. Fryer, Introduction to Combinatorics. Academic Press, NY, 1972, p. 175.
T. Bohman and P. Keevash. Dynamic concentration of the triangle-free process. Random Structures & Algorithms, 58.2 (2021), 221-293.
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 288.
H. J. Ryser, Combinatorial Mathematics, Chapter 4 - A Theorem of Ramsey, Mathematical Association of America, Carus Mathematical Monograph 14, 1963, p. 42.
J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 840.
G. Fiz Pontiveros, S. Griffiths, and R. Morris. The triangle-free process and the Ramsey number R(3, k). Mem. Amer. Math. Soc., 263.1274 (2020), v+125.
H. J. Ryser, Combinatorial Mathematics. Mathematical Association of America, Carus Mathematical Monograph 14, 1963, p. 42.
LINKS
Vigleik Angeltveit and Brendan D. McKay, R(5,5) <= 48, arXiv:1703.08768 [math.CO], 2017.
Marcelo Campos, Simon Griffiths, Robert Morris, and Julian Sahasrabudhe, An exponential improvement for diagonal Ramsey, arXiv preprint arXiv:2303.09521 [math.CO], 2023.
Erdős problems database contributors, Erdős problem database, see nos. 77-78, 87, 545, 986.
Geoff Exoo, Ramsey Numbers.
R. E. Greenwood and A. M. Gleason, Combinatorial relations and chromatic graphs, Canad. J. Math., 7 (1955), 1-7.
R. Getschmann, Enumeration of Small Ramsey Graphs.
Jan Goedgebeur and Stanisław P. Radziszowski, New Computational Upper Bounds for Ramsey Numbers R(3,k), arXiv:1210.5826 [math.CO], 2012-2013.
R. E. Greenwood and A. M. Gleason, Combinatorial relations and chromatic graphs, Canad. J. Math., 7 (1955), 1-7.
J. G. Kalbfleisch, Construction of special edge-chromatic graphs, Canad. Math. Bull., 8 (1965), 575-584.
Jeong Han Kim, The Ramsey number R(3, t) has order of magnitude t^2/log t, Random Structures & Algorithms Vol. 7, No. 3 (1995), pp. 173-207.
Richard L. Kramer, Ricardo's Ramsey Number Page.
Imre Leader, Friends and Strangers.
Math Reference Project, Ramsey Numbers.
Mathematical Database, Ramsey's Theory.
Sam Mattheus and Jacques Verstraete, The asymptotics of r(4,t), arXiv:2306.04007 [math.CO], 2023-2024. [Studies R(4,k)]
Online Dictionary of Combinatorics, Ramsey's Theorem.
Ivars Peterson, Math Trek, Party Games, Science News Online, Vol. 156, No. 23, Dec 04 1999.
Ivars Peterson, Math Trek, Party Games, Dec 06 1999.
Stanislaw Radziszowski, Small Ramsey Numbers, The Electronic Journal of Combinatorics, Dynamic Surveys, DS1, Mar 3 2017.
Eric Weisstein's World of Mathematics, Ramsey Number.
Wikipedia, Ramsey's theorem.
Jin Xu and C. K. Wong, Self-complementary graphs and Ramsey numbers I, Discrete Math., 223 (2000), 309-326.
FORMULA
From Joerg Arndt, Jun 01 2012: (Start)
The antidiagonals are symmetric.
R(r, 1) = R(1, r) = 1,
R(r, 2) = R(2, r) = r,
R(r, s) <= R(r-1, s) + R(r, s-1),
R(r, s) <= R(r-1, s) + R(r, s-1) - 1 if R(r-1, s) and R(r, s-1) are both even,
R(r, r) <= 4 * R(r, r-2) + 2. (End)
EXAMPLE
Array R(n,k), n >= 2, k >= 2, begins:
2, 3, 4, 5, 6, 7, 8, 9, 10,
3, 6, 9, 14, 18, 23, 28, 36,
4, 9, 18, 25, ?, ?, ?,
5, 14, 25, ?, ?, ?,
6, 18, ?, ?, ?,
7, 23, ?, ?,
8, 28, ?,
9, 36,
10,
CROSSREFS
KEYWORD
AUTHOR
N. J. A. Sloane, Feb 01 2001
EXTENSIONS
Next term is in the range 35-41.
More terms in example section (antidiagonals 6-10; cf. A000791) from Omar E. Pol, Jun 11 2012
Edited by N. J. A. Sloane, Nov 05 2023
STATUS
approved