Supersaturation conjecture for clique counts in Kr+1K_{r+1}-free graphs

At least 7 years old · documented by

Let r≥s≥3r\geq s\geq 3, let ϵ>0\epsilon>0, and let GG be a graph with m=e(G)m=e(G) edges. Write k⁡s(G)\operatorname{k}_s(G) for the number of copies of KsK_s in GG. Supersaturation conjecture. There exist δ>0\delta>0 and m0m_0 such that, whenever m≥m0m\geq m_0 and

k⁡s(G)≥mex⁡Ks(m,Kr+1)+ϵms/2,\operatorname{k}_s(G)\geq \operatorname{mex}_{K_s}(m,K_{r+1})+\epsilon m^{s/2},

then GG contains at least δm(r+1)/2\delta m^{(r+1)/2} copies of Kr+1K_{r+1}. This predicts a quantitative supersaturation phenomenon: exceeding the extremal KsK_s count for Kr+1K_{r+1}-free graphs by a term of order ms/2m^{s/2} forces many copies of Kr+1K_{r+1}; the supplied text gives no resolution status.

References

Primary source

Jamie Radcliffe and Andrew Uzzell, “Stability and Erdős–Stone type results for F-free graphs with a fixed number of edges”, arXiv:1810.04746 (2018).

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.