TY - JOUR
T1 - Hamilton cycles and perfect matchings in the KPKVB model
AU - Fountoulakis, Nikolaos
AU - Mitsche, Dieter
AU - Müller, Tobias
AU - Schepers, Markus
N1 - Funding Information:
Research partially supported by the Alan Turing Institute, United Kingdom, grant no. EP/N510129/1.Research partially supported by IDEXLYON of Universit? de Lyon, France (Programme Investissements d'Avenir ANR16-IDEX-0005) and by Labex MILYON, France/ANR-10-LABX-0070.Research partially supported by NWO, The Netherlands grants 639.032.529 and 612.001.409.Research partially supported by NWO, The Netherlands grant 639.032.529.
Publisher Copyright:
© 2020 Elsevier B.V.
PY - 2021/1
Y1 - 2021/1
N2 - 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.
AB - 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.
KW - Hamilton cycle
KW - Hyperbolic random graph
KW - Perfect matching
KW - Poisson process
KW - Randomized algorithm
KW - Tiling
UR - http://www.scopus.com/inward/record.url?scp=85092112767&partnerID=8YFLogxK
U2 - 10.1016/j.spa.2020.09.012
DO - 10.1016/j.spa.2020.09.012
M3 - Article
SN - 0304-4149
VL - 131
SP - 340
EP - 358
JO - Stochastic processes and their applications
JF - Stochastic processes and their applications
ER -