Random Turán Theorem for the Fano Plane

Abstract

Let $F$ denote the Fano plane, the $3$-uniform hypergraph with $7$ vertices and $7$ edges. Frankl and Füredi, and independently Keevash and Sudakov, proved that the largest $F$-free subhypergraph of $K_n^{(3)}$ is bipartite. In this paper, we determine the sharp threshold for this property in the random setting. We show that for $\hat{p}={\Theta }_F\cdot n^{-2/3}{\left(\log n\right)}^{1/6}$, where ${\Theta }_F$ is an explicit constant depending on $F$, we have: (i) if $(1+\epsilon )\hat{p}\le p=o(1)$, then with high probability every largest $F$-free subhypergraph of $G_{n,p}^{(3)}$ is bipartite; and (ii) if $\frac{1}{n^2}\ll p\le (1-\epsilon )\hat{p}$, then with high probability every largest $F$-free subhypergraph of $G_{n,p}^{(3)}$ is not bipartite. To the best of our knowledge, this work provides the first sharp threshold result obtained for a Turán-type problem in random hypergraphs.

51 pages, 3 figures