Anticoncentration of random spanning trees in graphs with large minimum degree
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914405950685184 |
|---|---|
| author | Bitonti, Veronica Michel, Lukas Scott, Alex |
| author_facet | Bitonti, Veronica Michel, Lukas Scott, Alex |
| contents | A classical result by Otter shows that the complete graph has an exponential number of non-isomorphic spanning trees. This was recently extended by Lee to every almost regular graph of sufficiently large degree.
In this paper, we consider graphs of large minimum degree. We show that every connected graph $G$ with $n$ vertices and minimum degree $d$ has at least $n^{Ω(d)}$ non-isomorphic spanning trees. This is tight up to the constant factor in the exponent. In fact, we prove the following anticoncentration result: if $\mathcal{T}$ is a uniformly random spanning tree of $G$, then for every tree $T$, the probability that $\mathcal{T}$ is isomorphic to $T$ is at most $n^{-Ω(d)}$. This proves a conjecture of Lee in a strong form. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_17630 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Anticoncentration of random spanning trees in graphs with large minimum degree Bitonti, Veronica Michel, Lukas Scott, Alex Combinatorics Probability A classical result by Otter shows that the complete graph has an exponential number of non-isomorphic spanning trees. This was recently extended by Lee to every almost regular graph of sufficiently large degree. In this paper, we consider graphs of large minimum degree. We show that every connected graph $G$ with $n$ vertices and minimum degree $d$ has at least $n^{Ω(d)}$ non-isomorphic spanning trees. This is tight up to the constant factor in the exponent. In fact, we prove the following anticoncentration result: if $\mathcal{T}$ is a uniformly random spanning tree of $G$, then for every tree $T$, the probability that $\mathcal{T}$ is isomorphic to $T$ is at most $n^{-Ω(d)}$. This proves a conjecture of Lee in a strong form. |
| title | Anticoncentration of random spanning trees in graphs with large minimum degree |
| topic | Combinatorics Probability |
| url | https://arxiv.org/abs/2603.17630 |