Clique supersaturation conjecture for Ks,tK_{s,t} when rsr\le s

Let Ks,tK_{s,t} be the complete bipartite graph with parts of sizes ss and tt, let KrK_r be the complete graph on rr vertices, and let N(F,G)\mathcal{N}(F,G) denote the number of copies of FF in GG. The Ks,tK_{s,t} clique supersaturation conjecture. If 2rst2\le r\le s\le t, then there exists a constant k0k_0 such that every nn-vertex graph GG satisfying N(Kr,G)=knr(r2)/s\mathcal{N}(K_r,G)=k n^{r-\binom{r}{2}/s} and kk0k\ge k_0 also satisfies

N(Ks,t,G)kst/(r2)nso(1).\mathcal{N}(K_{s,t},G)\ge k^{st/\binom{r}{2}} n^{s-o(1)}.

The conjecture asserts that, in the range rsr\le s, every graph with the prescribed number of KrK_r copies contains at least as many Ks,tK_{s,t} copies as the corresponding random-graph heuristic predicts. The source notes that the case r=2r=2 follows from a proposition, making r=s=3r=s=3 the next open case.

Sources & referencesView supporting material

Primary source

Quentin Dubroff, Benjamin Gunby, Bhargav Narayanan and Sam Spiro, “Clique Supersaturation”, arXiv:2312.08265 (2023).

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.