2016/10/30 by Julian Wellman, Seth Pettie, Wellman, Julian +1
Computer Science · Engineering · Mathematics · #Coding theory and cryptography #cs.CG #cs.DM #graph theory and CDMA systems #math.CO #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1610.09774
arxiv created 2016/10/31 · arxiv updated 2016/11/01
An order-s Davenport-Schinzel sequence over an n-letter alphabet is one avoiding immediate repetitions and alternating subsequences with length s+2. The main problem is to determine the maximum length of such a sequence, as a function of n and s. When s is fixed this problem has been settled but when s is a function of n, very little is known about the extremal function λ(s,n) of such sequences. In this paper we give a new recursive construction of Davenport-Schinzel sequences that is based on dense 0-1 matrices avoiding large all-1 submatrices (aka Zarankiewicz's Problem.) In particular, we give a simple construction of n2/t × n matrices containing n1+1/t 1s that avoid t× 2 all-1 submatrices. Our lower bounds on λ(s,n) exhibit three qualitatively different behaviors depending on the size of s relative to n. When s ≤ loglog n we show that λ(s,n)/n ≥ 2s grows exponentially with s. When s = no(1) we show λ(s,n)/n ≥ ((s)/(2loglogs n))loglogs n grows faster than any polynomial in s. Finally, when s=Ω(n1/t(t-1)!), λ(s,n) = Ω(n2 s/(t-1)!) matches the trivial upper bound O(n2s) asymptotically, whenever t is constant.