Pith. sign in

REVIEW 1 minor 19 references

The size of the spanning-tree spectrum of simple graphs

T0 review · 0 major / 1 minor · reviewed 2026-06-29 · grok-4.3

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

Pith's one-line read The number of distinct spanning-tree counts for simple graphs on n vertices grows at least like exp(c n log n) for any fixed c below 1/4.

desk verdict The paper proves the exp(c n log n) lower bound on the number of distinct spanning-tree counts for simple n-vertex graphs and resolves the Chan-Kontorovich-Pak conjecture. read the letter →

arxiv 2605.25088 v1 pith:FG4RPMB4 submitted 2026-05-24 math.CO

Vishesh Jain This is my paper · ORCID
classification math.CO
keywords spanningtreessimplegraphsdistinctvaluesexponentiallowerboundgraphspectrumSedláčekproblemenumerationof
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 establishes a lower bound on how many different numbers of spanning trees can appear among all simple graphs with a fixed number n of vertices. It shows that this number is at least exp(c n log n) for any constant c in (0, 1/4) and all large n. The bound matches the best possible order of growth up to the specific constant c. A sympathetic reader cares because the result gives a precise quantitative answer to a question posed in the late 1960s about the variety of spanning-tree counts.

What carries the argument

A sufficiently rich family of simple graphs on n vertices whose spanning-tree counts τ(G) realize many distinct values, separated by a counting argument.

What would settle it

An explicit family of simple graphs on some large n whose distinct τ(G) values number fewer than exp(c n log n) for a fixed c < 1/4.

Watch

Extended reading notes

Core claim

For every fixed 0 < c < 1/4, the number of distinct values of τ(G), as G ranges over simple graphs on n vertices, is at least exp(c n log n) for all sufficiently large n. This is optimal up to the choice of the constant c and resolves a conjecture of Chan-Kontorovich-Pak regarding a problem of Sedláček from the late 1960s.

Load-bearing premise

A large enough collection of simple graphs on n vertices exists whose spanning tree counts are all distinct.

Editorial extensions

If this is right

  • The spanning-tree spectrum of simple graphs on n vertices has size at least exp(c n log n).
  • The conjecture of Chan-Kontorovich-Pak on Sedláček's problem is confirmed.
  • The lower bound holds for every fixed c in (0, 1/4) and all sufficiently large n.
  • The result is asymptotically tight up to the constant factor in the exponent.

Reading between the lines

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

  • The same style of counting argument could be applied to other integer-valued graph invariants to obtain exponential lower bounds on their spectra.
  • The construction implies that the image of τ is dense enough in the integers to separate many graphs even under mild restrictions on edge density.
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.

Referee Report

0 major / 1 minor

Summary. The manuscript proves that for every fixed 0 < c < 1/4, the number of distinct values taken by τ(G), the number of spanning trees of G, as G ranges over all simple graphs on n vertices, is at least exp(c n log n) for all sufficiently large n. The result is stated to be optimal up to the constant c and resolves the Chan-Kontorovich-Pak conjecture on a problem of Sedláček.

Significance. If correct, the result supplies a near-optimal exponential lower bound on the size of the spanning-tree spectrum of simple graphs. It supplies a concrete, falsifiable quantitative statement that settles a conjecture from the late 1960s and demonstrates that the function τ takes many distinct values on the class of n-vertex simple graphs.

minor comments (1)
  1. [Abstract] The abstract and introduction could usefully include a one-sentence pointer to the main construction (e.g., the family of graphs used to realize the distinct τ-values) so that readers can immediately locate the key technical step.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive report and recommendation to accept the manuscript.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity detected

full rationale

The paper proves an exponential lower bound on the number of distinct spanning-tree counts τ(G) over simple n-vertex graphs via an explicit combinatorial construction of a sufficiently rich family of graphs whose τ values are shown to be distinct. No equations, parameters, or claims in the abstract or described argument reduce the target count to a fitted input, self-definition, or self-citation chain; the result is presented as resolving an external conjecture of Chan-Kontorovich-Pak without internal circular reduction.

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

Abstract-only review; no explicit free parameters, axioms, or invented entities are visible. The result is a pure existence lower bound on a counting function.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The size of the spanning-tree spectrum of simple graphs." pith.science (2026). https://pith.science/paper/FG4RPMB4

@misc{pith2026260525088,
  author       = {Pith},
  title        = {Pith review of: The size of the spanning-tree spectrum of simple graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FG4RPMB4}},
  note         = {Machine review of arXiv:2605.25088}
}
abstract

For a graph $G$, let $\tau(G)$ denote the number of spanning trees. We show that for every fixed $0 < c < 1/4$, the number of distinct values of $\tau(G)$, as $G$ ranges over simple graphs on $n$ vertices, is at least $\exp(c n \log n)$ for all sufficiently large $n$. This is optimal up to the choice of the constant $c$ and resolves a conjecture of Chan-Kontorovich-Pak regarding a problem of Sedl\'a\v{c}ek from the late 1960s.

