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

Markus Schepers

Research output: ThesisThesis fully internal (DIV)

166 Downloads (Pure)

Abstract

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.
Original languageEnglish
QualificationDoctor of Philosophy
Awarding Institution
  • University of Groningen
Supervisors/Advisors
  • Müller, Tobias, Supervisor
  • Wit, Ernst, Supervisor
Award date22-May-2020
Place of Publication[Groningen]
Publisher
Print ISBNs978-94-034-2672-3
Electronic ISBNs978-94-034-2673-0
DOIs
Publication statusPublished - 2020

Cite this