Random hypergraph removal conjecture

Let Kk+1(k)K_{k+1}^{(k)} be the complete kk-uniform hypergraph on k+1k+1 vertices. Let HH be the random kk-uniform hypergraph on nn vertices obtained by selecting each kk-edge independently with probability pp.

Random hypergraph removal conjecture. For every δ>0\delta>0 and every integer k3k\geq 3, there exist constants ϵ>0\epsilon>0 and CC such that, if pCn1/kp\geq Cn^{-1/k}, then with probability tending to 11 as nn\to\infty, every subgraph of HH containing at most ϵpk+1nk+1\epsilon p^{k+1}n^{k+1} copies of Kk+1(k)K_{k+1}^{(k)} may be made Kk+1(k)K_{k+1}^{(k)}-free by removing at most δpnk\delta pn^k edges.

This is the random analogue of the hypergraph removal lemma, whose dense form implies Szemerédi's theorem. The statement is known for k=3k=3 but remains open for general kk.

Sources & referencesView supporting material

Primary source

D. Conlon and W. T. Gowers, “Combinatorial theorems in sparse random sets”, arXiv:1011.4310 (2015).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.