Báo cáo toán học: " Lower Bounds on van der Waerden Numbers: Randomized- and Deterministic-Constructive"

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 .

Không thể tạo bản xem trước, hãy bấm tải xuống
TÀI LIỆU MỚI ĐĂNG
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.