2013/01/09 by Pascal Ochem, Ochem, Pascal, Alexandre Pinlou +1
Computer Science · Mathematics · #68R15 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #math.CO #msc:68R15
paper · pdf · doi:10.48550/arxiv.1301.1873
11 pages
arxiv created 2013/01/09 · arxiv updated 2013/01/10
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= (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 improves previous bounds due to Bell and Goh, and Rampersad.