Pith. sign in

REVIEW 3 major objections 4 minor 33 references

Branching Ratios of Input Trees for Directed Multigraphs

T0 review · 3 major / 4 minor · reviewed 2026-08-10 · deepseek-v4-flash

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

Pith's one-line read The branching ratio of every node in a finite directed multigraph exists and equals the Perron eigenvalue of the subgraph of nodes that feed into it.

desk verdict True headline result, but the proof has a real lower-bound gap and Theorem 8.1 contradicts Example 1.1. read the letter →

arxiv 2501.06812 v1 pith:RDAIALID submitted 2025-01-12 math.CO

Paolo Boldi , Ian Stewart This is my paper · ORCID
classification math.CO MSC 05C5005C2015A18
keywords branchingratioinputtreedirectedmultigraphPerroneigenvalueupstreamsubnetworkwalkcountsPerron-Frobeniustheoremasymptoticgrowth
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 gives a general definition of the branching ratio of a node in a finite directed multigraph: the growth rate of the number of walks of length $\ell$ that end at that node. It proves that the root limit $\delta(i)=\lim_{\ell\to\infty}(a_i(\ell))^{1/\ell}$ always exists and equals the Perron eigenvalue $\rho(i)$ of the upstream subnetwork $U(i)$, the subgraph induced by all nodes that can reach $i$. This matters because branching ratios are used in biology and distributed computing to quantify how information accumulates at a node, and earlier ratio-based definitions can fail to converge for perfectly ordinary networks. The paper also pins down the fine asymptotics: in the strongly connected case $a_i(\ell)$ is asymptotic to $C_r\rho^\ell$ with $r\equiv \ell\pmod h$, and in general to a polynomial $R_s(\ell)\rho^\ell$ whose period is the least common multiple of the periods of the dominant strongly connected components.

What carries the argument

The load-bearing objects are the aggregate walk count $a_i(\ell)=(uA^\ell)_i$, with $u=(1,\ldots,1)$, and the Perron eigenvalue $\rho(i)$ of the upstream subnetwork $U(i)$. The proof splits $a_i(\ell)=\sum_\lambda P_\lambda(\ell)\lambda^\ell$ into dominant terms with $|\lambda|=\rho$ and subdominant terms, then uses the Cesàro-average limit $\lim_{k\to\infty}\frac1k\sum_{\ell=0}^{k}\rho^{-\ell}A^\ell = vw^T$ from the Perron–Frobenius theorem to rule out cancellation of the dominant terms. The Upstream Principle—any walk ending at an upstream node can be extended by a fixed walk to $i$—carries the lower bound from strongly connected components to arbitrary nodes.

What would settle it

Build a network where the upstream subnetwork of node $i$ is the union of two strongly connected components with the same Perron eigenvalue $\rho$ and periods $2$ and $3$, feeding into $i$. Compute $a_i(\ell)=(uA^\ell)_i$ for $\ell=0,\ldots,12$: the theorem predicts $(a_i(\ell))^{1/\ell}\to\rho$ and that $a_i(\ell)/\rho^\ell$ is eventually periodic with period $6$. If the root limit differs from $\rho$, or the period is not $6$, the central claim fails.

Watch

Extended reading notes

Core claim

The central claim is that for every node $i$ of any finite directed multigraph, the sequence $(a_i(\ell))^{1/\ell}$ converges, and its limit $\delta(i)$ is the largest real eigenvalue of the adjacency matrix of $U(i)$. This is proved first for strongly connected graphs, using the decomposition of $a_i(\ell)$ into a finite sum of polynomials times powers of eigenvalues and the Cesàro-average form of the Perron–Frobenius theorem to show that the dominant spectral terms do not cancel in the aggregate walk count. The general case follows by the Upstream Principle: a lower bound on walk counts transfers from any upstream node to the node in question, so the branching ratio is the maximum of the branching ratios of the strongly connected components that feed into $i$.

Load-bearing premise

The proof relies on counting all walks that end at a node, summed over every possible starting node, so that the dominant eigenvalue contributions cannot cancel; if one fixed the starting node, the walk count could be zero for infinitely many lengths and the root limit might not exist.

Editorial extensions

If this is right

  • Every node has a well-defined branching ratio, even when the ratio $a_i(\ell+1)/a_i(\ell)$ fails to converge, as in the three-step doubling example.
  • The branching ratio is computable by linear algebra: it is the Perron eigenvalue of the upstream subnetwork, not of the whole graph.
  • Nodes in the same strongly connected component have the same branching ratio, because their upstream subnetworks coincide.
  • If the upstream subnetwork is acyclic the branching ratio is $0$, matching the convention that finite input trees grow at rate zero.
  • The asymptotic shape of $a_i(\ell)$ is periodic in $\ell$ with period equal to the lcm of the periods of the dominant strongly connected components; the constant prefactor becomes a polynomial in the general reducible case.

