solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看14895次
Constructing sparse Davenport-Schinzel sequences by hypergraph edge coloring. (arXiv:1810.07175v1 [math.CO])
来源于:arXiv
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. 查看全文>>