Extremal problems on ordered and convex geometric hypergraphs

An ordered hypergraph is a hypergraph whose vertex set is linearly ordered, and a convex geometric hypergraph is a hypergraph whose vertex set is cyclically ordered. Extremal problems for ordered and convex geometric graphs have a rich history with applications to a variety of problems in combinatorial geometry. In this paper, we consider analogous extremal problems for uniform hypergraphs, and discover a general partitioning phenomenon which allows us to determine the order of magnitude of the extremal function for various ordered and convex geometric hypergraphs. A special case is the ordered $n$-vertex $r$-graph $F$ consisting of two disjoint sets $e$ and $f$ whose vertices alternate in the ordering. We show that for all $n\ge 2r+1$, the maximum number of edges in an ordered $n$-vertex $r$-graph not containing $F$ is exactly $$\left(\genfrac{}{}{0px}{}{n}{r}\right)-\left(\genfrac{}{}{0px}{}{n-r}{r}\right)\mathrm{.}$$ This could be considered as an ordered version of the Erd\H{o}s-Ko-Rado Theorem, and generalizes earlier results of Capoyleas and Pach and Aronov-Dujmovi\v{c}-Morin-Ooms-da Silveira.