Séminaire CAESAR
de combinatoire additive
Séance du 16 mai 2013
(11 heures, UPMC Jussieu, couloir 15-25, salle 101):
Maria AXENOVICH
(Université de Karlruhe, Allemagne)
A regularity lemma and twins in words
For a word S, let f(S) be the largest integer m such that there
are two disjoint identical (scattered) subwords of length m.
Let f(n; G) = min{f(S) : S is of length n; over alphabet G}.
We show that 2f(n; {0; 1}) = n- o(n) using the regularity
lemma for words. In other words, any binary word of length n
can be split into two identical subwords (referred to as twins) and,
perhaps, a remaining subword of length o(n). We prove a similar
result for k identical subwords of a word over an alphabet with at
most k letters. Joint work with Y. Person and S. Puzynina.
Retour à la page d'accueil du
séminaire