The diameter of uniform spanning trees in high dimensions
The diameter of uniform spanning trees in high dimensions
复制标题
高维均匀生成树的直径
DOI：
--
复制
发表时间：
2019
影响因子：
2
通讯作者：
Matan Shalev
中科院分区：
文献类型：
--
作者：
Peleg Michaeli;Asaf Nachmias;Matan Shalev
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 Θ(n)documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$Theta (sqrt{n})$$end{document}. In particular this result applies to expanders, finite tori Zmddocumentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$mathbb {Z}_m^d$$end{document} of dimension d≥5documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$d ge 5$$end{document}, the hypercube {0,1}mdocumentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$${0,1}^m$$end{document}, and small perturbations thereof.
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 Θ(n)documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$Theta (sqrt{n})$$end{document}. In particular this result applies to expanders, finite tori Zmddocumentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$mathbb {Z}_m^d$$end{document} of dimension d≥5documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$d ge 5$$end{document}, the hypercube {0,1}mdocumentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$${0,1}^m$$end{document}, and small perturbations thereof.