How many double squares can a string contain?

12/03/2015 - 12:00 - 13:00
Speaker: 
מיקום: 
Abstract: 

Counting the number of types of squares rather than their occurrences, we consider
the problem of bounding the maximum number of distinct squares in a string. Fraenkel and
Simpson showed in 1998 that a string of length n contains at most 2n distinct squares.
Ilie presented in 2007 an asymptotic upper bound of 2n(log n). We show that a string
of length n contains at most b11n=6c distinct squares. This new upper bound is obtained
by investigating the combinatorial structure of double squares and showing that a string of
length n contains at most b5n=6c double squares. In addition, the established structural
properties provide a novel proof of Fraenkel and Simpson's result. Joint work with Antoine
Deza and Adrien Thierry.