Lower Bounds on van der Waerden Numbers: Randomized- and Deterministic-Constructive
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 l...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Electronic Journal of Combinatorics
2014
|
| Online Access: | http://hdl.handle.net/1721.1/89798 https://orcid.org/0000-0003-3381-0459 |
| _version_ | 1826194314022092800 |
|---|---|
| author | Gasarch, William Haeupler, Bernhard |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Gasarch, William Haeupler, Bernhard |
| author_sort | Gasarch, William |
| collection | MIT |
| description | 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 Lovasz 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 Lovasz 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. |
| first_indexed | 2024-09-23T09:53:49Z |
| format | Article |
| id | mit-1721.1/89798 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T09:53:49Z |
| publishDate | 2014 |
| publisher | Electronic Journal of Combinatorics |
| record_format | dspace |
| spelling | mit-1721.1/897982022-09-30T17:32:37Z Lower Bounds on van der Waerden Numbers: Randomized- and Deterministic-Constructive Gasarch, William Haeupler, Bernhard Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Haeupler, Bernhard 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 Lovasz 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 Lovasz 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. 2014-09-18T15:25:00Z 2014-09-18T15:25:00Z 2011-03 2010-05 Article http://purl.org/eprint/type/JournalArticle 1077-8926 http://hdl.handle.net/1721.1/89798 Gasarch, William, and Bernhard Haeupler. "Lower Bounds on van der Waerden Numbers: Randomized- and Deterministic-Constructive." Electronic Journal of Combinatorics, Volume 18, Issue 1 (2011). https://orcid.org/0000-0003-3381-0459 en_US http://www.combinatorics.org/ojs/index.php/eljc/article/view/v18i1p64 Electronic Journal of Combinatorics Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Electronic Journal of Combinatorics Electronic Journal of Combinatorics |
| spellingShingle | Gasarch, William Haeupler, Bernhard Lower Bounds on van der Waerden Numbers: Randomized- and Deterministic-Constructive |
| title | Lower Bounds on van der Waerden Numbers: Randomized- and Deterministic-Constructive |
| title_full | Lower Bounds on van der Waerden Numbers: Randomized- and Deterministic-Constructive |
| title_fullStr | Lower Bounds on van der Waerden Numbers: Randomized- and Deterministic-Constructive |
| title_full_unstemmed | Lower Bounds on van der Waerden Numbers: Randomized- and Deterministic-Constructive |
| title_short | Lower Bounds on van der Waerden Numbers: Randomized- and Deterministic-Constructive |
| title_sort | lower bounds on van der waerden numbers randomized and deterministic constructive |
| url | http://hdl.handle.net/1721.1/89798 https://orcid.org/0000-0003-3381-0459 |
| work_keys_str_mv | AT gasarchwilliam lowerboundsonvanderwaerdennumbersrandomizedanddeterministicconstructive AT haeuplerbernhard lowerboundsonvanderwaerdennumbersrandomizedanddeterministicconstructive |