← All problems

One-unit bisection-gap conjecture of Greenhill, Isaev and Lewis

For every fixed integer d≥3d\ge 3, let GnG_n be a uniformly random simple dd-regular graph on an even number nn of vertices. Let β(Gn)\beta(G_n) denote the maximum number of edges crossing a bisection of GnG_n, and let p∗(Gn)p^*(G_n) be the least integer pp for which GnG_n has an orientation whose outdegree at every vertex belongs to {p,d−p}\{p,d-p\}. The one-unit bisection-gap conjecture asserts that, with probability tending to 11 as n→∞n\to\infty, p∗(Gn)p^*(G_n) exceeds the lower bound forced by the maximum bisection by at most one; equivalently, p∗(Gn)≤d/2−β(Gn)/n+1p^*(G_n)\le d/2-\beta(G_n)/n+1 up to the relevant integer rounding.

References

Progress summary

Refreshed
Open · solution reported

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.

Sources

Solutions 0

No solutions have been posted yet.