Formations and generalized Davenport-Schinzel sequences

Abstract

Let $up(r,t)=(a_1{a}_2\dots a_r{)}^t$. We investigate the problem of determining the maximum possible integer $n(r,t)$ for which there exist $2t-1$ permutations ${\pi }_1,{\pi }_2,\dots ,{\pi }_{2t-1}$ of $1,2,\dots ,n(r,t)$ such that the concatenated sequence ${\pi }_1{\pi }_2\dots {\pi }_{2t-1}$ has no subsequence isomorphic to $up(r,t)$. This quantity has been used to obtain an upper bound on the maximum number of edges in $k$-quasiplanar graphs. It was proved by (Geneson, Prasad, and Tidor, Electronic Journal of Combinatorics, 2014) that $n(r,t)\le (r-1{)}^{2^{2t-2}}$. We prove that $n(r,t)=\Theta (r^{\left(\genfrac{}{}{0ex}{}{2t-1}{t}\right)})$, where the constant in the bound depends only on $t$. Using our upper bound in the case $t=2$, we also sharpen an upper bound of (Klazar, Integers, 2002), who proved that $Ex(up(r,2),n)<(2n+1)L$ where $L=Ex(up(r,2),K-1)+1$, $K=(r-1{)}^4+1$, and $Ex(u,n)$ denotes the extremal function for forbidden generalized Davenport-Schinzel sequences. We prove that $K=(r-1{)}^4+1$ in Klazar's bound can be replaced with $K=(r-1)\left(\genfrac{}{}{0ex}{}{r}{2}\right)+1$. We also prove a conjecture from (Geneson, Prasad, and Tidor, Electronic Journal of Combinatorics, 2014) by showing for $t\ge 1$ that $Ex(abc(acb{)}^{t}abc,n)=n{2}^{\frac{1}{t!}\alpha (n{)}^t\pm O(\alpha (n{)}^{t-1})}$. In addition, we prove that $Ex(abcacb(abc{)}^{t}acb,n)=n{2}^{\frac{1}{(t+1)!}\alpha (n{)}^{t+1}\pm O(\alpha (n{)}^t)}$ for all $t\ge 1$.

References in corpus (5)

• Improved bounds and new techniques for Davenport-Schinzel sequences and their generalizations
• Tight bounds on the maximum size of a set of permutations with bounded VC-dimension
• Longest Common Subsequences in Sets of Permutations
• Sequences of formation width $4$ and alternation length $5$
• An algorithm for bounding extremal functions of forbidden sequences

Cited by in corpus (1)

• An algorithm for bounding extremal functions of forbidden sequences