A000791 -id:A000791 - cp's OEIS frontend

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

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

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

A000789 Maximal order of a triangle-free cyclic graph with no independent set of size n.

Original entry on oeis.org

2, 5, 8, 13, 16, 21, 26, 35, 38, 45, 48

Offset: 2

N. J. A. Sloane

Previous name was: Ramsey numbers.
The sequence may be considered as consisting of a special kind of Ramsey numbers. It is related to the ordinary two-color Ramsey numbers R(3,n), given in A000791, by the relation a(n) <= A000791(n)-1 as proved by Kalbfleisch. He also calculated the first eight terms, and noted that the inequality sometimes is strict. The first n for which this happens is n=6.
The terms a(10), a(11) and a(12) were calculated by Harborth and Krause. - Jörgen Backelin, Jan 07 2016

			That a(6) >= 16 is seen from the cyclic (or circulant) graph on 16 vertices, with edges between vertices of index distances 1, 3, or 8, since this cyclic graph indeed is triangle-free and has independence number five, which is less than six.
On the other hand, a(6) < 17, since any triangle free graph with independence number less than six and at least 17 vertices has exactly 17 vertices and cannot be regular, but all cyclic graphs are regular.
Thus, indeed, a(6) = 16.

H. Harborth, S. Krause: Ramsey Numbers for Circulant Colorings, Congressus Numerantium 161 (2003), pp. 139-150.
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).

J. G. Kalbfleisch, Construction of special edge-chromatic graphs, Canad. Math. Bull., 8 (1965), 575-584.

Cf. A000791.

New title and a(10), a(11), a(12) added by Jörgen Backelin, Jan 12 2016

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.

A267295 Circulant Ramsey numbers RC_2(3,n) of the second kind.

Original entry on oeis.org

3, 6, 9, 14, 17, 22, 27, 36, 39, 46, 49

Offset: 2

Jörgen Backelin, Jan 12 2016

The smallest number a(n), such that any triangle-free cyclic (also known as circulant) graph with at least a(n) vertices has independence number at least n. The terminology and the terms given here are from Harborth and Krause (2003); however, in another form, essentially they were considered and partly calculated already by Kalbfleich in 1965.
a(n) = A000789(n)+1 and a(n) >= A267296(n) for all n.
Moreover, the sequence is related to the ordinary two-color Ramsey numbers R(3,n), given in A000791, by the relation a(n) <= A000791(n) for all n, as proved by Kalbfleisch. This inequality is known to be strict for 6 <= n <= 8, and for n = 10.

H. Harborth, S. Krause: Ramsey Numbers for Circulant Colorings, Congressus Numerantium 161 (2003), 139-150.

J. G. Kalbfleisch, Construction of special edge-chromatic graphs, Canad. Math. Bull., 8 (1965), 575-584.
Index entries for sequences related to Ramsey numbers

Cf. A000789, A000791, A267296.

A267296 Circulant Ramsey numbers RC_1(3,n) of the first kind.

Original entry on oeis.org

3, 3, 9, 14, 15, 22, 25, 34, 37, 46, 49

Offset: 2

Jörgen Backelin, Jan 12 2016

The smallest positive number a(n), such that any triangle-free cyclic (also known as circulant) graph with a(n) vertices has independence number at least n. The terminology and the terms given here are from Harborth and Krause.
a(n) <= A267295(n) for all n.
Moreover, the sequence is related to the ordinary two-color Ramsey numbers R(3,n), given in A000791, by the relation a(n) <= A000791(n) for all n, as proved by Kalbfleisch. This inequality is known to be an equality for n = 2 or 4 <= n <= 5.

H. Harborth, S. Krause, Ramsey Numbers for Circulant Colorings, Congressus Numerantium 161 (2003), 139-150.

Index entries for sequences related to Ramsey numbers

Cf. A000791, A267295.

A210240 Ramsey numbers R(3,n).

Original entry on oeis.org

5, 8, 13, 17, 22

Offset: 3

N. J. A. Sloane, Mar 19 2012

See Graver-Yackel for definition.
It is known that a(8) is in [26-29], a(9) is 35 or 36.
Differs by 1 from the list provided by A000791. - Ray G. Opao, Jun 24 2012

Jack E. Graver and James Yackel, Some graph theoretic results associated with Ramsey's theorem. J. Combinatorial Theory 4 1968 125--175. MR0225685 (37 #1278)
Eric W. Weisstein, MathWorld: Ramsey Number

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

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

A000789 Maximal order of a triangle-free cyclic graph with no independent set of size n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A267295 Circulant Ramsey numbers RC_2(3,n) of the second kind.

Views

Author

Keywords

Comments

References

Links

Crossrefs

A267296 Circulant Ramsey numbers RC_1(3,n) of the first kind.

Views

Author

Keywords

Comments

References

Links

Crossrefs

A210240 Ramsey numbers R(3,n).

Views

Author

Keywords

Comments

Links

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