A regularity lemma and twins in words

Details A regularity lemma and twins in words A regularity lemma and twins in words

2012-04-10

arxiv.org/abs/1204.2180v1

Mathematics

Combinatorics

Scientific paper

For a word $S$, let $f(S)$ be the largest integer $m$ such that there are two disjoints identical (scattered) subwords of length $m$. Let $f(n, \Sigma) = \min \{f(S): S \text{is of length} n, \text{over alphabet} \Sigma \}$. Here, it is shown that \[2f(n, \{0,1\}) = n-o(n)\] using the regularity lemma for words. I.e., 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)$. A similar result is proven for $k$ identical subwords of a word over an alphabet with at most $k$ letters.

Affiliated with

Also associated with

No associations

Rating

A regularity lemma and twins in words does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A regularity lemma and twins in words, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A regularity lemma and twins in words will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-645435