Hypergraphs do jump

Abstract

We say that $\alpha \in [0,1)$ is a jump for an integer $r\ge 2$ if there exists $c(\alpha )>0$ such that for all $\epsilon >0$ and all $t\ge 1$ any $r$-graph with $n\ge n_0(\alpha ,\epsilon ,t)$ vertices and density at least $\alpha +\epsilon$ contains a subgraph on $t$ vertices of density at least $\alpha +c$. The Erd\H os--Stone--Simonovits theorem implies that for $r=2$ every $\alpha \in [0,1)$ is a jump. Erd\H os showed that for all $r\ge 3$, every $\alpha \in [0,r!/r^r)$ is a jump. Moreover he made his famous "jumping constant conjecture" that for all $r\ge 3$, every $\alpha \in [0,1)$ is a jump. Frankl and Rödl disproved this conjecture by giving a sequence of values of non-jumps for all $r\ge 3$. We use Razborov's flag algebra method to show that jumps exist for $r=3$ in the interval $[2/9,1)$. These are the first examples of jumps for any $r\ge 3$ in the interval $[r!/r^r,1)$. To be precise we show that for $r=3$ every $\alpha \in [0.2299,0.2316)$ is a jump. We also give an improved upper bound for the Turán density of $K_4^{-}=\{123,124,134\}$: $\pi (K_4^{-})\le 0.2871$. This in turn implies that for $r=3$ every $\alpha \in [0.2871,8/27)$ is a jump.

11 pages, 1 figure, 42 page appendix of C++ code. Revised version including new Corollary 2.3 thanks to an observation of Dhruv Mubayi