Andrew Baker, Antonie Deza and Frantisek Franek
A Parameterized Formulation for the Maximum Number of Runs Problem
Abstract: |
A parameterized approach to the problem of the maximum number of runs in a string was introduced by Deza and Franek. In the approach referred to as the d-step approach, in addition to the usual parameter the length of the string, the size of the string's alphabet is considered. The behaviour of the function ρ_{d}(n), the maximum number of runs over all strings of length n with exactly d distinct symbols, can be handily expressed in the terms of properties of a table referred to as the (d, n - d) table in which ρ_{d}(n) is the entry at the dth row and (n - d)th column. The approach leads to a conjectured upper bound ρ_{d}(n) ≤ n - d for 2 ≤ d ≤ n. The parameterized formulation shows that the maximum within any column of the (d, n - d) table is achieved on the main diagonal, i.e. for n = 2d, and motivates the investigation of the structural properties of the run-maximal strings of length n bounded by a constant times the size of the alphabet d. We show that ρ_{d}(n) = ρ_{n - d}(2n - 2d) for 2 ≤ d ≤ n < 2d, ρ_{d}(2d) ≤ ρ_{d - 1}(2d - 1) + 1 for d > 3, ρ_{d - 1}(2d - 1) = ρ_{d - 2}(2d - 2) = ρ_{d - 3}(2d - 3) for d ≥ 5, and {ρ_{d}(n) ≤ n - d for 2 ≤ d ≤ n} ↔ {ρ_{d}(9d) ≤ 8d for d ≥ 2}. The results allow for an efficient computational verification of entries in the (d, n - d) table for higher values of n and point to a plausible way of either proving the maximum number of runs conjecture by showing that possible counter-examples on the main diagonal would exhibit an impossible structure, or to discover an unexpected counter-example on the main diagonal of the (d, n - d) table. This approach provides a purely analytical proof of ρ_{d}(2d) = d for d ≤ 15 and, using the computational results of ρ_{2}(d + 2) for d = 16, …, 23, a proof of ρ_{d}(2d) = d for d ≤ 23. |
Download paper: | |||
PostScript | BibTeX reference |
Download presentation: |