no. 11 · Monday 9 November 2026
Circular flows and bisections of random regular graphs
Abstract
For every fixed odd $d\ge5$, we prove that the circular flow number of a uniformly random simple $d$-regular graph is asymptotically almost surely less than $2+4/(d-1)-\varepsilon_d$ for an explicit constant $\varepsilon_d>0$. At degree five the upper bound is $3-1/24006$. At degree seven it is $21/8$, answering a question of Li and Li. For every fixed $p\ge1$, we also obtain a strongly connected Jaeger orientation at degree $4p+1$, with outdegrees in $\{p,3p+1\}$. At large degrees we count dense bisections together with sets that violate their cut inequalities. This gives flow intervals of length $O(d^{-2})$ above the maximum-bisection lower bound of Li and Li. The finite-degree estimates, together with the large-degree transfer, also prove the conjecture of Greenhill, Isaev and Lewis that the threshold for orientations with outdegrees in $\{p,d-p\}$ exceeds the corresponding bisection threshold by at most one.
- comments
- 55 pages, Conjecture 7.1 in version 1 (positive gaps for circular flow number of random 5- and 7-regular graphs)is now proved, and Conjecture 7.1 is replaced with a new conjecture
- fields
- Combinatorics, Probability