# On a conjecture by Eriksson concerning overlap in strings

Cakir, I; Chryssaphinou, O; Månsson, M (1999). On a conjecture by Eriksson concerning overlap in strings. Combinatorics, Probability & Computing, 8(5):429-440.

## Abstract

Consider a finite alphabet Ω and strings consisting of elements from Ω. For a given string w, let cor(w) denote the autocorrelation, which can be seen as a measure of the amount of overlap in w. Furthermore, let aw(n) be the number of strings of length n that do not contain w as a substring. Eriksson [4] stated the following conjecture: if cor(w)>cor(w′), then aw(n)>aw′(n) from the first n where equality no longer holds. We prove that this is true if [mid R:]Ω[mid R:][gt-or-equal, slanted]3, by giving a lower bound for aw(n)−aw′(n).

## Abstract

Consider a finite alphabet Ω and strings consisting of elements from Ω. For a given string w, let cor(w) denote the autocorrelation, which can be seen as a measure of the amount of overlap in w. Furthermore, let aw(n) be the number of strings of length n that do not contain w as a substring. Eriksson [4] stated the following conjecture: if cor(w)>cor(w′), then aw(n)>aw′(n) from the first n where equality no longer holds. We prove that this is true if [mid R:]Ω[mid R:][gt-or-equal, slanted]3, by giving a lower bound for aw(n)−aw′(n).

## Statistics

### Citations

3 citations in Web of Science®
4 citations in Scopus®