Optimal Bounds on Spanning Tree Embeddings

Source abstract

We prove that the number of labelled embeddings of any $n$-vertex tree $T$ into an $n$-vertex graph $G$ of maximum degree $d$ satisfies $$\mathrm{inj}(T,G) \leq (d/e)^n \exp(o_d(1) n).$$ The bound is sharp up to determining $o_d(1)$, even for paths, and the dependence of the error $\exp(o_d(1)n)$ on $d$ is necessary. As an immediate corollary, we obtain an optimal anticoncentration bound for the isomorphism class of a uniformly random spanning tree in a connected $d$-regular graph, answering a conjecture of H. Lee. The proof combines Brégman's inequality with entropy methods.