Abstract
We show that the diameter of a uniformly drawn spanning tree of a simple connected graph on n vertices with minimal degree linear in n is typically of order √n. A byproduct of our proof, which is of independent interest, is that on such graphs the Cheeger constant and the spectral gap are comparable.
Original language | English (US) |
---|---|
Pages (from-to) | 1010-1030 |
Number of pages | 21 |
Journal | Combinatorics Probability and Computing |
Volume | 31 |
Issue number | 6 |
DOIs | |
State | Published - Nov 2022 |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Statistics and Probability
- Computational Theory and Mathematics
- Applied Mathematics
Keywords
- dense graphs
- spectral gap
- Uniform spanning trees