cp's OEIS Frontend

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

%I A059442 #84 Sep 04 2025 10:54:06
%S A059442 2,3,3,4,6,4,5,9,9,5,6,14,18,14,6,7,18,25,25,18,7,8,23
%N A059442 Array of Ramsey numbers R(n,k) (n >= 2, k >= 2) read by antidiagonals.
%C A059442 See A212954 for another version of this table. The present entry is the main one for these Ramsey numbers R(n,k).
%C A059442 From _Jianglin Luo_, Jan 08 2024: (Start)
%C A059442 Fence conjecture: R(m,n) <= (2m-1)*A008284_T(2m-6+n,m) + m + 1  for n >= m >= 3.
%C A059442 R(3,n) == 1,3,4 (mod 5) for n >= 1. (End)
%D A059442 G. Berman and K. D. Fryer, Introduction to Combinatorics. Academic Press, NY, 1972, p. 175.
%D A059442 T. Bohman and P. Keevash. Dynamic concentration of the triangle-free process. Random Structures & Algorithms, 58.2 (2021), 221-293.
%D A059442 L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 288.
%D A059442 H. J. Ryser, Combinatorial Mathematics, Chapter 4 - A Theorem of Ramsey, Mathematical Association of America, Carus Mathematical Monograph 14, 1963, p. 42.
%D A059442 J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 840.
%D A059442 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.
%D A059442 H. J. Ryser, Combinatorial Mathematics. Mathematical Association of America, Carus Mathematical Monograph 14, 1963, p. 42.
%H A059442 Vigleik Angeltveit and Brendan D. McKay, <a href="https://arxiv.org/abs/1703.08768">R(5,5) <= 48</a>, arXiv:1703.08768 [math.CO], 2017.
%H A059442 Thomas Bloom, <a href="https://www.erdosproblems.com/77">Problem 77</a>, <a href="https://www.erdosproblems.com/78">Problem 78</a>, <a href="https://www.erdosproblems.com/87">Problem 87</a>, <a href="https://www.erdosproblems.com/545">Problem 545</a>, and <a href="https://www.erdosproblems.com/986">Problem 986</a>, Erdős Problems.
%H A059442 Marcelo Campos, Simon Griffiths, Robert Morris, and Julian Sahasrabudhe, <a href="https://arxiv.org/abs/2303.09521">An exponential improvement for diagonal Ramsey</a>, arXiv preprint arXiv:2303.09521 [math.CO], 2023.
%H A059442 Geoff Exoo, <a href="http://isu.indstate.edu/ge/RAMSEY">Ramsey Numbers</a>.
%H A059442 R. E. Greenwood and A. M. Gleason, <a href="http://dx.doi.org/10.4153/CJM-1955-001-4">Combinatorial relations and chromatic graphs</a>, Canad. J. Math., 7 (1955), 1-7.
%H A059442 R. Getschmann, <a href="http://www.getschmann.org/doc/thesis.html">Enumeration of Small Ramsey Graphs</a>.
%H A059442 Jan Goedgebeur and Stanisław P. Radziszowski, <a href="http://arxiv.org/abs/1210.5826">New Computational Upper Bounds for Ramsey Numbers R(3,k)</a>, arXiv:1210.5826 [math.CO], 2012-2013.
%H A059442 R. E. Greenwood and A. M. Gleason, <a href="http://dx.doi.org/10.4153/CJM-1955-001-4">Combinatorial relations and chromatic graphs</a>, Canad. J. Math., 7 (1955), 1-7.
%H A059442 J. G. Kalbfleisch, <a href="http://dx.doi.org/10.4153/CMB-1965-041-7">Construction of special edge-chromatic graphs</a>, Canad. Math. Bull., 8 (1965), 575-584.
%H A059442 Jeong Han Kim, <a href="https://people.tamu.edu/~huafei-yan//Teaching/Math689/ramsey5.pdf">The Ramsey number R(3, t) has order of magnitude t^2/log t</a>, Random Structures & Algorithms Vol. 7, No. 3 (1995), pp. 173-207.
%H A059442 Richard L. Kramer, <a href="http://www.public.iastate.edu/~ricardo/ramsey">Ricardo's Ramsey Number Page</a>.
%H A059442 Imre Leader, <a href="http://pass.maths.org.uk/issue16/features/ramsey/">Friends and Strangers</a>.
%H A059442 Math Reference Project, <a href="http://www.mathreference.com/gph,ramsey.html">Ramsey Numbers</a>.
%H A059442 Mathematical Database, <a href="https://web.archive.org/web/20051103112334 /http://mathdb.org/notes_download/elementary/combinatorics/de_D7/de_D7.pdf">Ramsey's Theory</a>.
%H A059442 Sam Mattheus and Jacques Verstraete, <a href="https://arxiv.org/abs/2306.04007">The asymptotics of r(4,t)</a>, arXiv:2306.04007 [math.CO], 2023-2024. [Studies R(4,k)]
%H A059442 Online Dictionary of Combinatorics, <a href="http://www.math.uic.edu/~fields/comb_dic/R.html">Ramsey's Theorem</a>.
%H A059442 Ivars Peterson, Math Trek, <a href="http://web.archive.org/web/20000229093140/http://www.sciencenews.org/sn_arc99/12_4_99/mathland.htm">Party Games</a>, Science News Online, Vol. 156, No. 23, Dec 04 1999.
%H A059442 Ivars Peterson, Math Trek, <a href="http://web.archive.org/web/20010414061349/http://www.maa.org/mathland/mathtrek_12_6_99.html">Party Games</a>, Dec 06 1999.
%H A059442 Terence Tao, <a href="https://github.com/teorth/erdosproblems/blob/main/README.md#table">Erdős problem database</a>, see nos. 77-78, 87, 545, 986.
%H A059442 Stanislaw Radziszowski, <a href="https://doi.org/10.37236/21">Small Ramsey Numbers</a>, The Electronic Journal of Combinatorics, Dynamic Surveys, DS1, Mar 3 2017.
%H A059442 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/RamseyNumber.html">Ramsey Number</a>.
%H A059442 Wikipedia, <a href="http://en.wikipedia.org/wiki/Ramsey_theorem">Ramsey's theorem</a>.
%H A059442 Jin Xu and C. K. Wong, <a href="http://dx.doi.org/10.1016/S0012-365X(00)00020-0">Self-complementary graphs and Ramsey numbers I</a>, Discrete Math., 223 (2000), 309-326.
%F A059442 From _Joerg Arndt_, Jun 01 2012: (Start)
%F A059442 The antidiagonals are symmetric.
%F A059442 R(r, 1) = R(1, r) = 1,
%F A059442 R(r, 2) = R(2, r) = r,
%F A059442 R(r, s) <= R(r-1, s) + R(r, s-1),
%F A059442 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,
%F A059442 R(r, r) <= 4 * R(r, r-2) + 2. (End)
%e A059442 Array R(n,k), n >= 2, k >= 2, begins:
%e A059442    2,  3,  4,  5,  6,  7,  8,  9, 10,
%e A059442    3,  6,  9, 14, 18, 23, 28, 36,
%e A059442    4,  9, 18, 25,  ?,  ?,  ?,
%e A059442    5, 14, 25,  ?,  ?,  ?,
%e A059442    6, 18,  ?,  ?,  ?,
%e A059442    7, 23,  ?,  ?,
%e A059442    8, 28,  ?,
%e A059442    9, 36,
%e A059442   10,
%Y A059442 The second (n = 3) row gives A000791.
%Y A059442 A000984 gives the upper bound for R(n,n) from Ramsey's original proof.
%Y A059442 A120414 gives a conjecture for R(n,n).
%Y A059442 See A212954 for another version.
%K A059442 nonn,tabl,nice,hard,changed
%O A059442 0,1
%A A059442 _N. J. A. Sloane_, Feb 01 2001
%E A059442 Next term is in the range 35-41.
%E A059442 More terms in example section (antidiagonals 6-10; cf. A000791) from _Omar E. Pol_, Jun 11 2012
%E A059442 Edited by _N. J. A. Sloane_, Nov 05 2023