Circular flows and bisections of random regular graphs

Abstract

Jaeger conjectured that, for every positive integer $p$, every $4p$-edge-connected graph admits an orientation with congruent indegree and outdegree modulo $2p+1$. We prove a stronger probabilistic counterpart: a uniformly random simple $(4p+1)$-regular graph has a strongly connected orientation with all outdegrees in $\{p,3p+1\}$ with probability tending to one as its even order grows. More generally, for every fixed odd $d\ge9$, there is $\varepsilon_d>0$ such that its circular flow number is less than $2+4/(d-1)-\varepsilon_d$ with probability tending to one. We give explicit margins at the small degrees and prove the bound $91/33$ at degree seven, answering a fixed-upper-bound question of Li and Li. Gaps below $3$ at degree five and below $8/3$ at degree seven remain open. A uniform estimate for dense bisections also gives short intervals above the Li–Li maximum-bisection lower bound. Finally, we prove the one-unit bisection-gap conjecture of Greenhill, Isaev and Lewis: at every fixed degree $d\ge3$, the typical minimum parameter for orientations with outdegrees in $\{p,d-p\}$ exceeds the threshold forced by the maximum bisection by at most one.