OFFSET
3,1
COMMENTS
The two-color van der Waerden number w(3,n) is also denoted as w(2;3,n).
Ahmed et al. give lower bounds for a(20)-a(30) which may in fact be the true values. - N. J. A. Sloane, May 13 2018
B. Green shows that w(3,n) is bounded below by n^b(n), where b(n) = c*(log(n)/ log(log(n)))^(1/3). T. Schoen proves that for large n one has w(3,n) < exp(n^(1 - c)) for some constant c > 0. - Peter Luschny, Feb 03 2021
REFERENCES
Knuth, Donald E., Satisfiability, Fascicle 6, volume 4 of The Art of Computer Programming. Addison-Wesley, 2015, page 5.
LINKS
Tanbir Ahmed, Oliver Kullmann, and Hunter Snevily, On the van der Waerden numbers w(2;3,t), arXiv:1102.5433 [math.CO], 2011-2014; Discrete Applied Math., 174 (2014), 27-51.
Thomas Bloom, Problem #721, Erdős problems.
Thomas Bloom and Olof Sisask, An improvement to the Kelley-Meka bounds on three-term arithmetic progressions, arXiv:2309.02353 [math.NT], 2023.
Ben Green, New lower bounds for van der Waerden numbers, arXiv:2102.01543 [math.CO], 2021-2022.
Zach Hunter, Improved lower bounds for van der Waerden numbers, Combinatorica (2022), 1231-1252, arXiv:2111.01099 [math.CO], 2021-2022.
Zander Kelley and Raghu Meka, Strong Bounds for 3-Progressions, arXiv:2302.05537 [math.NT], 2023-2024.
Tomasz Schoen, A subexponential bound for van der Waerden numbers, arXiv:2006.02877 [math.CO], June 2020.
FORMULA
a(n) >= exp(c(log n)^(4/3) / (log log n)^(1/3)) for constant c > 0. (Green)
a(n) >= exp(c(log n)^2 / log log n) for constant c > 0. (Hunter)
a(n) < exp(n^c) for constant c < 1. (Schoen)
a(n) << exp(O((log n)^9)). (Bloom and Sisask)
CROSSREFS
KEYWORD
nonn,hard,more
AUTHOR
N. J. A. Sloane, based on an email from Tanbir Ahmed, Sep 07 2010
EXTENSIONS
a(19) from Ahmed et al. added by Jonathan Vos Post, Mar 01 2011
STATUS
approved
