Alon–Krivelevich–Sudakov conjecture for K_{s,t}-free graphs

Let GG be a graph with mm edges, and let sp(G)=mc(G)m/2\mathrm{sp}(G)=\mathrm{mc}(G)-m/2 denote its surplus, where mc(G)\mathrm{mc}(G) is the number of edges in a largest bipartite subgraph of GG. For integers ts2t\ge s\ge2, let Ks,tK_{s,t} be the complete bipartite graph with parts of sizes ss and tt, and let sp(m,Ks,t)\mathrm{sp}(m,K_{s,t}) be the smallest surplus among all Ks,tK_{s,t}-free graphs with mm edges. Alon–Krivelevich–Sudakov conjecture. For all ts2t\ge s\ge2 and all mm,

sp(m,Ks,t)=Ω(m34+18s4).\mathrm{sp}(m,K_{s,t})=\Omega\left(m^{\frac34+\frac{1}{8s-4}}\right).

This is a special case of the general surplus conjecture for forbidden graphs. The source presents it as open and discusses bounds for this family.

Sources & referencesView supporting material

Primary source

Jinghua Deng, Jianfeng Hou, Siwei Lin and Qinghou Zeng, “MaxCut in graphs with sparse neighborhoods”, arXiv:2307.09309 (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.