pipette
ENEnglish

Optimal Bounds on Spanning Tree Embeddings

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

Preprint

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.