Association for Mathematical Research retweetledi
New paper on arxiv, with my Rutgers colleague Swee Hong Chan and Igor Pak of UCLA: arxiv.org/abs/2411.18782
We study numbers of spanning trees of graphs, answering a 55-year old question of Sedlacek.
A graph is just a bunch of vertices connected by some edges. Here’s a pic of all the connected (that is, spanning all the vertices) graphs on 4 vertices. A “spanning tree” is a subgraph (drop some edges) that is still connected but has no cycles (no paths through the graph that come back to where they started). For a given graph, G, write τ(G) for how many spanning trees it has. This is a fascinating quantity that’s been studied since (at least) 1847, when it appeared in Kirchhoff’s work on resistance in electrical circuits (this is where he proved the "matrix-tree theorem", that τ can be computed as the determinant of a minor of the graph Laplacian). By happenstance, this quantity appears all over the place. In evolutionary biology, τ counts the number of possible phylogenic trees connecting sets of species based on genetic or evolutionary data. In the arithmetic of Ramanujan graphs (of Lubotzky-Phillips-Sarnak), τ coincides with class numbers of certain function fields. Etc etc.
In the 60’s, Sedlacek started to ask a number of very natural questions about what values τ can take in different families, ordered by the number of vertices. For the size-4 graphs in the image, we see that the set of values taken by τ is:
1, 3, 4, 8, and 16.
Of particular interest to us is the family of planar graphs. It’s easy to show from Euler characteristic that τ takes *at most* exponentially many values. Does the set of values also grow *at least* exponentially? Sedlacek could prove that they grow at least quadratically. Skipping a lot of intermediate results, the previous best growth rate was due to Stong, who showed in 2022 that the number of distinct values of τ on planar graphs with n vertices grows at least like
exp(C n^{2/3}).
One of the difficulties here is that there are only exponentially many planar graphs to begin with, and τ can have exponentially large multiplicity (for example, there are exponentially many trees, for whom τ is of course always 1). Nevertheless, we’re able in this paper to resolve the question (at least qualitatively), that τ indeed grows exponentially.
In fact we show much more, namely, it looks like the set of values of τ will eventually be just *all* (sufficiently large) numbers, in an exponential range; we prove a positive proportion and outline how to prove density 1 (if you just want to show exponential growth, even less is needed). The method of proof is really fun, too, and happens in three steps:
• We reduce the graph question to a question in Diophantine geometry, that smells a lot like Zaremba’s conjecture.
• A decade ago, Bourgain and I made some progress on that problem, and that work (which has been extended now by Frolenkov, Huang, and especially Kan) applies to this context. It turns out that a key role is played by the Hausdorff dimension of a certain fractal, which needs to overcome a threshold value. The Diophantine problem is thus reduced to one in Thermodynamics.
• To resolve the Thermodynamics, we have to rigorously compute this dimension, and (very luckily for us!) it turns out to indeed exceed the threshold, but just barely, in the hundredths place.
This was a really fun project to work on. For more details, please see the paper.
English
