pith. sign in

arxiv: 2604.22219 · v1 · submitted 2026-04-24 · 🧮 math.CO

Jaeger-type orientations of random regular graphs

Catherine Greenhill , Mikhail Isaev , Charles Lewis This is my paper

Pith reviewed 2026-05-08 11:16 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C8005C20
keywords random regular graphsp-orientationsJaeger's conjecturesmall subgraph conditioningconfiguration modelgraph orientationsregular graphs
0
0 comments X

The pith

Random d-regular graphs have a p-orientation with high probability for several (d,p) pairs including Jaeger's cases.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that for certain pairs of d and p, a randomly selected d-regular graph almost surely possesses a p-orientation, meaning an assignment of directions to edges so that every vertex ends up with either in-degree p or out-degree p. This covers the specific cases p=3 and p=4 from Jaeger's conjecture, for which d equals 13 and 17, even though the conjecture fails to hold for every possible graph. The authors obtain the result by applying the small subgraph conditioning method inside the configuration model that generates uniform random d-regular graphs. They also identify some other (d,p) pairs where the high-probability existence fails, using a connection to the maximum size of a bisection in the graph.

Core claim

Working in the configuration model, the probability that a random d-regular graph admits a p-orientation tends to one as the number of vertices grows, for the listed values of d and p. This includes the p=3 and p=4 cases of Jaeger's conjecture, where d=4p+1, even though deterministic counterexamples exist. The small subgraph conditioning method is used to establish the result, while some negative cases follow from relating the absence of p-orientations to small maximum bisections.

What carries the argument

The small subgraph conditioning method applied to the property of possessing a p-orientation in the configuration model of random d-regular graphs.

If this is right

  • Almost every 13-regular graph admits a 3-orientation.
  • Almost every 17-regular graph admits a 4-orientation.
  • The same high-probability existence holds for additional (d,p) pairs beyond Jaeger's conjecture.
  • For some other (d,p) values the property fails with high probability because the maximum bisection is too small.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Counterexamples to Jaeger's conjecture must be atypical among all regular graphs of the given degree.
  • The link to bisection size indicates that p-orientability is controlled by how well the graph can be partitioned into two equal sets.
  • The conditioning technique could be tested on further orientation variants or on other degree sequences.

Load-bearing premise

The small subgraph conditioning method applies directly to the property of possessing a p-orientation in the configuration model for random d-regular graphs.

What would settle it

An explicit computation for one of the claimed (d,p) pairs showing that the proportion of d-regular graphs with a p-orientation stays bounded away from 1 for large n.

read the original abstract

We consider $p$-orientations, which are defined to be orientations of $d$-regular graphs such that every vertex either has in-degree $p$ or out-degree $p$. These generalise the orientations considered in Jaeger's conjecture, where $d=4p+1$. Working with random $d$-regular graphs using the small subgraph conditioning method, we prove that a $d$-regular graph has a $p$-orientation with high probability for several values of $(d,p)$, including the $p=3,4$ cases of Jaeger's conjecture (known to be deterministically false). Some negative results are obtained by exploiting a connection with maximum bisection size.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript proves that a random d-regular graph admits a p-orientation with high probability for several pairs (d,p), including the p=3 and p=4 cases of Jaeger's conjecture (known to be false for all graphs). The proof applies the small subgraph conditioning method to the configuration model; negative results are obtained by relating non-existence of p-orientations to the maximum bisection size.

Significance. If the calculations hold, the work supplies probabilistic existence results for an orientation property that fails deterministically, thereby illustrating the difference between worst-case and typical-case behavior in regular graphs. The explicit use of small subgraph conditioning (with the requisite first- and second-moment analysis after conditioning on short cycles) and the bisection link for negative statements are clear strengths. The paper contributes a concrete application of an established technique to a natural generalization of Jaeger's problem.

