The diameter of uniform spanning trees in high dimensions

• 成果类型: Article
• 署名作者: Michaeli, Peleg; Nachmias, Asaf; Shalev, Matan
• 署名单位: Tel Aviv University
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051
• DOI: 10.1007/s00440-020-00999-2
• 发表日期: 2021
• 页码: 261-294
• 关键词: random-walk; interlacements

摘要

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(root n). In particular this result applies to expanders, finite tori Z(m)(d) of dimension d >= 5, the hypercube {0, 1}(m), and small perturbations thereof.