Perfect matchings, Hamilton cycles, degree distribution and local clustering in Hyperbolic Random Graphs

Markus Schepers

Onderzoeksoutput

175 Downloads (Pure)

Samenvatting

In this thesis we study a random graph model proposed by Krioukov et al.~in 2010. In this model, vertices are chosen randomly inside a disk in the hyperbolic plane and two vertices are adjacent 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.

We derive the entire limiting degree distribution. We show the convergence of the clustering coefficient to an explicitly given closed-form expression. We show that the clustering function for fixed degree converges to an explicitly given closed-form expression and derive the asymptotic scaling for growing degrees.

We show that for a certain range of parameters there are no perfect matchings and Hamilton cycles asymptotically almost surely, whereas for another range of parameters there are perfect matchings and Hamilton cycles asymptotically almost surely.
Originele taal-2English
KwalificatieDoctor of Philosophy
Toekennende instantie
  • Rijksuniversiteit Groningen
Begeleider(s)/adviseur
  • Müller, Tobias, Supervisor
  • Wit, Ernst, Supervisor
Datum van toekenning22-mei-2020
Plaats van publicatie[Groningen]
Uitgever
Gedrukte ISBN's978-94-034-2672-3
Elektronische ISBN's978-94-034-2673-0
DOI's
StatusPublished - 2020

Citeer dit