Optimal Bounds on Spanning Tree Embeddings

Csongor Beke, Vladimir Bošković, Nina Kamčev, Yiting Wang

arXivarxiv/2610.08362Oct 6, 2026math.COscore 0

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 $$ \mathrm{inj}(T,G) \leq (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.

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2610.08362
curl -X POST /api/v1/records/arxiv/2610.08362/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.08362/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'