Räty–Sudakov–Tomon surplus conjecture for graphs far from clique unions
Räty–Sudakov–Tomon surplus conjecture for graphs far from clique unions
Let be a regular graph on vertices, with max-cut surplus . Say that is -far from a graph if no graph isomorphic to can be obtained from by adding or removing at most edges.
Räty–Sudakov–Tomon conjecture. For any , there exists a such that, if is -far from every disjoint union of cliques, then
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.