Hamilton cycles and perfect matchings in the KPKVB model

Nikolaos Fountoulakis, Dieter Mitsche, Tobias Müller, Markus Schepers*

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)
19 Downloads (Pure)

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 non-vanishing clustering coefficient. The model is specified using three parameters: the number of nodes n, which we think of as going to infinity, and α,ν>0, which we think of as constant. Roughly speaking α controls the power law exponent of the degree sequence and ν the average degree. Here we show that for every α<1∕2 and ν=ν(α) sufficiently small, the model does not contain a perfect matching with high probability, whereas for every α<1∕2 and ν=ν(α) sufficiently large, the model contains a Hamilton cycle with high probability.

Original languageEnglish
Pages (from-to)340-358
Number of pages19
JournalStochastic processes and their applications
Volume131
Early online date20-Sep-2020
DOIs
Publication statusPublished - Jan-2021

Keywords

  • Hamilton cycle
  • Hyperbolic random graph
  • Perfect matching
  • Poisson process
  • Randomized algorithm
  • Tiling

Cite this