Anticoncentration of random spanning trees in almost regular graphs
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909987841769472 |
|---|---|
| author | Lee, Hyunwoo |
| author_facet | Lee, Hyunwoo |
| contents | The celebrated formula of Otter \emph{[Ann. of Math. (2) 49 (1948), 583--599]} asserts that the complete graph contains exponentially many non-isomorphic spanning trees. In this paper, we show that every connected almost regular graph with sufficiently large degree already contains exponentially many non-isomorphic spanning trees. Indeed, we prove a stronger statement: for every fixed $n$-vertex tree $T$, $$
\Pr\bigl[\mathcal{T} \simeq_{\mathrm{iso}} T\bigr] = e^{-Ω(n)}, $$ where $\mathcal{T}$ is a uniformly random spanning tree of a connected $n$-vertex almost regular graph with sufficiently large degree. To prove this, we introduce a graph-theoretic variant of the classical balls--into--bins model, which may be of independent interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_07740 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Anticoncentration of random spanning trees in almost regular graphs Lee, Hyunwoo Combinatorics Probability The celebrated formula of Otter \emph{[Ann. of Math. (2) 49 (1948), 583--599]} asserts that the complete graph contains exponentially many non-isomorphic spanning trees. In this paper, we show that every connected almost regular graph with sufficiently large degree already contains exponentially many non-isomorphic spanning trees. Indeed, we prove a stronger statement: for every fixed $n$-vertex tree $T$, $$ \Pr\bigl[\mathcal{T} \simeq_{\mathrm{iso}} T\bigr] = e^{-Ω(n)}, $$ where $\mathcal{T}$ is a uniformly random spanning tree of a connected $n$-vertex almost regular graph with sufficiently large degree. To prove this, we introduce a graph-theoretic variant of the classical balls--into--bins model, which may be of independent interest. |
| title | Anticoncentration of random spanning trees in almost regular graphs |
| topic | Combinatorics Probability |
| url | https://arxiv.org/abs/2601.07740 |