The diameter of the uniform spanning tree of dense graphs

DOI10.1017/S0963548322000062MaRDI QIDQ5886350zbMATH OpenOpenAlexFDO

Authors Noga Alon, Asaf Nachmias, Matan Shalev

Publication date 31 March 2023

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2009.09656

zbMATH Keywords

dense graphsspectral gapuniform spanning trees

Mathematics Subject Classification ID

Trees (05C05) Distance in graphs (05C12) Density (toughness, etc.) (05C42) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random walks on graphs (05C81) Interacting random processes; statistical mechanics type models; percolation theory (60K35)

Recommendations

• The diameter of uniform spanning trees in high dimensions
• Diameter of random spanning trees in a given graph
• The local limit of the uniform spanning tree on dense graphs
• scientific article; zbMATH DE number 5730481
• Critical random graphs and the structure of a minimum spanning tree

Cites work

• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• Approximating the Permanent
• Bounds on the L 2 Spectrum for Markov Chains and Markov Processes: A Generalization of Cheeger's Inequality
• Eigenvalues and expanders
• Elementary bounds on Poincaré and log-Sobolev constants for decomposable Markov chains
• scientific article; zbMATH DE number 3829941 (Why is no real title available?)
• scientific article; zbMATH DE number 3978019 (Why is no real title available?)
• scientific article; zbMATH DE number 19286 (Why is no real title available?)
• scientific article; zbMATH DE number 1256746 (Why is no real title available?)
• Improved Cheeger's inequality, analysis of spectral partitioning algorithms through higher order spectral gap
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Probability on trees and networks
• Random real trees
• Random trees and applications
• The continuum random tree. I
• The continuum random tree. III
• The diameter of uniform spanning trees in high dimensions

Cited in

(9)

• The local limit of the uniform spanning tree on dense graphs
• Existence of a spanning tree having small diameter
• A diameter-revealing proof of the Bondy-Lovász lemma
• The diameter of uniform spanning trees in high dimensions
• Diameter of random spanning trees in a given graph
• scientific article; zbMATH DE number 5730481 (Why is no real title available?)
• Algorithms for diameters of unicycle graphs and diameter-optimally augmenting trees
• Logarithmic corrections to scaling in the four-dimensional uniform spanning tree
• The GHP scaling limit of uniform spanning trees of dense graphs

This page was built for publication: The diameter of the uniform spanning tree of dense graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5886350)