Counting degree-constrained orientations

Jie-Xiang Zhu; Jing Yu

Counting degree-constrained orientations

T0 review · 1 major / 0 minor · reviewed 2026-05-22 · grok-4.3

Challenge this review Download PDF Read on arXiv ↗

Pith's one-line read The number of graph orientations with out-degrees restricted to given sets equals a signed sum over edge subsets of products of polynomial coefficient sums.

desk verdict The paper gives a signed-sum formula for counting orientations with arbitrary out-degree sets P_v via gauge transforms, generalizing the Eulerian case, but the generality of the gauge step needs explicit checks. read the letter →

arxiv 2504.12693 v4 submitted 2025-04-17 math.CO

Jing Yu , Jie-Xiang Zhu This is my paper

classification math.CO

keywords degree-constrainedorientationsgraphdualityformulagaugetransformationsEulerianevenenumeration

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 a duality formula that rewrites the count of degree-constrained orientations as an alternating sum involving subsets of edges and sums of selected coefficients from polynomials tied to each vertex's allowed out-degrees. This identity supplies a closed-form expression that avoids direct enumeration of orientations. The derivation proceeds by applying gauge transformations to the generating function for all orientations and offers a separate probabilistic reading of the same identity. The formula immediately yields explicit expressions for even orientations and for mixed Eulerian-even orientations on arbitrary graphs, extending an earlier result limited to Eulerian orientations.

What carries the argument

The duality formula expressing the orientation count N(G; prod P_v) as a signed sum over edge subsets of products of coefficient sums from the polynomials tied to each P_v.

What would settle it

A small graph together with explicit sets P_v for which direct enumeration of valid orientations yields a number different from the value of the signed sum over edge subsets.

Watch

Extended reading notes

Core claim

N(G; prod P_v) equals a signed sum over edge subsets of products of coefficient sums drawn from the family of polynomials associated with the admissible sets P_v. The identity is obtained by gauge transformations on the orientation-generating polynomial and is re-derived by viewing that polynomial as the expectation of a random product of polynomials. The same identity supplies explicit formulas for even orientations and mixed Eulerian-even orientations and recovers the Borbényi-Csikvári formula for Eulerian orientations as a special case.

Load-bearing premise

Gauge transformations applied to the orientation-generating polynomial preserve the exact count of orientations satisfying the degree constraints.

Editorial extensions

If this is right

The number of even orientations on any graph is given by an explicit signed sum over edge subsets.
The number of mixed Eulerian-even orientations is given by a similar explicit signed sum.
The earlier formula for Eulerian orientations arises as the special case in which every P_v is the set of even integers.
The same identity admits a probabilistic reading as the expectation of a random polynomial product.

Reading between the lines

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

The formula may simplify further when the polynomials for the sets P_v possess additional algebraic structure such as roots of unity or generating functions with known closed forms.
The signed-sum representation could be used to derive asymptotic estimates or concentration results for the number of constrained orientations in random graphs.
The approach suggests that similar gauge or expectation identities might exist for other local constraints on orientations or for related objects such as flows or matchings.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

The main thing here is a duality formula that writes the count of orientations with out-degree of v in P_v as a signed sum over edge subsets, built from coefficient sums of some polynomials tied to the P_v family. It extends the Borbényi-Csikvári result on Eulerian orientations and supplies both a gauge-transform derivation and a probabilistic one that views the generating function as an expectation of a random product. That dual route is a solid move for cross-checking the identity. The applications to even orientations and mixed Eulerian-even orientations drop out cleanly once the formula is available, and they work on general graphs without extra assumptions on G. The citation pattern is appropriate and the work avoids circularity by importing the gauge technique from outside the orientation literature. The soft spot sits in the gauge step itself. Gauge transforms from holographic algorithms usually demand that the local factors stay inside a closed algebraic span or satisfy invariance after the change of variables; the abstract does not spell out why arbitrary integer subsets P_v meet that requirement, and if extra terms appear that fail to cancel in the signed sum, the general claim would only hold for the special cases already checked. The probabilistic derivation may sidestep some of this, but it still needs to be shown that it reproduces the same cancellations. This is aimed at combinatorialists who work on exact enumeration or algebraic graph theory. Someone who already knows generating functions or orientation polynomials will extract the most value. The result has enough concrete content and two derivations to merit referee time rather than a desk reject, even if the generality requires closer inspection. I would bring it to a reading group to walk through the gauge calculation on a small example. I would not cite it until the arbitrary-P_v case is verified. Recommendation: send it to peer review and ask the referees to focus on whether the gauge preserves the necessary relations for general admissible sets.

