REVIEW 3 minor 8 references
An equality for balanced digraphs
T0 review · 0 major / 3 minor · reviewed 2026-08-06 · deepseek-v4-flash
Pith's one-line read For any balanced directed multigraph, the number of k-arc subgraphs that make a chosen vertex reachable from every other vertex and that realize a prescribed set of directed cycles does not depend on the chosen vertex.
desk verdict A clean, fully worked-out equality for balanced digraphs that unifies several known enumerative results; no load-bearing flaw found. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The argument turns on Proposition 3.1: in a balanced digraph, every bipartition $V=P\sqcup Q$ has $|A(P,Q)|=|A(Q,P)|$, meaning equally many arcs cross from $P$ to $Q$ as from $Q$ to $P$. The proof packages $k$-arc subsets by their attraction basins—$S(B)$, the vertices that can reach $s$, and $T(B)$, the vertices that can reach $t$—inside the family $U_{k,Z}$ of subsets whose basins together cover $V$ and whose cycle set is exactly $Z$. For each nontrivial partition $(P,Q)$, two lemmas give matching formulas for the number of subsets with $S(B)=P$ and the number with $T(B)=Q$, both expressed in terms of a common family $X^{P,Q}_{k-m,Z}$; the balance identity makes the binomial coefficients match. A subtractive counting step then assembles these partition-by-partition equalities into $\gamma_{k,Z}(s)=\gamma_{k,Z}(t)$.
What would settle it
Run a brute-force enumeration of $\gamma_{k,Z}(s)$ over every vertex $s$ of every small balanced multidigraph (loops and parallel arcs allowed), for all $k$ and all cycle sets $Z$. Theorem 1.5 predicts the counts agree for all roots; any single discrepancy, such as a deviation from the values $\gamma_3(s)=3$ and $\gamma_4(s)=2$ in the paper's four-vertex example, would refute the claim.
Extended reading notes
Core claim
The central claim is Theorem 1.5: if $D=(V,A,\psi)$ is balanced, then for every $k\in\mathbb{N}$, every subset $Z$ of the cycles of $D$, and every pair of vertices $s,t$, the number $\gamma_{k,Z}(s)$ of $k$-element subsets $B\subseteq A$ such that every vertex has a directed path to $s$ in $D\langle B\rangle$ and the cycle set of $B$ is exactly $Z$ equals $\gamma_{k,Z}(t)$. In words, the count of $k$-arc spanning subgraphs that make a chosen vertex a root and realize a specified directed-cycle configuration is independent of which vertex is chosen. The acyclic case $Z=\emptyset$ is Theorem 1.1, and summing $\gamma_{k,Z}$ over all $Z$ gives Theorem 1.3. The proof delivers the equality uniformly for all $k$, including values where both sides are zero.
Load-bearing premise
The whole result rests on the digraph being balanced—equal indegree and outdegree at every vertex—because that is what makes every cut have equally many arcs in both directions.
Editorial extensions
If this is right
- When $k=|V|-1$, the counted objects are exactly the spanning arborescences rooted at $s$, so the theorem reproduces the classical fact that every root of a balanced digraph supports the same number of arborescences.
- For the bidirected digraph of an undirected multigraph $G$ with $k=|E|$, $s$-convergences are exactly the acyclic orientations of $G$ with unique sink $s$; hence the number of acyclic orientations with a prescribed unique sink is independent of the sink.
- For weakly connected balanced digraphs, the largest $k$ with a nonzero count is the size of a maximum acyclic subdigraph (equivalently $|A|$ minus the minimum feedback arc set), so root-independence holds for that extremal count as well.
- Theorem 1.3, obtained by summing over all cycle sets $Z$, gives an unrestricted root-independence statement: the number of $k$-arc subsets for which every vertex reaches $s$ is independent of $s$; for bidirected graphs this counts orientations with $s$ as a to-root.
- The full Theorem 1.5 sharpens all of these: even if one prescribes which directed cycles the chosen arcs may contain, the root-independence survives.
Reading between the lines
- Because the proof's only balance-dependent step is the cut identity, a weighted version should hold whenever arc weights are respected by a bijection between $A(P,Q)$ and $A(Q,P)$; this would make the theorem a statement about weighted generating functions rather than plain counts.
- Since the equality holds for every cycle set $Z$ separately, the polynomial $\sum_k \gamma_{k,Z}(s)\,x^k$ is root-independent for each $Z$; identifying this common polynomial with a known digraph invariant, a question the authors leave open, would connect the result to algebraic graph theory.
- The subtractive proof suggests a bijective strengthening may exist: a map between $s$-convergences and $t$-convergences that preserves arc count and cycle set, and perhaps further statistics such as in-degree sequences. Such a map, if found, would explain the equality without inclusion-exclusion.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This paper proves that for a finite balanced directed multigraph D, for any integer k and any subset Z of the set of cycles of D, the number of k-arc subsets B of A such that every vertex can reach a fixed vertex s in the subdigraph D⟨B⟩ and such that the set of cycles of D⟨B⟩ equals Z is independent of the choice of s. The authors derive this as Theorem 1.5, with Theorems 1.1 and 1.3 as immediate consequences. The proof is built from a sequence of lemmas about 'attraction basins', culminating in a bijection between two sets satisfying S(B)=P and T(B)=Q, and uses the balance condition exactly through the equality |A(P,Q)|=|A(Q,P)|. The introduction situates the result as a common generalization of known theorems on spanning arborescences, acyclic orientations, and maximum acyclic subgraphs.
Significance. The result is a clean, unifying statement for balanced digraphs, and the proof is elementary and fully written out. The bijective core (Lemma 3.14) is particularly nice and gives a constructive explanation of the equality. The paper explicitly recovers several known results, which both demonstrates the breadth of the theorem and provides a useful literature review. I also appreciate the careful discussion of the limitations of the method (e.g., the note that several lemmas do not require balance) and the suggestions for making the proof bijective via the Garsila-Milne involution principle. The paper is a solid contribution to enumerative combinatorics of digraphs.
minor comments (3)
- [Section 3, pages 12 and 14 (Definition 3.13)] The symbol Z is used both for the fixed subset of CycsA (as in Theorem 1.5) and, in 'i∈Z' within the definitions of P_i(A) and X_{i,Z}^{P,Q}, for the integers. This notational clash should be removed by using \mathbb{Z} for the integers or by renaming the cycle set (e.g., to \mathcal{Z}). The proof is understandable, but the current typesetting makes the definition of X_{i,Z}^{P,Q} ambiguous.
- [Examples 1.2 and 1.6] The phrases '1-convergences', '2-convergences', and '1-preconvergences' refer to the root vertex s (i.e., convergences to vertex 1), not to the size k, which is potentially confusing since γ_k(s) and δ_k(s) are indexed by size. For clarity, write 'convergences to vertex 1' or 's=1 pre-convergences'.
- [Proof of Lemma 3.5, page 9] The underbrace in the line '(E∪C)\A(P,Q)|{z}⊇C' is typeset in a way that obscures the argument; it should be 'C⊆A(P,Q)' or a short parenthetical. The logical step is valid after this correction.
Circularity Check
No circular derivation: Theorem 1.5 is proved by a self-contained bijective counting argument; the only self-citation is to the first author's textbook for standard background and is not load-bearing.
full rationale
The paper's main theorem (Theorem 1.5) is proved directly. The crucial equality, Proposition 3.12, compares two sums whose only difference is the binomial coefficients C(|A(P,Q)|, m) and C(|A(Q,P)|, m). These coefficients are equal by Proposition 3.1, which is proved in the paper from the balanced hypothesis (each vertex has equal indegree and outdegree). This is not circular: balance is the theorem's assumption, not its conclusion. The bijections Phi and Psi in Lemma 3.14 are genuinely inverse; their well-definedness relies on Lemmas 3.5, 3.6, 3.8 (for the forward direction) and Lemmas 3.3, 3.4, 3.5, 3.6 (for the reverse direction), all of which are proved from the definitions and do not presuppose the desired equality. The subtraction step in Lemma 3.10 is a valid partition of U_{k,Z} by the nonempty set S(B), and Lemma 3.11 is the analogous partition by T(B). No fitted parameter is renamed as a prediction; no uniqueness theorem is imported from prior work; no ansatz is smuggled in via citation. The only self-citation is [22s], the first author's own textbook, used for standard terminology ("cycle", "arborescence") and as a pointer to a known exercise for Proposition 3.1, which is nonetheless fully proved in the text. The arborescence characterization from [22s] in Section 2 is used only to connect the new theorem to known particular cases, not to prove the main result. Therefore, the derivation is self-contained and the circularity score is low, reflecting only a minor non-load-bearing self-citation.
Assumptions & free parameters
assumptions (2)
- standard math Standard finite-set counting principles (sum rule, inclusion-exclusion) and basic properties of paths and cycles in digraphs.
- domain assumption The digraph D is balanced: for every vertex v, deg+(v) = deg-(v).
Cite this review
Pith. "Pith review of An equality for balanced digraphs." pith.science (2026). https://pith.science/paper/4PJ4NTGM
@misc{pith2026250722388,
author = {Pith},
title = {Pith review of: An equality for balanced digraphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/4PJ4NTGM}},
note = {Machine review of arXiv:2507.22388}
}
abstract
Consider a directed multigraph $D$ that is balanced (i.e., at each vertex, the indegree equals the outdegree). Let $A$ be its set of arcs. Fix an integer $k$. Let $s$ be a vertex of $D$. We show that the number of $k$-element subsets $B$ of $A$ that contain no cycles but contain a path from each vertex to $s$ (we call them "$s$-convergences") is independent on $s$. This generalizes known facts about spanning arborescences, acyclic orientations and maximal acyclic subdigraphs (or, equivalently, minimum feedback arc sets). Moreover, this result can be generalized even further, replacing "contain no cycles" with "have a given set of cycles".
Reference graph
Works this paper leans on
-
[1]
An introduction to graph theory
Darij Grinberg, An introduction to graph theory, arXiv:2308.04512v3. https://arxiv.org/abs/2308.04512v3
-
[2]
https://doi.org/10.1007/978-3-319-71840-8
J rgen Bang-Jensen, Gregory Gutin (eds.), Classes of Directed Graphs, Springer 2018. https://doi.org/10.1007/978-3-319-71840-8
-
[3]
https://arxiv.org/abs/2201.11974v5 Lo\" c Foissy, Bialgebras in cointeraction, the antipode and the eulerian idempotent, arXiv:2201.11974v5
-
[4]
Curtis Greene, Thomas Zaslavsky, On the interpretation of Whitney numbers through arrangement of hyperplanes, zonotopes, non-Radon partitions, and orientations of graphs. Trans. Amer. Math. Soc. 280(1) (1983), pp. 97--126. https://doi.org/10.1090/S0002-9947-1983-0712251-1
-
[5]
Computing the EHZ capacity is NP-hard
Karla Leipold, Frank Vallentin, Computing the EHZ capacity is NP-hard, arXiv:2402.09914v3. https://arxiv.org/abs/2402.09914v3
-
[6]
K\' e vin Perrot, Trung Van Pham, Feedback Arc Set Problem and NP-Hardness of Minimum Recurrent Configuration Problem of Chip-Firing Game on Directed Graphs, Annals of Combinatorics 19 (2015), pages 373--396
work page 2015
-
[7]
https://arxiv.org/abs/1909.03339v2 K\' e vin Perrot, On the complexity of counting feedback arc sets, Chicago Journal of Theoretical Computer Science 2022, Article 01, pages 1--8, arXiv:1909.03339v2
work page Pith review arXiv 1909
-
[8]
https://doi.org/10.1007/978-1-4612-4968-9
Dennis Stanton, Dennis White, Constructive Combinatorics, Springer 1986. https://doi.org/10.1007/978-1-4612-4968-9
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.