Application of entropy compression in pattern avoidance

MaRDI QIDQ405191zbMATH OpenFDO

Authors 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, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i2p7

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

pattern avoidanceword

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Abstract: In combinatorics on words, a word $w$ over an alphabet $Sigma$ is said to avoid a pattern $p$ over an alphabet $Delta$ if there is no factor $f$ of $w$ such that $f=(p)$ where $h:Delt{a}^{\ast }oSigm{a}^{\ast }$ 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 $2^k$ (resp. $3imes{2}^{k-1}$) is 3-avoidable (resp. 2-avoidable). This improves previous bounds due to Bell and Goh, and Rampersad.

Recommendations

• Further applications of a power series method for pattern avoidance
• Pattern avoidance in partial words over a ternary alphabet
• scientific article; zbMATH DE number 4035171
• Doubled patterns are 3-avoidable
• Avoidability of formulas with two variables

Cites work

• scientific article; zbMATH DE number 4027472 (Why is no real title available?)
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• A constructive proof of the general Lovász local lemma
• A generator of morphisms for infinite words
• Acyclic edge-coloring using entropy compression
• Avoidable patterns in strings of symbols
• BLOCKING SETS OF TERMS
• 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
• Further applications of a power series method for pattern avoidance
• Nonrepetitive colouring via entropy compression
• Strict bounds for pattern avoidance

Cited in

(17)

• Further applications of a power series method for pattern avoidance
• Avoidability of palindrome patterns
• Computing depths of patterns
• Entropy compression versus Lovász local lemma
• Avoidability of formulas with two variables
• Compressibility and probabilistic proofs
• Grasshopper avoidance of patterns
• Nonrepetitive colouring via entropy compression
• Approaching repetition thresholds via local resampling and entropy compression
• A short proof that shuffle squares are 7-avoidable
• Generating square-free words efficiently
• Pattern avoidance in partial words over a ternary alphabet
• New problems of pattern avoidance
• Doubled patterns are 3-avoidable
• Non-constructive upper bounds for repetition thresholds
• Moser-Tardos resampling algorithm, entropy compression method and the subset gas
• Doubled patterns with reversal and square-free doubled patterns

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q405191)