A relationship between generalized Davenport-Schinzel sequences and interval chains
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[subscript 0],a[subscript 1]][a[subscript 1...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
European Mathematical Information Service (EMIS)
2016
|
| Online Access: | http://hdl.handle.net/1721.1/100752 |
| _version_ | 1826212946417549312 |
|---|---|
| author | Geneson, Jesse |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Geneson, Jesse |
| author_sort | Geneson, Jesse |
| collection | MIT |
| description | 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[subscript 0],a[subscript 1]][a[subscript 1] + 1,a[subscript 2]]…[a[subscript k−1] + 1,a[subscript k]] for integers 1 ≤ a[subscript 0] ≤ a[subscript 1] <…< a[subscript k] ≤ 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 ≥ 1 and 1 ≤ s ≤ k ≤ 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[subscript 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. Nivasch (2010) proved that D[subscript 5,2d+1](m) = Θ(mα[subscript d](m)) for all fixed d ≥ 2. We show that D[subscript s+1,s](m) = ([m - [s/2] over [s/2]]) for all s ≥ 2. We also prove new lower bounds which imply that D[subscript 5,6](m) = Θ(mloglogm) and D[subscript 5,2d+2](m) = Θ(mαd(m)) for all fixed d ≥ 3. |
| first_indexed | 2024-09-23T15:40:40Z |
| format | Article |
| id | mit-1721.1/100752 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T15:40:40Z |
| publishDate | 2016 |
| publisher | European Mathematical Information Service (EMIS) |
| record_format | dspace |
| spelling | mit-1721.1/1007522022-09-29T15:27:46Z A relationship between generalized Davenport-Schinzel sequences and interval chains Geneson, Jesse Massachusetts Institute of Technology. Department of Mathematics Geneson, Jesse 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[subscript 0],a[subscript 1]][a[subscript 1] + 1,a[subscript 2]]…[a[subscript k−1] + 1,a[subscript k]] for integers 1 ≤ a[subscript 0] ≤ a[subscript 1] <…< a[subscript k] ≤ 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 ≥ 1 and 1 ≤ s ≤ k ≤ 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[subscript 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. Nivasch (2010) proved that D[subscript 5,2d+1](m) = Θ(mα[subscript d](m)) for all fixed d ≥ 2. We show that D[subscript s+1,s](m) = ([m - [s/2] over [s/2]]) for all s ≥ 2. We also prove new lower bounds which imply that D[subscript 5,6](m) = Θ(mloglogm) and D[subscript 5,2d+2](m) = Θ(mαd(m)) for all fixed d ≥ 3. National Science Foundation (U.S.). Graduate Research Fellowship (Grant 1122374) 2016-01-07T16:35:46Z 2016-01-07T16:35:46Z 2015-08 2014-10 Article http://purl.org/eprint/type/JournalArticle 1077-8926 http://hdl.handle.net/1721.1/100752 Geneson, Jesse. "A relationship between generalized Davenport-Schinzel sequences and interval chains." Electronic Journal of Combinatorics 22(3) (August 2015). en_US http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i3p19 Electronic Journal of Combinatorics Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf European Mathematical Information Service (EMIS) European Mathematical Information Service (EMIS) |
| spellingShingle | Geneson, Jesse A relationship between generalized Davenport-Schinzel sequences and interval chains |
| title | A relationship between generalized Davenport-Schinzel sequences and interval chains |
| title_full | A relationship between generalized Davenport-Schinzel sequences and interval chains |
| title_fullStr | A relationship between generalized Davenport-Schinzel sequences and interval chains |
| title_full_unstemmed | A relationship between generalized Davenport-Schinzel sequences and interval chains |
| title_short | A relationship between generalized Davenport-Schinzel sequences and interval chains |
| title_sort | relationship between generalized davenport schinzel sequences and interval chains |
| url | http://hdl.handle.net/1721.1/100752 |
| work_keys_str_mv | AT genesonjesse arelationshipbetweengeneralizeddavenportschinzelsequencesandintervalchains AT genesonjesse relationshipbetweengeneralizeddavenportschinzelsequencesandintervalchains |