Suppose W(k,2) is the smallest number such that if n≥W(k,2), for each coloring of the set {1,2,...,n} with two colors there exists a monochromatic arithmetic progression of length k. Prove that W(k,2)=Ω(2k2).
Problem
Source: Iran 3rd round 2012-Special Lesson exam-Part 2-P2
Tags: function, probability, arithmetic sequence, combinatorics proposed, combinatorics
17.09.2012 05:38
What is Ω(n) ? I've only ever seen it represent the number of prime factors of n, counting multiplicity.
17.09.2012 06:37
ocha wrote: What is Ω(n) ? I've only ever seen it represent the number of prime factors of n, counting multiplicity. Well, I really don't know, because I'm not attending the classes anymore. But I think it wants us to prove a lower bound for the Van der Waerden numbers.
17.09.2012 10:48
Big Omega notation, where W(k,2) is bounded below by a function of growth rate equivalent to 2k2.
17.09.2012 12:49
Let fix n. Consider a random coloring of {1,2,…,n} with two colors. The probability to exists a monochromatic arithmetic progression with step 1 and of length k is less than 2n2−k. In the same way the probability to have an arithmetic progression with step i, (1≤i≤n) and of length k is less than 2n2−k. This means that the probability to exists a monochromatic arithmetic progression of lenght k is less than 2n22−k. Now, if 2n22−k<1, it means that there exists coloring of {1,2,…,n} without monochromatic progression of length k. 2n22−k<1 yeilds n<2−122k2, which means W(k,2)=Ω(2k2)
17.09.2012 13:03
There is a neat proof of that bound via the probabilistic method. Here are the steps: Colour the set {1,2,…,n} uniformly at random, using two colours. Consider an arbitrary k-arithmetic progression inside {1,2,…,n}. The probability that it is monochromatic is 2×12×⋯×12⏟k times =12k−1. If P(k,n) denotes the number of k-arithmetic progressions inside {1,2,…,n}, prove that P(k,n)∼n22(k−1). Hence the probability that we get a monochromatic k-arithmetic progression is ≤P(k,n)×12k−1∼n2(k−1)2k. Note that if this probability is less than 1, then we get the lower bound W(k,2)>n. To get the result, simply check that with n=2k2, the above probability is indeed eventually less than 1. Two remarks: 1) An extensive survey on lower bounds on the van der Waerden number W(k,2) is Lower Bounds on van der Waerden Numbers: Randomized- and Deterministic-Constructive by W. Gasarch and B. Haeupler. In particular, the above approach is essentially the one originally used by Erdős and Rado. 2) It can be used, mutatis mutandis, to get a similar lower bound on W(k,r) (that is, for an r-colouring of the set {1,2,…,n}). EDIT: beaten by a somewhat long shot by dgrozev, oh well.
18.08.2019 22:05
@mathmanman: Ok, perhaps you don't know the exact meaning of the English idiom "Long shot". I just gave a straitforward answer to the OP. I knew, it was the Erdos approach, and there was a lot of history behind it. But, the fact I didn't make an historic retrospection didn't make it a long shot! Btw, do you know the expression "To beat around the bush"?