Application of entropy compression in pattern avoidance

zbMath1299.68046arXiv1301.1873MaRDI QIDQ405191

Pascal Ochem, Alexandre Pinlou

Publication date: 4 September 2014

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

pattern avoidanceword

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Related Items (13)

Doubled patterns are 3-avoidable ⋮ A short proof that shuffle squares are 7-avoidable ⋮ Computing Depths of Patterns ⋮ Approaching repetition thresholds via local resampling and entropy compression ⋮ Moser-Tardos resampling algorithm, entropy compression method and the subset gas ⋮ Doubled patterns with reversal and square-free doubled patterns ⋮ Avoidability of palindrome patterns ⋮ Generating square-free words efficiently ⋮ Nonrepetitive colouring via entropy compression ⋮ Compressibility and probabilistic proofs ⋮ Entropy compression versus Lovász local lemma ⋮ Grasshopper avoidance of patterns ⋮ Pattern avoidance in partial words over a ternary alphabet

Cites Work

• Unnamed Item
• Unnamed Item
• Strict bounds for pattern avoidance
• Nonrepetitive colouring via entropy compression
• Further applications of a power series method for pattern avoidance
• Avoidable patterns in strings of symbols
• Every binary pattern of length six is avoidable on the two-letter alphabet
• Exponential lower bounds for the number of words of uniform length avoiding a pattern
• Acyclic edge-coloring using entropy compression
• A generator of morphisms for infinite words
• A constructive proof of the general lovász local lemma
• BLOCKING SETS OF TERMS

This page was built for publication: Application of entropy compression in pattern avoidance