A relationship between generalized Davenport-Schinzel sequences and interval chains (Q2517665)

Summary: Let an \((r, s)\)-formation be a concatenation of \(s\) permutations of \(r\) distinct letters, and let a block of a sequence be a subsequence of consecutive distinct letters. A \(k\)-chain on \([1, m]\) is a sequence of \(k\) consecutive, disjoint, nonempty intervals of the form \([a_{0}, a_{1}] [a_{1}+1, a_{2}]\dots[a_{k-1}+1, a_{k}]\) for integers \(1 \leq a_{0} \leq a_{1} <\dots< a_{k} \leq m\), and an \(s\)-tuple is a set of \(s\) distinct integers. An \(s\)-tuple stabs an interval chain if each element of the \(s\)-tuple is in a different interval of the chain. \textit{N. Alon} et al. [in: Proceedings of the nineteenth annual ACM-SIAM symposium on discrete algorithms, San Francisco, CA, January 20--22, 2008. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM). 1194--1203 (2008; Zbl 1192.68812)] observed similarities between bounds for interval chains and Davenport-Schinzel sequences, but did not identify the cause. We show for all \(r \geq 1\) and \(1 \leq s \leq k \leq m\) that the maximum number of distinct letters in any sequence \(S\) on \(m+1\) blocks avoiding every \((r, s+1)\)-formation such that every letter in \(S\) occurs at least \(k+1\) times is the same as the maximum size of a collection \(X\) of (not necessarily distinct) \(k\)-chains on \([1, m]\) so that there do not exist \(r\) elements of \(X\) all stabbed by the same \(s\)-tuple. Let \(D_{s,k}(m)\) be the maximum number of distinct letters in any sequence which can be partitioned into \(m\) blocks, has at least \(k\) occurrences of every letter, and has no subsequence forming an alternation of length \(s\). \textit{G. Nivasch} [J. ACM 57, No. 3, Article No. 17, 44 p. (2014)] proved that \(D_{5, 2d+1}(m) = \Theta( m \alpha_{d}(m))\) for all fixed \(d \geq 2\). We show that \(D_{s+1, s}(m) = \binom{m- \lceil \frac{s}{2} \rceil}{\lfloor \frac{s}{2} \rfloor}\) for all \(s \geq 2\). We also prove new lower bounds which imply that \(D_{5, 6}(m) = \Theta(m \log \log m)\) and \(D_{5, 2d+2}(m) = \Theta(m \alpha_{d}(m))\) for all fixed \(d \geq 3\).