Leírás
An {\it ordered r-graph} is an $r$-uniform hypergraph whose vertex set
is linearly ordered.
An $r$-uniform hypergraph whose vertex set is {\it cyclically} ordered
is frequently called a {\it convex geometric $r$-graph} because its
vertex set can conveniently be represented by the vertex set of a
convex polygon.
Extremal problems for ordered and cyclically ordered graphs have a rich history.
We consider extremal problems for different types of paths and
matchings in ordered and cyclically ordered $r$-graphs.
We prove bounds on Tur\'an numbers for these configurations; some of
them are exact. Our theorem on
zigzag paths in cyclic $r$-graphs is a common generalization of early
results of Hopf and Pannwitz, Sutherland, Kupitz and Perles for cyclic
graphs. It also yields the current best bound for the extremal problem
for tight paths in uniform hypergraphs. There are interesting
similarities and differences between the ordered setting and the
convex geometric setting.
One of our tools is a partition theorem:
Let $H$ be a cyclically ordered $r$-graph, with cyclic ordering $<$ on
the vertices.
Let $v(H) = \bigl|\bigcup_{e \in H} e\bigr|$ and $d(H) = e(H)/v(H)^{r
- 1}$ denote the {\em codegree density} of $H$.
The cyclically ordered $G$ is a {\em split $r$-graph} if there exists
a partition of $V(G)$ into cyclic intervals $X_1 < X_2 < \dots < X_{r
- 1}< X_1$ such that for some $i \in [r - 1]$, every edge $e$ of $G$
has two vertices in $X_i$ and one vertex in every $X_j : j \neq i$.
\begin{thm}\label{splitter}
For every $r\geq 3$ there exists $c \ge r^{-5r^2}$ such that every
cyclically ordered $r$-graph $H$ contains a split subgraph $G$ with
$d(G) \geq c\,d(H)$.
\end{thm}
This is joint work with Tao Jiang, Alexander Kostochka, Dhruv Mubayi
and Jacques Verstra\"ete.