How far are ternary words from shuffle squares?
Ayush Basu, Andrzej Ruciński · Ars Mathematica Contemporanea · 2024
A shuffle square is a word which consists of two identical and disjoint, but possibly intertwining subwords. For every natural number n, we construct a ternary word of length n which requires a removal of at least Ω(log²n) of its letters in order to become a shuffle square.