Optimal Bounds on Spanning Tree Embeddings
En palabras de los autores
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.
Resultado principalLimitación que admiten los autores
Apareció: miércoles, 7 de octubre. arXiv. Preprint, todavía sin revisión por pares.