2021/12/28 by Dudek, Andrzej, Grytczuk, Jarosław, Ruciński, Andrzej · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2112.14197
Twins in a finite word are formed by a pair of identical subwords placed at disjoint sets of positions. We investigate the maximum length of twins in a random word over a k-letter alphabet. The obtained lower bounds for small values of k significantly improve the best estimates known in the deterministic case. Bukh and Zhou in 2016 showed that every ternary word of length n contains twins of length at least 0.34n. Our main result states that in a random ternary word of length n, with high probability, one can find twins of length at least 0.41n. In the general case of alphabets of size k≥ 3 we obtain analogous lower bounds of the form (1.64)/(k+1)n which are better than the known deterministic bounds for k≤ 354. In addition, we present similar results for multiple twins in random words.