Bounding sequence extremal functions with formations (Q405315): Difference between revisions

Summary: An \((r, s)\)-formation is a concatenation of \(s\) permutations of \(r\) letters. If \(u\) is a sequence with \(r\) distinct letters, then let \(\mathit{Ex}(u, n)\) be the maximum length of any \(r\)-sparse sequence with \(n\) distinct letters which has no subsequence isomorphic to \(u\). For every sequence \(u\) define \(\mathit{fw}(u)\), the formation width of \(u\), to be the minimum \(s\) for which there exists \(r\) such that there is a subsequence isomorphic to \(u\) in every \((r, s)\)-formation. We use \(\mathit{fw}(u)\) to prove upper bounds on \(\mathit{Ex}(u, n)\) for sequences \(u\) such that \(u\) contains an alternation with the same formation width as \(u\).{ }We generalize Nivasch's bounds on \(\mathit{Ex}((ab)^{t}, n)\) by showing that \(\mathit{fw}((12\dots l)^{t})=2t-1\) and \(\mathit{Ex}((12\dots l)^{t}, n) =n2^{\frac{1}{(t-2)!}\alpha(n)^{t-2}\pm O(\alpha(n)^{t-3})}\) for every \(l \geq 2\) and \(t\geq 3\), such that \(\alpha(n)\) denotes the inverse Ackermann function. Upper bounds on \(\mathit{Ex}((12\dots l)^{t} , n)\) have been used in other papers to bound the maximum number of edges in \(k\)-quasiplanar graphs on \(n\) vertices with no pair of edges intersecting in more than \(O(1)\) points.{ }If \(u\) is any sequence of the form \(a v a v' a\) such that \(a\) is a letter, \(v\) is a nonempty sequence excluding \(a\) with no repeated letters and \(v'\) is obtained from \(v\) by only moving the first letter of \(v\) to another place in \(v\), then we show that \(\mathit{fw}(u)=4\) and \(\mathit{Ex}(u, n) =\Theta(n\alpha(n))\). Furthermore we prove that \(\mathit{fw}(abc(acb)^{t})=2t+1\) and \(\mathit{Ex}(abc(acb)^{t}, n) = n2^{\frac{1}{(t-1)!}\alpha(n)^{t-1}\pm O(\alpha(n)^{t-2})}\) for every \(t\geq 2\).