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.
Type de document :
Article dans une revue
Electronic Journal of Combinatorics, Electronic Journal of Combinatorics, 2014, 21 (2), pp.1-12. 〈http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i2p7〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01233448
Contributeur : Alexandre Pinlou <>
Soumis le : mercredi 25 novembre 2015 - 11:12:34
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Identifiants

  • HAL Id : lirmm-01233448, version 1

Collections

Citation

Pascal Ochem, Alexandre Pinlou. Application of entropy compression in pattern avoidance. Electronic Journal of Combinatorics, Electronic Journal of Combinatorics, 2014, 21 (2), pp.1-12. 〈http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i2p7〉. 〈lirmm-01233448〉

Partager

Métriques

Consultations de la notice

129