Reading between the lines

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

  • Readers working with weighted or continuous-time networks can expect the same theorem to hold for non-negative real weights, since the Perron–Frobenius and decomposition arguments do not use integrality of edge multiplicities.
  • The asymptotic periodic refinement suggests that in biological networks with several upstream modules, the branching ratio alone is too coarse: short-time walk counts will oscillate with period $g$ even though the root limit is stable.
  • A practical numerical shortcut follows: compute $\rho(i)$ directly from the upstream adjacency matrix instead of simulating walks; the subdominant spectral gap controls the error.
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.

Referee Report

3 major / 4 minor

Summary. The paper defines the branching ratio δ(i) of a node i in a finite directed multigraph as the root-limit lim_ℓ (a_i(ℓ))^{1/ℓ} of the number of walks terminating at i, and claims that this limit always exists and equals the Perron eigenvalue ρ(i) of the upstream subnetwork U(i). The proof proceeds by an upper bound from the generalized eigenspace decomposition, a lower bound obtained first for strongly connected graphs via Perron–Frobenius theory and a Cesàro-average argument, and then an Upstream Principle to pass to the general case. The paper also derives asymptotic refinements: in the irreducible case it asserts a_i(ℓ) ∼ C_r ρ^ℓ with constants depending on ℓ modulo the period, and in the general case it asserts a_i(ℓ) ∼ R_s(ℓ)ρ^ℓ with polynomials depending on ℓ modulo an lcm of periods. Motivation is drawn from biological networks and distributed systems.

Significance. If the main theorem is correct, the paper gives a clean and useful characterization: the branching ratio is a Perron eigenvalue of a canonically defined subgraph, reducing its computation to linear algebra. The definition is made independently of the eigenvalue conclusion, no parameters are fitted, and the Upstream Principle is a nice reduction. The asymptotic refinements in Section 8 are also potentially useful. However, the proof of the lower bound in the strongly connected case has a genuine gap, and two statements in Section 8 are internally contradicted by the paper's own examples. These issues are load-bearing for the claimed theorems and require substantive repair, although the underlying results appear likely to be true and fixable within the manuscript's framework.

major comments (3)
  1. [Section 6, proof of Theorem 6.1, around Eqs. (6.22)–(6.24)] The proof establishes only that S1(ℓ) is not identically zero. Since S1 is a finite sum c_k ζ^{kℓ}ρ^ℓ, it is a quasi-polynomial, and a nonzero quasi-polynomial can vanish on an entire residue class, for example 1 + (−1)^ℓ. The Cesàro-average contradiction rules out S1 ≡ 0 globally, not S1 ≡ 0 on a single residue class modulo h. Therefore the inference that 'there exists an eventually positive polynomial Q(ℓ)' with a_i(ℓ) ≥ Q(ℓ)ρ^ℓ does not follow. A per-residue argument using the cyclic class structure, or Perron–Frobenius applied to A^h, is needed. Because Theorem 7.2 inherits the lower bound through the Upstream Principle, the existence half of the main result is not proved as written.
  2. [Section 8.1, Theorem 8.1] The assertion that the constants C_r are independent of i is false and is contradicted by the paper's own Example 1.1. That example is strongly connected and aperiodic (h = 1), and Eq. (1.2) gives a_1(ℓ) ∼ (1/√5)φ^ℓ while a_2(ℓ) ∼ (φ/√5)φ^ℓ, so the constants differ by node. Corollary 8.2 explicitly states that C may depend on i. The proof's appeal to the Upstream Principle is insufficient: U(i) = G for all i gives the same spectral data, but not the same coefficient of the Perron projection onto the i-th coordinate. Theorem 8.1 should be corrected to C_r = C_r(i), or the independence claim removed.
  3. [Section 8.2, proof of Theorem 8.3, final paragraph] The sentence claiming that the Upstream Principle implies the polynomials R_k are the same for all nodes in the same SCC does not follow and is false by the same example: nodes 1 and 2 of Example 1.1 lie in the same strongly connected component and have different asymptotic constants. Equality of the upstream subnetwork U(i) = U(j) does not imply equality of the i-th and j-th coordinates of the generalized-eigenvector expansion of u. The statement 'but are the same for all nodes in the same SCC of G' should be removed or replaced by an explicit coordinate-wise computation.
