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

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

Author

Geoffrey Critzer, Dec 03 2016

Keywords

• nonn

Comments

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.

References

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

Links

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

Crossrefs

Cf. A212954.

Programs

Maple

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

Mathematica

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

Formula

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

Extensions

More terms from Robert Israel, Dec 07 2016