论文标题
统一跨膜的密集图的直径
The diameter of the uniform spanning tree of dense graphs
论文作者
论文摘要
我们表明，在$ n $中的$ n $顶点上的简单连接图的均匀绘制的跨度树的直径通常为$ n $中的最低度线性，通常为$ \ sqrt {n} $的顺序。我们的证明的副产品是独立关注的，是在此类图上，脸颊常数和光谱差距是可比的。
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 $\sqrt{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.
