{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T16:43:49Z","timestamp":1753893829102,"version":"3.41.2"},"reference-count":0,"publisher":"The Electronic Journal of Combinatorics","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electron. J. Combin."],"abstract":"<jats:p>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 \\ldots l)^{t})=2t-1$ and $\\mathit{Ex}((12\\ldots 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 \\ldots 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$.<\/jats:p>","DOI":"10.37236\/3663","type":"journal-article","created":{"date-parts":[[2020,1,10]],"date-time":"2020-01-10T19:56:33Z","timestamp":1578686193000},"source":"Crossref","is-referenced-by-count":4,"title":["Bounding Sequence Extremal Functions with Formations"],"prefix":"10.37236","volume":"21","author":[{"given":"Jesse","family":"Geneson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rohil","family":"Prasad","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jonathan","family":"Tidor","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"23455","published-online":{"date-parts":[[2014,8,13]]},"container-title":["The Electronic Journal of Combinatorics"],"original-title":[],"link":[{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v21i3p24\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v21i3p24\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,17]],"date-time":"2020-01-17T05:49:39Z","timestamp":1579240179000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v21i3p24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,8,13]]},"references-count":0,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2014,7,3]]}},"URL":"https:\/\/doi.org\/10.37236\/3663","relation":{},"ISSN":["1077-8926"],"issn-type":[{"type":"electronic","value":"1077-8926"}],"subject":[],"published":{"date-parts":[[2014,8,13]]},"article-number":"P3.24"}}