Constructing sparse Davenport-Schinzel sequences by hypergraph edge coloring
share
A sequence is called r-sparse if every contiguous subsequence of length r has no repeated letters. A DS(n, s)-sequence is a 2-sparse sequence with n distinct letters that avoids alternations of length s+2. Pettie and Wellman (2018) asked whether there exist r-sparse DS(n, s)-sequences of length Ω(s n^2) for s ≥ n and r > 2, which would generalize a result of Roselle and Stanton (1971) for the case r = 2. We construct r-sparse DS(n, s)-sequences of length Ω(s n^2) for s ≥ n and r > 2. Our construction uses linear hypergraph edge-coloring bounds. We also use the construction to generalize a result of Pettie and Wellman by proving that if s = Ω(n^1/t (t-1)!), then there are r-sparse DS(n, s)-sequences of length Ω(n^2 s / (t-1)!) for all r ≥ 2. In addition, we find related results about the lengths of sequences avoiding (r, s)-formations.
READ FULL TEXT