Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Lower Bounds on van der Waerden Numbers: Randomized- and Deterministic-Constructive. | Lower Bounds on van der Waerden Numbers Randomized- and Deterministic-Constructive William Gasarch Bernhard Haeupler Department of Computer Science CSAIL University of Maryland at College Park Massachusetts Institute of Technology College Park MD 20742 USA Cambridge MA 02130 USA gasarch@ haeupler@ Submitted May 19 2010 Accepted Mar 8 2011 Published Mar 24 2011 Mathematics Subject Classification 05D10 Abstract 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. 1 Introduction Notation Let n 1 . n and N 1 2 . . If k G N then a k-AP means an arithmetic progression of size k . k numbers of the form a a d . a k 1 d with a d G N . Recall van der .
