A059442 Array of Ramsey numbers R(n,k) (n >= 2, k >= 2) read by antidiagonals.

2, 3, 3, 4, 6, 4, 5, 9, 9, 5, 6, 14, 18, 14, 6, 7, 18, 25, 25, 18, 7, 8, 23

Offset: 0

Author

N. J. A. Sloane, Feb 01 2001

Keywords

• nonn
• tabl
• nice
• hard
• changed

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)

Examples

			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,
		

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.
• Thomas Bloom, Problem 77, Problem 78, Problem 87, Problem 545, and Problem 986, Erdős Problems.
• Marcelo Campos, Simon Griffiths, Robert Morris, and Julian Sahasrabudhe, An exponential improvement for diagonal Ramsey, arXiv preprint arXiv:2303.09521 [math.CO], 2023.
• 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.
• Terence Tao, Erdős problem database, see nos. 77-78, 87, 545, 986.
• 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.

Crossrefs

The second (n = 3) row gives A000791.

A000984 gives the upper bound for R(n,n) from Ramsey's original proof.

A120414 gives a conjecture for R(n,n).

See A212954 for another version.

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)

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