Asymptotic enumeration of orientations of a graph as a function of the out-degree sequence

Brendan D. McKay; Mikhail Isaev; Tejas Iyer

Asymptotic enumeration of orientations of a graph as a function of the out-degree sequence

T0 review · 0 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Counting orientations with a prescribed imbalance sequence now reaches sparse graphs, via a saddle-point formula built from Bradley-Terry paired-comparison merits.

desk verdict A genuine extension to sparse orientations with explicit error bounds; the load-bearing step is the quoted integration theorem, which looks sound but is the place to check. read the letter →

arxiv 1908.01309 v2 pith:DBLCI7RB submitted 2019-08-04 math.CO math.PR

Mikhail Isaev , Tejas Iyer , Brendan D. McKay This is my paper · ORCID

classification math.COmath.PR MSC 05C3005A1605C20

keywords orientationsofgraphsimbalancesequencescoreasymptoticenumerationsaddlepointmethodBradley-TerrymodelCheegerconstantEulerian

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper proves an asymptotic formula for the number of ways to orient the edges of an undirected graph so that each vertex has a prescribed out-degree minus in-degree. The formula applies to graphs whose average degree is at least $n^{1/3+\varepsilon}$ and that are strongly mixing, with target imbalances not too large. This matters because the same count includes tournaments with a given score sequence, Eulerian orientations, and bipartite graphs with a fixed degree sequence, and earlier formulas stopped at dense graphs. The proof evaluates a product generating function by the saddle-point method, choosing the contour radii from the balance equations of the Bradley-Terry paired-comparisons model.

What carries the argument

The machinery is the saddle-point evaluation of the coefficient integral $N(G,b)=(2\pi i)^{-n}\oint\cdots\oint\prod_{jk\in E(G)}(x_j/x_k+x_k/x_j)\,dx_1\cdots dx_n/(x_1^{b_1+1}\cdots x_n^{b_n+1})$. The contours are chosen as circles $x_j=r_j^{1/2}e^{i\theta_j}$, where $r$ solves the Bradley-Terry balance equations $\sum_{k\sim j}(r_j-r_k)/(r_j+r_k)=b_j$, so the radii put the contour at the saddle point. The asymptotic evaluation then rests on four objects from equation (4): the product $P(G,b)$, the positive-definite matrix $A$ whose quadratic form is a weighted edge sum, the cumulant corrections $f_3,f_4,f_6$ built from $\lambda_{jk}=r_j/(r_j+r_k)$, and the normal random vector $X$ with density proportional to $e^{-x^TAx}$. Bounding the integral away from the saddle region uses the Cheeger constant and short-path arguments.

What would settle it

Take a family of graphs satisfying the average-degree and Cheeger conditions (for example, random regular graphs with degree $\Delta=n^{2/3}$) and choose a target imbalance sequence with one large spike just beyond the Theorem 4 threshold but still achievable by some orientation. Compute the exact number of orientations by exhaustive search for $n\le 20$ and compare each count with the leading term and predicted error of the formula; any sequence for which the ratio fails to approach 1 would refute the claimed range.

Watch

Extended reading notes

Core claim

The central discovery is an explicit asymptotic formula for $N(G,b)$, the number of orientations of a graph $G$ with imbalance sequence $b$: under assumptions on the average degree, the Cheeger constant, and the solution of the balance equations, $N(G,b)$ equals $\pi^{-(n-1)/2} P(G,b)^{-1} \Delta^{1/2} n^{1/2} |A|^{-1/2} \exp(\psi(G,b) + O(R^3\Delta^{-3/2+\varepsilon/2}n + \Delta^{-3+\varepsilon}n))$. Here $P(G,b)$ is the probability that a random orientation with Bradley-Terry parameters $r$ produces a particular orientation with imbalance $b$, and the prefactor is the inverse square root of the weighted spanning-tree sum of $G$. The result extends earlier dense-graph enumeration to average degree $n^{1/3+\varepsilon}$ and gives an explicit error term, making the formula usable for estimating subdigraph probabilities in random orientations with a fixed imbalance sequence.

