Sidorenko Hypergraphs and Random Turán Numbers

Abstract

Let $\mathrm{ex}(G_{n,p}^r,F)$ denote the maximum number of edges in an $F$-free subgraph of the random $r$-uniform hypergraph $G_{n,p}^r$, and let $s(F):=\sup \{s:\exists H,t_F(H)=t_{K_r^r}(H{)}^{s+e(F)}>0\}$. Following recent work of Conlon, Lee, and Sidorenko, we prove non-trivial lower bounds on $\mathrm{ex}(G_{n,p}^r,F)$ whenever $s(F)>0$, i.e. $F$ is not Sidorenko. This connection between Sidorenko's conjecture and random Turán problems gives new lower bounds on $\mathrm{ex}(G_{n,p}^r,F)$ whenever $s(F)>0$, and further allows us to establish upper bounds for $s(F)$ whenever upper bounds for $\mathrm{ex}(G_{n,p}^r,F)$ are known. As a consequence, we prove that $s({\mathrm{E}}^r(K_{k+1}^k))=\frac{1}{r-k}$ where ${\mathrm{E}}^r(K_{k+1}^k)$ is the $r$-expansion of $K_{k+1}^k$.

18 pages (+2 page Appendix), 1 figure