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≥9, there is εd>0 such that its circular flow number is less than 2+4/(d−1)−ε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≥3, the typical minimum parameter for orientations with outdegrees in {p,d−p} exceeds the threshold forced by the maximum bisection by at most one.
Related
- Regular Graphs Without Isomorphic Bisections
- Circular regular dessins with underlying graphs bf K2e,2f(2d): the metacyclic case
- Edge universality of random regular graphs of growing degrees
- When are random regular triangle-free graphs bipartite?
- Analysis of Polynomial Threshold Functions on Random Regular Graphs: Computational Complexity of Detecting Noisy Random Lifts
BibTeX
@misc{jafari2026circular,
title = {{Circular flows and bisections of random regular graphs}},
author = {Amir Jafari},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.03763},
eprint = {2611.03763},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.03763},
}
RIS
TY - UNPB
TI - Circular flows and bisections of random regular graphs
AU - Amir Jafari
PY - 2026
DA - 2026/11/02
PB - arXiv
DO - 10.48550/arxiv.2611.03763
UR - https://arxiv.org/abs/2611.03763
AB - 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≥9, there is ε_d>0 such that its circular flow number is less than 2+4/(d−1)−ε_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≥3, the typical minimum parameter for orientations with outdegrees in {p,d−p} exceeds the threshold forced by the maximum bisection by at most one.
ER -