On the number of distinct spanning trees in pseudorandom 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_ | 1866911677352509440 |
|---|---|
| author | Wang, Yiting |
| author_facet | Wang, Yiting |
| contents | A celebrated result of Otter says the number of distinct unlabelled spanning trees in $K_n$ is $α^n$ up to subexponential factors for an absolute constant $α>0$. In this note, we prove that for every $0<\varepsilon<α$, there are constants $C$ and $d_0$ such that every $(n,d,λ)$-graph with $d\geq d_0$ and $d/λ\geq C$ has at least $(α-\varepsilon)^n$ distinct unlabelled spanning trees. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_12742 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On the number of distinct spanning trees in pseudorandom graphs Wang, Yiting Combinatorics A celebrated result of Otter says the number of distinct unlabelled spanning trees in $K_n$ is $α^n$ up to subexponential factors for an absolute constant $α>0$. In this note, we prove that for every $0<\varepsilon<α$, there are constants $C$ and $d_0$ such that every $(n,d,λ)$-graph with $d\geq d_0$ and $d/λ\geq C$ has at least $(α-\varepsilon)^n$ distinct unlabelled spanning trees. |
| title | On the number of distinct spanning trees in pseudorandom graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2605.12742 |