Half-flips are 5-avoidable
Settles the open problem of the minimal alphabet size for avoiding half-flips in infinite words, a question in combinatorics on words.
The paper proves that half-flips (non-empty factors uv and vu with |u|=|v|) are avoidable over a 5-letter alphabet by constructing a pure morphic word, and shows that restricted half-flips are avoidable over smaller alphabets (3 letters for |u|≥2, 2 letters for |u|≥4).
A word contains a \emph{half-flip} if it contains non-empty factors $uv$ and $vu$ where $|u|=|v|$. Fici reports a non-constructive proof of the existence of an infinite word over a finite alphabet avoiding half-flips and asks for the size of the smallest alphabet over which half-flips may be avoided. Currie and Rampersad have proposed a pure morphic word over 8 letters and a morphic word over 5 letters and conjecture that they avoid half-flips. We present a pure morphic word over 5 letters that avoids half-flips. We also show that half-flips with $|u|\ge2$ are 3-avoidable and that half-flips with $|u|\ge4$ are 2-avoidable.