Räty–Sudakov–Tomon bisection-width conjecture

The conjecture concerns the largest possible bisection width of dense regular graphs. A September 2026 preprint by Oliver Janzer, István Tomon, and Fredy Yip claims the sharp dense-regime deficit and presents it as resolving the conjecture.

Known results

• Räty, Sudakov, and Tomon proved positive-discrepancy lower bounds of order $\Omega(\sqrt{d}\,n)$ for $d\le n^{2/3}$, $\Omega(n^2/d)$ for $n^{2/3}\le d\le n^{4/5}$, and $\Omega(d^{1/4}n/\log n)$ up to the dense range.
• For regular graphs with $n^{3/4}<d\le (1/2-\varepsilon)n$, they proved $\operatorname{disc}^{+}(G)=\Omega_{\varepsilon}(d^{1/3}n)$, while identifying the matching bisection-width behavior as conjectural.

September 2026 claimed resolution

The new preprint claims that every $d$-regular $n$-vertex graph with $d\le (1-\varepsilon)n/2$ has bisection width at most $dn/4-\Omega_{\varepsilon}(d^{1/3}n)$, with optimal order in the dense regime. No independent verification, referee report, or error assessment was found.

Current status (as of September 2026): The dense-regime bound is claimed in a new preprint but remains unverified; the conjecture is not independently established.