A059442 -id:A059442 - 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

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

Original entry on oeis.org

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

Offset: 1

Joerg Arndt, Jun 01 2012

Essentially the same as A059442, which is the main entry for these numbers.

			The initial antidiagonals are:
1,
1,  1,
1,  2,  1,
1,  3,  3,  1,
1,  4,  6,  4,  1,
1,  5,  9,  9,  5,  1,
1,  6, 14, 18, 14,  6,  1,
1,  7, 18, 25, 25, 18,  7,  1,
1,  8, 23,  ?,  ?,  ?, 23,  8,  1,
1,  9, 28,  ?,  ?,  ?,  ?, 28,  9,  1,
1, 10, 36,  ?,  ?,  ?,  ?,  ?, 36, 10,  1,
...
...

See A059442.

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

Cf. A000791, A213368 (row sums).

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

Edited by N. J. A. Sloane, Nov 05 2023

A120414 a(0)=0, a(1)=1; thereafter a(n) = ceiling((3/2)^(n-3)n(n-1)).

Original entry on oeis.org

0, 1, 2, 6, 18, 45, 102, 213, 426, 821, 1538, 2820, 5075, 8996, 15743, 27247, 46709, 79405, 133996, 224640, 374400

Offset: 0

Jeff Boscole (jazzerciser(AT)hotmail.com), Jul 06 2006

Original definition was "Conjectured Ramsey number R(n,n)."
R(m,n) = minimal number of nodes R such that in any graph with R nodes there is either an m-clique or an independent set of size n. This sequence gives the diagonal entries R(n,n).
Only these values have been proved: 0,1,2,6,18. a(5) is known to be in the range 43-49. - N. J. A. Sloane, Sep 16 2006
a(5) is at most 48, see the Angeltveit/McKay reference. - Jurjen N.E. Bos, Apr 11 2017
Ramsey numbers for simple binary partition.
Campos, Griffiths, Morris, & Sahasrabudhe prove that R(n,n) < 3.993^n for large enough n; they say the constant "could be improved further with some additional (straightforward, but somewhat technical) optimisation". This sequence posits a constant of 1.5. - Charles R Greathouse IV, Mar 18 2023

G. Berman and K. D. Fryer, Introduction to Combinatorics. Academic Press, NY, 1972, p. 175.

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.
Eric Weisstein's World of Mathematics, Ramsey Number
Wikipedia, Ramsey's theorem.

Cf. A000791, A059442, A212954 (which have many more references).

Join[{0,1},Table[Ceiling[(3/2)^(n-3) n(n-1)],{n,2,20}]] (* Harvey P. Dale, Aug 29 2024 *)

Edited by N. J. A. Sloane, Sep 16 2006

This was initially submitted as a conjecture for the Ramsey number R(n,n). I have replaced the definition with the exct formula that was used. - N. J. A. Sloane, Nov 05 2023

A213368 Row sums of triangle A212954 of two color Ramsey numbers.

Original entry on oeis.org

1, 2, 4, 8, 16, 30, 60, 102

Offset: 1

Omar E. Pol, Jun 10 2012

The next terms is known to be in the range 179-195.

			Since the triangle A212954 is symmetric we can write:
a(1)  = 1.
a(2)  = 2*1 = 2.
a(3)  = 2*1+2 = 2+2 = 4.
a(4)  = 2*(1+3) = 2*4 = 8.
a(5)  = 2*(1+4)+6 = 2*5+6 = 10+6 = 16.
a(6)  = 2*(1+5+9) = 2*15 = 30.
a(7)  = 2*(1+6+14)+18 = 2*21+18 = 42+18 = 60.
a(8)  = 2*(1+7+18+25) = 2*51 = 102.
And for the next three known terms we can write:
a(9)  = 2*(1+8+23+ ?)+ ? = ?.
a(10) = 2*(1+9+28+ ?+ ?) = ?.
a(11) = 2*(1+10+36+ ?+ ?)+ ? = ?.

Eric Weisstein's World of Mathematics, Ramsey Number
Wikipedia, Ramsey's theorem

Cf. A000791, A059442, A212954.

cp's OEIS Frontend

A000791 Ramsey numbers R(3,n).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions

A120414 a(0)=0, a(1)=1; thereafter a(n) = ceiling((3/2)^(n-3)n(n-1)).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Extensions

A213368 Row sums of triangle A212954 of two color Ramsey numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

cp's OEIS Frontend

A000791 Ramsey numbers R(3,n).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions

A120414 a(0)=0, a(1)=1; thereafter a(n) = ceiling((3/2)^(n-3)*n*(n-1)).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Extensions

A213368 Row sums of triangle A212954 of two color Ramsey numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A120414 a(0)=0, a(1)=1; thereafter a(n) = ceiling((3/2)^(n-3)n(n-1)).