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

Sam Mattheus and Jacques Verstraete, The asymptotics of r(4,t), arXiv:2306.04007. [Studies R(4,k)]

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

Table of n, a(n) for n=0..22.

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.

R. E. Greenwood and A. M. Gleason, Combinatorial relations and chromatic graphs, Canad. J. Math., 7 (1955), 1-7.

G. Exoo, Ramsey Numbers.

R. Getschmann, Enumeration of Small Ramsey Graphs.

J. Goedgebeur and S. 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.

I. Leader, Friends and Strangers.

Math Reference Project, Ramsey Numbers.

Mathematical Database, Ramsey's Theory.

Online Dictionary of Combinatorics, Ramsey's Theorem.

I. Peterson, Math Trek, Party Games, Science News Online, Vol. 156, No. 23, Dec 04 1999.

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

The second (n = 3) row gives A000791.

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

See A212954 for another version.

Sequence in context: A031501 A279417 A203996 * A225273 A014410 A180986

Adjacent sequences: A059439 A059440 A059441 * A059443 A059444 A059445

Keyword

nonn,tabl,nice,hard,changed

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