On Long Words Avoiding Zimin Patterns

DOI10.4230/LIPICS.STACS.2017.19zbMATH Open1402.68145arXiv1902.05540OpenAlexW2604316470MaRDI QIDQ4636617FDOQ4636617

Stefan Göller, Arnaud Carayol

Publication date: 19 April 2018

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1902.05540

Recommendations

• On long words avoiding Zimin patterns
• Bounds on Zimin word avoidance
• Unavoidable regularities in long words with bounded number of symbol occurrences
• Unavoidable regularities in long words with bounded number of symbol occurrences
• On Unavoidable Sets of Word Patterns
• Avoiding letter patterns in ternary square-free words
• Avoidable binary patterns in partial words
• Avoidable binary patterns in partial words
• Asymptotic density of Zimin words
• Pattern avoidance in partial words over a ternary alphabet

zbMATH Keywords

lower boundscombinatorics on wordsunavoidable patterns

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Cited In (6)

• Defining long words succinctly in FO and MSO
• Long unavoidable patterns
• Title not available (Why is that?)
• On long words avoiding Zimin patterns
• Tower-type bounds for unavoidable patterns in words
• Unavoidable regularities in long words with bounded number of symbol occurrences

This page was built for publication: On Long Words Avoiding Zimin Patterns

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4636617)