Time: 2:00pm Tuesday, 31st March.

Location: SIT 459

Speaker: Prof. Frantisek Franek, McMaster University

Title: The d-step conjecture for runs verified

Abstract:

In 1999 Kolpakov & Kucherov showed that the maximum number of runs in a string is linear in the length of the string. A run is a maximal repetition. They posited a so-called runs conjecture that the upper bound should be at most the length of the string, i.e. that ρ = max{r(x) : |x| = n} ≤ n, where r(x) denotes the number of runs in a string x.

Many researchers, including the speaker, since investigated the problem and several progressively closer asymptotic lower and upper bounds were achieved. In 2012, Deza and Franek proposed a d-step approach and conjectured that ρd(n) = max{r(x) : |x| = n and x has exactly d distinct symbols} ≤ n−d for any 2 ≤ d ≤ n. In 2015, Bannai et al. proved the runs conjecture giving a universal upper bound of ρ(n) ≤ n−2. Refining their method, we proved the d-step conjecture showing some interesting structural properties of run-maximal strings.

### Like this:

Like Loading...

*Related*

## Discussion

## No comments yet.