The paper tackles two related problems in graph theory involving random regular graphs, which are networks where every node has exactly the same number of connections. The first problem concerns "circular flows," a concept measuring how smoothly you can assign directed traffic along the edges of a graph. A smaller circular flow number means the graph has a more balanced and flexible flow structure. The authors prove that a randomly chosen regular graph almost certainly has a very small circular flow number, confirming and strengthening a decades-old conjecture by Jaeger. Jaeger predicted that sufficiently well-connected graphs always admit orientations where traffic is balanced in a precise modular arithmetic sense, and the authors show this holds not just for specific graphs but overwhelmingly for random ones.
The second problem concerns "bisections," which means splitting a graph's nodes into two equal groups while trying to maximize or minimize the number of edges that cross between the two groups. The authors establish tight bounds on how well you can bisect a random regular graph, connecting this to the flow problem. Specifically, they prove a conjecture by Greenhill, Isaev, and Lewis stating that the difficulty of orienting a graph's edges in a balanced way is almost entirely explained by how the graph can be bisected: the two quantities differ by at most one, with high probability. This bridges two seemingly different optimization problems in a clean and precise way.
The technical approach combines probabilistic methods with tools from the theory of network flows and graph orientations. A key ingredient is a uniform estimate showing that dense bisections of random regular graphs concentrate tightly around predictable values. The results are largely sharp, meaning the bounds proved are close to the best possible. Some questions remain open, particularly for low-degree graphs, such as whether the circular flow number of a random 5-regular or 7-regular graph can be pushed below certain thresholds. These gaps point to genuine mathematical obstacles rather than limitations of the methods used.