{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T16:43:30Z","timestamp":1753893810091,"version":"3.41.2"},"reference-count":0,"publisher":"The Electronic Journal of Combinatorics","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electron. J. Combin."],"abstract":"<jats:p>The van der Waerden number $W(k,2)$ is the smallest integer $n$ such that every $2$-coloring of 1 to $n$ has a monochromatic arithmetic progression of length $k$. The existence of such an $n$ for any $k$ is due to van der Waerden but known upper bounds on $W(k,2)$ are enormous.  Much effort was put into developing lower bounds on $W(k,2)$.  Most of these lower bound proofs employ the probabilistic method often in combination with the Lov\u00e1sz Local Lemma. While these proofs show the existence of a $2$-coloring that has no monochromatic arithmetic progression of length $k$ they provide no efficient algorithm to find such a coloring. These kind of proofs are often informally called nonconstructive in contrast to constructive proofs that provide an efficient algorithm. This paper clarifies these notions and gives definitions for deterministic- and randomized-constructive proofs as different types of constructive proofs. We then survey the literature on lower bounds on $W(k,2)$ in this light. We show how known nonconstructive lower bound proofs based on the Lov\u00e1sz Local Lemma can be made randomized-constructive using the recent algorithms of Moser and Tardos. We also use a derandomization of Chandrasekaran, Goyal and Haeupler to transform these proofs into deterministic-constructive proofs.  We provide greatly simplified and fully self-contained proofs and descriptions for these algorithms.<\/jats:p>","DOI":"10.37236\/551","type":"journal-article","created":{"date-parts":[[2020,1,11]],"date-time":"2020-01-11T03:52:15Z","timestamp":1578714735000},"source":"Crossref","is-referenced-by-count":2,"title":["Lower Bounds on van der Waerden Numbers: Randomized- and Deterministic-Constructive"],"prefix":"10.37236","volume":"18","author":[{"given":"William","family":"Gasarch","sequence":"first","affiliation":[]},{"given":"Bernhard","family":"Haeupler","sequence":"additional","affiliation":[]}],"member":"23455","published-online":{"date-parts":[[2011,3,24]]},"container-title":["The Electronic Journal of Combinatorics"],"original-title":[],"link":[{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v18i1p64\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v18i1p64\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,17]],"date-time":"2020-01-17T23:15:09Z","timestamp":1579302909000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v18i1p64"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,3,24]]},"references-count":0,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2011,1,5]]}},"URL":"https:\/\/doi.org\/10.37236\/551","relation":{},"ISSN":["1077-8926"],"issn-type":[{"type":"electronic","value":"1077-8926"}],"subject":[],"published":{"date-parts":[[2011,3,24]]},"article-number":"P64"}}