{"id":"146facb5-2eb3-4900-88d6-010db500d296","arxiv_id":"1908.01309","paper_version":2,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"An asymptotic enumeration formula for orientations with a given imbalance sequence is proved for sparse graphs with strong expansion.","lead":"This paper proves an asymptotic formula for counting orientations of a graph where each vertex has a prescribed imbalance between out- and in-degree. It extends the known techniques from dense graphs to sparse ones, down to average degree about n^(1/3), and forms a bridge to the Bradley-Terry paired-comparison model.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the proof is internally coherent; the main residual risk is the unverified external saddle-point theorem used in Lemma 15, not a flaw in the argument itself.","rationale":"The reader identified assumption A3 as the weakest assumption; I agree that A3 is the least transparent to verify in applications, but it is an explicit assumption, not a hidden or circular one. The more load-bearing dependence is the quoted integration theorem from the authors' earlier paper [12], which supplies the saddle-point expansion in Lemma 15. I checked the immediate hypotheses of that theorem against the estimates in the paper and found them consistent, including the global growth condition for the degree-6 polynomial f. Since the proof of [12, Theorem 4.4] is not reproduced, an independent check of its application is the one verification that could change the verdict. Because no concrete internal error was found, I do not recommend changing the reader's ACCEPT verdict, but residual uncertainty about the external theorem keeps confidence at moderate rather than high.","tokens_in":23446,"tokens_out":44586,"duration_ms":444009,"concrete_test":"Independently re-derive Lemma 15 directly from [12, Theorem 4.4], checking hypotheses (a)-(d) for f = i(f3+f5)+f4+f6 with A having lambda_min(A) >= c Delta. In particular, verify that |f(x)| <= n^{c3} e^{c2 x^T A x / n} holds for all x with c3 constant, using max_r r^6 e^{-c2 (Delta/n) r^2} = O((n/Delta)^3), and confirm that the resulting error term matches O(R^3 Delta^{-3/2+epsilon/2} n + Delta^{-3+epsilon} n). If any hypothesis fails or the error constant acquires an extra factor depending on n/Delta, Lemma 15 and Theorem 1 would need revision.","verdict_should_be":"UNCHANGED","load_bearing_attack":"No significant objection identified. Reading the proof as a conditional statement, the central claim is sound under assumptions A1, A2, and A3. The analytic core (Lemma 15) applies the quoted [12, Theorem 4.4] consistently: the derivative bounds satisfy conditions (b) and (c) with the stated phi_1 and phi_2, Var f_im = o(log n) follows from A3, the Zeta contribution is absorbed, and the degree-6 polynomial f is globally dominated by e^{c2 x^T A x / n} because lambda_min(A) = Omega(Delta), so condition (d) is satisfiable with a constant c3 independent of n. The only true residual risk is that [12, Theorem 4.4] is quoted rather than proved in this paper, so the correctness of Lemma 15 depends on that external result holding exactly as stated and on all hypotheses being checked. Assumption A3 is honestly presented as an assumption with Theorem 4 giving only a sufficient condition; this limits the scope of applicability but is not an internal inconsistency. No circular reasoning, parameter fitting, or unsupported numerical claim was found.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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).","tokens_in":23634,"tokens_out":16221,"duration_ms":147878,"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.","major_comments":[],"minor_comments":[{"comment":"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.","section":"§1, after Eq. (5), and §3.1, end of Lemma 15"},{"comment":"The summation index in 'Since ∑_{j=0}^n b_j = 0' should run from 1 to n, not from 0 to n.","section":"§2, Proof of Theorem 4"},{"comment":"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.","section":"Abstract and Theorem 1"},{"comment":"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.","section":"§3.2, Lemma 23"},{"comment":"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.","section":"§5.4, Theorem 32"}],"recommendation":"minor_revision","confidential_remarks":"The paper is within the scope of the journal and the proof is internally coherent. The self-citation to [12] is legitimate, but because the main saddle-point lemma is quoted from the authors' own earlier work, an editor may wish to have the hypotheses of [12, Theorem 4.4] independently double-checked; my own reading found no gap. The only substantive correction I request is the erroneous O(n^{-1/2+ε}) bound after Eq. (5), which is local and does not affect the validity of the main theorem."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nWhat 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.\n\nSoft 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.\n\nWho'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.","headline":"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.","tokens_in":24166,"tokens_out":2751,"would_cite":true,"duration_ms":28391,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C30","05A16","05C20"],"pacs":[],"model":"deepseek-v4-flash","headline":"Counting orientations with a prescribed imbalance sequence now reaches sparse graphs, via a saddle-point formula built from Bradley-Terry paired-comparison merits.","keywords":["orientations of graphs","imbalance sequence","score sequence","asymptotic enumeration","saddle point method","Bradley-Terry model","Cheeger constant","Eulerian orientations"],"falsifier":"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.","tokens_in":23235,"feed_emoji":"📊","tokens_out":7810,"duration_ms":70292,"temperature":0.7,"pith_summary":"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.","feed_headline":"Counting orientations by imbalance now reaches sparse graphs","feed_subtitle":"Exact asymptotic count via Bradley-Terry saddle points; includes Eulerian orientations and subdigraph probabilities.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the saddle-point integration theorem (Lemma 31 and Theorem 32) used to evaluate the main integral.","marker":"[12]"},{"why":"Introduces the Bradley-Terry paired-comparison model whose balance equations define the saddle-point parameters $r$.","marker":"[3]"},{"why":"Gives the original proof that the balance equations have a unique solution when the comparison digraph is strongly connected.","marker":"[24]"},{"why":"Provides techniques for asymptotic enumeration of $0$--$1$ matrices with fixed margins, which the bipartite case extends.","marker":"[2]"},{"why":"Used via the max-flow min-cut theorem to characterize expected imbalance sequences and prove solvability of the balance equations.","marker":"[6]"},{"why":"Relates the Cheeger constant to algebraic connectivity and supplies spectral bounds used throughout the proof.","marker":"[20]"},{"why":"Isserlis' formula computes the normal moments needed for the cumulant correction $\\psi(G,b)$.","marker":"[13]"},{"why":"The matrix-tree theorem identifies $\\Delta^{1/2}n^{1/2}|A|^{-1/2}$ with the inverse square root of the weighted spanning-tree sum.","marker":"[21]"},{"why":"Previous asymptotic enumeration of Eulerian orientations for dense graphs, extended to the sparse range by Corollary 3.","marker":"[11]"}],"fun_headline_variants":["Sparse graph orientations counted exactly by imbalance","Asymptotic count for sparse graph imbalance sequences","New formula for orientation counts via imbalance","Enumeration of sparse orientations via Bradley-Terry","Counting orientations by out-degree sequence now sparse"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Sparse graph orientations counted exactly by imbalance","Asymptotic count for sparse graph imbalance sequences","New formula for orientation counts via imbalance","Enumeration of sparse orientations via Bradley-Terry","Counting orientations by out-degree sequence now sparse"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000759,"raw_usage":{"total_tokens":3329,"prompt_tokens":863,"completion_tokens":2466,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":479,"completion_tokens_details":{"reasoning_tokens":2398}},"tokens_in":479,"tokens_out":2466,"duration_ms":15897,"temperature":1.0,"reasoning_tokens":2398,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:16:59.849860+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Isaev and B","cited_arxiv_id":null,"evidence_quote":"Supplies the saddle-point integration theorem (Lemma 31 and Theorem 32) used to evaluate the main integral."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces the Bradley-Terry paired-comparison model whose balance equations define the saddle-point parameters $r$."},{"cited_title":"Zermelo, Die Berechnung der Turnier-Ergebnisse als ein Maxim umproblem der Wahrscheinlichkeitsrechnung, Math","cited_arxiv_id":null,"evidence_quote":"Gives the original proof that the balance equations have a unique solution when the comparison digraph is strongly connected."},{"cited_title":"Barvinok and J","cited_arxiv_id":null,"evidence_quote":"Provides techniques for asymptotic enumeration of $0$--$1$ matrices with fixed margins, which the bipartite case extends."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Used via the max-flow min-cut theorem to characterize expected imbalance sequences and prove solvability of the balance equations."},{"cited_title":"Mohar, Isoperimetric numbers of graphs, J","cited_arxiv_id":null,"evidence_quote":"Relates the Cheeger constant to algebraic connectivity and supplies spectral bounds used throughout the proof."},{"cited_title":"Isserlis, On a formula for the product-moment coefficient of any order of a normal frequency distribution in any number of variables, Biometrika, 12 (1918) 134–139","cited_arxiv_id":null,"evidence_quote":"Isserlis' formula computes the normal moments needed for the cumulant correction $\\psi(G,b)$."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The matrix-tree theorem identifies $\\Delta^{1/2}n^{1/2}|A|^{-1/2}$ with the inverse square root of the weighted spanning-tree sum."},{"cited_title":"Isaev and K","cited_arxiv_id":null,"evidence_quote":"Previous asymptotic enumeration of Eulerian orientations for dense graphs, extended to the sparse range by Corollary 3."}],"review_version":1}