{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T16:44:13Z","timestamp":1753893853679,"version":"3.41.2"},"reference-count":0,"publisher":"The Electronic Journal of Combinatorics","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electron. J. Combin."],"abstract":"<jats:p>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}] \\ldots [a_{k-1}+1, a_{k}]$ for integers $1 \\leq a_{0} \\leq a_{1} &lt; \\ldots &lt; 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. Alon et al. (2008) 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$\u00a0 blocks, has at least $k$ occurrences of every letter, and has no subsequence forming an alternation of length $s$. Nivasch (2010) 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$. <\/jats:p>","DOI":"10.37236\/4768","type":"journal-article","created":{"date-parts":[[2020,1,10]],"date-time":"2020-01-10T10:26:43Z","timestamp":1578652003000},"source":"Crossref","is-referenced-by-count":4,"title":["A Relationship Between Generalized Davenport-Schinzel Sequences and Interval Chains"],"prefix":"10.37236","volume":"22","author":[{"given":"Jesse","family":"Geneson","sequence":"first","affiliation":[]}],"member":"23455","published-online":{"date-parts":[[2015,8,14]]},"container-title":["The Electronic Journal of Combinatorics"],"original-title":[],"link":[{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v22i3p19\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v22i3p19\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,17]],"date-time":"2020-01-17T05:13:44Z","timestamp":1579238024000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v22i3p19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,8,14]]},"references-count":0,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2015,7,1]]}},"URL":"https:\/\/doi.org\/10.37236\/4768","relation":{},"ISSN":["1077-8926"],"issn-type":[{"type":"electronic","value":"1077-8926"}],"subject":[],"published":{"date-parts":[[2015,8,14]]},"article-number":"P3.19"}}