Unavoidable Patterns in Words
summary
Defines FN(q) as the least length forcing Zeeman word ZN in any q-letter string and proves concrete growth rates and constructions. Main claims: for fixed N FN(q) grows as a tower of q of height N−1 up to lower order terms and this is essentially tight, F3(q) = Θ(2^q q!) with matching construction, and F2(q) = 2q+1. Proof techniques combine a randomized construction using the local lemma plus a combinatorial stepping-up amplification and explicit De Bruijn based constructions.
AI-written summary · about