Load-bearing premise

The enumeration formula stands on two structural assumptions: the graph's Cheeger constant must be at least a fixed fraction of the maximum degree, and the balance equations must have a solution whose neighbouring ratios $r_j/r_k$ stay within $1+O(1)$ with the required decay; if either fails, the saddle-point and error-term arguments do not go through.

Editorial extensions

If this is right

For Eulerian orientations ($b=0$), the formula reduces to an explicit asymptotic count $2^{|E(G)|+(n-1)/2}\pi^{-(n-1)/2}\kappa(G)^{-1/2}\exp(-\frac14\sum_{jk\in E(G)}(d_j^{-1}+d_k^{-1})^2)$ with a small relative error, valid for graphs with even degrees, average degree at least $n^{1/3+\varepsilon}$, and Cheeger constant at least $\gamma\Delta$.
The probability that a random Eulerian orientation of $G$ contains a fixed Eulerian subdigraph $\vec H$ is asymptotically $2^{-m}\prod_j(1-h_j/d_j)^{-1/2}$, with an explicit error, whenever the residual graph $G\setminus H$ still satisfies the mixing condition.
The expected number of directed Hamiltonian cycles in a random Eulerian orientation of $G$ is $2^{-n+1}N_H\exp(\sum_j d_j^{-1}+o(1))$, where $N_H$ is the number of Hamiltonian cycles of $G$.
The theorem provides a general route to subdigraph occurrence probabilities for arbitrary imbalance sequences whenever both the numerator and denominator in the probability ratio satisfy the theorem's conditions.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The explicit error term suggests the method may tolerate average degrees below $n^{1/3+\varepsilon}$; what the calculation actually needs is for the final error terms to vanish, and the current $\Delta\ge n^{1/3+\varepsilon}$ threshold is where the quoted bounds close.
A testable extension is to push the spike-heavy regime: Theorem 4's condition is sufficient, not necessary, so imbalance sequences with a few large entries may still satisfy assumption A3 and fall inside the formula even when $\|b\|_\infty$ is large.
Because $P(G,b)$ is the Bradley-Terry probability of a single orientation, the theorem gives a practical sampling recipe: generate orientations from the tilted independent-edge model and reweight or reject, which should produce uniform orientations with fixed imbalance when the theorem's conditions hold.
In the bipartite case the formula counts $0$--$1$ matrices with prescribed margins and a fixed zero pattern; the same saddle-point machinery may extend to other linear constraint sets, such as contingency tables with structural zeros.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Here's my take on arXiv:1908.01309. The paper genuinely extends asymptotic enumeration of orientations to graphs with average degree as low as n^{1/3+ε}, with arbitrary imbalance sequences, not just Eulerian or dense. That's a real step beyond the tournament/dense case, and the formula in Theorem 1 is explicit enough to be usable. The proof is long but it is honest work: every lemma either gets a proof in the appendix or a precise quotation, and the main computation is a saddle-point expansion that routes through the authors' own integration theorem [12, Thm 4.4]. I have no reason to think that theorem is wrong, and the stress-test checked the hypotheses; but it's the one part I'd want a referee to double-check rather than take on faith.

What impressed me: the balance equations for the Bradley-Terry model are taken seriously as the saddle-point condition, and the paper includes a clean characterization of when they have a solution (Lemma 6 and Theorem 7 via max-flow/min-cut and entropy). The new bounds for the MLE ratios in Theorem 4 are a genuine add-on. The error terms are explicit, and the subdigraph application section is a nice demonstration, even if it's only carried out for Eulerian orientations.

Soft spots, in proportion. The theorem is conditional on A3, which requires the Bradley-Terry solution to have bounded ratios on edges. Theorem 4 gives a sufficient condition, not a necessary one, so imbalance sequences with occasional spikes can fall outside. That's not a hidden flaw—the paper states it honestly—but it narrows the range of application more than the abstract suggests. Second, the dependence on [12] means the paper doesn't stand fully alone. If [12, Thm 4.4] has any hidden edge case, the main result would need revisiting. I haven't verified every hypothesis by hand; the stress-test did and reports they are satisfied. Third, the error bounds are a bit of a thicket with ε and R, but that's normal for this genus.

