Skip to content
Preprint

Circular flows and bisections of random regular graphs

Nov 2026 · 0 citations · 15 references
Mathematics

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.

View source

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.