[40] Let s1 ...sn be a string over an alphabet of cardinality c.

A monochromatic arithmetic progression (m.a.p.) of length k is a subsequence sisi+tsi+2t ...si+(k−1)t with all characters equal. The van der Waerden number w(k;

c) is the least number n such that every string of length n contains a m.a.p. of length k. Use the incompressibility method in the following problems.

(a) Show that w(k;

c) > √k − 1 · c k

2 −1.

(b) Strengthen the bound to w(k;

c) > ck−2 4k · k−1 k .

Comments. The lower bound of Item

(b) matches the one obtained originally by L. Lov´asz, and is worse than later applications of Lov´asz’s Local Lemma by a factor 4/e; see for example [Z. Sz´abo, Random Struct. Alg., 1:3(1990), 343–360]. The method can also be used for other Ramsey-type lower bounds. Hint for Item (b):

(i) Show that logc(n· k · k k−1 )+ 1 characters suffice to encode a m.a.p., if it is known to intersect some other fixed progression of length k.

(ii) Consider a procedure that in a long incompressible string repeatedly does the following: Find a m.a.p. within the first w(k;

c) characters. Encode it by some string, delete the corresponding characters, and replace them with characters from the end of the string.

(iii) Use the following fact without proof: With logc 4 additional characters in the encoding of every deleted progression one can guarantee that there is always a m.a.p. in the first w(k;

c) characters that intersects the positions of a previously deleted progression (determinable without additional characters).

Implement Items (i) through (iii) as follows: Maintain a stack whose elements each contain the positions of a progression that has been deleted.

Upon deletion of a progression, push its positions onto the stack. If a progression in the current string intersects the positions on top of the stack, encode it this way; otherwise, delete the top of the stack. Encoding which case happened can be done with logc 2 characters and every case happens at most once per deleted progression. Source: [P. Schweitzer,

[Inform. Process. Lett., 109:4(2009), 229–232]. Later T. Kulich and M.
Kemeˇnov´a [Inform. Process. Lett., 111:9(2011) 436–439] improved the result to give exactly the same result as the Lov´asz Local Lemma.