Räty–Sudakov–Tomon surplus conjecture for graphs far from clique unions

Let GG be a regular graph on nn vertices, with max-cut surplus sp(G)\mathsf{sp}(G). Say that GG is ϵ\epsilon-far from a graph HH if no graph isomorphic to HH can be obtained from GG by adding or removing at most ϵV(G)2\epsilon |V(G)|^2 edges.

Räty–Sudakov–Tomon conjecture. For any ϵ>0\epsilon>0, there exists a c>0c>0 such that, if GG is ϵ\epsilon-far from every disjoint union of cliques, then

sp(G)cn5/4.\mathsf{sp}(G) \geq c n^{5/4}.

This conjecture predicts a polynomial improvement over Edwards' bound for regular graphs that are far from the natural low-surplus examples. The supplied text gives no resolution; the cited work establishes a related lower bound with a logarithmic loss in a restricted very dense regular setting.

Sources & referencesView supporting material

Primary source

Shengtong Zhang, “An Alon-Boppana–type bound for very dense graphs, with applications to max-cut”, arXiv:2507.10037 (2025).

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.