The diameter of uniform spanning trees in high dimensions

We show that the diameter of a uniformly drawn spanning tree of a connected graph on \(n\) vertices which satisfies certain high-dimensionality conditions typically grows like \(\Theta(\sqrt{n})\). In particular this result applies to expanders, finite tori \(\mathbb{Z}_m^d\) of dimension \(d \geq 5...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2019-11
Main Authors: Michaeli, Peleg, Nachmias, Asaf, Shalev, Matan
Format: Article
Language:English
Subjects:
Apexes
Diameters
Expanders
Graph theory
Hypercubes
Toruses
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We show that the diameter of a uniformly drawn spanning tree of a connected graph on \(n\) vertices which satisfies certain high-dimensionality conditions typically grows like \(\Theta(\sqrt{n})\). In particular this result applies to expanders, finite tori \(\mathbb{Z}_m^d\) of dimension \(d \geq 5\), the hypercube \(\{0,1\}^m\), and small perturbations thereof.
ISSN:2331-8422
DOI:10.48550/arxiv.1911.12319