2026-07-20T01:57:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7014 2024-03-06T10:39:09Z ddc:004 open_access

On Long Words Avoiding Zimin Patterns Carayol, Arnaud Göller, Stefan Unavoidable patterns combinatorics on words lower bounds A pattern is encountered in a word if some infix of the word is the image of the pattern under some non-erasing morphism. A pattern p is unavoidable if, over every finite alphabet, every sufficiently long word encounters p. A theorem by Zimin and independently by Bean, Ehrenfeucht and McNulty states that a pattern over n distinct variables is unavoidable if, and only if, p itself is encountered in the n-th Zimin pattern. Given an alphabet size k, we study the minimal length f(n,k) such that every word of length f(n,k) encounters the n-th Zimin pattern. It is known that f is upper-bounded by a tower of exponentials. Our main result states that f(n,k) is lower-bounded by a tower of n-3 exponentials, even for k=2. To the best of our knowledge, this improves upon a previously best-known doubly-exponential lower bound. As a further result, we prove a doubly-exponential upper bound for encountering Zimin patterns in the abelian sense. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Arnaud Carayol and Stefan Göller 2017 Is Part Of LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2017.19 urn:nbn:de:0030-drops-70140 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.19 eng https://creativecommons.org/licenses/by/3.0/legalcode