The spanning tree spectrum: improved bounds and simple proofs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918129393729536 |
|---|---|
| author | Alon, Noga Bucić, Matija Gishboliner, Lior |
| author_facet | Alon, Noga Bucić, Matija Gishboliner, Lior |
| contents | The number of spanning trees of a graph $G$, denoted $τ(G)$, is a well studied graph parameter with numerous connections to other areas of mathematics. In a recent remarkable paper, answering a question of Sedláček from 1969, Chan, Kontorovich and Pak showed that $τ(G)$ takes at least $1.1103^n$ different values across simple (and planar) $n$-vertex graphs $G$, for large enough $n$. We give a very short, purely combinatorial proof that at least $1.55^n$ values are attained. We also prove that exponential growth can be achieved with regular graphs, determining the growth rate in another problem first raised by Sedláček in the late 1960's. We further show that the following modular dual version of the result holds. For any integer $N$ and any $u < N$ there exists a planar graph on $O(\log N)$ vertices whose number of spanning trees is $u$ modulo $N$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_23648 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The spanning tree spectrum: improved bounds and simple proofs Alon, Noga Bucić, Matija Gishboliner, Lior Combinatorics The number of spanning trees of a graph $G$, denoted $τ(G)$, is a well studied graph parameter with numerous connections to other areas of mathematics. In a recent remarkable paper, answering a question of Sedláček from 1969, Chan, Kontorovich and Pak showed that $τ(G)$ takes at least $1.1103^n$ different values across simple (and planar) $n$-vertex graphs $G$, for large enough $n$. We give a very short, purely combinatorial proof that at least $1.55^n$ values are attained. We also prove that exponential growth can be achieved with regular graphs, determining the growth rate in another problem first raised by Sedláček in the late 1960's. We further show that the following modular dual version of the result holds. For any integer $N$ and any $u < N$ there exists a planar graph on $O(\log N)$ vertices whose number of spanning trees is $u$ modulo $N$. |
| title | The spanning tree spectrum: improved bounds and simple proofs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2503.23648 |