Optimal Bounds on Spanning Tree Embeddings
In the authors' words
We prove that the number of labelled embeddings of any -vertex tree into an -vertex graph of maximum degree satisfies The bound is sharp up to determining , even for paths, and the dependence of the error on 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 -regular graph, answering a conjecture of H. Lee. The proof combines Br\'egman's inequality with entropy methods.
Main resultLimitation the authors admit
Appeared: Wednesday, October 7. arXiv. Preprint, not yet peer-reviewed.