Bounding sequence extremal functions with formations

An (r, s)-formation is a concatenation of s permutations of r letters. If u is a sequence with r distinct letters, then let 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 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 fw(u) to prove upper bounds on Ex(u,n) for sequences u such that u contains an alternation with the same formation width as u. Upper bounds on Ex((12... 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 avav'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 fw(u) = 4 and Ex(u,n) = Θ(nα(n)). Furthermore we prove that fw(abc(acb)^t) = 2t + 1 and for every t ≥ 2.