On Long Words Avoiding Zimin Patterns

DOI10.4230/LIPICS.STACS.2017.19MaRDI QIDQ4636617zbMATHOpenAlexFDO

Authors Arnaud Carayol, Stefan Göller

Publication date 19 April 2018

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

zbMATH Keywords

lower boundscombinatorics on wordsunavoidable patterns

Mathematics Subject Classification ID

Combinatorics on words (68R15)

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.

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

Cited in

(8)

• On long words avoiding Zimin patterns
• Searching for Zimin patterns
• scientific article; zbMATH DE number 1786461 (Why is no real title available?)
• Unavoidable regularities in long words with bounded number of symbol occurrences
• Bounds on Zimin word avoidance
• Long unavoidable patterns
• Defining long words succinctly in FO and MSO
• Tower-type bounds for unavoidable patterns in words

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)