TAU Combinatorics Seminar 2022/23

When: Sunday, October 23, 10am
Speaker: Raphael Yuster, University of Haifa
Title: The number of bounded-degree spanning trees


For a graph $G$, let $c_k(G)$ be the number of spanning trees of $G$ with maximum degree at most $k$. For $k \ge 3$, it is proved that every connected $n$-vertex $r$-regular graph $G$ with $r \ge \frac{n}{k+1}$ satisfies $$ c_k(G)^{1/n} \ge (1-o_n(1)) r \cdot z_k $$ where $z_k > 0$ approaches $1$ extremely fast (e.g. $z_{10}=0.999971$). The minimum degree requirement is essentially tight as for every $k \ge 2$ there are connected $n$-vertex $r$-regular graphs $G$ with $r=\lfloor n/(k+1) \rfloor -2$ for which $c_k(G)=0$. Regularity may be relaxed, replacing $r$ with the geometric mean of the degree sequence and replacing $z_k$ with $z_k^*$ that also approaches $1$, as long as the maximum degree is at most $n-n\sqrt{2\ln k/k}$.

The same holds with no restriction on the maximum degree as long as the minimum degree is at least $\frac{n}{k}(1+o_k(1))$.