{
  "id": "1901.09175",
  "version": "v1",
  "published": "2019-01-26T08:23:29.000Z",
  "updated": "2019-01-26T08:23:29.000Z",
  "title": "Hamilton cycles and perfect matchings in the KPKVB model",
  "authors": [
    "Nikolaos Fountoulakis",
    "Dieter Mitsche",
    "Tobias Müller",
    "Markus Schepers"
  ],
  "comment": "18 pages, 2 figures",
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "abstract": "In this paper we consider the existence of Hamilton cycles and perfect matchings in a random graph model proposed by Krioukov et al.~in 2010. In this model, nodes are chosen randomly inside a disk in the hyperbolic plane and two nodes are connected if they are at most a certain hyperbolic distance from each other. It has been previously shown that this model has various properties associated with complex networks, including a power-law degree distribution, \"short distances\" and a strictly positive clustering coefficient. The model is specified using three parameters: the number of nodes $n$, which we think of as going to infinity, and $\\alpha, \\nu > 0$, which we think of as constant. Roughly speaking $\\alpha$ controls the power law exponent of the degree sequence and $\\nu$ the average degree. Here we show that for every $\\alpha < 1/2$ and $\\nu=\\nu(\\alpha)$ sufficiently small, the model does not contain a perfect matching with high probability, whereas for every $\\alpha < 1/2$ and $\\nu=\\nu(\\alpha)$ sufficiently large, the model contains a Hamilton cycle with high probability.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-01-26T08:23:29.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "hamilton cycle",
      "perfect matching",
      "kpkvb model",
      "high probability",
      "power-law degree distribution"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 18,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}