minor comments (3)
  1. [§2] §2: the precise list of (d,p) pairs for which the positive result is proved should be collected in a single table or enumerated statement rather than scattered through the text.
  2. [§3] The notation for the configuration model and the cycle counts used in conditioning is standard but would benefit from a short reminder of the exact probability space in the opening paragraph of §3.
  3. [Figure 1] Figure 1 (or the corresponding table) comparing bisection sizes could include a brief caption explaining how the plotted quantity directly implies the non-existence of a p-orientation.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of our manuscript, including the recognition of the significance of our probabilistic existence results for p-orientations in random d-regular graphs and the application of small subgraph conditioning to cases of Jaeger's conjecture. The report correctly notes the use of the configuration model and the link to maximum bisection size for negative results. As no specific major comments were raised, we have no point-by-point rebuttals to provide.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The derivation applies the small subgraph conditioning method to the configuration model of random d-regular graphs to establish that the number of p-orientations has expectation tending to infinity and concentrates positively after conditioning on short cycles. This is a direct moment calculation on the random graph model for the target property; no parameter is fitted to data and then renamed as a prediction, no definition equates the orientation count to itself, and no load-bearing step reduces to a self-citation whose content is unverified or imported by ansatz. The method is an external probabilistic tool whose applicability is checked explicitly for the chosen (d,p) pairs, rendering the central claim independent of its inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the applicability of the small subgraph conditioning method to the p-orientation property and on standard properties of the configuration model for random regular graphs.

axioms (1)
  • domain assumption Small subgraph conditioning applies to the property of having a p-orientation in random d-regular graphs.
    The paper invokes this method to obtain the high-probability statements.

pith-pipeline@v0.9.0 · 5402 in / 1215 out tokens · 68355 ms · 2026-05-08T11:16:31.931536+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

