Bounding sequence extremal functions with formations

zbMATH Open1300.05012arXiv1308.3810MaRDI QIDQ405315FDOQ405315

Authors: Rohil Prasad, Jonathan Tidor, Jesse Geneson Edit this on Wikidata

Publication date: 4 September 2014

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: An $(r,s)$-formation is a concatenation of $s$ permutations of $r$ letters. If $u$ is a sequence with $r$ distinct letters, then let $mathitEx(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 $mathitfw(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 $mathitfw(u)$ to prove upper bounds on $mathitEx(u,n)$ for sequences $u$ such that $u$ contains an alternation with the same formation width as $u$. We generalize Nivasch's bounds on $mathitEx((ab{)}^t,n)$ by showing that $mathitfw((12ldotsl{)}^t)=2t-1$ and $mathitEx((12ldotsl{)}^t,n)=n{2}^{frac1(t-2)!alpha(n{)}^{t-2}pmO(alpha(n{)}^{t-3})}$ for every $lgeq2$ and $tgeq3$, such that $alpha(n)$ denotes the inverse Ackermann function. Upper bounds on $mathitEx((12ldotsl{)}^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 $ava{v}^{\prime }a$ such that $a$ is a letter, $v$ is a nonempty sequence excluding $a$ with no repeated letters and $v^{\prime }$ is obtained from $v$ by only moving the first letter of $v$ to another place in $v$, then we show that $mathitfw(u)=4$ and $mathitEx(u,n)=Theta(nalpha(n))$. Furthermore we prove that $mathitfw(abc(acb{)}^t)=2t+1$ and $mathitEx(abc(acb{)}^t,n)=n{2}^{frac1(t-1)!alpha(n{)}^{t-1}pmO(alpha(n{)}^{t-2})}$ for every $tgeq2$.

Full work available at URL: https://arxiv.org/abs/1308.3810

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Extremal functions for sequences
• Bounds for some minimizing sequences of functionals
• scientific article; zbMATH DE number 427792
• A linear upper bound in extremal theory of sequences
• Sharp bounds on formation-free sequences
• scientific article; zbMATH DE number 3921172
• scientific article; zbMATH DE number 825186
• Some inequalities between functionals on bounded sequences
• Extremal bounds for functions of bounded turning
• Constructive Bounded Sequences and Lipschitz Functions

zbMATH Keywords

permutationsformationsgeneralized Davenport-Schinzel sequencesinverse Ackermann function

Mathematics Subject Classification ID

Permutations, words, matrices (05A05)

Cites Work

• Title not available (Why is that?)
• The number of edges in \(k\)-quasi-planar graphs
• Improved bounds and new techniques for Davenport-Schinzel sequences and their generalizations
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Combinatorial Problem Connected with Differential Equations
• Improved bound for the union of fat triangles
• On the structure and composition of forbidden sequences, with geometric applications
• Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences

Cited In (7)

• Three generalizations of Davenport-Schinzel sequences
• Title not available (Why is that?)
• Title not available (Why is that?)
• Constructing sparse Davenport-Schinzel sequences
• Sharp bounds on formation-free sequences
• Forbidden formations in multidimensional 0-1 matrices
• Sequence saturation

This page was built for publication: Bounding sequence extremal functions with formations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q405315)