Talk information

Date: Sunday, January 18, 2026
Time: 10:10–11:00
Place: Schreiber 309
Speaker: Noga Alon (Princeton University and Tel Aviv University)
Title: The spanning-tree spectrum

Abstract:

Let $\tau(G)$ denote the number of spanning trees of a graph $G$.

In a recent remarkable paper, answering a question of Sedláček from 1969, Chan, Kontorovich and Pak showed that $\tau(G)$ takes at least $1.1103^n$ different values across simple (and planar) $n$-vertex graphs $G$, for all large $n$. Their proof applies fairly deep results in Number Theory.

I will describe a short purely combinatorial proof that at least $1.55^n$ values are attained. Moreover, exponential growth can be achieved with cubic graphs, settling another problem first raised by Sedláček in the late 1960’s. If time permits I will also sketch a proof of the following modular result:

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$.

Joint work with Matija Bucić and Lior Gishboliner.