|
%I #70 Jan 08 2024 22:40:50
%S 2,3,3,4,6,4,5,9,9,5,6,14,18,14,6,7,18,25,25,18,7,8,23
%N Array of Ramsey numbers R(n,k) (n >= 2, k >= 2) read by antidiagonals.
%C See A212954 for another version of this table. The present entry is the main one for these Ramsey numbers R(n,k).
%C From _Jianglin Luo_, Jan 08 2024: (Start)
%C Fence conjecture: R(m,n) <= (2m-1)*A008284_T(2m-6+n,m) + m + 1 for n >= m >= 3.
%C R(3,n) == 1,3,4 (mod 5) for n >= 1. (End)
%D G. Berman and K. D. Fryer, Introduction to Combinatorics. Academic Press, NY, 1972, p. 175.
%D T. Bohman and P. Keevash. Dynamic concentration of the triangle-free process. Random
%D Structures & Algorithms, 58.2 (2021), 221-293.
%D L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 288.
%D Sam Mattheus and Jacques Verstraete, The asymptotics of r(4,t), arXiv:2306.04007. [Studies R(4,k)]
%D H. J. Ryser, Combinatorial Mathematics, Chapter 4 - A Theorem of Ramsey, Mathematical Association of America, Carus Mathematical Monograph 14, 1963, p. 42.
%D J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 840.
%D G. Fiz Pontiveros, S. Griffiths, and R. Morris. The triangle-free process and the Ramsey
%D number R(3, k). Mem. Amer. Math. Soc., 263.1274 (2020), v+125.
%D H. J. Ryser, Combinatorial Mathematics. Mathematical Association of America, Carus Mathematical Monograph 14, 1963, p. 42.
%H 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 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 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 G. Exoo, <a href="http://isu.indstate.edu/ge/RAMSEY">Ramsey Numbers</a>.
%H R. Getschmann, <a href="http://www.getschmann.org/doc/thesis.html">Enumeration of Small Ramsey Graphs</a>.
%H J. Goedgebeur and S. 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 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 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 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 Richard L. Kramer, <a href="http://www.public.iastate.edu/~ricardo/ramsey">Ricardo's Ramsey Number Page</a>.
%H I. Leader, <a href="http://pass.maths.org.uk/issue16/features/ramsey/">Friends and Strangers</a>.
%H Math Reference Project, <a href="http://www.mathreference.com/gph,ramsey.html">Ramsey Numbers</a>.
%H 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 Online Dictionary of Combinatorics, <a href="http://www.math.uic.edu/~fields/comb_dic/R.html">Ramsey's Theorem</a>.
%H I. 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 I. 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 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 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/RamseyNumber.html">Ramsey Number</a>.
%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Ramsey_theorem">Ramsey's theorem</a>.
%H 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 From _Joerg Arndt_, Jun 01 2012: (Start)
%F The antidiagonals are symmetric.
%F R(r, 1) = R(1, r) = 1,
%F R(r, 2) = R(2, r) = r,
%F R(r, s) <= R(r-1, s) + R(r, s-1),
%F 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 R(r, r) <= 4 * R(r, r-2) + 2. (End)
%e Array R(n,k), n >= 2, k >= 2, begins:
%e 2, 3, 4, 5, 6, 7, 8, 9, 10,
%e 3, 6, 9, 14, 18, 23, 28, 36,
%e 4, 9, 18, 25, ?, ?, ?,
%e 5, 14, 25, ?, ?, ?,
%e 6, 18, ?, ?, ?,
%e 7, 23, ?, ?,
%e 8, 28, ?,
%e 9, 36,
%e 10,
%Y The second (n = 3) row gives A000791.
%Y A120414 gives a conjecture for R(n,n).
%Y See A212954 for another version.
%K nonn,tabl,nice,hard
%O 0,1
%A _N. J. A. Sloane_, Feb 01 2001
%E Next term is in the range 35-41.
%E More terms in example section (antidiagonals 6-10; cf. A000791) from _Omar E. Pol_, Jun 11 2012
%E Edited by _N. J. A. Sloane_, Nov 05 2023
|
