you're reading...

SACT seminar: The d-step conjecture for runs verified

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

Location: SIT 459

Speaker: Prof. Frantisek Franek, McMaster University

Title: The d-step conjecture for runs verified


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.



No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

Enter your email address to subscribe to receive notifications of new announcements by email.

Join 68 other followers

%d bloggers like this: