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

About 3 years old · traced to

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 t≥s≥2t\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 t≥s≥2t\ge s\ge2 and all mm,

sp(m,Ks,t)=Ω(m34+18s−4).\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.

References

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.