Referee Report

1 major / 0 minor

Summary. The paper claims to prove a general duality formula for the number of orientations N(G; ∏_{v∈V} P_v) with out-degree constraints given by arbitrary sets P_v ⊆ ℤ, expressing this count as a signed sum over edge subsets that involves products of coefficient sums drawn from an associated family of polynomials. The proof proceeds via gauge transformations applied to the orientation-generating polynomial (imported from statistical physics and holographic algorithms) together with an alternative probabilistic derivation that interprets the generating function as an expectation of a random product. Applications recover explicit formulas for even orientations and for mixed Eulerian-even orientations, generalizing the Borbényi–Csikvári result on Eulerian orientations.

Significance. If the duality identity holds for arbitrary admissible sets P_v, the result supplies a uniform combinatorial tool for counting degree-constrained orientations on general graphs and extends known closed-form expressions beyond the Eulerian case. The dual proofs—one algebraic via gauge transformations and one probabilistic—constitute a methodological strength that may facilitate further extensions. The concrete applications to even and mixed Eulerian orientations demonstrate immediate utility.

major comments (1)

In the duality proof, the gauge transformation is applied to the orientation-generating polynomial without an explicit verification that arbitrary integer subsets P_v ⊆ ℤ preserve the required algebraic closure or transformation properties under the chosen gauge. If the transformation introduces higher-degree terms or non-local dependencies that are not cancelled by the subsequent edge-subset summation, the signed-sum identity fails to hold for general P_v even though it may hold for the special cases (even orientations, Eulerian) treated in the applications. This assumption is load-bearing for the central claim of generality.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their detailed review and insightful comments. We are pleased that the significance of the duality formula and the dual proofs are recognized. We address the major comment below.

read point-by-point responses

Referee: In the duality proof, the gauge transformation is applied to the orientation-generating polynomial without an explicit verification that arbitrary integer subsets P_v ⊆ ℤ preserve the required algebraic closure or transformation properties under the chosen gauge. If the transformation introduces higher-degree terms or non-local dependencies that are not cancelled by the subsequent edge-subset summation, the signed-sum identity fails to hold for general P_v even though it may hold for the special cases (even orientations, Eulerian) treated in the applications. This assumption is load-bearing for the central claim of generality.

Authors: The orientation-generating polynomial is constructed as a product over vertices of the polynomials encoding the sets P_v and over edges of the edge variables. The gauge transformation is a local operation at each vertex that modifies the vertex polynomials while preserving the overall generating function up to the gauge factors. Because each P_v is finite, the associated polynomial has finite degree, and the gauge can be chosen (as in the holographic algorithm literature) to ensure that the transformed polynomials satisfy the necessary relations for the subsequent summation over edge subsets to yield the desired count. This construction does not depend on the specific form of P_v beyond finiteness and thus holds generally. The special cases in the applications arise from particular choices of P_v (e.g., even degrees corresponding to even-powered terms), but the general argument applies verbatim. We acknowledge that an explicit verification of the algebraic closure for arbitrary P_v would strengthen the presentation and will add a short lemma or paragraph detailing this in the revised manuscript. revision: yes

Circularity Check

0 steps flagged · score 0.0 of 10

Derivation relies on external gauge transformations and probabilistic methods with no self-referential reduction

full rationale

The central duality formula is obtained by applying gauge transformations (imported from statistical physics and holographic algorithms) to the orientation-generating polynomial, followed by a separate probabilistic derivation interpreting it as an expectation. These are external techniques not defined in terms of the target count N(G; prod P_v). The paper also generalizes a result by Borbényi and Csikvári (distinct authors) for the Eulerian case. No equations reduce the claimed identity to a fitted parameter, self-definition, or load-bearing self-citation chain; the result remains independent of its own outputs.

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

