Bounding sequence extremal functions with formations (Q405315)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Bounding sequence extremal functions with formations |
scientific article |
Statements
Bounding sequence extremal functions with formations (English)
0 references
4 September 2014
0 references
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\).
0 references
formations
0 references
generalized Davenport-Schinzel sequences
0 references
inverse Ackermann function
0 references
permutations
0 references
0 references