Application of entropy compression in pattern avoidance - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles The Electronic Journal of Combinatorics Year : 2014

Application of entropy compression in pattern avoidance

Pascal Ochem


In combinatorics on words, a word w over an alphabet Σ is said to avoid a pattern p over an alphabet Δ if there is no factor f of w such that f=h(p) where h:Δ∗→Σ∗ is a non-erasing morphism. A pattern p is said to be k-avoidable if there exists an infinite word over a k-letter alphabet that avoids p. We give a positive answer to Problem 3.3.2 in Lothaire's book "Algebraic combinatorics on words'", that is, every pattern with k variables of length at least 2k (resp. 3×2k−1) is 3-avoidable (resp. 2-avoidable). This conjecture was first stated by Cassaigne in his thesis in 1994. This improves previous bounds due to Bell and Goh, and Rampersad.

Dates and versions

lirmm-01233448 , version 1 (25-11-2015)



Pascal Ochem, Alexandre Pinlou. Application of entropy compression in pattern avoidance. The Electronic Journal of Combinatorics, 2014, 21 (2), pp.1-12. ⟨10.37236/3038⟩. ⟨lirmm-01233448⟩
105 View
0 Download



Gmail Facebook X LinkedIn More