minor comments (4)
  1. [Example 4.4, Eq. (4.19)] All four displayed cases are labelled ℓ ≡ 0 (mod 4), which is presumably a typo for residues 0, 1, 2, 3; additionally the four expressions do not appear to match the claimed formula a_6(ℓ) = ⌈ℓ/4⌉ for the included values. Please correct the residue labels and verify the constants.
  2. [Example 4.6] The lines 'a_2(ℓ) = 0' and 'a_2(ℓ) = 2' appear to be typos. For the displayed adjacency matrix, node 2 has a self-loop and node 3 has no incoming edges, so the expected values are a_1(ℓ) = 3·2^ℓ, a_2(ℓ) = 2 for ℓ ≥ 1, and a_3(ℓ) = 0 for ℓ ≥ 1.
  3. [Section 3.2, after Eq. (3.17)] The cross-reference 'As in Lemma 3.16' should be 'Lemma 3.6'.
  4. [Lemma 3.6 and Remark 3.9] Lemma 3.6 states that the polynomial P_λ(ℓ) is over R and 'clearly must be eventually positive', but the construction gives a complex polynomial. Remark 3.9 later addresses real and imaginary parts, but the wording in the lemma should be corrected for consistency.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the branching ratio is defined independently as a root limit and its equality with the Perron eigenvalue is derived from standard spectral arguments, not assumed.

full rationale

The derivation chain is self-contained. Definition 3.2 fixes δ(i) as the root limit of the walk count a_i(ℓ), while ρ(i) is separately defined in Definition 3.3 as the Perron eigenvalue of the upstream subnetwork U(i); the paper's central work is to prove these coincide (Theorems 6.1 and 7.2). That proof uses Lemma 3.5 to convert matching polynomial upper and lower bounds into the root limit, Lemma 3.7 for the upper bound via the Jordan–Chevalley decomposition of B(i), and the Cesàro-average part of Perron–Frobenius plus the Upstream Principle for the lower bound. No parameter is fitted to data and no 'prediction' is renamed from an input: the examples are explicit computations, not tuned outputs. Self-citations to [7,8,18,25,31] appear only as background on fibrations, balanced colourings, and input trees, and are not premises of the branching-ratio theorem. The possible gap noted by a skeptic—that non-identically-zero S1 does not by itself force a per-residue eventually positive lower bound in Theorem 6.1—is a correctness issue in the proof, not a circularity: the conclusion δ(i)=ρ(i) is not assumed by the definition or imported from the authors' prior work. Therefore the paper earns a circularity score of 0.

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

The proof relies only on standard linear algebra and graph theory. No parameters are fitted to data and no new entities are postulated.

assumptions (4)
  • standard math Perron-Frobenius theorem for irreducible nonnegative matrices (Theorem 5.2)
    Provides the Perron eigenvalue, its positivity, and the Cesaro average formula used throughout Section 6.
  • standard math Jordan-Chevalley decomposition of linear operators
    Used in Lemma 3.6 to express a_i(l) as a sum of polynomials times eigenvalues to the l-th power.
  • standard math Condensation of a finite digraph is acyclic
    Invoked in Lemma 7.3 to justify the block upper triangular form of the upstream adjacency matrix.
  • standard math Walks can be concatenated; the number of walks of length l ending at i is (uA^l)_i
    Defines the central quantity and supports the Upstream Principle (Proposition 3.12).

how reviews work

0 comments
Cite this review

Pith. "Pith review of Branching Ratios of Input Trees for Directed Multigraphs." pith.science (2026). https://pith.science/paper/RDAIALID

@misc{pith2026250106812,
  author       = {Pith},
  title        = {Pith review of: Branching Ratios of Input Trees for Directed Multigraphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RDAIALID}},
  note         = {Machine review of arXiv:2501.06812}
}
read the original abstract

We define the branching ratio of the input tree of a node in a finite directed multigraph, prove that it exists for every node, and show that it is equal to the largest eigenvalue of the adjacency matrix of the induced subgraph determined by all upstream nodes. This real eigenvalue exists by the Perron-Frobenius Theorem for non-negative matrices. We motivate our analysis with simple examples, obtain information about the asymptotics for the limit growth of the input tree, and establish other basic properties of the branching ratio.

Figures

Figures reproduced from arXiv: 2501.06812 by the authors.

