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.

Review text

Summary: 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= h(p)\) where \(h: \Delta^*\to\Sigma^*\) 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 \textit{M. Lothaire}'s book [Algebraic combinatorics on words. Cambridge: Cambridge University Press (2002; Zbl 1001.68093)], that is, every pattern with \(k\) variables of length at least \(2^k\) (resp. \(3\times2^{k-1}\)) is 3-avoidable (resp. 2-avoidable). This conjecture was first stated by \textit{J. Cassaigne} [Motifs évitables et régularité dans les mots. Paris: Université Paris VI (PhD Thesis) (1994)]. This improves previous bounds due to \textit{J. P. Bell} and \textit{T. L. Goh} [Inf. Comput. 205, No. 9, 1295--1306 (2007; Zbl 1127.68073)] and \textit{N. Rampersad} [Electron. J. Comb. 18, No. 1, Research Paper P134, 8 p. (2011; Zbl 1219.68128)].

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

• 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
• scientific article; zbMATH DE number 4027472 (Why is no real title available?)
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• Nonrepetitive colouring via entropy compression
• Strict bounds for pattern avoidance

Cited in

(17)

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