Application of entropy compression in pattern avoidance

Pascal Ochem 1 Alexandre Pinlou 1
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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.
Complete list of metadatas
Contributor : Alexandre Pinlou <>
Submitted on : Wednesday, November 25, 2015 - 11:12:34 AM
Last modification on : Wednesday, October 17, 2018 - 5:08:02 PM


  • HAL Id : lirmm-01233448, version 1



Pascal Ochem, Alexandre Pinlou. Application of entropy compression in pattern avoidance. The Electronic Journal of Combinatorics, Open Journal Systems, 2014, 21 (2), pp.1-12. ⟨⟩. ⟨lirmm-01233448⟩



Record views