2025/03/31 by Noga Alon, Matija Bucić, Alon, Noga +3 · 2 citations
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Stochastic processes and statistical mechanics #Advanced Graph Theory Research
paper · pdf · doi:10.48550/arxiv.2503.23648
The number of spanning trees of a graph G, denoted τ(G), is a well studied graph parameter with numerous connections to other areas of mathematics. In a recent remarkable paper, answering a question of Sedláček from 1969, Chan, Kontorovich and Pak showed that τ(G) takes at least 1.1103n different values across simple (and planar) n-vertex graphs G, for large enough n. We give a very short, purely combinatorial proof that at least 1.55n values are attained. We also prove that exponential growth can be achieved with regular graphs, determining the growth rate in another problem first raised by Sedláček in the late 1960's. We further show that the following modular dual version of the result holds. For any integer N and any u < N there exists a planar graph on O(log N) vertices whose number of spanning trees is u modulo N.