A212954 -id:A212954 - cp's OEIS frontend

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

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.

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

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

A279032 a(n) is the greatest integer such that binomial(a(n),n)*2^(1 - binomial(n,2)) < 1.

Original entry on oeis.org

0, 1, 3, 6, 11, 17, 27, 42, 65, 100, 152, 231, 349, 527, 792, 1186, 1771, 2639, 3923, 5817, 8609, 12715, 18747, 27595, 40557, 59522, 87239, 127704, 186721, 272717, 397913, 580029, 844734, 1229199, 1787215, 2596587, 3769796, 5469375, 7930078, 11490820, 16640682

Offset: 1

Geoffrey Critzer, Dec 03 2016

nonn

a(n) is a lower bound on the Ramsey number R(n,n). In other words, a(n) is less than the least integer N such that every graph on N vertices contains an n clique or a size n independent set.

D. B. West, Introduction to Graph Theory, Pearson, 2015, page 385.

Chai Wah Wu, Table of n, a(n) for n = 1..1000

Cf. A212954.

f:= proc(n) local k,r,B;
  k:= max(floor(n*2^(n/2)/(exp(1)*sqrt(2))),n);
  r:= 2^(binomial(n,2)-1);
  B:= binomial(k,n);
  if B < r then
    while B*(k+1)/(k+1-n) < r do k:= k+1; B:= B*k/(k-n) od;
  else
    while B*(k-1)/k > r do B:= B*(k-1)/k; k:= k-1 od;
    k:= k-1;
  fi;
  k
end proc:
map(f, [$1..40]); # Robert Israel, Dec 07 2016

Table[Position[Table[Binomial[m, n] < 2^(Binomial[n, 2] - 1), {m, 1, 50000}],False][[1]] - 1, {n, 1, 25}] // Flatten

a(n) is asymptotic to n*2^(n/2)/(e*sqrt(2)).

More terms from Robert Israel, Dec 07 2016

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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

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

A279032 a(n) is the greatest integer such that binomial(a(n),n)*2^(1 - binomial(n,2)) < 1.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

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