login
A279032
a(n) is the greatest integer such that binomial(a(n),n)*2^(1 - binomial(n,2)) < 1.
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,3
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.
FORMULA
a(n) is asymptotic to n*2^(n/2)/(e*sqrt(2)).
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
CROSSREFS
Cf. A212954.
Sequence in context: A011901 A169739 A109471 * A124454 A335631 A013932
KEYWORD
nonn
AUTHOR
Geoffrey Critzer, Dec 03 2016
EXTENSIONS
More terms from Robert Israel, Dec 07 2016
STATUS
approved