Who's it for: enumerative and probabilistic combinatorics people working on orientations, 0-1 matrices with fixed margins, or Bradley-Terry models. It deserves a serious referee; I'd send it to review rather than desk reject. If I worked in the area I'd cite it.

Referee Report

0 major / 5 minor

Summary. The paper proves an asymptotic formula (Theorem 1) for the number N(G,b) of orientations of an n-vertex graph G with a prescribed imbalance sequence b, under assumptions A1 (maximum degree Δ ≥ n^{1/3+ε}), A2 (Cheeger constant h(G) ≥ γΔ), and A3 (the Bradley-Terry balance equations (2) have a solution r with r_j/r_k ≤ 1+R on edges, with R satisfying the stated o(log n) condition). The formula expresses N(G,b) as an explicit product involving a normalizing factor P(G,b), a determinant/spanning-tree factor Δ^{1/2} n^{1/2} |A|^{-1/2}, and an exponential containing the cumulant correction ψ(G,b), with explicit error terms. The proof uses Cauchy's integral formula, a saddle-point expansion (Lemma 15, quoting Theorem 32 from [12]), and a geometric/spectral analysis of the integral away from the saddle region. The paper also proves existence/uniqueness and ratio bounds for solutions of the balance equations (Theorem 7, Lemma 8, Theorem 4), derives a corollary for Eulerian orientations (Corollary 3), and applies the method to estimate the probability that a random Eulerian orientation contains a fixed Eulerian subdigraph (Theorem 24, Corollary 25).

Significance. Assuming the quoted saddle-point theorem is sound, the result is a substantial advance: it unifies and extends earlier enumeration results for tournaments and dense Eulerian orientations from Δ=Ω(n) to graphs with degree as low as n^{1/3+ε} under a strong mixing assumption, and it gives explicit corrections rather than only leading asymptotics. The paper is notably honest: A3 is stated as an assumption with a sufficient condition in Theorem 4, no free parameters are fitted, and all nonstandard technical lemmas are either proved in the appendix or quoted from published work. The application to subdigraph occurrences and the new bounds for Bradley-Terry maximum likelihood estimators are useful by-products. The main residual risk is the delegation of the core saddle-point expansion to the external [12, Theorem 4.4]; the hypotheses are checked in the text and I did not find a gap, but the central formula inherits the exact correctness of that theorem.

minor comments (5)

[§1, after Eq. (5), and §3.1, end of Lemma 15] The assertion that R^3 Δ^{-3/2+ε/2} n = O(n^{-1/2+ε}) does not follow from A3 in general. For example, when Δ=n^{1/3+ε}, A3 allows R=o(n^{-1/3+ε/2}), which gives R^3 Δ^{-3/2+ε/2} n = o(n^{-1/6-ε/3+ε^2/2}), not O(n^{-1/2+ε}). The error term is still o(1), so the theorem is unaffected, but the stated bound should be corrected.
[§2, Proof of Theorem 4] The summation index in 'Since ∑_{j=0}^n b_j = 0' should run from 1 to n, not from 0 to n.
[Abstract and Theorem 1] The abstract says the graph has average degrees at least n^{1/3+ε}, while Theorem 1 assumes the maximum degree Δ satisfies A1. Since the maximum degree is at least the average degree, the abstract states a stronger condition than the theorem; the wording should be aligned.
[§3.2, Lemma 23] The statement that the Jacobian matrix 'is triangular' is imprecise: the displayed entries show only that the matrix is block triangular when the X-coordinates are ordered before the U∪W coordinates, and the omitted entries involving derivatives of z and ξ with respect to components in X are generally nonzero. The determinant computation is still valid, but the wording should be clarified.
[§5.4, Theorem 32] Since the central saddle-point expansion is quoted from [12], it would be helpful for the reader if the authors added a short sentence in Lemma 15 explicitly identifying which numbered conditions (a)–(d) of Theorem 32 are verified by which displayed bounds, rather than only saying that conditions (b) and (c) hold.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the enumeration formula is derived from an exact contour integral with the balancing vector r chosen as a saddle point; no fitted quantity is renamed as a prediction.

