Hyperbolic Random Graphs: Clique Number and Degeneracy with Implications for Colouring

Baguley, Samuel; Maus, Yannic; Ruff, Janosch; Skretas, George

doi:10.4230/LIPIcs.STACS.2025.13

Hyperbolic Random Graphs: Clique Number and Degeneracy with Implications for Colouring

Samuel Baguley

Hasso Plattner Institute, University of Potsdam, Germany Yannic Maus

TU Graz, Austria Janosch Ruff

Hasso Plattner Institute, University of Potsdam, Germany George Skretas

Hasso Plattner Institute, University of Potsdam, Germany

Abstract

Hyperbolic random graphs inherit many properties that are present in real-world networks. The hyperbolic geometry imposes a scale-free network with a strong clustering coefficient. Other properties like a giant component, the small world phenomena and others follow. This motivates the design of simple algorithms for hyperbolic random graphs.

In this paper we consider threshold hyperbolic random graphs (HRGs). Greedy heuristics are commonly used in practice as they deliver a good approximations to the optimal solution even though their theoretical analysis would suggest otherwise. A typical example for HRGs are degeneracy-based greedy algorithms [Bläsius, Fischbeck; Transactions of Algorithms ’24]. In an attempt to bridge this theory-practice gap we characterise the parameter of degeneracy yielding a simple approximation algorithm for colouring HRGs. The approximation ratio of our algorithm ranges from $(2/\sqrt{3})$ to $4/3$ depending on the power-law exponent of the model. We complement our findings for the degeneracy with new insights on the clique number of hyperbolic random graphs. We show that degeneracy and clique number are substantially different and derive an improved upper bound on the clique number. Additionally, we show that the core of HRGs does not constitute the largest clique.

Lastly we demonstrate that the degeneracy of the closely related standard model of geometric inhomogeneous random graphs behaves inherently different compared to the one of hyperbolic random graphs.

Keywords and phrases:

hyperbolic random graphs, scale-free networks, power-law graphs, cliques, degeneracy, vertex colouring, chromatic number

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Random network models

Related Version:

Full Version: https://arxiv.org/abs/2410.11549 [1]

Acknowledgements:

The authors would like to thank Thomas Bläsius for enriching discussions and Maximilian Katzmann for running experiments indicating a gap between core and maximum inner-neighbourhood during a research visit of JR in Karlsruhe.

Funding:

This research was partially funded by the German Research Foundation (Deutsche Forschungsgemeinschaft, DFG) – project number 390859508, and by Austrian Science Fund (FWF) https://doi.org/10.55776/P36280, https://doi.org/10.55776/I6915, and https://doi.org/10.55776/DOC183.

DOI:

10.4230/LIPIcs.STACS.2025.13

Event:

42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Editors:

Olaf Beyersdorff, Michał Pilipczuk, Elaine Pimentel, and Nguyễn Kim Thắng

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Many real-world networks have a heterogeneous degree distribution, close to a power-law, as well as a constant clustering coefficient. The hyperbolic random graph model (HRG) introduced by Krioukov et. al. [29] combines both properties [19], which has led to considerable interest in recent years. Various aspects of HRGs have been studied, including clique size [8, 9, 16], treewidth [10], minimum vertex cover size [4, 5], and diameter [17, 24, 33]. A hyperbolic random graph is a graph embedded in the hyperbolic plane where pairs of vertices have an edge if they are close according to the hyperbolic distance. It is generated by randomly throwing $n$ vertices on a disk of radius $R$ (dependent on $n$ ). Since hyperbolic space grows exponentially, most vertices are of small degree and located close to the boundary of the disk, while few vertices have large degree and lie close to the centre. This distribution of vertices leads to the power-law degree distribution of HRGs.

In this paper, we study the vertex colouring problem on HRGs, along with the related concepts of clique number and degeneracy. The $k$ -colouring problem asks to colour the vertices of a graph with $k$ colours, while assigning different colours to adjacent vertices. The chromatic number $\chi(G)$ is the minimum number of colours needed to colour a graph in such a way. For $k\geq 3$ the problem is one of the original NP-hard problems [13, 21]. On general graphs, even loosely approximating the chromatic number is particularly hard [36].

The answer to the colouring problem is closely related to the clique number $\omega(G)$ and the degeneracy of a graph. The clique number is the number of vertices of the largest clique of the graph and it serves as a natural lower bound to the chromatic number. The degeneracy $\kappa(G)$ is the minimum integer $k^{\prime}$ for which there exists an ordering of the vertex set of $G$ , $V=(v_{1},v_{2},\cdots,v_{n})$ , such that for every index $i\in[n-1]$ , $v_{i}$ has at most $k^{\prime}$ neighbours with greater index. Any graph $G$ can be easily coloured with $\kappa(G)+1$ colours by iterating through the vertices in reverse order and simply colouring a vertex with a colour not used by any of its higher ranked neighbours.

We aim to study these structural parameters that are not only fundamental to the model but also in general for algorithm design in various models of computation [2, 12, 18]. The most prominent large clique in an HRG is formed by the vertices in the graph’s core [8]. Simply put, the core emerges among polynomially many vertices of distance at most $R/2$ from the centre of the disk, which due to the triangle inequality form a clique. We denote the size of this clique by $\sigma(G)$ . At this point one may wonder whether the core forms the largest clique of the graph, a statement that we disprove in Proposition 16. Nevertheless we show that the largest clique can at most be small constant factor larger than the core.

Theorem (Simplified version of Theorem 20).

There exists a constant $\delta>0$ such that for any threshold HRG $G$ , $\sigma(G)+1\leq\omega(G)\leq\sqrt{4/3-\delta}\cdot\sigma(G)$ holds w.e.h.p. ¹¹1An event holds with extremely high probability (w.e.h.p.), if for every $c>1$ , there exists an $n_{0}$ such that for every $n\geq n_{0}$ the event holds with probability at least $1-n^{-c}$ .

This upper bound improves on prior work [8], which showed that there exists some constant $c>1$ such that $\omega(G)\leq c\cdot\sigma(G)$ holds w.e.h.p., but without providing any upper bound on $c$ .

We can now see that the core and clique are not the same. Nonetheless, (i) this theorem shows that the largest clique size and the core size are closely related, and (ii) the core of HRGs is a very well understood object, whereas the largest clique is not. Thus the natural approach to bound the degeneracy is to use the core. We show the following theorem.

Theorem (Simplified version of Theorems 9 and 9).

There exist constants $\delta_{1},\delta_{2}>0$ such that for any threshold HRG $G$ , $(1+\delta_{1})\cdot\sigma(G)\leq\kappa(G)\leq(4/3-\delta_{2})\cdot\sigma(G)$ holds w.e.h.p.

The main surprise of this theorem is that the degeneracy is bounded away from the coresize by a constant factor. As the chromatic number is lower bounded by the core size, the upper bound on the degeneracy in this theorem implies a simple algorithm colouring with at most $(4/3-\delta_{2})\chi(G)$ colours. The approximation guarantee of this algorithm ranges from $2/\sqrt{3}$ to $4/3$ depending on further model parameters, see Section 2 and Theorem 11 for details. In any case, this improves on the previously best approximation ratio of $2$ [7, Lemma 7]. The algorithm iteratively removes vertices of degree at most $(4/3-\delta_{2})\sigma(G)-1$ and then colours them in the reverse order. The next thing one would hope is to be able colour the graph with $\omega(G)$ colours using the same process. In [3], the authors conducted experiments where they were iteratively removing the vertex with the smallest degree of the graph, up to vertices with residual degree equal to $\omega(G)$ . In their findings, this process did not remove every vertex, implying $\omega(G)$ ¡ $\kappa(G)$ for their generated graphs. We substantiate their findings by providing a rigorous proof demonstrating that the clique number is, in fact, a constant factor smaller than the degeneracy.

Theorem (Simplified version of Theorem 13).

There exists a constant $\varepsilon>0$ such that for any threshold HRG $G$ , $\omega(G)\leq(1-\varepsilon)\cdot\kappa(G)$ holds w.e.h.p.

Our final contribution is to study the degeneracy of geometric inhomogeneous random graphs (GIRGs) [23], a sibling to HRGs. The GIRGs also combine heterogeneity and high clustering. For most properties GIRGs and HRGs exhibit the same behaviour. Perhaps the first paper to find a difference between them is [9], where the authors show that the minimum number of maximal cliques in the two models differ. We show a significant discrepancy for the degeneracy of GIRGs compared to that of HRGs, see Figure 1 and Corollary 24.

Outline.

See Figure 1 for a table with our results, as well as a plot comparing the bounds of our theorems for various model parameters. In Section 1.1 we provide a detailed discussion of our results and techniques. Section 3 contains bounds on the degeneracy of HRGs (Theorem 9). In Section 4, we show the gap between clique number and degeneracy (Theorem 13), as well as bounds on the clique number (Theorem 20). Finally, Section 5 contains results about the degeneracy of GIRGs. Statements where proofs or details are omitted due to space constraints can be found in the full version [1].

Figure 1: Results on the degeneracy

\kappa(G)

and the size of the largest clique

\omega(G)

in hyperbolic random graphs (HRG) and geometric inhomogeneous random graphs (GIRG). The bounds hold w.e.h.p. and are stated in comparison to the core size

\sigma(G)

. Each curve represents the multiplicative factor in front of

\sigma(G)

for

\kappa(G)

and

\omega(G)

(y-axis) depending on the parameter

\alpha\in(1/2,1)

(x-axis). Prior work is listed with white background, whereas our results are listed with blue background.

1.1 Discussion of our Results and Techniques

HRGs have a power-law degree distribution [19, 34], that is, the probability that a vertex has degree $k$ is given by $\sim k^{-(2\alpha+1)}$ . The model parameter $\alpha\in(1/2,1)$ controls the power-law exponent and all our results, particularly the size of the aforementioned constant factor gap depends on the choice of $\alpha$ . For the ease of presentation this overview largely omits this dependence, but the summary of our results in Figure 1 plots it in detail.

Upper bound on degeneracy (Theorem 9).

One consequence of generating a graph in hyperbolic space is that vertices tend to have fewer neighbours with increasing radius, i.e., the expected number of neighbours of a vertex decreases with the distance from the centre of the hyperbolic disc. This produces the power-law degree distribution that is valuable in modelling real-world networks. It also leads to a simple approach for upper bounding degeneracy: instead of removing vertices ordered by (increasing) degree, we remove them by (decreasing) radius. If $k$ is such that each vertex has at most $k$ neighbours of smaller radius, then $k$ is an upper bound on the degeneracy.

The notion governing this approach is the inner-neighbourhood of a vertex, see Figure 2. The inner-neighbourhood of a vertex $u$ with radius $r$ , denoted $\operatorname{\Gamma}(u)$ , is the set of vertices of distance at most $R$ from $u$ , i.e., they are neighbours of $u$ , and with radius at most $r$ , i.e., they are closer to the centre of the disc than $u$ . The size $|\operatorname{\Gamma}(u)|$ of the inner-neighbourhood is called the inner-degree of $u$ . The expected value of $|\operatorname{\Gamma}(u)|$ scales with the area of $u$ ’s inner-ball $\mathcal{I}(r)=\mathcal{B}_{u}(R)\cap\mathcal{B}_{0}(r)$ . More precisely, $\mathbb{E}\left[|\operatorname{\Gamma}(u)|\right]=(n-1)\cdot\mu(\mathcal{I}(r))$ . See Figure 2 a for a visual representation. The vertex of largest inner-degree is denoted $u^{*}$ ; the choice of $u^{*}$ and the value of $|\operatorname{\Gamma}(u^{*})|$ depend on the random distribution of the vertices.

Figure 2: Illustration of the inner-neighbourhood. (a) The pink area is the ball

\mathcal{B}_{0}(r)

. The hatched area

\mathcal{I}_{u}=\mathcal{B}_{u}(R)\cap\mathcal{B}_{0}(r)

is the inner-ball of

u

. The vertices

V\cap\mathcal{I}_{u}

form the inner-neighbourhood

\operatorname{\Gamma}(u)

. (b) Sketch of proof of Lemma 6. Vertex

u^{*}

is the vertex with the largest inner-degree. Each vertex

v\in U=V\cap\mathcal{B}_{0}(r^{*})

has at least nearly as many neighbours within

\mathcal{B}_{0}(r^{*})

as

|\operatorname{\Gamma}(u^{*})|

(w.e.h.p.).

If vertices are removed from outside to inside, then each vertex at the time of its removal will have degree less or equal to the inner-degree of $u^{*}$ . To bound the degeneracy, we derive a probabilistic upper bound for $|\operatorname{\Gamma}(u^{*})|$ . We do this by finding the radius that maximises $\mu(\mathcal{I}(r))$ , which upper bounds $\mathbb{E}\left[|\operatorname{\Gamma}(u)|\right]$ (for every vertex $u$ ). Since $|\operatorname{\Gamma}(u)|$ is concentrated we can apply a Chernoff and a union bound to obtain a high probability upper bound for $|\operatorname{\Gamma}(u^{*})|$ . Despite the simplicity of the inner-neighbourhood, we elaborate on this key concept as it is not only crucial to our upper bound on degeneracy but also for most of our other results discussed later on.

