The feasible region of hypergraphs

Abstract

Let $\mathcal{F}$ be a family of $r$-uniform hypergraphs. The feasible region $\Omega (\mathcal{F})$ of $\mathcal{F}$ is the set of points $(x,y)$ in the unit square such that there exists a sequence of $\mathcal{F}$-free $r$-uniform hypergraphs whose edge density approaches $x$ and whose shadow density approaches $y$. The feasible region provides a lot of combinatorial information, for example, the supremum of $y$ over all $(x,y)\in \Omega (\mathcal{F})$ is the Turán density $\pi (\mathcal{F})$, and $\Omega (\varnothing )$ gives the Kruskal-Katona theorem. We undertake a systematic study of $\Omega (\mathcal{F})$, and prove that $\Omega (\mathcal{F})$ is completely determined by a left-continuous almost everywhere differentiable function; and moreover, there exists an $\mathcal{F}$ for which this function is not continuous. We also extend some old related theorems. For example, we generalize a result of Fisher and Ryan to hypergraphs and extend a classical result of Bollobás by almost completely determining the feasible region for cancellative triple systems.

Minor changes in page 2 and page 3 and Lemma 5.3

References in corpus (2)

• The Clique Density Theorem
• New Short Proofs to Some Stability Theorems