Combinatorial Theory

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\).

Mathematics Subject Classifications: 05C65, 05C80, 05D05, 05D40

Keywords: Hypergraph, Sidorenko Conjecture, Random Turán Problem