Minimal hypergraph non-jumps

Abstract

An $r$-uniform hypergraph, or $r$-graph, has density $|E(G)|/|V(G{)}^{(r)}|$. We say $\hat{I}\pm$ is a jump for $r$-graphs if there is some constant $\hat{I}´=\hat{I}´(\hat{I}\pm )$ such that, for each $\epsilon >0$ and $n\ge r$, any sufficiently large $r$-graph of density at least $\epsilon$ has a subgraph of order $n$ and density at least $\hat{I}\pm +\hat{I}´$. For $r=2$, all $\hat{I}\pm$ are jumps. For $r\ge 3$, Erdős showed all $[0,\frac{r!}{r^r})$ are jumps, and conjectured all $[0,1)$ are jumps. Since then, a variety of non-jumps have been proved, using a method introduced by Frankl and Rödl. Our aim in this paper is to provide a general setting for this method. As an application, we give several new non-jumps, which are smaller than any previously known. We also demonstrate that these are the smallest the current method can prove.

16 pages, 1 figure, 1 table