Extremal problems for ordered (hyper)graphs: applications of Davenport–Schinzel sequences

NEW

Problem: Let $G_1$ be the ordered graph on vertices $1<2<3<4<5$ with edges

For a simple ordered hypergraph $H$, write $H\succ G_1$ if there are vertices $x_1<\cdots <x_5$ of $H$ and four distinct hyperedges containing respectively

Then

Klazar’s Open Problem 3.4 asks for the asymptotic order of $\operatorname{ex}_e(G_1,n)$.

Result:

The lower bound follows from the ordered graph extremal function:

For the upper bound, let $H$ be a $G_1$-free simple ordered hypergraph on at most $n$ vertices. Call a pair $\{x,y\}$ heavy if it is contained in at least $4=e(G_1)$ hyperedges of $H$, and light otherwise.

Let $G_h$ be the graph of heavy pairs. If $G_h$ contained $G_1$, then each of its four required pairs would lie in at least four hyperedges, so we could choose four distinct hyperedges greedily, giving $H\succ G_1$, contradiction. Thus $G_h$ is $G_1$-free.

Hyperedges all of whose pairs are heavy are cliques of $G_h$. In any $G_1$-free ordered graph $G$, every edge $a<b$ has at most two common neighbors to the right of $b$; otherwise $a<b<c<d<e$ gives $G_1$. Hence $G$ has at most $2e(G)$ triangles and at most $e(G)$ copies of $K_4$, and no $K_5$. Therefore the number of non-singleton cliques in $G_h$ is $O(e(G_h))=O(\operatorname{gex}(G_1,n))$.

For every remaining hyperedge choose one light pair inside it. The graph $G_\ell$ formed by these chosen pairs is also $G_1$-free; otherwise the four chosen pairs of a $G_1$-copy would come from four distinct hyperedges of $H$. Since each light pair lies in at most three hyperedges,

Adding at most $n$ singleton hyperedges gives

Together with the lower bound, this proves $\operatorname{ex}_e(G_1,n)=\Theta(n\log n)$.

Verification audit: the proof uses exactly Klazar’s ordered containment relation; hyperedges are simple; extra vertices in hyperedges are allowed; the four witnessing hyperedges are explicitly distinct; and the only external input is the known ordered graph bound $\operatorname{gex}(G_1,n)=\Theta(n\log n)$.

Citation: Klazar, “Extremal problems for ordered (hyper)graphs: applications of Davenport–Schinzel sequences,” arXiv:math/0305037, Open Problem 3.4.
Füredi; Füredi–Hajnal: $\operatorname{gex}(G_1,n)=\Theta(n\log n)$, as cited in Klazar, Theorem 3.3.