Premium
An application of Lovász' local lemma‐A new lower bound for the van der Waerden number
Author(s) -
Szabó Zoltán
Publication year - 1990
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240010307
Subject(s) - van der waerden's theorem , combinatorics , integer (computer science) , lemma (botany) , mathematics , upper and lower bounds , arithmetic progression , discrete mathematics , computer science , biology , mathematical analysis , poaceae , programming language , ecology
The van der Waerden number W(n) is the smallest integer so that if we divide the integers {1,2, …, W(n) } into two classes, then at least one of them contains an arithmetic progression of length n . We prove in this paper that W(n) ≥ 2 n / n ϵ for all sufficiently large n .