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.
LINKS
Chai Wah Wu, Table of n, a(n) for n = 1..1000
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
KEYWORD
nonn
AUTHOR
Geoffrey Critzer, Dec 03 2016
EXTENSIONS
More terms from Robert Israel, Dec 07 2016
STATUS
approved