One-unit bisection-gap conjecture of Greenhill, Isaev and Lewis
For every fixed integer , let be a uniformly random simple -regular graph on an even number of vertices. Let denote the maximum number of edges crossing a bisection of , and let be the least integer for which has an orientation whose outdegree at every vertex belongs to . The one-unit bisection-gap conjecture asserts that, with probability tending to as , exceeds the lower bound forced by the maximum bisection by at most one; equivalently, up to the relevant integer rounding.
References
- Circular flows and bisections of random regular graphs — arXiv — Amir Jafari
Source: arXiv
Progress summary
A 2026 preprint claims to prove the conjecture for every fixed regular degree, but the proof has not been independently verified.
The conjecture predicts a one-unit upper gap relating graph bisections to constrained orientations across fixed regular degrees. On April 24, 2026, Catherine Greenhill, Mikhail Isaev, and Charles Lewis submitted a preprint claiming the result.
April 2026 claimed proof
The preprint claims the conjectured upper gap for every fixed regular degree and derives related orientation and bisection estimates for random regular graphs. Its broader results include asymptotic orientation thresholds, but the proof is unrefereed and no independent mathematical assessment was found.
Current status (as of November 2026): the conjecture has a claimed proof in an unrefereed preprint, but its resolution remains unverified.
Solutions 0
No solutions have been posted yet.