full rationale

The paper's central formula for N(G, b) is obtained from the exact Cauchy integral N(G, b) = [x_1^{b_1} ... x_n^{b_n}] ∏_{jk∈G}(x_j/x_k + x_k/x_j), with contours x_j = r_j^{1/2} e^{iθ_j}. The count itself is independent of the choice of r; r is not fitted to N(G, b) but is selected as the solution of the balance equations (2), which express that the Bradley-Terry random orientation with parameters r has expected imbalance b. This is a legitimate saddle-point choice, not a self-definitional reduction: the formula would hold for any positive r, and the chosen r only simplifies the exponential factor P(G, b)^{-1}. Lemma 5 proves an equivalence between conditional uniformity and the Bradley-Terry form, so the model is not imported as an unverifiable ansatz. The asymptotic evaluation in Lemma 15 quotes [12, Theorem 4.4], a general saddle-point integration theorem whose assumptions concern derivative bounds and normal moments and do not include the orientation count being proved; it is also a published external result, even though its authors overlap with the present paper. Assumption A3 is honestly presented as a sufficient regularity condition, with Theorem 4 giving a sufficient condition in terms of ||b||_∞, so it is not a fitted input disguised as a prediction. The later subdigraph probability result (Theorem 24) simply divides two applications of Corollary 3 and estimates the ratio of determinants; it contains no circular step. The only residual risk is whether the quoted general theorem in [12] is correct exactly as stated, which is a correctness hazard external to the circularity question, not a logical reduction of the paper's result to its own inputs.

Assumptions & free parameters 0 free parameters · 7 assumptions · 0 invented entities

No parameters are fitted to data. The vector r is the unique (up to scale) solution of the balance equations (2), and all quantities in (4) are functions of G and b. The proof relies on standard tools plus the quoted integration theorem of Isaev and McKay [12]. No new physical or mathematical entities are postulated.

assumptions (7)

domain assumption The graph sequence satisfies n^(1/3+ε) ≤ Δ ≤ n-1 for some constant ε>0 (Assumption A1).
Assumption in Theorem 1; ensures the error terms in (5) vanish and the saddle point expansion applies.
domain assumption The Cheeger constant h(G) satisfies h(G) ≥ γΔ for some constant γ>0 (Assumption A2).
Assumption in Theorem 1; supplies the expansion/spectral gap used in Lemmas 12, 18, and 30.
domain assumption The balance equations (2) have a solution r with r_j/r_k ≤ 1+R for every edge jk, where 0 ≤ R = O(1) and R^2 (n/Δ) log(2n/Δ) = o(log n) (Assumption A3).
Assumption in Theorem 1; bounds the saddle point asymmetry, and R appears in the final error term.
standard math Integration theorem from Isaev and McKay [12, Theorem 4.4], quoted in full in Section 5.4.
Used as a black box to evaluate the main saddle-point integral in Lemma 15; the paper does not re-derive it, but it is a published theorem.
standard math Isserlis' formula for Gaussian moments, quoted in Lemma 13.
Used to compute the expectation terms ψ(G,b) via Gaussian moments.
standard math Max-flow min-cut theorem of Ford and Fulkerson, used in Lemma 6.
Establishes the existence of a random orientation with expected imbalance sequence b, a step in Theorem 7.
standard math Matrix-Tree theorem, used to interpret Δ^(1/2) n^(1/2) |A|^(-1/2) as κ(G,r)^(-1/2).
Used in the discussion after Theorem 1 and in the proof of Corollary 3.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Asymptotic enumeration of orientations of a graph as a function of the out-degree sequence." pith.science (2026). https://pith.science/paper/DBLCI7RB

