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

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01233448
Contributor : Alexandre Pinlou <>
Submitted on : Wednesday, November 25, 2015 - 11:12:34 AM
Last modification on : Monday, August 5, 2019 - 3:26:03 PM

Identifiers

  • HAL Id : lirmm-01233448, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

180