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 $\Omega(s n^{2})$ for $s \geq 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 $\Omega(s n^{2})$ for $s \geq 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 = \Omega(n^{1/t} (t-1)!)$, then there are $r$-sparse $DS(n, s)$-sequences of length $\Omega(n^{2} s / (t-1)!)$ for all $r \geq 2$. In addition, we find related results about the lengths of sequences avoiding $(r, s)$-formations. 查看全文>>