@misc{pith2026190801309,
  author       = {Pith},
  title        = {Pith review of: Asymptotic enumeration of orientations of a graph as a function of the out-degree sequence},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/DBLCI7RB}},
  note         = {Machine review of arXiv:1908.01309}
}

abstract

We prove an asymptotic formula for the number of orientations with given out-degree (score) sequence for a graph $G$. The graph $G$ is assumed to have average degrees at least $n^{1/3 + \varepsilon}$ for some $\varepsilon > 0$, and to have strong mixing properties, while the maximum imbalance (out-degree minus in-degree) of the orientation should be not too large. Our enumeration results have applications to the study of subdigraph occurrences in random orientations with given imbalance sequence. As one step of our calculation, we obtain new bounds for the maximum likelihood estimators for the Bradley-Terry model of paired comparisons.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

25 extracted references · 25 canonical work pages

[12]

Isaev and B

M. Isaev and B. D. McKay, Complex martingales and asymptotic e numeration, Random Structures Algorithms, 52 (2018) 616–661

work page 2018
[1]

Alon and V

N. Alon and V. D. Milman, λ1, isoperimetric inequalities for graphs, and superconcen- trators, J. Combin. Theory Ser. B , 38 (1985) 73–88

work page 1985
[2]

Barvinok and J

A. Barvinok and J. A. Hartigan, An asymptotic formula for the nu mber of non-negative integer matrices with prescribed row and column sums, Trans. Amer. Math. Soc. , 364 (2012) 4323–4368

work page 2012
[3]

R. A. Bradley and M. E. Terry, Rank analysis of incomplete block de signs: I. the method of paired comparisons, Biometrika, 39 (1952) 324–345

work page 1952
[4]

E. R. Canﬁeld, C. Greenhill, and B. D. McKay, Asymptotic enumera tion of dense 0-1 matrices with speciﬁed line sums, J. Combin. Theory Ser. A , 115 (2008), 32–66

work page 2008
[5]

L. R. Ford, Jr., Solution of a ranking problem from binary comparis ons, Amer. Math. Monthly, 64, part 2 (1957) 28–33

work page 1957
[6]

L. R. Ford Jr. and D. R. Fulkerson, Maximum ﬂow through a netwo rk, Canad. J. Math. , 8 (1956) 399–404

work page 1956
[7]

Z. Gao, B. D. McKay and X. Wang, Asymptotic enumeration of tou rnaments with a given score sequence containing a speciﬁed digraph, Random Structures Algorithms , 16 (2000) 47–57

work page 2000

Show all 25 references

[8]

C. S. Greenhill and B. D. McKay, Random dense bipartite graphs a nd directed graphs with speciﬁed degrees, Random Structures Algorithms , 35 (2009) 222–249

2009
[9]

D. R. Hunter, MM algorithms for generalized Bradley-Terry mode ls, Ann. Statist. , 32 (2004) 384–406

2004
[10]

Isaev, Asymptotic behavior of the number of Eulerian orient ations of graphs [Rus- sian], Mat

M. Isaev, Asymptotic behavior of the number of Eulerian orient ations of graphs [Rus- sian], Mat. Zametki , 93 (2013) 828–843. Translation: Math. Notes , 93 (2013) 816–829

2013
[11]

Isaev and K

M. Isaev and K. Isaeva, Asymptotic enumeration of Eulerian or ientations for graphs with strong mixing properties [Russian], Diskretn. Anal. Issled. Oper. , 20 (2013) 40–58. Translation: https://hal.archives-ouvertes.fr/hal-00730657v2

2013
[13]

Isserlis, On a formula for the product-moment coeﬃcient of any order of a normal frequency distribution in any number of variables, Biometrika, 12 (1918) 134–139

L. Isserlis, On a formula for the product-moment coeﬃcient of any order of a normal frequency distribution in any number of variables, Biometrika, 12 (1918) 134–139. 30

1918
[14]

