{
  "id": "2012.01664",
  "version": "v1",
  "published": "2020-12-03T02:34:50.000Z",
  "updated": "2020-12-03T02:34:50.000Z",
  "title": "The diameter of the minimum spanning tree of the complete graph with inhomogeneous random weights",
  "authors": [
    "Othmane Safsafi"
  ],
  "comment": "30 pages, 6 figures",
  "categories": [
    "math.PR"
  ],
  "abstract": "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-12-03T02:34:50.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60C05",
      "05C80",
      "90B15"
    ],
    "keywords": [
      "inhomogeneous random weights",
      "complete graph",
      "random minimum spanning trees",
      "typical distances",
      "exploration trees"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 30,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}