Squarefree word
Encyclopedia
In combinatorics
, a square-free word is a word
that does not contain any subword twice in a row. There exist infinite square-free words in any alphabet
with three or more symbols, as proved by Axel Thue
. To build an infinite square-free word in the alphabet {a, b, c}, let
be any word starting with the letter a. Define the words 
recursively as follows: the word 
is obtained from 
by replacing each a in 
with abcbacbcabcba, each b with bcacbacabcacb, and each c with cabacbabcabac (this example was found by J. Leech ). It is possible to check that the sequence converges to the infinite square-free word abcbacbcabcbabcacbacabcacbcabacbabcabacbcacbacabcacb...
Over a two-letter alphabet {a, b} the only square-free words are the empty word and a, b, ab, ba, aba, and bab. There is, however, an infinite cube-free word: the Thue-Morse sequence
.
The Thue number
of a graph
G is the smallest number k such that G has a k-coloring for which the sequence of colors along every non-repeating path is squarefree.
Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
, a square-free word is a word
String (computer science)
In formal languages, which are used in mathematical logic and theoretical computer science, a string is a finite sequence of symbols that are chosen from a set or alphabet....
that does not contain any subword twice in a row. There exist infinite square-free words in any alphabet
Alphabet
An alphabet is a standard set of letters—basic written symbols or graphemes—each of which represents a phoneme in a spoken language, either as it exists now or as it was in the past. There are other systems, such as logographies, in which each character represents a word, morpheme, or semantic...
with three or more symbols, as proved by Axel Thue
Axel Thue
Axel Thue was a Norwegian mathematician, known for highly original work in diophantine approximation, and combinatorics....
. To build an infinite square-free word in the alphabet {a, b, c}, let
be any word starting with the letter a. Define the words recursively as follows: the word is obtained from by replacing each a in with abcbacbcabcba, each b with bcacbacabcacb, and each c with cabacbabcabac (this example was found by J. Leech ). It is possible to check that the sequence converges to the infinite square-free word abcbacbcabcbabcacbacabcacbcabacbabcabacbcacbacabcacb...Over a two-letter alphabet {a, b} the only square-free words are the empty word and a, b, ab, ba, aba, and bab. There is, however, an infinite cube-free word: the Thue-Morse sequence
Thue-Morse sequence
In mathematics, the Thue–Morse sequence, or Prouhet–Thue–Morse sequence, is a binary sequence that begins:Any other ordered pair of symbols may be used instead of 0 and 1; the logical structure of the Thue–Morse sequence does not depend on the symbols that are used to represent it.- Direct...
.
The Thue number
Thue number
In the mathematical area of graph theory, the Thue number of a graph is a variation of the chromatic index, defined by Alon et al. and named by them after mathematician Axel Thue, who studied the squarefree words used to define this number.Alon et al...
of a graph
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
G is the smallest number k such that G has a k-coloring for which the sequence of colors along every non-repeating path is squarefree.