## Constructing sparse Davenport-Schinzel sequences by hypergraph edge coloring. (arXiv:1810.07175v1 [math.CO])

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 &gt; 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 &gt; 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.查看全文

## Solidot 文章翻译

 你的名字 留空匿名提交 你的Email或网站 用户可以联系你 标题 简单描述 内容 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.
﻿