Lower bound on degeneracy (Theorem 9).

In Lemma 6 we show that the maximum inner-degree also produces a lower bound on the degeneracy $\kappa(G)$ , in the sense that $\kappa(G)\geq(1-o(1))|\operatorname{\Gamma}(u^{*})|$ w.e.h.p. This yields asymptotically tight bounds on $\kappa(G)$ . We prove the lower bound of $\kappa(G)$ by considering the subgraph $G^{\prime}$ induced by the vertices that have smaller radius than $u^{*}$ (see Figure 2 b). Note that $G^{\prime}$ contains vertices that are not neighbours of $u^{*}$ . We show that every vertex $u$ in $G^{\prime}$ has, w.e.h.p., at least $(1-o(1))|\operatorname{\Gamma}(u^{*})|$ neighbours in $G^{\prime}$ ; this statement uses the choice of $u^{*}$ and is not true if $u$ was an arbitrary vertex. Now, in any ordering of the vertices of $G^{\prime}$ , the first vertex has at least $(1-o(1))|\operatorname{\Gamma}(u^{*})|$ neighbours of greater index, implying $(1-o(1))|\operatorname{\Gamma}(u^{*})|\leq\kappa(G^{\prime})\leq\kappa(G)$ . While this provides a lower bound that asymptotically matches our upper bound, a lower order gap remains.

Gap between clique number and degeneracy (Theorem 13).

The most immediate lower bound for degeneracy is the clique number [2], because in every ordering of the vertices of $G$ , the vertex of the clique with the lowest index has at least $\omega(G)-1$ neighbours of higher index. We prove that the lower bounds on the degeneracy that are derived from the clique number are strictly worse than the bounds discussed above obtained via analysing the inner-degree. Our approach to show this is the following: we take an arbitrary clique $K$ and the vertex $u$ with the largest radius in $K$ . Let $G^{\prime\prime}$ be the subgraph induced by $\operatorname{\Gamma}(u)$ . Next, we partition $G^{\prime\prime}$ intro three sets of vertices, each containing at least a constant fraction of the vertices of $G^{\prime\prime}$ w.e.h.p. See Figure 3 b for an illustration of this partition. Lastly, we use purely geometric arguments to show that $K$ cannot contain vertices from all three sets. The gap then follows as the left out set contains a constant fraction of $u$ ’s inner neighbourhood. This gap between $\omega(G)$ and $\kappa(G)$ makes approaches for computing the clique number via degeneracy, like that of Walteros and Buchanan [35], unsuitable for HRGs.

Clique number and the core (Theorem 20).

The upper bound on the clique number is proven via a geometric approach. Let $u, v, w$ be any three vertices. If the vertices are far apart they cannot be contained in a clique. Otherwise their pairwise distance is at most $R$ . Using the hyperbolic of version Jung’s theorem [20, 14, 15] implies that they are contained in a ball $\mathcal{B}$ of small radius and we show that $\mathcal{B}$ also has a small area. Hence the expected number of vertices in $\mathcal{B}$ is small as well. As this expectation is well concentrated whenever the area is significantly large, this bound holds with extremely high probability when introducing lower order deviations from the expectation. Via a union bound over all possible $\binom{n}{3}$ triples of vertices we rule out that any clique contained in such a covering ball is large. The main claim now follows because any clique has to be contained in one of these coverings balls. The question of whether $\omega(G)/\sigma(G)\to 1$ as $n\to\infty$ remains open.

2 Preliminaries

Hyperbolic Random Graphs.

We follow the formalisation of hyperbolic random graphs introduced in [34], which is known as the native representation. We denote by $\mathbb{H}^{2}=[0,\infty)\times[0,2\pi)$ the hyperbolic plane in the polar coordinate system, where a point $x\in\mathbb{H}^{2}$ is parametrised by a radius $r(x)$ and an angle $\varphi(x)$ . We equip $\mathbb{H}^{2}$ with a metric $\operatorname{d_{h}}(x,y)$ characterised by

\displaystyle\cosh(\operatorname{d_{h}}(x,y))=\cosh(r(x))\cosh(r(y))-\sinh(r(y% ))\sinh(r(x))\cos(\varphi(x)-\varphi(y)).

(1)

This metric is what gives $\mathbb{H}^{2}$ a hyperbolic geometry, of curvature -1, as opposed to the Euclidean metric. We equip $\mathbb{H}^{2}$ with the topology induced by $\operatorname{d_{h}}$ .

The geometric space of most importance in this work is the bounded disk in $\mathbb{H}^{2}$ defined by $\mathcal{D}_{R}=[0,R]\times[0,2\pi)$ , where $R=2\log(n)+C$ with $C\in\Theta(1)$ . We refer to point $(0,0)$ as the centre of this disk. The space $\mathcal{D}_{R}$ inherits the topology of $\mathbb{H}^{2}$ , and from now on we shall only consider subsets of this space – thus, for example, a ball around a point $x\in\mathcal{D}_{R}$ is defined by the set $\mathcal{B}_{x}(\varepsilon)=\{y\in\mathcal{D}_{R}:\operatorname{d_{h}}(x,y)% \leq\varepsilon\}\subseteq\mathcal{D}_{R}$ .

We now introduce a probability measure $\mu$ on $\mathcal{D}_{R}$ , which is parametrised by the model parameter $\alpha\in(1/2,1)$ , and was first defined by Papadopoulos et. al. [34]. For measurable $\mathcal{S}\subseteq\mathcal{D}_{R}$ , define

\displaystyle\mu(\mathcal{S})=\int_{S}\rho(x)\,\mathrm{d}x,\qquad\rho(x)=\frac% {\alpha\sinh(\alpha x)}{2\pi(\cosh(\alpha R)-1)},

where $\rho$ is the density of $\mu$ with respect to the Lebesgue measure on $\mathcal{D}_{R}$ . This measure differs from the uniform probability measure on $\mathcal{D}_{R}$ in that it puts more mass at the centre of the disk; both measures coincide at $\alpha=1$ . The benefit of $\mu$ lies in the properties it induces in our central object of study, the hyperbolic random graph.

Threshold hyperbolic random graph (HRG).

A (threshold) hyperbolic random graph or HRG is a pair $G=(V,E)$ defined by the following procedure. First, $n$ vertices are sampled independently at random in $\mathcal{D}_{R}$ according to $\mu$ . Then any two vertices $u,v\in V$ are connected by an edge if and only if their distance $\operatorname{d_{h}}(u,v)$ is at most $R$ . We write $G\sim\mathcal{G}(n,\alpha,C)$ to denote a graph generated in this way. A vertex $u\in V$ is identified by its point coordinates in $\mathbb{H}^{2}$ and we write $V\cap\mathcal{A}$ to denote the set of vertices that are located in an area $\mathcal{A}\subseteq\mathcal{D}_{R}$ .

The use of $\mu$ to distribute vertices in $\mathcal{D}_{R}$ has the effect of giving $G$ a power-law degree distribution, as was shown in [19, 34]. It is sometimes convenient to characterise connection of vertices in terms of their angular distance, and to that end we define

