pith. sign in

arxiv: 2410.10337 · v3 · submitted 2024-10-14 · 🧮 math.CO

Entropy and the growth rate of universal covering trees

Idan Eisner , Shlomo Hoory This is my paper

Pith reviewed 2026-05-23 18:57 UTC · model grok-4.3

classification 🧮 math.CO
keywords universal covering treenon-backtracking random walkgrowth rateentropy rategraph parametersvariance of bits
0
0 comments X

The pith

A checkable condition decides exactly when graph cover growth equals non-backtracking entropy rate.

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

The paper studies the relation between ρ, the growth rate of a graph's universal covering tree, and Λ, the entropy rate of its non-backtracking random walk. It is already known that ρ is always at least Λ. The authors derive a simple necessary and sufficient condition for when equality holds. They also prove that the variance of random bits consumed by an ℓ-step non-backtracking walk stays bounded when equality holds and grows linearly with ℓ when it fails. The equality case yields infinitely many non-trivial examples.

Core claim

For an undirected graph G, ρ(G) equals Λ(G) if and only if a certain easy-to-check condition holds; the variance of the number of random bits used by a length-ℓ non-backtracking random walk is then O(1) under equality and Ω(ℓ) otherwise.

What carries the argument

The necessary and sufficient condition on the graph for equality between the universal covering tree growth rate ρ and the non-backtracking walk entropy rate Λ.

If this is right

  • When the condition holds, the number of random bits used by a non-backtracking walk has bounded variance independent of length.
  • When the condition fails, that variance grows linearly with the length of the walk.
  • There exist infinitely many non-trivial graphs for which ρ equals Λ.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The condition supplies an explicit way to construct or recognize graphs whose covering-tree growth matches their walk entropy.
  • The variance distinction offers a statistical test for whether equality holds on a given graph.
  • The same variance analysis may extend to other walk models on the same graphs.

Load-bearing premise

The already-known fact that ρ(G) is at least Λ(G) for every undirected graph, together with the standard definitions of those two parameters.

What would settle it

A concrete graph that satisfies the stated condition yet has ρ not equal to Λ, or that fails the condition yet has ρ equal to Λ.

Figures

Figures reproduced from arXiv: 2410.10337 by Idan Eisner, Shlomo Hoory.

