Square-free words with one possible mismatch (Q297663): Difference between revisions

A classical problem in combinatorics on words is, given a pattern \(p\), to decide what is the least size of an alphabet \(A\) such that there exist arbitrarily long words (or, equivalently, an infinite word) not containing \(p\). For example, A. Thue showed in 1906 that it is possible to construct an infinite word over an alphabet of three letters not containing squares, that is, factors of the form \(xx\), while it is readily verified that every sufficiently long word over a binary alphabet must contain a square. In this paper the author considers a new pattern that he calls ``square with one error'', that is, a factor of the form \(xy\) where \(y\) differs from \(x\) in one letter. The paper announces several results (the proofs are omitted for space constraints) on the minimal size of the alphabet over which it is possible to construct infinite words not containing squares of half-length \(k_0\) and squares with one error of half-length \(k_1\), for all the possible combinations of \(k_0\) and \(k_1\).