\displaystyle\theta_{R}(r_{1},r_{2})=\arccos\left(\frac{\cosh(r_{1})\cosh(r_{2% })-\cosh(R)}{\sinh(r_{1}\sinh(r_{2})}\right),

which per (1) yields the following observation.

Observation 1.

Two vertices $u$ and $v$ are connected if and only if their angular distance is less than $\theta_{R}(r(u),r(v))$ .

We also make use of the following expression of the distribution of the radius of a vertex $u$ .

\displaystyle\mathbb{P}\left(r(u)\leq r\right)=\mu\left(\mathcal{B}_{0}(r)% \right)=\int_{0}^{r}\int_{-\pi}^{\pi}\rho(x)\,\mathrm{d}\theta\,\mathrm{d}x=% \frac{\cosh(\alpha r)-1}{\cosh(\alpha R)-1}=(1-o(1))e^{-\alpha(R-r)}

(2)

We briefly note that a variant of HRGs exists in which vertices are not connected purely according to whether their distance is below a threshold, but rather with probability $p(u,v)=(1+\exp\left(\frac{1}{2T}\left(\operatorname{d_{h}}(u,v)-R\right)\right% ))^{-1}$ determined by both distance and a “temperature” parameter $T$ (see e.g. [30, §3.1]).

Degeneracy, clique number, chromatic number and core.

For a graph $G=(V,E)$ , the degeneracy $\kappa(G)$ is the minimum integer $k$ for which there exists an ordering of the vertex set of $G$ , $V=(v_{1},v_{2},\cdots,v_{n})$ , such that for every index $i\in[n-1]$ , $v_{i}$ has at most $k$ neighbours with greater index. The clique number $\omega(G)$ is the size of the largest clique of $G$ . The chromatic number $\chi(G)$ is the smallest number of colours required so that a conflict-free vertex colouring is possible for $G$ . The core of a hyperbolic random graph is the set of vertices with radius at most $R/2$ and we denote its size by $\sigma(G)$ . Since for any points $u,v\in\mathcal{B}_{0}(R/2)$ the distance is at most $\operatorname{d_{h}}(u,v)\leq R$ , the core forms a clique. Finally, since the core is a clique, any vertex of a clique needs a different colour in a conflict-free colouring, and $\chi(G)\leq\kappa(G)+1$ (see e.g. [31, Lemma 4]), we have the following chain of inequalities.

Observation 2.

Let $G\sim\mathcal{G}(n,\alpha,C)$ be a threshold HRG. Then,

\sigma(G)\leq\omega(G)\leq\chi(G)\leq\kappa(G)+1.

Concentration bounds.

We use the following Chernoff bounds [32, Theorem 4.4].

Theorem 3 (Chernoff bound).

For $i\in[k]$ , let $X_{i}\in\{0,1\}$ be independent random variables and $X=\sum_{i}X_{i}$ . Then for $\varepsilon\in(0,1)$ ,

\displaystyle\mathbb{P}\left(X\geq(1+\varepsilon)\mathbb{E}[X]\right)\leq e^{-% \varepsilon^{2}\cdot\mathbb{E}[X]/3}\text{ and }\mathbb{P}\left(X\leq(1-% \varepsilon)\mathbb{E}[X]\right)\leq e^{-\varepsilon^{2}\cdot\mathbb{E}[X]/2}.

3 Degeneracy of Hyperbolic Random Graphs

A tool we make use of several times is the inner-ball of a point $x\in\mathcal{D}_{R}$ , defined by $\mathcal{I}_{x}=\mathcal{B}_{x}(R)\cap\mathcal{B}_{0}(r(x))$ . The inner-ball of a vertex is the inner-ball of the point using the vertex’ coordinates. The inner-neighbourhood of a vertex $u$ is the set of vertices (excluding $u$ ) contained in its inner-ball, that is, the neighbours of $u$ that have a smaller radius than $u$ (see Figure 2 a), and is denoted $\operatorname{\Gamma}(u)$ .

We upper bound the degeneracy $\kappa(G)$ via the inner-neighbourhood by using the following informal process. Consider a graph $G$ and order its vertices $(v_{1},v_{2},\cdots,v_{n})$ by decreasing radius, so $r(v_{i})\geq r(v_{i+1})$ , and iteratively remove vertices from $G$ one-by-one, from lower to higher index. Note that the set of neighbours of $v_{i}$ that have greater index than $i$ coincide with $\operatorname{\Gamma}(v_{i})$ . This implies that the degree of each vertex $v_{i}$ at the time of its removal is $|\operatorname{\Gamma}(v_{i})|$ . Let $u^{*}$ be the vertex $v_{k}$ that maximises $|\operatorname{\Gamma}(v_{k})|$ . As the largest degree of a vertex at the time of its removal is given by $|\operatorname{\Gamma}(u^{*})|$ , we get the following upper bound for the degeneracy.

Observation 4.

Let $G\sim\mathcal{G}(n,\alpha,C)$ be a threshold HRG and let $u^{*}$ be the vertex of $G$ with the largest inner-degree in $G$ . Then $\kappa(G)\leq|\operatorname{\Gamma}(u^{*})|$ .

We will now show that the largest inner-degree does not only yield an immediate upper bound on the degeneracy, but also a lower bound. Informally, this lower bound follows from the following argument. Order the vertices of the graph in descending order of their radius, that is, $(v_{1},v_{2},\ldots,v_{n})$ such that $r(v_{i})\geq r(v_{i+1})$ . For $i\in[n]$ , let $G_{i}=G\setminus\{v_{1},v_{2},\ldots,v_{i}\}$ . Let $v_{k}$ be the node with the maximum inner neighbourhood in $G$ . We show (with a probabilistic guarantee) that the graph $G_{k}$ has minimum degree $(1-o(1))|\operatorname{\Gamma}(v_{k})|$ . Before we make this formal, we introduce a slightly modified version of [19, Lemma 3.3], that implies the following: the closer a vertex is to the origin, the more neighbours it has in expectation. This can be derived via the fact that the angle $\theta_{R}(r,x)$ is monotonically decreasing in $x$ .

Corollary 5.

Let $r,s,t\in[0,R)$ with $s<t$ . Then $\mu(\mathcal{B}_{s}(R)\cap\mathcal{B}_{0}(r))\geq\mu(\mathcal{B}_{t}(R)\cap% \mathcal{B}_{0}(r))$ .

Corollary 5 tells us that any vertex with radius at most $r$ has in expectation at least as many neighbours up to radius $r$ , as the expected inner-degree of a vertex with radius exactly $r$ . In order to derive a high-probability bound on $|\operatorname{\Gamma}(u^{*})|$ it now suffices to show concentration around the expectation of all considered neighbourhoods.

Since the size of every clique $K$ is upper bounded by the inner-degree of the vertex in $u\in K$ that has the largest radius, $\omega(G)$ is a lower bound for the maximum inner-degree. We can now lower bound the degeneracy $\kappa(G)$ based on the largest inner-degree. Note that, in contrast to the upper bound of Observation 4, the lower bound is not deterministic.

Lemma 6.

Let $G\sim\mathcal{G}(n,\alpha,C)$ be a threshold HRG. Then $\kappa(G)\geq(1-o(1))|\operatorname{\Gamma}(u^{*})|$ w.e.h.p.

Proof.

For any subgraph $H\subseteq G$ , it is clear that $\kappa(G)\geq\min_{v\in V(H)}\mathrm{deg}|_{H}(v)$ , where $\mathrm{deg}|_{H}(v)=\sum_{w\in V\setminus\{v\}}\operatorname{\mathds{1}}\{\{v% ,w\}\in E(H)\}$ . We let $H$ be the (random) subgraph of $G$ created by restricting $G$ to vertices that land in $\mathcal{B}_{0}(r)$ , that is, that have radius at most $r$ , and keeping the same edges. Then for any $v\in V$ ,

$\displaystyle\mathbb{E}[\mathrm{deg}\|_{H}(v)\|r(v)]$	$\displaystyle=\sum_{w\in V\setminus\{v\}}\mathbb{P}(w\in\mathcal{B}_{0}(r)\cap% \mathcal{B}_{r(v)}(R)\;\|\;r(v))\operatorname{\mathds{1}}\{r(v)\leq r\}$
	$\displaystyle=(n-1)\mu(\mathcal{B}_{0}(r)\cap\mathcal{B}_{r(v)}(R))% \operatorname{\mathds{1}}\{r(v)\leq r\}$
	$\displaystyle\geq(n-1)\mu(\mathcal{B}_{0}(r)\cap\mathcal{B}_{r}(R))% \operatorname{\mathds{1}}\{r(v)\leq r\}.$	(Corollary 5)

We write $\gamma\coloneqq(n-1)\mu(\mathcal{B}_{0}(r)\cap\mathcal{B}_{r}(R))$ . Since $\mathrm{deg}|_{H}(v)$ is a sum of Bernoulli random variables that are all independent under $\mathbb{P}(\,\cdot\,|\,r(v))$ , a Chernoff bound (Theorem 3) gives

$\displaystyle\mathbb{P}\Big{(}\min_{v\in V(H)}\mathrm{deg}\|_{H}(v)$	$\displaystyle<(1-\varepsilon)\gamma\Big{)}=\mathbb{P}\Big{(}\bigcup_{v\in V}\{% \mathrm{deg}\|_{H}(v)<(1-\varepsilon)\gamma,r(v)\leq r\}\Big{)}$
	$\displaystyle\leq n\mathbb{P}(\mathrm{deg}\|_{H}(v)<(1-\varepsilon)\gamma,r(v)% \leq r)$	(Union bound)
	$\displaystyle=n\mathbb{E}\left[\mathbb{P}(\mathrm{deg}\|_{H}(v)<(1-\varepsilon)% \gamma\;\|\;r(v))\operatorname{\mathds{1}}\{r(v)\leq r\}\right]$	(Tower rule)
	$\displaystyle\leq n\mathbb{E}\Big{[}\mathrm{e}^{-\varepsilon^{2}\mathbb{E}[% \mathrm{deg}\|_{H}(v)\|r(v)]/2}\operatorname{\mathds{1}}\{r(v)\leq r\}\Big{]}$	(Chernoff bound)
	$\displaystyle\leq n\mathrm{e}^{-\gamma\varepsilon^{2}/2}\mathbb{P}(r(v)\leq r)% \leq n\mathrm{e}^{-\gamma\varepsilon^{2}/2}.$

Taking $r$ to be the argmax of $\gamma$ yields $\gamma(r)\geq\mathbb{E}[\Gamma(u^{*})]$ . By Observation 2 and applying (2) at $R/2$ we have that $\gamma(r)\geq\mathbb{E}[\Gamma(u^{*})]\geq\mathbb{E}[\sigma(G)]\in n^{\Omega(1% )}.$ Thus, choosing $\varepsilon=1/\log(n)$ , we obtain for any constant $c$ as long as $n$ is large enough

\displaystyle\mathbb{P}(\kappa(G)<(1-\varepsilon)|\operatorname{\Gamma}(u^{*})% |)\leq\mathbb{P}(\kappa(G)<(1-\varepsilon)\gamma(r))\leq n\mathrm{e}^{-\gamma(% r)\varepsilon^{2}/2}\leq n\mathrm{e}^{-n^{\Omega(1)}/\log(n)}\leq n^{1-c},

that is, $\kappa(G)\geq(1-o(1))|\operatorname{\Gamma}(u^{*})|$ w.e.h.p. $\hfill\blacktriangleleft$

In the rest of this section we derive bounds for the largest inner-degree on HRGs that hold w.e.h.p. which, by Observations 4 and 6, translate into results for the degeneracy. Since a vertex $v$ belongs to the inner-neighbourhood of a vertex $u$ , if and only if it resides in the inner-ball of $u$ , we can use the measure of an inner-ball $\mathcal{I}_{u}$ to bound the maximum inner-degree of a graph. Moreover, the measure of the inner-ball is invariant under rotation around the origin, which is why we write $\mu\left(\mathcal{I}(r)\right)$ instead of $\mu\left(\mathcal{I}_{u}\right)$ for $r=r(u)$ . We sum up our results for the area of the inner-ball in the following technical lemma.

Lemma 7 (Volume of the inner-ball).

Let $\Delta\in\Theta(1)$ and let $u\in\mathcal{D}_{R}$ with radius $r=R/2+\Delta$ . Then, depending on $\Delta$ , there exist constants $\gamma,\eta$ , such that

	$\displaystyle\mu(\mathcal{I}(r))$	$\displaystyle\geq\left(1+\Theta\left(e^{-\alpha R}\right)\right)\frac{\alpha e% ^{-\alpha r}}{(\alpha-1/2)}\left(\frac{2}{\pi}e^{\frac{1}{2}(2\alpha-1)(2r-R)}% -\left(\frac{2}{\pi}-\frac{(\alpha-1/2)}{\alpha}\right)\right)$	and
	$\displaystyle\mu(\mathcal{I}(r))$	$\displaystyle\leq\left(1+\Theta\left(e^{-\alpha R}\right)\right)\frac{\alpha e% ^{-\alpha r}}{\alpha-1/2}\left(\gamma e^{\frac{1}{2}(2\alpha-1)(2r-R)}-\eta% \right),$

where

\displaystyle\gamma,\eta=\begin{cases}1,\frac{1}{2\alpha}&\text{ for }\Delta% \geq 0,\\ \frac{4}{3\sqrt{3}},\frac{1}{2\alpha}-\left(1-\frac{4}{3\sqrt{3}}\right)\left(% \frac{4}{3}\right)^{(\alpha-1/2)}&\text{ for }\Delta\geq\log(\sqrt{4/3}),\\ \frac{1}{\sqrt{2}},\frac{1}{2\alpha}-\left(1-\frac{4}{3\sqrt{3}}\right)\left(% \frac{4}{3}\right)^{(\alpha-1/2)}-\left(\frac{4}{3\sqrt{3}}-\frac{1}{\sqrt{2}}% \right)2^{(\alpha-1/2)}&\text{ for }\Delta\geq\log(\sqrt{2}),\\ \frac{2}{3},\frac{1}{2\alpha}-\left(1-\frac{4}{3\sqrt{3}}\right)\left(\frac{4}% {3}\right)^{(\alpha-1/2)}-\left(\frac{4}{3\sqrt{3}}-\frac{1}{\sqrt{2}}\right)2% ^{(\alpha-1/2)}-\left(\frac{1}{\sqrt{2}}-\frac{2}{3}\right)2^{(2\alpha-1)}&% \text{ for }\Delta\geq\log(2).\\ \end{cases}

Lemma 8.

Let $r^{*}$ be the radial coordinate of the point in $\mathcal{D}_{R}$ that maximises the measure of the inner-ball. Then $r^{*}=R/2+\log\left(\frac{\alpha\eta}{\gamma(1-\alpha)}\right)/(2\alpha-1)$ .

Proof.

Using the expression of $\mu(\mathcal{I}(r))$ in Lemma 7,

\displaystyle\frac{\mathrm{d}}{\mathrm{d}r}\mu(\mathcal{I}(r))

\displaystyle=\left(1+\Theta\left(e^{-\alpha R}\right)\right)\left(\frac{\eta% \alpha^{2}e^{-\alpha r}}{\alpha-1/2}-\frac{\gamma\alpha e^{-\alpha r}}{\alpha-% 1/2}\left((1-\alpha)e^{\frac{1}{2}(2\alpha-1)(2r-R)}\right)\right).

Setting this equal to $0$ and solving for $r$ yields $r^{*}=R/2+\log(\frac{\alpha\eta}{\gamma(1-\alpha)})/(2\alpha-1)$ . $\hfill\blacktriangleleft$

We use Lemma 7 to upper and lower bound the degeneracy. The lower bound tells us that there exists a constant $\delta_{\alpha}>0$ such that $\kappa(G)\geq(1+\delta_{\alpha})\sigma(G)$ w.e.h.p. The constant $\delta_{\alpha}$ is increasing with increasing $1/2<\alpha<1$ , see Figure 1.

Theorem 9 (Bounds on the degeneracy).

Let $G\sim\mathcal{G}(n,\alpha,C)$ be a threshold HRG. Then w.e.h.p. its degeneracy $\kappa(G)$ satisfies

\displaystyle\frac{(4-o(1))}{\pi}\left(\frac{2\left(1-\alpha\right)}{\frac{\pi% }{2}-\alpha\left(\pi-2\right)}\right)^{\frac{1-\alpha}{2\alpha-1}}\sigma(G)% \leq\kappa(G)\leq((4/3)^{\alpha}+o(1))\sigma(G).

Proof sketch.

The upper bound is obtained by using $r^{*}$ as stated in Lemma 8 for the upper bound of the inner-ball with $(n-1)\mu(\mathcal{I}(r^{*}))$ , and using a Chernoff bound along with a union bound which gives an upper bound for $|\operatorname{\Gamma}(u^{*})|$ w.e.h.p. Observation 4 then yields the upper bound for the degeneracy. For the lower bound, we first show that there exists a vertex with a radius $\tilde{r}$ close in value to $r^{*}$ w.e.h.p. Then $(1-o(1))(n-1)\mu(\mathcal{I}(\tilde{r}))$ lower bounds $|\operatorname{\Gamma}(u^{*})|$ w.e.h.p. This gives a lower bound for the degeneracy, due to Lemma 6. $\hfill\blacktriangleleft$

Applying Observations 2 and 9, the following is immediate.

Corollary 10 (Bounds on the chromatic number).

Let $G\sim\mathcal{G}(n,\alpha,C)$ be a threshold HRG. Then w.e.h.p. its chromatic number is $\sigma(G)\leq\chi(G)\leq((4/3)^{\alpha}+o(1))\sigma(G).$

Our structural results directly produce algorithmic applications. The small gap between degeneracy and core translates into an efficient approximation algorithm to colour a HRG.

Theorem 11.

Let $G\sim\mathcal{G}(n,\alpha,C)$ be a threshold HRG. Then an approximate vertex colouring of $G$ can be computed in time $\mathcal{O}(n)$ with approximation ratio $((4/3)^{\alpha}+o(1))$ w.e.h.p.

Proof sketch..

Using a smallest-last vertex ordering [31] the number of colours required is upper-bounded by $\kappa(G)$ . Computing the smallest-last vertex ordering, and then using the ordering to colour the graph, both takes linear as the giant component is sparse w.e.h.p. by [25, Corollary 17]. The approximation ratio is achieved by comparing the lower bound of the chromatic number in Corollary 10 to the upper bound of the degeneracy in Theorem 9. $\hfill\blacktriangleleft$

4 Clique Number of Hyperbolic Random Graphs

Recall that for any graph $G$ , the clique number $\omega(G)$ , chromatic number $\chi(G)$ , and degeneracy $\kappa(G)$ are related via the inequalities $\omega(G)\leq\chi(G)\leq\kappa(G)+1$ . For this reason we are interested in the relationship between clique number and degeneracy for hyperbolic random graphs. In Section 4.1 we show that the two differ and that for HRGs, the degeneracy is strictly larger than the clique number by a constant multiplicative constant. In Section 4.2 we give new insights about where in the hyperbolic disk the largest clique is formed. We then conclude the section by providing a new upper bound for the clique number in Section 4.3 that states a leading constant in front of the size of the core, and that is increasing in $\alpha$ .

4.1 The gap between Clique Number and Degeneracy

Because of the centralising effect of hyperbolic geometry, one might hope to show that the clique contained in the core of the disk is the largest, and that $\omega(G)=(1-o(1))\kappa(G)$ . This would achieve two things on HRGs: first, it would imply a tight bound for the chromatic number $\chi(G)$ , sandwiching it between clique number and degeneracy. Moreover, it would also imply a linear time $(1+o(1))$ -approximation algorithm for the two NP-complete problems clique number and chromatic number using a smallest-last vertex ordering (see [31]).

In this section we disprove these claims. We show that there exists a constant gap between clique number and degeneracy; this is the content of Theorem 13. Before embarking on the details of the proof, we first sketch its idea. For any clique $K$ , its size is bounded by the inner-degree $|\operatorname{\Gamma}(u)|$ , where $u$ is the vertex with largest radius among the vertices of $K$ . For $r(u)\leq R/2+o(1)$ and $r(u)\in R/2+\omega(1)$ , $|\operatorname{\Gamma}(u)|$ is already smaller by a multiplicative constant than the lower bound for the degeneracy given in Theorem 9. What remains is to extend the result to $r(u)\in R/2+\Theta(1)$ , which requires more intricate arguments and is addressed in the following lemma.

Lemma 12.

Let $G\sim\mathcal{G}(n,\alpha,C)$ be a threshold HRG, let $\Delta\in\Theta(1)$ and let $K$ be any clique where $u\in K$ is the vertex with largest radius $r_{K}=R/2+\Delta$ . Then w.e.h.p. there exists a constant $\varepsilon\in(0,1)$ such that $|K|\leq(1-\varepsilon)|\operatorname{\Gamma}(u)|$ .

Proof.

Figure 3: Illustration of a separator. (a) The line

a_{\varphi}

partitions disk

\mathcal{D}_{R}

into two halfdisks

\mathcal{D}_{1}

(blue) and

\mathcal{D}_{2}

(pink). The hypercycle

\mathcal{H}_{\varphi}

(hatched area) is defined by the line

a_{\varphi}

. Points located in different halfdisks and outside the hatched area have distance at least

R

. (b) The separator (hatched area) separates the inner-neighbourhood (grey area) of a vertex

u

of radius

r_{K}

into three sub-areas

\mathcal{S}_{0}

,

\mathcal{S}_{1}

and

\mathcal{S}_{2}

. Any vertex located in

\mathcal{S}_{1}

has no edge to a vertex in

\mathcal{S}_{2}

.

Let $G^{\prime}$ be the inner-neighbourhood of $u$ , i.e., the induced subgraph $G^{\prime}=G[\Gamma(u)]$ . Then $K\subseteq V(G^{\prime})$ , and thus $\omega(G^{\prime})\geq|K|$ . We show that $\omega(G^{\prime})<(1-\varepsilon)|\operatorname{\Gamma}(u)|$ w.e.h.p.

We accomplish this by proving that there exists a colouring for $G^{\prime}$ with $(1-\varepsilon)|V(G^{\prime})|=(1-\varepsilon)|\operatorname{\Gamma}(u)|$ many colours. This implies an upper bound for the chromatic number $\chi(G^{\prime})$ , which also serves as an upper bound for $\omega(G^{\prime})$ . We do this by partitioning the inner-neighbourhood $\mathcal{I}_{u}$ into three disjoint sub-regions $\mathcal{S}_{0}\cup\mathcal{S}_{1}\cup\mathcal{S}_{2}$ such that no vertex in $\mathcal{S}_{1}$ is adjacent to any vertex in $\mathcal{S}_{2}$ . Thus, $\mathcal{S}_{0}$ separates $\mathcal{S}_{1}$ from $\mathcal{S}_{2}$ and we can colour the set of vertices $V\cap\mathcal{S}_{1}$ with the same colours as $V\cap\mathcal{S}_{2}$ . Thus if $\min\{|V\cap\mathcal{S}_{1}|,|V\cap\mathcal{S}_{2}|\}\geq\varepsilon|% \operatorname{\Gamma}(u)|$ w.e.h.p., our desired statement will be proven.

To find such a separator $\mathcal{S}_{0}$ , we follow the lines drawn by Bläsius et. al. [10] where hypercycles for hyperbolic random graphs were introduced (see Figure 3 a). A hypercycle $\operatorname{\mathcal{H}}_{\varphi}$ (of radius $R/2$ ) is defined as follows: let $a_{\varphi}$ denote the line whose points have angle $\varphi$ and $\varphi+\pi$ . Then $\operatorname{\mathcal{H}}_{\varphi}:=\{u\in\mathcal{D}_{R}:\operatorname{d_{h% }}(u,a_{\varphi})\leq R/2\}$ , i.e. the set of points with distance at most $R/2$ to line $a_{\varphi}$ . Consider the point $u=\left(r_{K},\varphi\right)$ and let $\mathcal{S}_{0}:=\mathcal{I}_{u}\cap\operatorname{\mathcal{H}}_{\varphi}$ . To define $\mathcal{S}_{1}$ and $\mathcal{S}_{2}$ separate $\mathcal{D}_{R}$ into the two disjoint halfdisks $\mathcal{D}_{1}=\{x\in\mathcal{D}_{R}:\varphi(x)-\varphi\leq\pi\}$ and $\mathcal{D}_{2}=\{x\in\mathcal{D}_{R}:\varphi(x)-\varphi\geq\pi\}$ (see Figure 3 a). Then we define $\mathcal{S}_{1}:=(\mathcal{I}_{u}\cap\mathcal{D}_{1})\setminus\operatorname{% \mathcal{H}}_{\varphi}$ and symmetrically $\mathcal{S}_{2}:=(\mathcal{I}_{u}\cap\mathcal{D}_{2})\setminus\operatorname{% \mathcal{H}}_{\varphi}$ .

We observe that any point $w\in\mathcal{S}_{1}$ has distance at least $R$ to any point $v\in\mathcal{S}_{2}$ . This can be shown for example by observing that the geodesic between $w$ and $v$ must pass through some point $x\in a_{\varphi}$ , and so $\operatorname{d_{h}}(w,v)=\operatorname{d_{h}}(w,x)+\operatorname{d_{h}}(x,v)% \geq\operatorname{d_{h}}(w,a_{\varphi})+\operatorname{d_{h}}(a_{\varphi},v)>R$ . This ensures our objective of separating the two regions via $\mathcal{S}_{0}$ .

Next, we show that there exists a constant $\varepsilon>0$ small enough, such that $\mu(\mathcal{S}_{1})=\mu(\mathcal{S}_{2})\geq\varepsilon n^{-\alpha}$ (a sketch of the idea is given in Figure 3 b). Setting $\phi(x)=\max(0,\theta_{R}\left(r_{K},x\right)-\theta_{R}(x,x)/2)$ we derive by symmetry

\mu(\mathcal{S}_{1})=\mu(\mathcal{S}_{2})=\int_{R/2}^{r}\int_{0}^{\phi(x)}\rho% (x)\,\mathrm{d}\phi\,\mathrm{d}x=\int_{R/2}^{R/2+\Delta}\phi(x)\rho(x)\,% \mathrm{d}x.

Now we choose another constant $\Delta^{\prime}<\Delta$ that fulfills $2\theta_{R}(R/2+\Delta,R/2+\Delta^{\prime})-\theta_{R}(R/2+\Delta^{\prime},R/2% +\Delta^{\prime})\eqqcolon c\in\Theta(1)$ . This is possible because $\Delta\in\Omega(1)$ . By our choice of $\Delta^{\prime}$ we then obtain

	$\displaystyle\mu(\mathcal{S}_{1})$	$\displaystyle\geq\int_{R/2+\Delta^{\prime}}^{R/2+\Delta}\phi(x)\rho(x)\,% \mathrm{d}x=\int_{R/2+\Delta^{\prime}}^{R/2+\Delta}\left(\theta_{R}(R/2+\Delta% ,x)-\frac{\theta_{R}(x,x)}{2}\right)\rho(x)\,\mathrm{d}x$
		$\displaystyle\geq c\int_{R/2+\Delta^{\prime}}^{R/2+\Delta}\rho(x)\,\mathrm{d}x% =\frac{c(\cosh(\alpha(R/2+\Delta))-\cosh(\alpha(R/2+\Delta^{\prime})))}{\cosh(% \alpha R)-1}\in\Omega(n^{-\alpha}),$

where the last line follows since $\theta_{R}(\cdot,\cdot)$ is monotonically decreasing and since $\rho(x)=\frac{\alpha\sinh(\alpha x)}{\cosh(\alpha R)-1}$ , $|\Delta-\Delta^{\prime}|>0$ and $R=2\log(n)+C$ . Therefore $\mu(\mathcal{S}_{1})\in\Omega(\mathbb{E}\left[|\operatorname{\Gamma}(u)|\right% ]/n)$ w.e.h.p., since

\liminf_{n\to\infty}\frac{n\mu(\mathcal{S}_{1})}{\mathbb{E}\left[|% \operatorname{\Gamma}(u)|\right]}=\liminf_{n\to\infty}\frac{\mu(\mathcal{S}_{1% })}{n^{-\alpha}}\frac{n^{1-\alpha}}{\mathbb{E}\left[|\operatorname{\Gamma}(u)|% \right]}>0,

where $\mathbb{E}\left[|\operatorname{\Gamma}(u)|\right]\leq n\mu(\mathcal{B}_{0}(R/2% +\Delta))\in\mathcal{O}(n^{1-\alpha})$ by Equation 2, because $\Delta\in\mathcal{O}(1)$ . Thus there exists some $\varepsilon>0$ for which, for $n$ large enough,

\mathbb{E}\left[|V\cap\mathcal{S}_{2}|\right]=\mathbb{E}\left[|V\cap\mathcal{S% }_{1}|\right]=n\mu(\mathcal{S}_{1})\geq(1-1/\log(n))^{-2}\varepsilon\mathbb{E}% \left[|\operatorname{\Gamma}(u)|\right];

since $|V\cap\mathcal{S}_{1}|\leq|\operatorname{\Gamma}(u)|$ a.s. and is strictly smaller with positive probability, then $\varepsilon<1$ .

Using a Chernoff bound for both $|V\cap\mathcal{S}_{1}|$ and $|V\cap\mathcal{S}_{2}|$ , we obtain that neither random variable is smaller than $(1-1/\log(n))\mathbb{E}\left[|V\cap\mathcal{S}_{1}|\right]\geq(1-1/\log(n))^{-% 1}\varepsilon\mathbb{E}\left[|\operatorname{\Gamma}(u)|\right]$ w.e.h.p. On the other hand, another application of a Chernoff bound reveals $|\operatorname{\Gamma}(u)|\leq(1+1/\log(n))\mathbb{E}\left[|\operatorname{% \Gamma}(u)|\right]$ w.e.h.p., since for $r(u)\in R/2+\Theta(1)$ we have $\mathbb{E}\left[|\operatorname{\Gamma}(u)|\right]\in\Theta(n^{(1-\alpha)})$ using Lemma 7. A union bound then shows that w.e.h.p., $\min\{|V\cap\mathcal{S}_{1}|,|V\cap\mathcal{S}_{2}|\}\geq\frac{\varepsilon% \mathbb{E}\left[|\operatorname{\Gamma}(u)|\right]}{1-1/\log(n)}\geq\varepsilon% |\operatorname{\Gamma}(u)|.$ As argued above, a naïve colouring that colours the vertices of $\mathcal{S}_{1}$ and $\mathcal{S}_{2}$ with the same set of colours yields the upper bound. $\hfill\blacktriangleleft$

Theorem 13 (Clique-degeneracy-gap).

Let $G\sim\mathcal{G}(n,\alpha,C)$ be a threshold HRG. Then w.e.h.p. there exists a constant $\varepsilon\in(0,1)$ such that $\kappa(G)/\omega(G)>1+\varepsilon$ .

Proof.

Let $K$ be the largest clique of $G$ , and let $u$ be the vertex of $K$ with maximal radius $r_{K}\coloneqq r(u)$ . We assume the following cases for $r_{K}$ which cover all possibilities:
Case 1 [ $r_{K}\in R/2+\omega(1)$ ]: Observe that $K\subseteq V\cap\mathcal{I}\left(r_{K}\right)$ . Hence, $|K|\leq|V\cap\mathcal{I}\left(r_{K}\right)|$ and

\displaystyle\mu\left(\mathcal{I}\left(r_{K}\right)\right)\leq\left(1+\Theta% \left(e^{-\alpha R}\right)\right)\frac{\alpha e^{-\alpha r_{K}}}{\alpha-1/2}% \left(\gamma e^{\frac{1}{2}(2\alpha-1)(2r_{K}-R)}-\eta\right)\in\Theta(1)n^{-% \alpha}e^{-(1-\alpha)\omega(1)},

by Lemma 7 since $\gamma$ and $\eta$ are both constants. Taking the expectation and using a Chernoff bound we have $|K|\in o(n^{1-\alpha})$ w.e.h.p. Recall that $\kappa(G)>(1+\delta)e^{-\alpha C/2}n^{1-\alpha}$ w.e.h.p. by Theorem 9. It follows $\kappa(G)/|K|\in\omega(1)$ w.e.h.p.
Case 2 [ $r_{K}\leq R/2+o(1)$ ]: Observe that the size of any clique $K\subseteq V\cap\mathcal{B}_{0}(r)$ is upper bounded by $X=|V\cap\mathcal{B}_{0}(r)|$ . By Equation 2 we have $\mu(\mathcal{B}_{0}(r_{K}))\leq(1+o(1))n^{-\alpha}e^{-\alpha C/2}$ . Hence, we get $\mathbb{E}[X]\leq(1+o(1))n^{1-\alpha}e^{-\alpha C/2}$ . Since $X$ is a binomial random variable we can apply a Chernoff bound, which yields $|K|\leq X\leq(1+o(1))n^{1-\alpha}e^{-\alpha C/2}$ w.e.h.p. Taking $\varepsilon=\delta/(1+\delta)$ with $\delta$ as in Theorem 9, we have

\frac{|K|}{1-\varepsilon}\leq(1+o(1))(1+\delta)n^{1-\alpha}e^{-\alpha C/2}<(1+% o(1))\kappa(G)\text{ w.e.h.p.}

Case 3 [ $r_{K}\in R/2+\Theta(1)$ ]: Let $\xi\in o(1)$ . Using Lemmas 12 and 6, we get w.e.h.p. that

\omega(G)=|K|\leq\frac{1-\varepsilon}{1-\xi}|\operatorname{\Gamma}(u)|\leq% \frac{1-\varepsilon}{1-\xi}|\operatorname{\Gamma}(u^{*})|\leq(1-\varepsilon)% \kappa(G),

for an adequate choice of $\xi$ . $\hfill\blacktriangleleft$

Corollary 14.

Let $G\sim\mathcal{G}(n,\alpha,C)$ be a threshold HRG. Then there exists a constant $\varepsilon\in(0,1)$ such that w.e.h.p., $\omega(G)\leq(4(1-\varepsilon)/3)^{\alpha}\sigma(G).$

Proof.

This follows from Theorems 9 and 13. $\hfill\blacktriangleleft$

4.2 Cliques larger than the Core

In this section, we show that there exist a super-constant number of unique cliques that contain the core, but are strictly larger than it. The overall argument goes as follows. We consider a set of vertices with radial coordinates slightly outside the core. We show that any vertex of this set has a constant probability to be adjacent to all vertices belonging to the core, and thus induces a clique that is larger than the core itself. To this end, the following lemma concerned about points close to the core proves useful.

Lemma 15.

Let $k\in\mathbb{N}\setminus\{0\}$ and $\xi_{k}=\log(1+\frac{\log^{k}(n)}{n^{1-\alpha}})\in o(1)$ . Consider two points with radial coordinates $r=R/2+\xi_{k}$ and $x=R/2$ . Then $\theta_{R}(r,x)\geq\pi-2\sqrt{\log^{k}(n)n^{\alpha-1}}$ .

Lemma 15 lower bounds the angle distance such that two points have distance at most $R$ .

Proposition 16.

Let $G\sim\mathcal{G}(n,\alpha,C)$ be a threshold HRG. Then w.e.h.p. there exist $\omega(\log(n))$ cliques that are larger than $\sigma(G)$ .

Proof.

Figure 4: Sketch of the proof idea for Proposition 16. (a) Illustration of the set of points

\mathcal{A}

(blue) of width

\xi

slightly outside of the core (pink). The intersection with a sector of angle

\psi

and the band

\mathcal{A}

forms a box

\mathcal{A}_{i}

that contains a vertex w.e.h.p. The number of non-intersecting boxes is

k=2\pi/\psi\in\omega(\log(n))

. (b) A vertex

u

located on the boundary of the area

\mathcal{A}

. The hatched area

\mathcal{F}_{u}

with angle at most

\phi

is the corresponding forbidden area of

u

. Any point in

\operatorname{\mathcal{F}_{u}}

has distance at least

R

to

u

. An adequate choice for the width

\xi

yields that this area is empty with constant probability.

For the proof we consider the Poissonized version of the HRG model (see e.g. [26, 27]). The upshot of this model is that it allows us to analyse disjoint areas in the hyperbolic disk independently. Since the final result holds w.e.h.p. this directly carries over to the uniform model w.e.h.p. ([22, Lemma 3.9]). We start by defining an area $\mathcal{A}$ close to the core. Let $\xi=\log\left(1+\frac{\log^{3}(n)}{n^{1-\alpha}}\right)\in o(1)$ and consider a band of points $\mathcal{A}:=\mathcal{B}_{0}(R/2+\xi)\setminus\mathcal{B}_{0}(R/2)$ . We see via $R=2\log(n)+C$ that

\displaystyle\begin{split}\mu(\mathcal{A})&=\int_{R/2}^{R/2+\xi}\frac{\sinh(% \alpha x)}{\cosh(\alpha R)-1}=\frac{\cosh(\alpha(R/2+\xi))-\cosh(\alpha R/2)}{% \cosh(\alpha R)-1}\\ &=(1+\Theta(e^{-\alpha R}))(e^{-\alpha(R/2-\xi)}-e^{-\alpha R/2})\\ &=(1+\Theta(e^{-\alpha R}))(n^{-\alpha}e^{-\alpha C/2}{\left(1+\log^{3}(n)n^{% \alpha-1}\right)}-n^{-\alpha}e^{-\alpha C/2})\\ &=(1+\Theta(e^{-\alpha R}))\big{(}e^{-\alpha C/2}\log^{3}(n)n^{-1}\big{)}\in% \Theta\left(\log^{3}\left(n\right)/n\right).\end{split}

(3)

Let $A=V\cap\mathcal{A}$ . Then $\mathbb{E}[|A|]\in\Theta\left(\log^{3}(n)\right)$ . We further partition the band $\mathcal{A}$ into $k=\lceil\log^{3/2}(n)\rceil$ sectors $\mathcal{A}_{1},\ldots,\mathcal{A}_{k}$ , each of equal size (see Figure 4 a), and $A_{i}=V\cap\mathcal{A}_{i}$ . Since $\mathbb{E}[|A|]\in\Theta\left(\log^{3}(n)\right)$ and $k=\log^{3/2}(n)$ , we have for any $i\in[k]$ that $\mathbb{E}[|A_{i}|]=\frac{\mathbb{E}[|A|]}{k}\in\omega(\log(n))$ . Since we are in the Poissonized model we get $\mathbb{P}\left(|A_{i}|=0\right)=e^{-\mathbb{E}\left[|A_{i}|\right]}\in n^{-% \omega(1)}.$ Subsequently, a union bound yields that there is no sector $\mathcal{A}_{i}$ that is empty w.e.h.p.

In the second step, we show that for any vertex $u\in A$ , the probability that there exists a vertex in its forbidden area $\operatorname{\mathcal{F}_{u}}:=\{x\in\mathcal{B}_{0}(R/2):\operatorname{d_{h}% }(u,x)>R\}$ (see Figure 4 b) is strictly less than $1$ . Since $r(u)\leq R/2+\xi$ , we have that $u\in A$ has distance at most $R$ (and thus, an edge) to any vertex in the area $\mathcal{B}_{0}(R/2-\xi)$ . Hence, we have $\operatorname{\mathcal{F}_{u}}\subset\mathcal{B}_{0}(R/2)\setminus\mathcal{B}_% {0}(R/2-\xi)$ . Now, for $R/2\geq x\geq R/2-\xi$ we seek to find the angle size $\phi=2(\pi-\theta_{R}(r(u),x))$ in order to upper bound $\mu(\operatorname{\mathcal{F}_{u}})$ . Since $\theta_{R}(r,x)$ is monotonically decreasing in $x$ we have $\phi\leq 2(\pi-\theta_{R}(R/2+\xi,R/2))$ and we obtain

	$\displaystyle\mu(\operatorname{\mathcal{F}_{u}})=\int_{R/2-\xi}^{R/2}\int_{0}^% {\phi}\rho(x)\,\mathrm{d}\phi\,\mathrm{d}x$	$\displaystyle\leq 2(\pi-\theta_{R}(R/2+\xi,R/2))\int_{R/2}^{R/2+\xi}\rho(x)\,% \mathrm{d}x$
		$\displaystyle\leq 2(\pi-\theta_{R}(R/2+\xi,R/2))\mu(\mathcal{A}),$

where we used $\int_{R/2-\xi}^{R/2}\rho(x)\,\mathrm{d}x\leq\int_{R/2}^{R/2+\xi}\rho(x)\,% \mathrm{d}x=\mu(\mathcal{A})$ . By our choice of $\xi=\log(1+\log^{3}(n)n^{\alpha-1})\in o(1)$ , we can apply Lemma 15 and obtain $\theta_{R}(R/2+\xi,R/2)\geq\pi-2\sqrt{\frac{\log^{3}(n)}{n^{1-\alpha}}}$ . In Equation 3 we established that $\mu(\mathcal{A})\in\Theta\left(\log^{3}\left(n\right)/n\right)$ . Combining the two leads to $\mu(\operatorname{\mathcal{F}_{u}})\in\mathcal{O}\Big{(}\sqrt{\log^{9}(n)n^{% \alpha-3}}\Big{)}$ .

Notice that for $\alpha\in(1/2,1)$ , the measure of the forbidden area of a vertex $u\in A$ is $\mu(\operatorname{\mathcal{F}_{u}})\in o(1/n)$ . Hence, writing $F=V\cap\operatorname{\mathcal{F}_{u}}$ , we get $\mathbb{E}[|F|]\in o(1)$ , i.e., the expected number of vertices in $\operatorname{\mathcal{F}_{u}}$ is vanishing. Applying Markov’s inequality then gives us $\mathbb{P}\left(|F|\geq 1\right)\in o(1)$ . Thus $p\coloneqq\mathbb{P}(|F|<1)\in\Omega(1)$ , so the forbidden area is empty with constant probability.

We now establish our third and final desired property. Namely, we construct a subset $U\subset A$ , consisting of vertices whose forbidden areas are empty and disjoint and for which $\mathbb{E}\left[|U|\right]\in\omega(\log(n))$ .

Recall that we partitioned $\mathcal{A}$ into $k=\log^{3/2}(n)\in\omega(\log(n))$ sectors. Let $X_{i}$ be the indicator that there exists a vertex $u\in\mathcal{A}_{i}$ whose forbidden area $\operatorname{\mathcal{F}_{u}}$ is empty. Then $X=\sum_{i=1}^{\lfloor k/2\rfloor}X_{2i}$ is a loose lower bound on the number of sectors with this property. By linearity of expectation, $p$ constant and $k=\log^{3/2}(n)$ we then obtain

\mathbb{E}[X]\geq\mathbb{E}\Big{[}\sum_{i=1}^{\lfloor k/2\rfloor}X_{2i}\Big{]}% \geq p\cdot\Theta(1)\log^{3/2}(n)\in\omega(\log(n)).

We proceed by showing independence among the random variables $X_{i}$ and $X_{j}$ for $|j-i|>1$ . To this end, observe that the angle $\psi$ (see Figure 4 b) spanned by any sector $\mathcal{A}_{i}$ is $\psi=2\pi/k\geq\left\lfloor 2\pi\log^{-3/2}(n)\right\rfloor$ . In contrast, we recall $\phi\leq 2(\pi-\theta_{R}(R/2+\xi,R/2))\leq 4\sqrt{\log^{3}(n)n^{\alpha-1}}$ . Since $\sqrt{\log^{3}(n)n^{\alpha-1}}\in o(\log^{-3/2}(n))$ we conclude $\phi\in o(\psi)$ . This implies that the forbidden areas $\mathcal{F}_{u}$ and $\mathcal{F}_{v}$ of any $u\in\mathcal{A}_{i}$ , $v\in\mathcal{A}_{j}$ are disjoint. Thus $X_{i}$ and $X_{j}$ are independent.

To wrap things up, recall that in the first step we established that each sector $\mathcal{A}_{i}$ contains a vertex w.e.h.p. Moreover, since the $X_{i}$ are independent, we have by a Chernoff bound that $X\in\omega(\log(n))$ w.e.h.p. Though these two events are not independent, we can apply the union bound to their complements to obtain that w.e.h.p. $\omega(\log(n))$ vertices outside of $\mathcal{B}_{0}(R/2)$ are adjacent to all vertices in $\mathcal{B}_{0}(R/2)$ , which finishes the proof. $\hfill\blacktriangleleft$

4.3 Upper Bound on the Clique Number

Recall that two vertices $u, v$ are adjacent if and only if $\operatorname{d_{h}}(u,v)\leq R$ and that we call the clique formed in $\mathcal{B}_{0}(R/2)$ the core whose size is $\sigma(G)=(1-o(1))e^{-\alpha C/2}n^{1-\alpha}$ w.e.h.p. The core size is a lower bound for the clique number $\omega(G)$ . We have established that the largest clique is smaller than the degeneracy w.e.h.p. (Theorem 13), and in this section we further investigate an upper bound for $\omega(G)$ . We note that the upper bound we derive in this section implies Theorem 13 for $\alpha$ large enough (see Figure 1). However, for smaller $\alpha$ , the upper bound for $\omega(G)$ is larger than the lower bound (Theorem 9) for $\kappa(G)$ in the HRG model, and thus does not directly imply Theorem 13 for these values for $\alpha$ .

Before going into details, we lay out our proof strategy. We aim to bound the region where a clique can be located. Since vertices are adjacent if and only if their (hyperbolic) distance is at most $R$ , this can be done by characterising a shape that covers any hyperbolic region of diameter $R$ . A classic result by Jung [20] answers the question of how large the radius of a ball in Euclidean space needs to be at most, so that its interior can contain an entire set of points of fixed diameter. The hyperbolic version of this result was discovered by Dekster [14, 15] nearly a century later. He extended Jung’s result to (among other geometries) hyperbolic space and we apply it as follows: we identify $\mathcal{O}(n^{3})$ many balls where one of these balls contains the clique of largest size $\omega(G)$ . This clique (and all the other identified cliques) needs to be located in a ball $B_{x}(r)$ with radius $r$ large enough. We use the hyperbolic variant of Jung’s theorem to upper bound $r$ which, in turn, allows us to upper bound the area of this ball. This yields an upper bound for the amount of vertices one such ball $B_{x}(r)$ could contain w.e.h.p., leading to an upper bound for $\omega(G)$ . Since we only need to consider at most $\mathcal{O}(n^{3})$ balls, a union bound is sufficient to derive the same bound for the worst case. We work with the following version of Jung’s theorem for hyperbolic geometry.

Theorem 17.

[14, Theorem 2] Let $\mathcal{K}\subset\mathbb{H}^{d}$ be compact and suppose that for any $y,z\in\mathcal{K}$ , $\operatorname{d_{h}}(y,z)\leq D$ . Then there exists $x\in\mathbb{H}^{d}$ such that $\mathcal{K}\subseteq\mathcal{B}_{x}(r)$ for $r$ satisfying

D\geq 2\sinh^{-1}\left(\sqrt{\frac{d+1}{2d}}\sinh(r)\right).

In the hyperbolic plane $\mathbb{H}^{2}$ , this simplifies to the following.

Corollary 18.

Let $\mathcal{K}\subset\mathbb{H}^{2}$ be compact and suppose that for any $y,z\in\mathcal{K}$ , $\operatorname{d_{h}}(y,z)\leq R$ . Then there exists $x\in\mathbb{H}^{2}$ such that $\mathcal{K}\subseteq\mathcal{B}_{x}(r)$ for $r$ satisfying $r\leq R/2+\log(2/\sqrt{3})$ .

Proof.

Using that $d=2$ , we directly get from Theorem 17 for diameter $R$ that $\frac{R}{2}\geq\sinh^{-1}(\sqrt{3/4}\sinh(r)).$ Rearranging and using for $x\in\mathbb{R}$ that $\sinh(x)=\frac{1}{2}e^{x}(1-e^{-2x})$ yields

R/2-r\geq\log(\sqrt{3/4})+\log\left(\frac{\left(1-e^{-2r}\right)}{\left(1-e^{-% R}\right)}\right).

Solving for $r$ and using that $r\geq R/2\geq\log(n)+C/2$ in conjunction with recalling that $C\in\Theta(1)$ , it follows that $r\leq R/2+\log(2/\sqrt{3}).$ $\hfill\blacktriangleleft$

Our next observation follows from the definition of $\mu$ , and formalises the intuition that $\mu$ puts more mass at the centre of the disk.

Observation 19.

Let $0<r\leq R$ and $u,v\in\mathcal{D}_{R}$ with $r(u)\geq r(v)$ . Then $\mu(\mathcal{B}_{u}(r))\leq\mu(\mathcal{B}_{v}(r))$ .

Recall that $\sigma(G)$ denotes the core size $|V\cap\mathcal{B}_{0}(R/2)|$ which is a lower bound for the clique number $\omega(G)$ (see Observation 2), and that $\sigma(G)=(1-o(1))e^{-\alpha C/2}n^{1-\alpha}$ w.e.h.p. We state our upper bound relative to this lower bound.

Theorem 20 (Clique upper bound).

Let $G\sim\mathcal{G}(n,\alpha,C)$ be a threshold HRG with $\alpha\in(1/2,1)$ . Then w.e.h.p.

\omega(G)\leq\left((4/3)^{\alpha/2}+o(1)\right)\sigma(G).

Proof.

Consider any triplet of vertices $u,v,w\in V$ with pairwise distance at most $R$ , so that they are pairwise adjacent. Since $u, v, w$ are a.s. in general position, there is a unique ball $\mathcal{B}_{x}(r)$ such that $u, v, w$ lie on the boundary $\partial\mathcal{B}_{x}(r)$ . By Corollary 18, $r\leq R/2+\log(\sqrt{4/3})$ since $\max{(\operatorname{d_{h}}(u,v),\operatorname{d_{h}}(v,w),\operatorname{d_{h}}% (u,w))}\leq R$ . Over all possible triplets $u,v,w\in V$ this gives us a set $B$ of at most $\binom{n}{3}$ closed balls. Any clique must be contained in one of these balls, and therefore so is the largest clique. Thus upper bounding the number of vertices for each individual ball $\mathcal{B}\in B$ yields an upper bound on the size of the largest clique.

We now upper bound the expected number of vertices in one ball $B$ . To this end we fix a ball $\mathcal{B}=\mathcal{B}_{x}(r)\in B$ and let $Y_{\mathcal{B}}$ be the random variable counting the number of vertices in $\mathcal{B}$ . The balls in $B$ are identically (though clearly not independently) distributed. Since vertices are thrown independently according to $\mu$ , we have that $Y_{\mathcal{B}}-3\sim\mathrm{Bin}(n-3,\mu(\mathcal{B}))$ , and so

$\displaystyle\mathbb{E}\left[Y_{\mathcal{B}}\right]=3+(n-3)\mu(\mathcal{B})$	$\displaystyle\leq 3+(n-3)\mu(\mathcal{B}_{0}(r))$	(Observation 19)
	$\displaystyle\leq 3+(n-3)\mu(\mathcal{B}_{0}(R/2+\log(2/\sqrt{3})))$	(Corollary 18)
	$\displaystyle\leq\big{(}\big{(}2/\sqrt{3}\big{)}^{\alpha}+o(1)\big{)}e^{-% \alpha C/2}n^{1-\alpha}.$	(Equation 2)

Thus $((4/3)^{\alpha/2}+o(1))\sigma(G)\geq(1+1/\log(n))\mathbb{E}\left[Y_{\mathcal{B% }}\right]$ w.e.h.p. This is relevant to the bound in the theorem statement because it implies that

	$\displaystyle\mathbb{P}\Big{(}\omega(G)>((4/3)^{\alpha/2}+o(1))\sigma(G)\Big{)}$	$\displaystyle\leq\mathbb{P}\Big{(}\max_{\mathcal{B}\in B}Y_{\mathcal{B}}>((4/3% )^{\alpha/2}+o(1))\sigma(G)\Big{)}$
		$\displaystyle\leq\mathbb{P}\Big{(}\max_{\mathcal{B}\in B}Y_{\mathcal{B}}>(1+1/% \log(n))\mathbb{E}[Y_{\mathcal{B}}]\Big{)}+n^{-c}$

for arbitrary $c$ . Thus to finish the proof we need to show concentration, which via a union bound over all triplets $u, v, w$ will yield the result. To show concentration we apply a Chernoff bound Theorem 3. Using $\varepsilon=(1/\log(n))$ we obtain

\displaystyle\mathbb{P}\left(Y_{\mathcal{B}}>(1+1/\log(n))\mathbb{E}[Y_{% \mathcal{B}}]\right)

\displaystyle\leq e^{-\mathbb{E}[Y_{\mathcal{B}}]/(3(1/\log(n))^{2})}\leq e^{-% \Theta(1)(n^{1-\alpha})/\log^{2}(n)}\leq n^{-c}

for any choice of $c$ , since for $\alpha<1$ , $\Theta(1)(n^{1-\alpha})\in n^{\Theta(1)}$ and $\liminf_{n\to\infty}\frac{n^{\Theta(1)}}{\log^{2}(n)}\in\omega(\log(n)).$ Finally, to show that this holds w.e.h.p. for all balls in $B$ , we use that $|B|\leq\binom{n}{3}<n^{3}$ , so that

	$\displaystyle\mathbb{P}\Big{(}\max_{\mathcal{B}\in B}Y_{\mathcal{B}}\geq(1+1/% \log(n))\mathbb{E}[Y_{\mathcal{B}}]\Big{)}$	$\displaystyle\leq\sum_{\mathcal{B}\in B}\mathbb{P}\left(Y_{\mathcal{B}}\geq(1+% 1/\log(n))\mathbb{E}[Y_{\mathcal{B}}]\right)$
		$\displaystyle\leq n^{3}\mathbb{P}\left(Y_{\mathcal{B}}\geq(1+1/\log(n))\mathbb% {E}[Y_{\mathcal{B}}]\right)\leq n^{-c+3}.\$

$\hfill\blacktriangleleft$ A further refinement of the “clique covering” argument of Theorem 20 should be possible. Any clique has by definition a diameter of at most $R$ , and so the shape in $\mathbb{H}^{2}$ of diameter $R$ with maximal area would provide an improved upper bound via a similar covering argument. It is not clear what a tight bound would be, and $\omega(G)\leq(1+o(1))\sigma(G)$ may be possible.

5 Geometric Inhomogeneous Random Graphs

Geometric Inhomogeneous Random Graphs or GIRGs were introduced in [11] as an alternative model to HRGs that capture many of the same properties, in particular the power-law degree distribution. In their most general form, GIRGs strictly generalise HRGs, but they are more often studied in a slightly restricted form; comparisons are made in [6, 28]. In this restricted form, called the standard GIRG model by [16], any HRG $G$ can be coupled with two GIRGs $H_{1}$ and $H_{2}$ such that $H_{1}\subseteq G\subseteq H_{2}$ , where $\subseteq$ denotes graph inclusion.

Because of this relationship, GIRGs are used as proxies for HRGs in some theoretical and experimental works. This is partly done because GIRGs are (by design) far more tractable than HRGs. It is therefore valuable to understand differences between the two models. In [6] experimental evidence was given to suggest that the “sandwiching” of an HRG by two standard GIRGs is not tight. In Corollary 24 we provide a theoretical result demonstrating a difference between the two models.

Definition 21 (Standard GIRG model).

Let $\beta\in(2,3)$ , $\lambda\in\Theta(1)$ , and $n\in\mathbb{N}$ . A geometric inhomogeneous random graph $G\sim\mathcal{G}(n,\beta,\lambda)$ is a random graph with vertex set $V=\{v_{1},\cdots,v_{n}\}$ satisfying the following properties.

1.

Every $u\in V$ is equipped with a random tuple $(w_{u},x_{u})$ , where weight $w_{u}\in[1,\infty)$ has density $f(y)=(\beta-1)y^{-\beta}$ and coordinate $x_{u}$ is drawn uniformly at random from $[0,1]$ ;
2.

Any pair of vertices $u,v\in V$ are connected if and only if $\min\{|x_{u}-x_{v}|,1-|x_{u}-x_{v}|\}\leq t(u,v)$ , where $t(u,v)=\frac{1}{2}\left(\frac{\lambda w_{u}w_{v}}{n}\right)$ .

One way of thinking of a GIRG is that vertices are being thrown uniformly at random onto the 1-dimensional torus $\mathbb{T}^{1}$ , and connected according to whether their distance is below their threshold $t(u,v)$ . The weights are drawn according to a Pareto distribution. Analogously to HRGs, for a vertex $u$ of a GIRG we define the inner-degree of $u$ to be $|\operatorname{\Gamma}(u)|=|\{v\in V|\text{$u$ and $v$ are connected and }w_{v% }\geq w_{u}\}|.$ The proofs of Observations 4 and 6 can be adapted to the GIRG model to characterise the degeneracy via the largest inner-degree.

Corollary 22.

Let $G\sim\mathcal{G}(n,2\alpha+1,\lambda)$ be a standard GIRG. Consider the vertex $u^{*}$ with the largest inner-degree in $G$ . Then w.e.h.p. $\kappa(G)=(1-o(1))|\operatorname{\Gamma}(u^{*})|.$

Corollary 22 allows us to state a tight bound for the degeneracy in comparison to the core of the GIRG, which is defined to contain all vertices of weight $\hat{w}\geq\sqrt{n/\lambda}$ , and has size $\sigma(G)=(1\pm o(1))\lambda^{-\alpha}n^{1-\alpha}$ w.e.h.p. This is analagous to the core of an HRG, which is the clique formed by vertices of radius at most $R/2$ , regardless of their angular coordinates.

Theorem 23.

Let $G\sim\mathcal{G}(n,2\alpha+1,\lambda)$ be a threshold GIRG. The degeneracy is w.e.h.p.

\kappa(G)=(2\pm o(1))(2(1-\alpha))^{({1-\alpha})/{(2\alpha-1)}}\sigma(G).

Proof.

We bound the maximal inner-degree $|\operatorname{\Gamma}(u^{*})|$ ; the statement then follows from Corollary 22. Notice that, independent of the geometric distance, a vertex with weight $w$ is adjacent to any vertex with weight $w^{\prime}$ if $w^{\prime}\geq\frac{n}{w\lambda}$ since $t(w,w^{\prime})=\frac{\lambda ww^{\prime}}{2n}\geq\frac{\lambda w\frac{n}{w% \lambda}}{2n}=\frac{1}{2}$ which is the maximal distance between two points in the unit torus. Thus, using $\beta=2\alpha+1$ , the probability that a vertex $v$ is in the inner-neighbourhood of a vertex $u$ with weight $w$ is

$\displaystyle\mathbb{P}\left(v\in\Gamma(u)\right)$	$\displaystyle=\mathbb{P}\left(\{\{u,v\}\in E\}\cap\{W_{v}\geq w\}\right)$
	$\displaystyle=\mathbb{P}\left(W_{v}\geq\frac{n}{w\lambda}\right)+2\int_{w}^{% \frac{n}{w\lambda}}t(y,w)2\alpha y^{-(2\alpha+1)}dy$	$\displaystyle(\text{$t(w,n/w\lambda)=1/2$})$
	$\displaystyle=\left(\frac{n}{w\lambda}\right)^{-2\alpha}+\frac{2\alpha\lambda w% }{n}\int_{w}^{\frac{n}{w\lambda}}y^{-2\alpha}dy$	$\displaystyle(\text{Pareto and threshold})$
	$\displaystyle=\left(\frac{n}{w\lambda}\right)^{-2\alpha}+\frac{2\alpha\lambda w% }{n(2\alpha-1)}\left(w^{1-2\alpha}-\left(\frac{n}{w\lambda}\right)^{1-2\alpha}\right)$	$\displaystyle\left(\int y^{-2\alpha}dy=\left[\frac{y^{1-2\alpha}}{1-2\alpha}% \right]\right)$
	$\displaystyle=\left(\frac{n}{w\lambda}\right)^{-2\alpha}+\frac{\alpha}{\alpha-% 1/2}\left(\frac{\lambda w^{2(1-\alpha)}}{n}-\left(\frac{n}{w\lambda}\right)^{-% 2\alpha}\right).$		(4)

Next, we calculate the value $w^{*}$ , which maximises the expected inner-degree. To this end, we consider the probability measure of the inner-neighbourhood, take its derivative with respect to $w$ and set it equal to $0$ . Differentiating yields

\displaystyle\frac{\mathrm{d}}{\mathrm{d}w}\mathbb{P}\left(v\in\Gamma(u)\right)

\displaystyle=\frac{2(nw)^{-(2\alpha+1)}(1-\alpha)\alpha\left(n^{2\alpha}w^{2}% \lambda-nw^{4\alpha}\lambda^{2\alpha}\right)}{2\alpha-1},

and solving for the maximum reveals $w^{*}=(2(1-\alpha))^{\frac{1}{4\alpha-2}}\sqrt{\frac{n}{\lambda}}\in\Theta(% \sqrt{n}).$

We plug in $w^{*}$ for the weight of $u$ denoted by $u^{*}$ into $\mathbb{P}\left(v\cap\Gamma(u^{*})\right)$ and get by (5) that

\mathbb{P}\left(v\in\Gamma(u^{*})\right)=2(2(1-\alpha))^{({1-\alpha})/{(2% \alpha-1)}}(n\lambda)^{-\alpha}.

Recalling that $\sigma(G)=(1\pm o(1))\lambda^{-\alpha}n^{1-\alpha}$ w.e.h.p., the upper bound now follows from the expectation of $|\operatorname{\Gamma}(u^{*})|$ and applying a Chernoff bound in conjunction with a union bound. The lower bound is established by showing that there exists a vertex within the range of weights $\tilde{w}=[w^{*}(1+n^{\alpha-1}\log^{2}(n))^{-1/(2\alpha)},w^{*}]$ w.e.h.p. and lower bound the inner-degree of such vertex. Using the Pareto distribution and $w^{*}\in\Theta(\sqrt{n})$ , we calculate the probability for a vertex $u$ to belong to the range of weights $\tilde{w}$ . We obtain

$\displaystyle\mathbb{P}\left(W_{u}\in\tilde{w}\right)$	$\displaystyle=\mathbb{P}\left(w^{}(1+n^{\alpha-1}\log^{2}(n))^{-1/(2\alpha)}% \leq W_{u}\leq w^{}\right)$	$\displaystyle(\text{Range of }\tilde{w})$
	$\displaystyle=\mathbb{P}\left(W_{u}\leq w^{}\right)-\mathbb{P}\left(W_{u}\leq w% ^{}(1+n^{\alpha-1}\log^{2}(n))^{-1/(2\alpha)}\right)$
	$\displaystyle=1-(w^{})^{-2\alpha}-(1-(w^{}(1+n^{\alpha-1}\log^{2}(n))^{-1/(2% \alpha)})^{-2\alpha})$	$\displaystyle(\text{Pareto})$
	$\displaystyle=(w^{}(1+n^{\alpha-1}\log^{2}(n))^{-1/(2\alpha)})^{-2\alpha}-(w^% {})^{-2\alpha}$
	$\displaystyle=(w^{*})^{-2\alpha}n^{\alpha-1}\log^{2}(n)$
	$\displaystyle=\Theta(1)\frac{\log^{2}(n)}{n}.$	$\displaystyle(w^{*}\in\Theta(\sqrt{n}))$

By this we have $\mathbb{E}\left[|V\cap\tilde{w}|\right]\in\omega(\log(n))$ . Using a Chernoff bound there exists a vertex within the desired weight range $\tilde{w}$ w.e.h.p. To conclude the proof we lower bound the inner-degree of a vertex $\tilde{u}$ included in the weight range $\tilde{w}$ . Note that $\tilde{w}=(1-o(1))w^{*}=(2-o(1)(1-\alpha))^{\frac{1}{4\alpha-2}}\sqrt{\frac{n}% {\lambda}}$ . We then have via Section 5

\mathbb{E}\left[|\operatorname{\Gamma}(\tilde{u})|\right]=(n-1)\mathbb{P}\left% (v\cap\Gamma(\tilde{u})\right)\geq(2-o(1))(2(1-\alpha))^{({1-\alpha})/{(2% \alpha-1)}}\lambda^{-\alpha}n^{1-\alpha}.

A final application of a Chernoff bound then ensures the concentration to finish the proof. $\hfill\blacktriangleleft$

Comparing the lower bound of the degeneracy for GIRGs given in Theorem 23 to the upper bound of a HRG we obtained in Theorem 9 we draw the conclusion that the degeneracy-to-core ratio between the two models is fundamentally different.

Corollary 24 (GIRG-HRG degeneracy difference).

Fix an $\alpha\in(1/2,1)$ . Let $G\sim\mathcal{G}(n,2\alpha+1,\lambda)$ be a standard GIRG and $H\sim\mathcal{G}(n,\alpha,C)$ be a threshold HRG. Then w.e.h.p.

\left|\frac{\kappa(G)}{\sigma(G)}-\frac{\kappa(H)}{\sigma(H)}\right|\in\Theta(% 1).

6 Conclusion

We have shown that the clique number, degeneracy, and chromatic number of HRGs are asymptotically (with small differences in the leading $O$ -notation constants) as large as the core, though the clique number and degeneracy differ significantly. Our upper bound on the degeneracy provides a constant factor approximation algorithm for the graph colouring problem. The approximation ratio ranges from $2/\sqrt{3}$ to $4/3$ and depends on the model parameter $\alpha$ . This raises several open questions and future research directions.

$\blacksquare$

Is the chromatic number bounded away from the degeneracy, the clique number, or both?
$\blacksquare$

Can HRGs be coloured optimally in polynomial time or is it NP-complete?
$\blacksquare$

What are the asymptotics of $\omega(G)/\sigma(G)$ ? Is the clique number a constant factor larger than the core and has similar behaviour as the degeneracy?

There are further directions of research such as determining other differences between HRGs and GIRGs or designing colouring algorithms for HRGs in various models of computation.

References

[1] Samuel Baguley, Yannic Maus, Janosch Ruff, and George Skretas. Hyperbolic random graphs: Clique number and degeneracy with implications for colouring. CoRR, 2024. doi:10.48550/arXiv.2410.11549.
[2] Leonid Barenboim and Michael Elkin. Distributed Graph Coloring: Fundamentals and Recent Developments. Morgan & Claypool Publishers, 2013. doi:10.1007/978-3-031-02009-4.
[3] Thomas Bläsius and Philipp Fischbeck. On the external validity of average-case analyses of graph algorithms. ACM Trans. Algorithms, 2024. doi:10.1145/3633778.
[4] Thomas Bläsius, Philipp Fischbeck, Tobias Friedrich, and Maximilian Katzmann. Solving vertex cover in polynomial time on hyperbolic random graphs. Theory Comput. Syst., 2023. doi:10.1007/S00224-021-10062-9.
[5] Thomas Bläsius, Tobias Friedrich, and Maximilian Katzmann. Efficiently approximating vertex cover on scale-free networks with underlying hyperbolic geometry. Algorithmica, 2023. doi:10.1007/S00453-023-01143-X.
[6] Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann, Ulrich Meyer, Manuel Penschuck, and Christopher Weyand. Efficiently Generating Geometric Inhomogeneous and Hyperbolic Random Graphs. In ESA, 2019. doi:10.4230/LIPIcs.ESA.2019.21.
[7] Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann, and Daniel Stephan. Strongly Hyperbolic Unit Disk Graphs. In STACS, 2023. doi:10.4230/LIPIcs.STACS.2023.13.
[8] Thomas Bläsius, Tobias Friedrich, and Anton Krohmer. Cliques in hyperbolic random graphs. Algorithmica, 2017. doi:10.1007/s00453-017-0323-3.
[9] Thomas Bläsius, Maximillian Katzmann, and Clara Stegehuis. Maximal cliques in scale-free random graphs. Network Science, 2024. doi:10.1017/nws.2024.13.
[10] Thomas Bläsius, Tobias Friedrich, and Anton Krohmer. Hyperbolic random graphs: Separators and treewidth. In ESA, 2016. doi:10.4230/LIPIcs.ESA.2016.15.
[11] Karl Bringmann, Ralph Keusch, and Johannes Lengler. Geometric inhomogeneous random graphs. Theoretical Computer Science, 2019. doi:10.1016/j.tcs.2018.08.014.
[12] Aleksander Bjørn Grodt Christiansen, Krzysztof Nowicki, and Eva Rotenberg. Improved dynamic colouring of sparse graphs. In STOC, 2023. doi:10.1145/3564246.3585111.
[13] Stephen A. Cook. The complexity of theorem-proving procedures. In STOC, 1971. doi:10.1145/800157.805047.
[14] B. V. Dekster. The Jung theorem for spherical and hyperbolic spaces. Acta Mathematica Hungarica, 1995. doi:10.1007/bf01874495.
[15] B. V. Dekster. The Jung theorem in metric spaces of curvature bounded above. Proceedings of the American Mathematical Society, 1997. doi:10.1090/s0002-9939-97-03842-2.
[16] Tobias Friedrich, Andreas Göbel, Maximilian Katzmann, and Leon Schiller. Cliques in high-dimensional geometric inhomogeneous random graphs. SIAM Journal on Discrete Mathematics, 2024. doi:10.1137/23m157394x.
[17] Tobias Friedrich and Anton Krohmer. On the Diameter of Hyperbolic Random Graphs. SIAM Journal on Discrete Mathematics, 2018. doi:10.1137/17M1123961.
[18] Mohsen Ghaffari and Christoph Grunau. Dynamic o(arboricity) coloring in polylogarithmic worst-case time. In STOC, 2024. doi:10.1145/3618260.3649782.
[19] Luca Gugelmann, Konstantinos Panagiotou, and Ueli Peter. Random Hyperbolic Graphs: Degree Sequence and Clustering. In ICALP, 2012. doi:10.1007/978-3-642-31585-5_51.
[20] Heinrich Jung. Ueber die kleinste Kugel, die eine räumliche Figur einschliesst. Journal für die reine und angewandte Mathematik, 1901. URL: http://eudml.org/doc/149122.
[21] Richard M. Karp. Reducibility among Combinatorial Problems, pages 85–103. Springer US, 1972. doi:10.1007/978-1-4684-2001-2_9.
[22] Maximilian Katzmann. About the analysis of algorithms on networks with underlying hyperbolic geometry. doctoralthesis, Universität Potsdam, 2023. doi:10.25932/publishup-58296.
[23] Ralph Keusch. Geometric Inhomogeneous Random Graphs and Graph Coloring Games. PhD thesis, ETH Zurich, 2018. doi:10.3929/ethz-b-000269658.
[24] Marcos Kiwi and Dieter Mitsche. A bound for the diameter of random hyperbolic graphs. In ANALCO, 2015.
[25] Marcos Kiwi and Dieter Mitsche. Spectral gap of random hyperbolic graphs and related parameters. The Annals of Applied Probability, 2018. doi:10.1214/17-aap1323.
[26] Marcos Kiwi and Dieter Mitsche. On the second largest component of random hyperbolic graphs. SIAM Journal on Discrete Mathematics, 2019. doi:10.1137/18m121201x.
[27] Marcos Kiwi, Markus Schepers, and John Sylvester. Cover and hitting times of hyperbolic random graphs. Random Structures & Algorithms, 2024. doi:10.1002/rsa.21249.
[28] Júlia Komjáthy and Bas Lodewijks. Explosion in weighted hyperbolic random graphs and geometric inhomogeneous random graphs. Stochastic Processes and their Applications, 2020. doi:10.1016/j.spa.2019.04.014.
[29] Dmitri Krioukov, Fragkiskos Papadopoulos, Maksim Kitsak, Amin Vahdat, and Marián Boguñá. Hyperbolic geometry of complex networks. Phys. Rev. E, 2010. doi:10.1103/PhysRevE.82.036106.
[30] Anton Krohmer. Structures & algorithms in hyperbolic random graphs. doctoralthesis, Universität Potsdam, 2016. URL: https://publishup.uni-potsdam.de/frontdoor/index/index/docId/39597.
[31] David W. Matula and Leland L. Beck. Smallest-last ordering and clustering and graph coloring algorithms. Journal of the ACM, 1983. doi:10.1145/2402.322385.
[32] Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005. doi:10.1017/CBO9780511813603.
[33] Tobias Müller and Merlijn Staps. The Diameter of KPKVB Random Graphs. Advances in Applied Probability, 2019. doi:10.1017/apr.2019.23.
[34] Fragkiskos Papadopoulos, Dmitri Krioukov, Marian Boguna, and Amin Vahdat. Greedy forwarding in dynamic scale-free networks embedded in hyperbolic metric spaces. In INFOCOM, 2010. doi:10.1109/infcom.2010.5462131.
[35] Jose L. Walteros and Austin Buchanan. Why is maximum clique often easy in practice? Operations Research, 2020. doi:10.1287/opre.2019.1970.
[36] David Zuckerman. Linear degree extractors and the inapproximability of max clique and chromatic number. Theory of Computing, 2007. doi:10.4086/toc.2007.v003a006.

[bib.bib1] [1] Samuel Baguley, Yannic Maus, Janosch Ruff, and George Skretas. Hyperbolic random graphs: Clique number and degeneracy with implications for colouring. CoRR, 2024. doi:10.48550/arXiv.2410.11549.

[bib.bib2] [2] Leonid Barenboim and Michael Elkin. Distributed Graph Coloring: Fundamentals and Recent Developments. Morgan & Claypool Publishers, 2013. doi:10.1007/978-3-031-02009-4.

[bib.bib3] [3] Thomas Bläsius and Philipp Fischbeck. On the external validity of average-case analyses of graph algorithms. ACM Trans. Algorithms, 2024. doi:10.1145/3633778.

[bib.bib4] [4] Thomas Bläsius, Philipp Fischbeck, Tobias Friedrich, and Maximilian Katzmann. Solving vertex cover in polynomial time on hyperbolic random graphs. Theory Comput. Syst., 2023. doi:10.1007/S00224-021-10062-9.

[bib.bib5] [5] Thomas Bläsius, Tobias Friedrich, and Maximilian Katzmann. Efficiently approximating vertex cover on scale-free networks with underlying hyperbolic geometry. Algorithmica, 2023. doi:10.1007/S00453-023-01143-X.

[bib.bib6] [6] Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann, Ulrich Meyer, Manuel Penschuck, and Christopher Weyand. Efficiently Generating Geometric Inhomogeneous and Hyperbolic Random Graphs. In ESA, 2019. doi:10.4230/LIPIcs.ESA.2019.21.

[bib.bib7] [7] Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann, and Daniel Stephan. Strongly Hyperbolic Unit Disk Graphs. In STACS, 2023. doi:10.4230/LIPIcs.STACS.2023.13.

[bib.bib8] [8] Thomas Bläsius, Tobias Friedrich, and Anton Krohmer. Cliques in hyperbolic random graphs. Algorithmica, 2017. doi:10.1007/s00453-017-0323-3.

[bib.bib9] [9] Thomas Bläsius, Maximillian Katzmann, and Clara Stegehuis. Maximal cliques in scale-free random graphs. Network Science, 2024. doi:10.1017/nws.2024.13.

[bib.bib10] [10] Thomas Bläsius, Tobias Friedrich, and Anton Krohmer. Hyperbolic random graphs: Separators and treewidth. In ESA, 2016. doi:10.4230/LIPIcs.ESA.2016.15.

[bib.bib11] [11] Karl Bringmann, Ralph Keusch, and Johannes Lengler. Geometric inhomogeneous random graphs. Theoretical Computer Science, 2019. doi:10.1016/j.tcs.2018.08.014.

[bib.bib12] [12] Aleksander Bjørn Grodt Christiansen, Krzysztof Nowicki, and Eva Rotenberg. Improved dynamic colouring of sparse graphs. In STOC, 2023. doi:10.1145/3564246.3585111.

[bib.bib13] [13] Stephen A. Cook. The complexity of theorem-proving procedures. In STOC, 1971. doi:10.1145/800157.805047.

[bib.bib14] [14] B. V. Dekster. The Jung theorem for spherical and hyperbolic spaces. Acta Mathematica Hungarica, 1995. doi:10.1007/bf01874495.

[bib.bib15] [15] B. V. Dekster. The Jung theorem in metric spaces of curvature bounded above. Proceedings of the American Mathematical Society, 1997. doi:10.1090/s0002-9939-97-03842-2.

[bib.bib16] [16] Tobias Friedrich, Andreas Göbel, Maximilian Katzmann, and Leon Schiller. Cliques in high-dimensional geometric inhomogeneous random graphs. SIAM Journal on Discrete Mathematics, 2024. doi:10.1137/23m157394x.

[bib.bib17] [17] Tobias Friedrich and Anton Krohmer. On the Diameter of Hyperbolic Random Graphs. SIAM Journal on Discrete Mathematics, 2018. doi:10.1137/17M1123961.

[bib.bib18] [18] Mohsen Ghaffari and Christoph Grunau. Dynamic o(arboricity) coloring in polylogarithmic worst-case time. In STOC, 2024. doi:10.1145/3618260.3649782.

[bib.bib19] [19] Luca Gugelmann, Konstantinos Panagiotou, and Ueli Peter. Random Hyperbolic Graphs: Degree Sequence and Clustering. In ICALP, 2012. doi:10.1007/978-3-642-31585-5_51.

[bib.bib20] [20] Heinrich Jung. Ueber die kleinste Kugel, die eine räumliche Figur einschliesst. Journal für die reine und angewandte Mathematik, 1901. URL: http://eudml.org/doc/149122.

[bib.bib21] [21] Richard M. Karp. Reducibility among Combinatorial Problems, pages 85–103. Springer US, 1972. doi:10.1007/978-1-4684-2001-2_9.

[bib.bib22] [22] Maximilian Katzmann. About the analysis of algorithms on networks with underlying hyperbolic geometry. doctoralthesis, Universität Potsdam, 2023. doi:10.25932/publishup-58296.

[bib.bib23] [23] Ralph Keusch. Geometric Inhomogeneous Random Graphs and Graph Coloring Games. PhD thesis, ETH Zurich, 2018. doi:10.3929/ethz-b-000269658.

[bib.bib24] [24] Marcos Kiwi and Dieter Mitsche. A bound for the diameter of random hyperbolic graphs. In ANALCO, 2015.

[bib.bib25] [25] Marcos Kiwi and Dieter Mitsche. Spectral gap of random hyperbolic graphs and related parameters. The Annals of Applied Probability, 2018. doi:10.1214/17-aap1323.

[bib.bib26] [26] Marcos Kiwi and Dieter Mitsche. On the second largest component of random hyperbolic graphs. SIAM Journal on Discrete Mathematics, 2019. doi:10.1137/18m121201x.

[bib.bib27] [27] Marcos Kiwi, Markus Schepers, and John Sylvester. Cover and hitting times of hyperbolic random graphs. Random Structures & Algorithms, 2024. doi:10.1002/rsa.21249.

[bib.bib28] [28] Júlia Komjáthy and Bas Lodewijks. Explosion in weighted hyperbolic random graphs and geometric inhomogeneous random graphs. Stochastic Processes and their Applications, 2020. doi:10.1016/j.spa.2019.04.014.

[bib.bib29] [29] Dmitri Krioukov, Fragkiskos Papadopoulos, Maksim Kitsak, Amin Vahdat, and Marián Boguñá. Hyperbolic geometry of complex networks. Phys. Rev. E, 2010. doi:10.1103/PhysRevE.82.036106.

[bib.bib30] [30] Anton Krohmer. Structures & algorithms in hyperbolic random graphs. doctoralthesis, Universität Potsdam, 2016. URL: https://publishup.uni-potsdam.de/frontdoor/index/index/docId/39597.

[bib.bib31] [31] David W. Matula and Leland L. Beck. Smallest-last ordering and clustering and graph coloring algorithms. Journal of the ACM, 1983. doi:10.1145/2402.322385.

[bib.bib32] [32] Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005. doi:10.1017/CBO9780511813603.

[bib.bib33] [33] Tobias Müller and Merlijn Staps. The Diameter of KPKVB Random Graphs. Advances in Applied Probability, 2019. doi:10.1017/apr.2019.23.

[bib.bib34] [34] Fragkiskos Papadopoulos, Dmitri Krioukov, Marian Boguna, and Amin Vahdat. Greedy forwarding in dynamic scale-free networks embedded in hyperbolic metric spaces. In INFOCOM, 2010. doi:10.1109/infcom.2010.5462131.

[bib.bib35] [35] Jose L. Walteros and Austin Buchanan. Why is maximum clique often easy in practice? Operations Research, 2020. doi:10.1287/opre.2019.1970.

[bib.bib36] [36] David Zuckerman. Linear degree extractors and the inapproximability of max clique and chromatic number. Theory of Computing, 2007. doi:10.4086/toc.2007.v003a006.

$\displaystyle\mathbb{P}\Big{(}\min_{v\in V(H)}\mathrm{deg}\|_{H}(v)$	$\displaystyle<(1-\varepsilon)\gamma\Big{)}=\mathbb{P}\Big{(}\bigcup_{v\in V}\{% \mathrm{deg}\|_{H}(v)<(1-\varepsilon)\gamma,r(v)\leq r\}\Big{)}$
	$\displaystyle\leq n\mathbb{P}(\mathrm{deg}\|_{H}(v)<(1-\varepsilon)\gamma,r(v)% \leq r)$	(Union bound)
	$\displaystyle=n\mathbb{E}\left[\mathbb{P}(\mathrm{deg}\|_{H}(v)<(1-\varepsilon)% \gamma\;\|\;r(v))\operatorname{\mathds{1}}\{r(v)\leq r\}\right]$	(Tower rule)
	$\displaystyle\leq n\mathbb{E}\Big{[}\mathrm{e}^{-\varepsilon^{2}\mathbb{E}[% \mathrm{deg}\|_{H}(v)\|r(v)]/2}\operatorname{\mathds{1}}\{r(v)\leq r\}\Big{]}$	(Chernoff bound)
	$\displaystyle\leq n\mathrm{e}^{-\gamma\varepsilon^{2}/2}\mathbb{P}(r(v)\leq r)% \leq n\mathrm{e}^{-\gamma\varepsilon^{2}/2}.$