Optimal Bounds on Spanning Tree Embeddings

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)\le (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.