The central claim rests on the applicability of gauge transformations to the orientation-generating polynomial, which is a domain assumption from statistical physics; no free parameters or invented entities are introduced in the abstract.

assumptions (2)

standard math Finite graphs have well-defined orientations and out-degrees.
Basic setup of the problem in graph theory.
domain assumption Existence of a family of polynomials whose coefficient sums relate to the admissible sets P_v.
The duality formula involves these polynomials as stated in the abstract.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Counting degree-constrained orientations." pith.science (2026). https://pith.science/paper/2504.12693

@misc{pith2026250412693,
  author       = {Pith},
  title        = {Pith review of: Counting degree-constrained orientations},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2504.12693}},
  note         = {Machine review of arXiv:2504.12693}
}

abstract

We study the enumeration of graph orientations under local degree constraints. Given a finite graph $G = (V, E)$ and a family of admissible sets $\{\mathsf P_v \subseteq \mathbb{Z} : v \in V\}$, let $\mathcal N (G; \prod_{v \in V} \mathsf P_v)$ denote the number of orientations in which the out-degree of each vertex $v$ lies in $P_v$. We prove a general duality formula expressing $\mathcal N(G; \prod_{v \in V} \mathsf P_v)$ as a signed sum over edge subsets, involving products of coefficient sums associated with $\{\mathsf P_v\}_{v \in V}$, from a family of polynomials. Our approach employs gauge transformations, a technique rooted in statistical physics and holographic algorithms. We also present a probabilistic derivation of the same identity, interpreting the orientation-generating polynomial as the expectation of a random polynomial product. As applications, we obtain explicit formulas for the number of even orientations and for mixed Eulerian-even orientations on general graphs. Our formula generalizes a result of Borb\'enyi and Csikv\'ari on Eulerian orientations of graphs.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

19 extracted references · 19 canonical work pages

[1]

[BBC24] F. Bencs,M. Borbényi, andP. Csikvári.Number of Eulerian orientations for Benjamini–Schramm convergent graph sequences,https://arxiv.org/abs/2409.18012(preprint), 2024 (cit. on p

work page arXiv 2024
[2]

BorbényiandP

