pipette
ESEspañol

Optimal Bounds on Spanning Tree Embeddings

Csongor Beke, Vladimir Bo\v{s}kovi\'c, Nina Kam\v{c}ev, Yiting Wang

Preprint

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.