Jech, The ranking of incomplete tournaments: A mathematic ian’s guide to popular sports, Amer

T. Jech, The ranking of incomplete tournaments: A mathematic ian’s guide to popular sports, Amer. Math. Monthly , 90 (1983) 246–266

1983
[15]

Joe, Majorization, entropy and paired comparisons, Ann

H. Joe, Majorization, entropy and paired comparisons, Ann. Statist., 16 (1988) 915–925

1988
[16]

B. D. McKay, The asymptotic numbers of regular tournaments , Eulerian digraphs and Eulerian oriented graphs, Combinatorica, 10 (1990) 367–377

1990
[17]

B. D. McKay and F. Skerman, Degree sequences of random digr aphs and bipartite graphs, J. Comb. , 7 (2016) 21–49

2016
[18]

B. D. McKay and X. Wang, Asymptotic enumeration of tourname nts with a given score sequence, J. Comb. Theory, Ser. A , 73 (1996) 77–90

1996
[19]

Mihail and P

M. Mihail and P. Winkler, On the number of Eulerian orientations of a graph, Algo- rithmica, 16 (1996) 402–414

1996
[20]

Mohar, Isoperimetric numbers of graphs, J

B. Mohar, Isoperimetric numbers of graphs, J. Combin. Theory Ser. B , 47 (1989) 274– 291

1989
[21]

J. W. Moon, Counting Labelled Trees , Canadian Mathematical Monographs, vol. 1, Canadian Mathematical Congress, Montreal, 1970

1970
[22]

R. C. Read, Some enumeration problems in graph theory, Docto ral Thesis, London University, 1958

1958
[23]

J. H. Spencer, Random regular tournaments, Period. Math. Hungar. , 5 (1974) 105–120

1974
[24]

Zermelo, Die Berechnung der Turnier-Ergebnisse als ein Maxim umproblem der Wahrscheinlichkeitsrechnung, Math

E. Zermelo, Die Berechnung der Turnier-Ergebnisse als ein Maxim umproblem der Wahrscheinlichkeitsrechnung, Math. Z. , 29 (1929) 436–460

1929
[25]

Zhan, Matrix Inequalities

X. Zhan, Matrix Inequalities. Lecture Notes in Mathematics, Vol. 1790. Springer, Berlin, 2002. 31

2002

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [12]

Isaev and B

M. Isaev and B. D. McKay, Complex martingales and asymptotic e numeration, Random Structures Algorithms, 52 (2018) 616–661

work page 2018

[2] [1]

Alon and V

N. Alon and V. D. Milman, λ1, isoperimetric inequalities for graphs, and superconcen- trators, J. Combin. Theory Ser. B , 38 (1985) 73–88

work page 1985

[3] [2]

Barvinok and J

A. Barvinok and J. A. Hartigan, An asymptotic formula for the nu mber of non-negative integer matrices with prescribed row and column sums, Trans. Amer. Math. Soc. , 364 (2012) 4323–4368

work page 2012

[4] [3]

R. A. Bradley and M. E. Terry, Rank analysis of incomplete block de signs: I. the method of paired comparisons, Biometrika, 39 (1952) 324–345

work page 1952

[5] [4]

E. R. Canﬁeld, C. Greenhill, and B. D. McKay, Asymptotic enumera tion of dense 0-1 matrices with speciﬁed line sums, J. Combin. Theory Ser. A , 115 (2008), 32–66

work page 2008

[6] [5]

L. R. Ford, Jr., Solution of a ranking problem from binary comparis ons, Amer. Math. Monthly, 64, part 2 (1957) 28–33

work page 1957

[7] [6]

L. R. Ford Jr. and D. R. Fulkerson, Maximum ﬂow through a netwo rk, Canad. J. Math. , 8 (1956) 399–404

work page 1956

[8] [7]

Z. Gao, B. D. McKay and X. Wang, Asymptotic enumeration of tou rnaments with a given score sequence containing a speciﬁed digraph, Random Structures Algorithms , 16 (2000) 47–57

work page 2000