Figure 1
Figure 1. Figure 1: Three graphs with ρ = Λ that are not regular, bipartite bi-regular, or obtained from such graphs by replacing each edge by a length k path. It can be verified that the suspended path condition holds with Λ equals √ √ 2, 2 and 2 for the graphs (a), (b) and (c), respectively. The third result, regards the random variable Rℓ counting the number of random bits consumed by a length ℓ NBRW starting from the stat… view at source ↗
Figure 2
Figure 2. Figure 2: A cycle with a vertex of degree more than two. [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: K4 minus an edge. Next, we regard the random variable Rℓ counting the number of random bits used by a length ℓ NBRW starting from the stationary distribution on the K4 minus an edge graph, as defined in the beginning of Subsection 5.1. By Corollary 11, the expected number of random bits per step is E[Rℓ/ℓ] = log2 Λ = 0.6, while log2 ρ = limℓ→∞ 1 ℓ log2 E[2Rℓ ] ≈ 0.605. This can be demonstrated by an experi… view at source ↗
Figure 4
Figure 4. Figure 4: The number of bits per step, Rℓ/ℓ, for the length ℓ = 1000 NBRW on K4 minus an edge. The black dots are the exact PDF, the yellow line is a best-fit normal distribution, the green line is at log2 Λ and the orange line is at log2 ρ which is the limit on ℓ of 1 ℓ log2 E [PITH_FULL_IMAGE:figures/full_fig_p019_4.png] view at source ↗
read the original abstract

This work studies the relation between two graph parameters, $\rho$ and $\Lambda$. For an undirected graph $G$, $\rho(G)$ is the growth rate of its universal covering tree, while $\Lambda(G)$ is a weighted geometric average of the vertex degree minus one, corresponding to the rate of entropy growth for the non-backtracking random walk (NBRW). It is well known that $\rho(G) \geq \Lambda(G)$ for all graphs, and that graphs with $\rho=\Lambda$ exhibit some special properties. In this work we derive an easy to check, necessary and sufficient condition for the equality to hold. Furthermore, we show that the variance of the number of random bits used by a length $\ell$ NBRW is $O(1)$ if $\rho = \Lambda$ and $\Omega(\ell)$ if $\rho > \Lambda$. As a consequence we exhibit infinitely many non-trivial examples of graphs with $\rho = \Lambda$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript studies the relationship between ρ(G), the growth rate of the universal covering tree of an undirected graph G, and Λ(G), a weighted geometric average of (degree minus one) that gives the entropy growth rate of the non-backtracking random walk. Building on the known inequality ρ(G) ≥ Λ(G), the authors derive a necessary and sufficient condition for equality ρ = Λ. They further establish that the variance of the number of random bits used by a length-ℓ non-backtracking random walk is O(1) when ρ = Λ and Ω(ℓ) when ρ > Λ, and use this to construct infinitely many non-trivial graphs achieving equality.

Significance. If the derived condition is necessary and sufficient and the variance dichotomy holds, the work supplies a practical, checkable criterion for identifying graphs where covering-tree growth matches NBRW entropy rate, together with a probabilistic characterization via bit-usage variance. The explicit construction of infinitely many examples demonstrates that the equality case is realizable beyond trivial graphs and strengthens the result. The paper ships a parameter-free derivation conditioned only on the standard inequality and definitions, which is a strength.

minor comments (2)
  1. The abstract states the variance result for the number of random bits, but the precise definition of 'number of random bits' (e.g., whether it is the cumulative entropy or the support size of the step distribution) should be stated explicitly in the introduction or §2 to avoid ambiguity for readers.
  2. The construction of infinitely many examples is mentioned as a consequence; a brief indication of the family of graphs (e.g., regular vs. biregular, or a recursive construction) in the abstract or early in the introduction would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive report, accurate summary of the contributions, and recommendation of minor revision. The significance assessment correctly highlights the checkable criterion for equality and the probabilistic characterization via variance.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper presents a necessary-and-sufficient condition for ρ(G)=Λ(G) that is derived from the already-established inequality ρ≥Λ together with the standard definitions of universal-cover growth rate and the weighted geometric mean for NBRW entropy. The variance dichotomy for the bit-count of an ℓ-step NBRW and the construction of infinitely many examples follow directly from this condition without any reduction to fitted parameters, self-citation chains, or ansatzes smuggled via prior work. No load-bearing step equates a claimed derivation to its own inputs by construction, so the derivation chain remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on the pre-existing inequality ρ(G) ≥ Λ(G) for undirected graphs and on standard definitions of covering-tree growth and non-backtracking entropy; no free parameters, invented entities, or ad-hoc axioms are mentioned in the abstract.

axioms (1)
  • domain assumption ρ(G) ≥ Λ(G) holds for every undirected graph G
    Stated as well-known background fact on which the equality condition is built.

pith-pipeline@v0.9.0 · 5693 in / 1184 out tokens · 18128 ms · 2026-05-23T18:57:13.845887+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

16 extracted references · 16 canonical work pages

  1. [1]

    Aldous and J

    D. Aldous and J. A. Fill. Reversible markov chains and random walks on graphs, 2002. Unfinished monograph, recompiled 2014, available at http://www.stat.berkeley.edu/~aldous/RWG/book.html

    work page 2002

  2. [2]

    N. Alon, I. Benjamini, E. Lubetzky, and S. Sodin. Non-backtracking ran- dom walks mix faster. Communications in Contemporary Mathematics , 9(04):585–603, 2007

    work page 2007

  3. [3]

    N. Alon, S. Hoory, and N. Linial. The moore bound for irregular graphs. Graphs and Combinatorics , 18(1):53–57, 2002

    work page 2002

  4. [4]

    Angel, J

    O. Angel, J. Friedman, and S. Hoory. The non-backtracking spectrum of the universal cover of a graph. Transactions of the American Mathematical Society, 367(6):4287–4318, 2015

    work page 2015

  5. [5]

    Ben-Hamou and J

    A. Ben-Hamou and J. Salez. Cutoff for nonbacktracking random walks on sparse random graphs. The Annals of Probability , 45(3):1752–1770, 2017

    work page 2017

  6. [6]

    Conchon-Kerjan

    G. Conchon-Kerjan. Sparse random graphs: from local specifications to global phenomena. PhD thesis, Universit´ e de Paris/Universit´ e Paris Diderot (Paris 7), 2021

    work page 2021

  7. [7]

    Conchon-Kerjan

    G. Conchon-Kerjan. Cutoff for random lifts of weighted graphs. Annals of Probability, 50(1):304–338, 2022

    work page 2022

  8. [8]

    Dembo and O

    A. Dembo and O. Zeitouni. Large deviations techniques and applications , volume 38. Springer Science & Business Media, 2009

    work page 2009

  9. [9]

    C. Glover. The Non-Backtracking Spectrum of a Graph and Non- Backtracking PageRank. Brigham Young University, 2021

    work page 2021

  10. [10]

    S. Hoory. The size of bipartite graphs with a given girth. Journal of Combinatorial Theory, Series B , 86(2):215–220, 2002

    work page 2002

  11. [11]

    S. Hoory. On the girth of graph lifts. arXiv preprint arXiv:2401.01238 , 2024

    work page arXiv 2024

  12. [12]

    R. A. Horn and C. R. Johnson. Matrix analysis . Cambridge university press, 2nd edition, 2012

    work page 2012

  13. [13]

    J. F. Kingman. A convexity property of positive matrices. The Quarterly Journal of Mathematics , 12(1):283–284, 1961. 21

    work page 1961

  14. [14]

    Lubetzky and Y

    E. Lubetzky and Y. Peres. Cutoff on all ramanujan graphs. Geometric and Functional Analysis, 26(4):1190–1216, 2016

    work page 2016

  15. [15]

    Lubetzky and A

    E. Lubetzky and A. Sly. Cutoff phenomena for random walks on random regular graphs. Duke Mathematical Journal , 153(3):475–510, 2010

    work page 2010

  16. [16]

    R. D. Nussbaum. Convexity and log convexity for the spectral radius. Linear Algebra and its Applications , 73:59–122, 1986. 22

    work page 1986