Spanning trees and continued fractions

2024/11/27 by Chan, Swee Hong, Alex Kontorovich, Kontorovich, Alex +2 · 1 citation
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Number Theory (math.NT) #Polynomial and algebraic computation #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.2411.18782

openalex publication_date 2024/11/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We prove the exponential growth of the cardinality of the set of numbers of spanning trees in simple (and planar) graphs on n vertices, answering a question of Sedláček from 1969. The proof uses a connection with continued fractions, ``thin orbits,'' and Zaremba's conjecture.

Cited by

• Chromatic Polynomial Evaluation Spectra

Related

• The spanning tree spectrum: improved bounds and simple proofs
• Counting graphs with different numbers of spanning trees through the counting of prime partitions
• On the number of spanning trees in bipartite graphs
• Sharp estimates for spanning trees
• Counting Spanning Trees of Threshold Graphs