28 extracted references · 28 canonical work pages

  1. [1]

    Aigner and G.M

    M. Aigner and G.M. Ziegler.Proofs from THE BOOK, 6th ed. Springer, Berlin, 2018

    work page 2018

  2. [2]

    Alon and P

    N. Alon and P. Pra lat. Modular orientations of random and quasi-random regular graphs. Combinatorics, Probability and Computing20(2011), 231–329

    work page 2011

  3. [3]

    Bender and E

    E. Bender and E. Canfield. The asymptotic number of non-negative integer matrices with given row and column sums.Journal of Combinatorial Theory, Series A24(1978), 296–307. 25

    work page 1978

  4. [4]

    Bollob´ as

    B. Bollob´ as. A probabilistic proof of an asymptotic formula for the number of labelled regular graphs.European Journal of Combinatorics1(1980), 311–316

    work page 1980

  5. [5]

    Bollob´ as

    B. Bollob´ as. The isoperimetric number of random regular graphs.European Journal of Combinatorics9(1988), 241–244

    work page 1988

  6. [6]

    Bondy and U

    A. Bondy and U. Murty.Graph Theory, 1st ed. Graduate Texts in Mathematics. Springer London, 2008

    work page 2008

  7. [7]

    Coja-Oghlan, P

    A. Coja-Oghlan, P. Loick, B. F. Mezei, and G. B. Sorkin. The Ising antiferromagnet and Max Cut on random regular graphs.SIAM Journal on Discrete Mathematics36(2022), 1306–1342

    work page 2022

  8. [8]

    Delcourt, C

    M. Delcourt, C. Greenhill, M. Isaev, B. Lidick´ y, and L. Postle. Decomposing random regular graphs into stars.European Journal of Combinatorics130(2025), 104216

    work page 2025

  9. [9]

    Delcourt, R

    M. Delcourt, R. Huq, and P. Pra lat. Almost all 9-regular graphs have a modulo-5 orientation.Electronic Journal of Combinatorics32(2)(2025), #P2.22

    work page 2025

  10. [10]

    Gerencs´ er and V

    B. Gerencs´ er and V. Harangi. Boosted second moment method in random regular graphs. Preprint, 2025.arXiv:2510.12600

    work page arXiv 2025

  11. [11]

    Greenhill, S

    C. Greenhill, S. Janson, and A. Ruci´ nski. On the number of perfect matchings in random lifts.Combinatorics, Probability and Computing19(2010), 791–817

    work page 2010

  12. [12]

    M. Han, J. Li, Y. Wu, and C. Zhang. Counterexamples to Jaeger’s circular flow conjec- ture.Journal of Combinatorial Theory, Series B131(2018), 1–11

    work page 2018

  13. [13]

    V. Harangi. Star decompositions and independent sets in random regular graphs. Preprint, 2025.arXiv:2503.09458

    work page arXiv 2025

  14. [14]

    V. Harangi. Star decompositions via orientations. Preprint, 2025.arXiv:2506.05194

    work page arXiv 2025

  15. [15]

    V. Harangi. RSB bounds on the maximum cut. Preprint, 2025.arXiv:2506.21296

    work page arXiv 2025

  16. [16]

    F. Jaeger. Nowhere-zero flow problems. InSelected Topics in Graph Theory(L. Beineke et al., eds), vol.3, Academic Press, London, 1988, pp. 91–95

    work page 1988

  17. [17]

    S. Janson. Random regular graphs: Asymptotic distributions and contiguity.Combina- torics, Probability and Computing4(1995), 369–405

    work page 1995

  18. [18]

    Kim and N

    J.-H. Kim and N. C. Wormald, Random matchings which induce Hamilton cycles, and Hamiltonian decompositions of random regular graphs,Journal of Combinatorial Theory, Series B81(2001), 20–44

    work page 2001

  19. [19]

    H.-J. Lai, Y. Shao, H. Wu and J. Zhou. On mod (2p+ 1)-orientations of graphs.Journal of Combinatorial Theory, Series B99(2009), 399–406. 26

    work page 2009

  20. [20]

    Meyer.Matrix Analysis and Applied Linear Algebra

    C. Meyer.Matrix Analysis and Applied Linear Algebra. Society for Industrial and Applied Mathematics, Philadelphia, 2000

    work page 2000

  21. [21]

    Pra lat and N

    P. Pra lat and N. Wormald. Almost all 5-regular graphs have a 3-flow.Journal of Graph Theory93(2020), 147–156

    work page 2020

  22. [22]

    R. W. Robinson and N.C. Wormald. Almost all cubic graphs are hamiltonian.Random Structures & Algorithms3(1992), 117–125

    work page 1992

  23. [23]

    R. W. Robinson and N.C. Wormald. Almost all regular graphs are hamiltonian.Random Structures & Algorithms5(1994), 363–374

    work page 1994

  24. [24]

    B. L. van der Waerden.Algebra, vol. I. Springer, New York, 2003

    work page 2003

  25. [25]

    N. C. Wormald. The asymptotic connectivity of labelled regular graphs.Journal of Combinatorial Theory (Series B)31(1981), 156–167

    work page 1981

  26. [26]

    Wormald.Models of Random Regular Graphs, vol

    N. Wormald.Models of Random Regular Graphs, vol. 267 ofLondon Mathematical Society Lecture Note Series. Cambridge University Press, Cambridge, 1999, pp. 239–298. A Second moment calculations The goal of this appendix is to prove Lemma 4.4. Sinceφis differentiable on the interior of K, it is enough to show that (I) The only critical point ofφon the interio...

    work page 1999

  27. [27]

    This proves the following criterion

    =−f(w 0) = 0, that is, 1/w 0 is a root offon the interval (1,∞). This proves the following criterion. Lemma A.1.The functionφhas a unique critical point on the interior ofKif and only if the polynomialfhas no root on the interval(1,∞). It is straightforward to verify this criterion in any particular case from (3). For instance, if the Taylor expansion off...

    work page 1956

  28. [28]

    Case (d, p) = (17,4)

    However, 21.9072≈˜φ 25 9 + 1 9 < φ(z ∗)≈21.9499. Case (d, p) = (17,4). In this case,g(x) = 207060x 4 +2598960x 3 +1856400x 2 −16336320x− 15315300, and by Descartes’ Rule of Signs, it has a unique positive rootx ∗ which lies in the interval [7/3,5/2]. We have θ1(x) θ(x) = 4x(x3 + 39x2 + 234x+ 286) x4 + 52x3 + 468x2 + 1144x+ 715 , − ˜A′ = 52(x6 + 36x5 + 666...

    work page 1992