[BC20] M. BorbényiandP. Csikvári.Counting degree-constrained subgraphs and orientations, Discrete Math., 343(6) (2020), 111842 (cit. on pp. 1,

work page 2020
[3]

Cai.Holographic algorithms: guest column, ACM SIGACT News,39(2) (2008), 51–81 (cit

[Cai08] J.-Y. Cai.Holographic algorithms: guest column, ACM SIGACT News,39(2) (2008), 51–81 (cit. on p

work page 2008
[4]

[CC17] J.-Y. CaiandX. Chen.Complexity Dichotomies for Counting Problems: Volume 1, Boolean Domain. Cambridge University Press, 2017 (cit. on p

work page 2017
[5]

[CL08] J.-Y. CaiandP. Lu.Basis collapse in holographic algorithms, Comput. Complexity,17(2) (2008), 254–281 (cit. on p

work page 2008
[6]

[CL09] J.-Y. CaiandP. Lu.Holographic algorithms: The power of dimensionality resolved, Theoret. Comput. Sci.,410(18) (2009), 1618–1628 (cit. on p

work page 2009
[7]

[CL10] J.-Y. CaiandP. Lu.On symmetric signatures in holographic algorithms, Theory Comput. Syst.,46(3) (2010), 398–415 (cit. on p

work page 2010
[8]

[CL11] J.-Y. CaiandP. Lu.Holographic algorithms: From art to science, J. Comput. System Sci.,77(1) (2011), 41–61 (cit. on p

work page 2011

Show all 19 references

[9]

[CLX08] J.-Y. Cai,P. Lu, andM. Xia.Holographic algorithms by Fibonacci gates and holographic reductions for hardness, 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), (2008), 644–653 (cit. on p

2008
[10]

ChertkovandV.Y

[CC06a] M. ChertkovandV.Y. Chernyak.Loop calculus in statistical physics and information science, Phys. Rev. E,73(6) (2006), 065102 (cit. on pp. 1,

2006
[11]

ChertkovandV.Y

[CC06b] M. ChertkovandV.Y. Chernyak.Loop series for discrete statistical models on graphs, J. Stat. Mech. Theory Exp.,2006(06) (2006), P06009 (cit. on p

2006
[12]

Csikvári.A short survey on stable polynomials, orientations and matchings, Acta Mathematica Hungarica,166(1) (2022), 1–16 (cit

[Csi22] P. Csikvári.A short survey on stable polynomials, orientations and matchings, Acta Mathematica Hungarica,166(1) (2022), 1–16 (cit. on p

2022
[13]

[LW72] E. H. LiebandF. Y. Wu.Two-Dimensional Ferroelectric Models, Phase Transitions and Critical Phenomena,1(1972). Ed. byC. DombandM. Green, 331–490 (cit. on p

1972
[14]

American Mathematical Soc., 2007 (cit. on p

2007
[15]

[Nag66] J. F. Nagle.Lattice statistics of hydrogen bonded crystals. I. The residual entropy of ice, J. Math. Phys.,7(8) (1966), 1484–1491 (cit. on p

1966
[16]

Valiant.Expressiveness of matchgates, Theoret

[Val02a] L.G. Valiant.Expressiveness of matchgates, Theoret. Comput. Sci.,289(1) (2002), 457–471 (cit. on p

2002
[17]

Valiant.Quantum computers that can be simulated classically in polynomial time, SIAM J

[Val02b] L.G. Valiant.Quantum computers that can be simulated classically in polynomial time, SIAM J. Comput.,31(4) (2002), 1229–1254 (cit. on p

2002
[18]

Valiant.Accidental algorithms, 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), (2006), 509–517 (cit

[Val06] L.G. Valiant.Accidental algorithms, 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), (2006), 509–517 (cit. on p

2006
[19]

Valiant.Holographic algorithms, SIAM J

[Val08]L.G. Valiant.Holographic algorithms, SIAM J. Comput.,37(5) (2008), 1565–1594 (cit. on p

2008

Pith tools

Reviewed May 22, 2026 · model on record in the stance chip above.

[1] [1]

[BBC24] F. Bencs,M. Borbényi, andP. Csikvári.Number of Eulerian orientations for Benjamini–Schramm convergent graph sequences,https://arxiv.org/abs/2409.18012(preprint), 2024 (cit. on p

work page arXiv 2024

[2] [2]

BorbényiandP

[BC20] M. BorbényiandP. Csikvári.Counting degree-constrained subgraphs and orientations, Discrete Math., 343(6) (2020), 111842 (cit. on pp. 1,

work page 2020

[3] [3]

Cai.Holographic algorithms: guest column, ACM SIGACT News,39(2) (2008), 51–81 (cit

[Cai08] J.-Y. Cai.Holographic algorithms: guest column, ACM SIGACT News,39(2) (2008), 51–81 (cit. on p

work page 2008

[4] [4]

[CC17] J.-Y. CaiandX. Chen.Complexity Dichotomies for Counting Problems: Volume 1, Boolean Domain. Cambridge University Press, 2017 (cit. on p

work page 2017

[5] [5]

[CL08] J.-Y. CaiandP. Lu.Basis collapse in holographic algorithms, Comput. Complexity,17(2) (2008), 254–281 (cit. on p

work page 2008

[6] [6]

[CL09] J.-Y. CaiandP. Lu.Holographic algorithms: The power of dimensionality resolved, Theoret. Comput. Sci.,410(18) (2009), 1618–1628 (cit. on p

work page 2009

[7] [7]

[CL10] J.-Y. CaiandP. Lu.On symmetric signatures in holographic algorithms, Theory Comput. Syst.,46(3) (2010), 398–415 (cit. on p

work page 2010

[8] [8]

[CL11] J.-Y. CaiandP. Lu.Holographic algorithms: From art to science, J. Comput. System Sci.,77(1) (2011), 41–61 (cit. on p

work page 2011