A120414 -id:A120414 - cp's OEIS frontend

A000791 Ramsey numbers R(3,n).

1, 3, 6, 9, 14, 18, 23, 28, 36

Offset: 1

a(10) is either 40, 41, or 42 (Goedgebeur, Radziszowski). - Ray G. Opao, Oct 07 2015
Kim proves that a(n) ~ n^2/log n; the lower and upper constants, respectively, can be chosen arbitrarily close to 1/162 and 1. (Kim notes that he made no attempt to make 1/162 tight.) - Charles R Greathouse IV, Jun 23 2023
As of 31 December 2023, Vigleik Angeltveit claims to have ruled out a(10)=42 with a massive computer search. See links. That would mean that 40 <= a(10) <= 41. - Allan C. Wechsler, Apr 05 2024

G. Berman and K. D. Fryer, Introduction to Combinatorics. Academic Press, NY, 1972, p. 175.
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 288.
J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 840.
Brendan McKay, personal communication.
H. J. Ryser, Combinatorial Mathematics. Mathematical Association of America, Carus Mathematical Monograph 14, 1963, p. 42.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vigleik Angeltveit, R(3,10) <= 41, arXiv:2401.00392 [math.CO], 2023.
Thomas Bloom, Problem 165, Problem 544, Problem 553, and Problem 986, Erdős Problems.
Geoff Exoo, Ramsey Numbers
Robert Getschmann, Enumeration of Small Ramsey Graphs (Wayback Machine archive)
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 (Wayback Machine archive)
Imre Leader, Friends and Strangers
Math Reference Project, Ramsey Numbers
Mathematical Database, Ramsey's Theory
Brendan McKay, Email to N. J. A. Sloane, Jul. 1991
Online Dictionary of Combinatorics, Ramsey's Theorem (Wayback Machine archive)
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.
Stanisław Radziszowski, Small Ramsey Numbers, The Electronic Journal of Combinatorics, Dynamic Surveys, #DS1: Jan 12, 2014.
Terence Tao, Erdős problem database, see no. 165, 544, 553, 986.
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.

A row of the table in A059442. Cf. A120414.

a(1) = 1 added by N. J. A. Sloane, Nov 05 2023

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

Original entry on oeis.org

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

N. J. A. Sloane, Feb 01 2001

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)

			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,

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.

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.

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.

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)

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

cp's OEIS Frontend

A000791 Ramsey numbers R(3,n).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions