The diameter of the uniform spanning tree of dense graphs

Noga Alon; Asaf Nachmias; Matan Shalev

doi:10.1017/S0963548322000062

The diameter of the uniform spanning tree of dense graphs

Noga Alon, Asaf Nachmias, Matan Shalev

Mathematics

Research output: Contribution to journal › Article › peer-review

1 Scopus citations

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	https://doi.org/10.1017/S0963548322000062
State	Published - Nov 2022

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Statistics and Probability
Computational Theory and Mathematics
Applied Mathematics

Keywords

Uniform spanning trees
dense graphs
spectral gap

Access to Document

10.1017/S0963548322000062

Cite this

@article{fee4cd06f8eb4ff6b5a535dfc13ede39,

title = "The diameter of the uniform spanning tree of dense graphs",

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.",

keywords = "Uniform spanning trees, dense graphs, spectral gap",

author = "Noga Alon and Asaf Nachmias and Matan Shalev",

note = "Publisher Copyright: {\textcopyright}The Author(s), 2022. Published by Cambridge University Press.",

year = "2022",

month = nov,

doi = "10.1017/S0963548322000062",

language = "English (US)",

volume = "31",

pages = "1010--1030",

journal = "Combinatorics Probability and Computing",

issn = "0963-5483",

publisher = "Cambridge University Press",

number = "6",

}

TY - JOUR

T1 - The diameter of the uniform spanning tree of dense graphs

AU - Alon, Noga

AU - Nachmias, Asaf

AU - Shalev, Matan

N1 - Publisher Copyright: ©The Author(s), 2022. Published by Cambridge University Press.

PY - 2022/11

Y1 - 2022/11

N2 - 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.

AB - 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.

KW - Uniform spanning trees

KW - dense graphs

KW - spectral gap

UR - https://www.scopus.com/pages/publications/85146206643

UR - https://www.scopus.com/inward/citedby.url?scp=85146206643&partnerID=8YFLogxK

U2 - 10.1017/S0963548322000062

DO - 10.1017/S0963548322000062

M3 - Article

AN - SCOPUS:85146206643

SN - 0963-5483

VL - 31

SP - 1010

EP - 1030

JO - Combinatorics Probability and Computing

JF - Combinatorics Probability and Computing

IS - 6

ER -

The diameter of the uniform spanning tree of dense graphs

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this