Recognition: unknown
On the number of distinct spanning trees in pseudorandom graphs
Pith reviewed 2026-05-14 20:16 UTC · model grok-4.3
The pith
Every sufficiently expanding pseudorandom graph has at least (α−ε)^n distinct unlabelled spanning trees.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
For every 0 < ε < α there exist constants C and d0 such that every (n,d,λ)-graph with d ≥ d0 and d/λ ≥ C contains at least (α − ε)^n distinct unlabelled spanning trees.
What carries the argument
The (n,d,λ)-graph: a d-regular graph on n vertices whose adjacency matrix has second-largest eigenvalue at most λ; the ratio d/λ measures expansion and is used to lower-bound the tree count.
If this is right
- The exponential number of spanning trees persists in any dense graph whose expansion ratio exceeds a fixed threshold.
- The lower bound depends only on the expansion parameter and not on additional global structure such as vertex-transitivity.
- For any fixed ε the threshold C can be chosen independently of n once d is sufficiently large.
- The result recovers Otter's theorem when the graph is the complete graph, which has d = n−1 and λ = 1.
Where Pith is reading between the lines
- Random d-regular graphs with d growing and λ bounded should satisfy the hypothesis for large enough d.
- The same expansion condition may yield exponential lower bounds for the number of other spanning subgraphs such as Hamilton paths.
- Quantitative improvements to the dependence of C on ε would immediately give explicit constants for random regular graphs.
Load-bearing premise
The graph must satisfy the (n,d,λ) pseudorandom condition with d/λ large enough for the expansion to control the tree enumeration.
What would settle it
An explicit (n,d,λ)-graph with d/λ arbitrarily large yet strictly fewer than (α−ε)^n distinct unlabelled spanning trees.
Figures
read the original abstract
A celebrated result of Otter says the number of distinct unlabelled spanning trees in $K_n$ is $\alpha^n$ up to subexponential factors for an absolute constant $\alpha>0$. In this note, we prove that for every $0<\varepsilon<\alpha$, there are constants $C$ and $d_0$ such that every $(n,d,\lambda)$-graph with $d\geq d_0$ and $d/\lambda \geq C$ has at least $(\alpha-\varepsilon)^n$ distinct unlabelled spanning trees.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper extends Otter's theorem by proving that for every 0 < ε < α, there exist constants C and d0 such that every (n,d,λ)-graph with d ≥ d0 and d/λ ≥ C has at least (α − ε)^n distinct unlabelled spanning trees. The argument obtains a lower bound on the number of labeled spanning trees via the matrix-tree theorem with eigenvalue control from the pseudorandom hypothesis, then partitions them into isomorphism classes by bounding automorphisms per class and comparing to the Otter generating function.
Significance. If the result holds, it shows that the exponential growth rate α^n of distinct spanning trees is robust under the (n,d,λ) pseudorandom condition once d/λ is large enough to control short cycles and walks. This provides a quantitative extension of a classical enumeration result to expander-like graphs using only standard spectral tools and generating-function comparison, without additional structure.
major comments (2)
- [Section 3] The section deriving the labeled-tree lower bound via the matrix-tree theorem must make explicit how the d/λ ≫ 1 hypothesis controls the contribution of walks of length up to n that could inflate the determinant; without a quantitative error term here, it is unclear whether the base remains strictly above α − ε.
- [Section 4] In the isomorphism-class partitioning argument, the bound on |Aut(T)| for a tree T on n vertices is used to divide the labeled count; this step requires a uniform upper bound on the number of labeled copies per unlabelled tree that is independent of the host graph's local structure beyond the pseudorandom assumption.
minor comments (2)
- [Introduction] The introduction should state the precise dependence of C and d0 on ε and α rather than treating them as existential constants only.
- [Abstract and Theorem 1.1] Notation for the second eigenvalue λ should be consistent between the abstract and the statement of the main theorem.
Simulated Author's Rebuttal
We thank the referee for the careful review and constructive comments. We address each major comment below and will incorporate the necessary clarifications in the revised manuscript.
read point-by-point responses
-
Referee: [Section 3] The section deriving the labeled-tree lower bound via the matrix-tree theorem must make explicit how the d/λ ≫ 1 hypothesis controls the contribution of walks of length up to n that could inflate the determinant; without a quantitative error term here, it is unclear whether the base remains strictly above α − ε.
Authors: We will revise Section 3 to include an explicit quantitative error bound. Specifically, we will show that under the assumption d/λ ≥ C for sufficiently large C, the contribution from walks of length at most n in the determinant expansion is at most (ε/2)^n times the main term, ensuring the lower bound on the number of labeled spanning trees remains at least (α - ε/2)^n or similar, which after division yields the desired (α - ε)^n for unlabelled trees. This uses standard bounds on the number of closed walks from the spectral gap. revision: yes
-
Referee: [Section 4] In the isomorphism-class partitioning argument, the bound on |Aut(T)| for a tree T on n vertices is used to divide the labeled count; this step requires a uniform upper bound on the number of labeled copies per unlabelled tree that is independent of the host graph's local structure beyond the pseudorandom assumption.
Authors: The partitioning relies on the combinatorial bound that each unlabelled tree corresponds to at most n! labeled trees, since |Aut(T)| ≥ 1. This upper bound is independent of the host graph and holds for any graph on n vertices. We will add a sentence in Section 4 clarifying that this step uses only this graph-independent combinatorial fact, with the pseudorandomness used only to lower bound the labeled count. revision: yes
Circularity Check
No significant circularity detected
full rationale
The paper derives a lower bound on the number of distinct unlabelled spanning trees by applying the matrix-tree theorem to obtain a lower bound on labeled spanning trees via eigenvalue bounds on the adjacency matrix of an (n,d,λ)-graph, followed by a standard automorphism-counting argument to partition into isomorphism classes and recover Otter's constant α up to an additive ε via generating-function comparison. None of these steps reduce by construction to a fitted parameter, a self-citation chain, or a renamed input; the d/λ ≫ 1 hypothesis supplies independent expansion control that is not presupposed in the target count. Otter's theorem is invoked as an external known result, not as a self-citation. The derivation is therefore self-contained against external benchmarks.
Axiom & Free-Parameter Ledger
axioms (2)
- standard math Existence of Otter's constant α > 0 such that the number of unlabelled spanning trees in K_n is α^n up to subexponential factors.
- domain assumption Standard properties of (n,d,λ)-graphs: every vertex degree d and every pair of disjoint sets has edge count close to the expected value controlled by λ.
Reference graph
Works this paper leans on
-
[1]
N. Alon, M. Krivelevich, and B. Sudakov, Embedding nearly-spanning bounded degree trees , Combinatorica 27 (2007), no. 6, 629–644
work page 2007
-
[2]
V. Bitonti, L. Michel, and A. Scott, Anticoncentration of random spanning trees in graphs with l arge minimum degree, 2026
work page 2026
-
[3]
Cayley, A theorem on trees , Quarterly Journal of Pure and Applied Mathematics 23 (1889), 376–378
A. Cayley, A theorem on trees , Quarterly Journal of Pure and Applied Mathematics 23 (1889), 376–378
-
[4]
J. Hyde, N. Morrison, A. Müyesser, and M. Pavez-Signé, Spanning trees in pseudorandom graphs via sorting networks , Proceedings of the American Mathematical Society 153 (2025), no. 06, 2353–2367
work page 2025
-
[5]
M. Krivelevich and B. Sudakov, Pseudo-random graphs , More sets, graphs and numbers, Bolyai Soc. Math. Stud., vol. 15, Springer, Berlin, 2006, pp. 199–262
work page 2006
-
[6]
Lee, Anticoncentration of random spanning trees in almost regul ar graphs , 2026
H. Lee, Anticoncentration of random spanning trees in almost regul ar graphs , 2026
work page 2026
-
[7]
Otter, The number of trees , Ann
R. Otter, The number of trees , Ann. of Math. (2) 49 (1948), 583–599
work page 1948
-
[8]
Pavez-Signé, Spanning trees in the square of pseudorandom graphs , 2023
M. Pavez-Signé, Spanning trees in the square of pseudorandom graphs , 2023. Institute of Science and Technology Austria, Klosterneubu rg, 3400, Austria. Email address : yiting.wang@ist.ac.at 3
work page 2023
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.