Figure 1
Figure 1. Fibonacci circuit. Its adjacency matrix is A =  0 1 1 1  , and the eigenvalues of A are 1± √ 5 2 , so the spectral radius (maximal or Perron eigenvalue) is 1+√ 5 2 = ϕ, the golden ratio. We focus on walks through this network, which are sequences of edges joined head to tail. The length of a walk is the number of edges in the sequence. We ask: How many walks of length ℓ are there that terminate at a given node i ∈… view at source ↗
Figure 2
Figure 2. Input trees for the Fibonacci circuit, up to level [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Left: Fibonacci circuit feeding forward to a single node with two self-loops. Right: Single node with two self-loops feeding forward to a Fibonacci circuit. Left Network: The SCCs are {1, 2} and {3}. The natural ordering on {1, 2, 3} is compatible with the feedforward structure. As a consequence, the adjacency matrix is A =   1 1 0 1 0 1 0 0 2   8 [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figures from the paper (7 more)
Figure 4
Figure 4. Figure 4: Left: A simple n-cycle. The adjacency matrix is A =        0 1 0 · · · 0 0 0 0 1 · · · 0 0 . . . . . . . . . . . . . . . . . . 0 0 0 · · · 0 1 1 0 0 · · · 0 0        17 [PITH_FULL_IMAGE:figures/full_fig_p017_4.png]
Figure 5
Figure 5. Figure 5: Left: A directed graph with six nodes. Right: Input tree of node 1. The sequence a1(ℓ) is: 1, 2, 2, 2, 4, 4, 4, 8, 8, 8, . . . The ratios a1(ℓ + 1)/a1(ℓ) are: 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, . . . which fails to converge. The adjacency matrix of the graph is: A =    …
Figure 6
Figure 6. Figure 6: Network whose adjacency matrix is reducible. [PITH_FULL_IMAGE:figures/full_fig_p019_6.png]
Figure 7
Figure 7. Figure 7: An 8-node reducible network with h = 4. 20 [PITH_FULL_IMAGE:figures/full_fig_p020_7.png]
Figure 8
Figure 8. Figure 8: An n-node polycycle. Let M = m1m2 · · · mn. It is easy to see that if p ≥ 0, 0 ≤ q ≤ n − 1, then a1(pn + q) = Mpm1 · · · mq 21 [PITH_FULL_IMAGE:figures/full_fig_p021_8.png]
Figure 9
Figure 9. Figure 9: 3-node network with distinct branching ratios. [PITH_FULL_IMAGE:figures/full_fig_p022_9.png]
Figure 10
Figure 10. Figure 10: Node with two upstream SCCs. Suppose that H1 has period h1 and H2 has period h2. Any walk terminating at i lies entirely within one of H1, H2, except for the final edge to vertex i. Therefore ai(ℓ) = a 1 j1 (ℓ − 1) + a 2 j2 (ℓ − 1) where, for m = 1, 2, the quantity a …

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

33 extracted references · 32 canonical work pages

  1. [1]

    Abdi and N

    A. Abdi and N. Olver. MA 431 Spectral Graph Theory, ahmadabdi.com/ma431/Lecture 1.pdf

    work page

  2. [2]

    D. Angluin. Local and global properties in networks of processors, Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing (STOC ’80), Association for Computing Machinery 1980, 82–93

    work page 1980

  3. [3]

    E.A. Bender. Asymptotic methods in enumeration, SIAM Rev.16 (1974) 485–515

    work page 1974

  4. [4]

    C. Berge. Graphs and Hypergraphs, North-Holland, Amsterdam 1973. 32

    work page 1973

  5. [5]

    Boldi, S

    P. Boldi, S. Shammah, S. Vigna, B. Codenotti, P. Gemmell, and J. Simon. Symmetry Breaking in Anonymous Networks: Characterizations. Proceedings of ISTCS, page 16–26, 1996

    work page 1996

  6. [6]

    Boldi and S

    P. Boldi and S. Vigna. Computing Vector Functions on Anonymous Networks. Proceedings of the Sixteenth Annual ACM Symposium on Principles of Distributed Computing, page 277, 1997

    work page 1997

  7. [7]

    Boldi and S

    P. Boldi and S. Vigna. Fibrations of graphs, Discrete Math.243 (2002) 21–66

    work page 2002

  8. [8]

    Boldi and S

    P. Boldi and S. Vigna. Universal dynamic synchronous self–stabilization, Distributed Computing 15 (2002) 137–153. Springer

    work page 2002

Show all 33 references
  1. [9]

    Boreviˇ c and I.R.ˇSafareviˇ c.Number Theory, Academic Press, New York 1966

    Z.I. Boreviˇ c and I.R.ˇSafareviˇ c.Number Theory, Academic Press, New York 1966

    1966

  2. [10]

    R. Bronson. Matrix Methods: An Introduction, Academic Press, New York 1970

    1970

  3. [11]

    Brualdi and H.J

    R.A. Brualdi and H.J. Reiser. Combinatorial Matrix Theory, Cambridge University Press, Cam- bridge 1992

    1992

  4. [12]

    R.A. Brualdi. Spectra of digraphs, Lin. Alg. & Appl.432 (2010) 2181–2213

    2010

  5. [13]

    Buckley and F

    F. Buckley and F. Harary, Distance in Graphs, Addison Wesley, Reading 1990

    1990

  6. [14]

    S.K. Butler. Eigenvalues and Structures of Graphs, PhD Thesis, U. California San Diego 2008

    2008

  7. [15]

    Frobenius

    G. Frobenius. Ueber Matrizen aus nicht negativen Elementen, Sitz. K¨ oniglich Preuss. Akad. Wiss. (May 1912) 456–477

    1912

  8. [16]

    Gantmacher

    F.R. Gantmacher. The Theory of Matricesvol. 2, AMS Chelsea Publishing, New York 2000

    2000

  9. [17]

    Godsil and G.F

    C. Godsil and G.F. Royle. Algebraic Graph Theory, Graduate Texts in Math. 207, Springer, New York 2001

    2001

  10. [18]

    Golubitsky and I

    M. Golubitsky and I. Stewart. Dynamics and Bifurcation in Networks, SIAM, Philadelphia 2023

    2023

  11. [19]

    Humphreys

    J.E. Humphreys. Introduction to Lie Algebras and Representation Theory, Graduate Texts in Math. 9, Springer, New York 1972

    1972

  12. [20]

    Kitchens

    B. Kitchens. Symbolic Dynamics, Springer, Berlin 1998

    1998

  13. [21]

    Lancaster and M

    P. Lancaster and M. Tismenetsky. The Theory of Matrices, Academic Press, Orlando 1985

    1985

  14. [22]

    S. Lang. Algebraic Number Theory, Springer, New York 2000

    2000

  15. [23]

    Leifer, F

    I. Leifer, F. Morone, S.D.S. Reis, J.S. Andrade Jr., M. Sigman, and H.A. Makse. Circuits with broken fibration symmetries perform core logic computations in biological networks, PLOS Comp. Biol. 16 1007776 (2020)

    2020

  16. [24]

    D. Lind. The entropies of topological Markov shifts and a related class of algebraic integers, Ergodic Theory Dyn. Sys.4 (1984) 283–300

    1984

  17. [25]

    Makse, P

    H.A. Makse, P. Boldi, F. Sorrentino, and I. Stewart, Symmetries of Living Systems, Cambridge University Press, to appear 2025

    2025

  18. [26]

    C. Meyer. Matrix Analysis and Applied Linear Algebra, SIAM, Philasdelphia 2000. 33

    2000

  19. [27]

    Morone, I

    F. Morone, I. Leifer, and H.A. Makse. Fibration symmetries uncover the building blocks of biolog- ical networks, Proc. Nat. Acad. Sci.117 (2020) 8306– 8314

    2020

  20. [28]

    Morone and H.A

    F. Morone and H.A. Makse. Symmetry group factorization reveals the structure-function relation in the neural connectome of Caenorhabditis elegans, Nature Communications(2019) 10 4961; doi: 10.1038/s41467-019-12675-8

    2019 doi

  21. [29]

    O. Perron. Zur Theorie der Matrices, Math. Ann. 64 (1907) 248–263

    1907

  22. [30]

    A.J. Schwenk. Computing the characteristic polynomial of a graph, in: R.A. Bari and F. Harary (eds.), Graphs and Combinatorics, Lect. Notes Math. 406, Springer, Berlin 1974, 153–172

    1974

  23. [31]

    I. Stewart. The lattice of balanced equivalence relations of a coupled cell network, Math. Proc. Camb. Phil. Soc.143 (2007) 165–183

    2007

  24. [32]

    W.T. Tutte. Graph Theory, Encyclopaedia of Mathematics and Its Applications (ed. G.-C. Rota) 21, Addison-Wesley, Menlo Park 1984

    1984

  25. [33]

    en.wikipedia.org/wiki/Perron-Frobenius theorem (7 June 2024)

    Wikipedia. en.wikipedia.org/wiki/Perron-Frobenius theorem (7 June 2024). 34

    2024

Pith tools

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