Figures

Figures reproduced from arXiv: 2605.25088 by the authors.

Figure 1
Figure 1. A schematic of the multigraph construction. All multi-edges involve the distinguished root ρ. Lemma 2.6. Let s, t ≥ 1. Let A ∈ Z s×s , E ∈ Z s×t , G ∈ Z t×s , H ∈ Z t×t . Then det   A 0 E 0 A E G G H   = det(A) det  A E 2G H . Proof. Subtract the second block row from the first block row. This gives det   A 0 E 0 A E G G H   = det   A −A 0 0 A E G G H   . Then add the first block column to the second b… view at source ↗
Figure 2
Figure 2. A schematic of the simple graph Gw. The “anchor” star allows us to replace parallel root-edges from the multigraph construction: a path vertex joined to a1, . . . , ah serves as a replacement for h parallel edges to the root. Twin copies of the paths allow determinant factors to survive even in the presence of anchor vertices. on N = Nm,q = 4m + q − 1 vertices; see [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

19 extracted references · 2 canonical work pages

  1. [1]

    Noga Alon, Matija Bucić, and Lior Gishboliner,The spanning tree spectrum: improved bounds and simple proofs, arXiv preprint, 2025, arXiv:2503.23648 [math.CO]

    work page arXiv 2025

  2. [2]

    Jernej Azarija,Counting graphs with different numbers of spanning trees through the counting of prime partitions, Czechoslovak Mathematical Journal64(2014), 31–35

    2014

  3. [3]

    Jernej Azarija and Riste Škrekovski,Euler’s idoneal numbers and an inequality concerning minimal graphs with a prescribed number of spanning trees, Mathematica Bohemica138(2013), 121–131

    2013

  4. [4]

    Norman Biggs,Algebraic graph theory, 2nd ed., Cambridge University Press, 1993

    1993

  5. [5]

    6346, Springer, 2010, pp

    Kevin Buchin and André Schulz,On the number of spanning trees a planar graph can have, Algorithms – ESA 2010 (Berlin, Heidelberg), Lecture Notes in Computer Science, vol. 6346, Springer, 2010, pp. 110–121

    2010

  6. [6]

    Steve Butler,Eigenvalues of2-edge-coverings, Linear and Multilinear Algebra58(2010), 413–423

    2010

  7. [7]

    Steve Butler,Using twins and scaling to construct cospectral graphs for the normalized Laplacian, Electronic Journal of Linear Algebra28(2015), 54–68

    2015

  8. [8]

    THE SIZE OF THE SPANNING-TREE SPECTRUM OF SIMPLE GRAPHS 13

    Arthur Cayley,A theorem on trees, Quarterly Journal of Pure and Applied Mathematics23(1889), 376–378. THE SIZE OF THE SPANNING-TREE SPECTRUM OF SIMPLE GRAPHS 13

Show all 19 references
  1. [9]

    Swee Hong Chan, Alex Kontorovich, and Igor Pak,Spanning trees and continued fractions, arXiv preprint, 2024, arXiv:2411.18782 [math.CO]

    2024

  2. [10]

    Kevin Ford,The distribution of integers with a divisor in a given interval, Annals of Mathematics168(2008), 367–433

    2008

  3. [11]

    G. H. Hardy and E. M. Wright,An introduction to the theory of numbers, 5th ed., Oxford University Press, 1979

    1979

  4. [12]

    J. W. Moon,Counting labelled trees, Canadian Mathematical Monographs, no. 1, Canadian Mathematical Con- gress, Montreal, 1970

    1970

  5. [13]

    Ladislav Nebeský,On the minimum number of vertices and edges in a graph with a given number of spanning trees, Časopis pro pěstování matematiky98(1973), 95–97

    1973

  6. [14]

    Jiří Sedláček,On the spanning trees of finite graphs, Časopis pro pěstování matematiky91(1966), 221–227

    1966

  7. [15]

    Jiří Sedláček,On the number of spanning trees of finite graphs, Časopis pro pěstování matematiky94(1969), 217–222

    1969

  8. [16]

    Jiří Sedláček,On the minimal graph with a given number of spanning trees, Canadian Mathematical Bulletin13 (1970), 515–517

    1970

  9. [17]

    Jiří Sedláček,Regular graphs and their spanning trees, Časopis pro pěstování matematiky95(1970), 420–426

    1970

  10. [18]

    Yaroslav Shitov,The range of0-1determinants is large, 2025, Preprint

    2025

  11. [19]

    Department of Mathematics, Statistics, and Computer Science, University of Illinois Chicago, Chicago, IL 60607, USA Email address:visheshj@uic.edu

    RichardStong,Minimal graphs with a prescribed number of spanning trees, AustralasianJournalofCombinatorics 82(2022), 182–196. Department of Mathematics, Statistics, and Computer Science, University of Illinois Chicago, Chicago, IL 60607, USA Email address:visheshj@uic.edu

    2022

Pith tools

Reviewed June 29, 2026 · model on record in the stance chip above.