PreprintCC BY 4.0arXiv
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 inj(T,G) ≤ (d/e)n exp(od(1) n). The bound is sharp up to determining od(1), even for paths, and the dependence of the error exp(od(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.
Related
- Spanning tree with bounded degree sum of two adjacent vertices
- Local scaling limit of the four-dimensional uniform spanning tree
- Combinatorial Algorithms for Partial Inverse Min-Max Spanning Tree Problem under the Weighted Sum Hamming Distance
- Edge-Defect Spectral Methods for Higher-Order Rankings of Spanning Tree Counts
- Spanning-Tree Maximization Forces Isoperimetry in the Square Lattice
BibTeX
@misc{beke2026optimal,
title = {{Optimal Bounds on Spanning Tree Embeddings}},
author = {Csongor Beke and Vladimir Bošković and Nina Kamčev and Yiting Wang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.08362},
eprint = {2610.08362},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.08362},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Optimal Bounds on Spanning Tree Embeddings
AU - Csongor Beke
AU - Vladimir Bošković
AU - Nina Kamčev
AU - Yiting Wang
PY - 2026
DA - 2026/10/06
PB - arXiv
DO - 10.48550/arxiv.2610.08362
UR - https://arxiv.org/abs/2610.08362
AB - 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 inj(T,G) ≤ (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.
ER -