论文标题
完整图的最小跨越树的直径不均匀的随机重量
The diameter of the minimum spanning tree of the complete graph with inhomogeneous random weights
论文作者
论文摘要
我们研究一种新型的随机最小跨越树。它建立在完整的图上，其中每个顶点都有一个重量，这是一个正实数。然后，给出每个边缘的容量，该容量是一个随机变量，仅取决于其端点权重的乘积。然后，我们研究与边缘能力相对应的最小跨树。在节点权重的有限矩情况下，我们表明，最小跨越树的预期直径和典型距离是$ n^{1/3} $的顺序。这是Addario-berry，Broutin和Reed [2009]的结果的概括。然后，我们使用结果来回答有关密切相关对象上典型距离的统计物理学的猜想。这项工作还为证明这种生成树的非平凡缩放限制的存在奠定了基础（对Addario-berry，Broutin，Goldschmidt和Miermont [2017]的结果的概括）。我们的证明是基于对Safsafi [2020]中进行的等级1关键不均匀随机图的详细研究，以及与这些图和Galton-Watson树相关的探索树之间的新型耦合。
We study a new type of random minimum spanning trees. It is built on the complete graph where each vertex is given a weight, which is a positive real number. Then, each edge is given a capacity which is a random variable that only depends on the product of the weights of its endpoints. We then study the minimum spanning tree corresponding to the edge capacities. Under a condition of finite moments on the node weights, we show that the expected diameter and typical distances of this minimum spanning tree are of order $n^{1/3}$. This is a generalization of the results of Addario-Berry, Broutin, and Reed [2009]. We then use our result to answer a conjecture in statistical physics about typical distances on a closely related object. This work also sets the ground for proving the existence of a non-trivial scaling limit of this spanning tree (a generalization of the result of Addario-Berry, Broutin, Goldschmidt, and Miermont [2017])). Our proof is based on a detailed study of rank-1 critical inhomogeneous random graphs, done in Safsafi [2020], and novel couplings between exploration trees related to those graphs and Galton-Watson trees.
