Application of entropy compression in pattern avoidance

Abstract: In combinatorics on words, a word

w

over an alphabet

S i g m a

is said to avoid a pattern

p

over an alphabet

D e l t a

if there is no factor

f

of

w

such that

f = (p)

where

h : D e l t a^{*} o S i g m a^{*}

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.

3 i m e s 2^{k - 1}

) is 3-avoidable (resp. 2-avoidable). This improves previous bounds due to Bell and Goh, and Rampersad.

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

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

Recommendations

Cites Work

Cited In (15)

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