Improved bounds on maximum sets of letters in sequences with forbidden alternations

Abstract

Let $A_{s,k}(m)$ be the maximum number of distinct letters in any sequence which can be partitioned into $m$ contiguous blocks of pairwise distinct letters, has at least $k$ occurrences of every letter, and has no subsequence forming an alternation of length $s$. Nivasch (2010) proved that $A_{5,2d+1}(m)=\theta (m{\alpha }_d(m))$ for all fixed $d\ge 2$. We show that $A_{s+1,s}(m)=\left(\genfrac{}{}{0ex}{}{m-\lceil \frac{s}{2}\rceil }{\lfloor \frac{s}{2}\rfloor }\right)$ for all $s\ge 2$, $A_{5,6}(m)=\theta (m\log \log m)$, and $A_{5,2d+2}(m)=\theta (m{\alpha }_d(m))$ for all fixed $d\ge 3$.

10 pages

References in corpus (1)

• Tight bounds on the maximum size of a set of permutations with bounded VC-dimension