Distributed Symmetry Breaking on Hyperbolic Random Graphs Yannic Maus ∗ #1 , Janosch Ruff † #2 , Sonia Simons#2 , and George Skretas#2 TU Graz, Austria Hasso Plattner Institute, University of Potsdam, Germany 1
2
arXiv:2607.09170v1 [cs.DC] 10 Jul 2026
Abstract Real-world networks like the internet share patterns like a power law degree distribution and a high clustering coefficient. Many of these properties are captured by the generative model of hyperbolic random graphs (HRGs), which provides a theoretical framework for studying such networks. Motivated by the observation that several algorithms perform better on real-world networks than their worst-case guarantees suggest, we design and analyse distributed algorithms under the assumption that the input graph is an HRG. Indeed, prior work has shown that the classical symmetry-breaking problem of Δ + 1 colouring, where Δ is the maximum degree of the graph, can be solved in 2 rounds on HRGs [Maus and Ruff; SODA’26]. In stark contrast to this 2-round algorithm for Δ + 1 colouring, we prove that the related symmetrybreaking problems of maximal independent set (MIS) and maximal matching (MM) are substantially harder: we establish a lower bound of Ω ( logloglogloglog𝑛 𝑛 ) for MIS and MM on HRGs. Our lower bound techniques rely on new structural insights that may be of independent interest: we show that HRGs contain 𝑑-ary trees with large height and degree which enables us to adapt and lift prior impossibility results for distributed algorithms to the setting of HRGs. We also show that these lower bounds are polynomial tight: we design algorithms tailored to 5/3 ̃ HRGs that solve MIS and MM in (log log 𝑛) rounds with high √ { probability } in the LOCAL model, improving over the general worst-case lower bound of Ω (min log Δ, log 𝑛 ) rounds [Khoury and Schild; FOCS’25]. Finally, we show that access to geometric information can significantly reduce the complexity of maximal matching: if vertices know their respective geometric embeddings, then MM can be solved in (log log log 𝑛) rounds on HRGs. This reveals a separation between the standard LOCAL model and an embedding-aware variant on hyperbolic random graphs.
∗ This research was funded in whole or in part by the Austrian Science Fund (FWF) https://doi.org/10.55776/P36280, https://doi.org/10.55776/I6915. For open access purposes, the author has applied a CC BY public copyright license to
any author-accepted manuscript version arising from this submission. † This research was partially funded by the German Research Foundation (Deutsche Forschungsgemeinschaft, DFG) – project number 390859508.
Contents 1 Introduction 1.1 Our Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Further Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1 2 4
2 Technical Overview 2.1 Efficient Algorithms for MIS and MM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Lower Bounds for MIS and MM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Embedding-Aware Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5 6 8 10
3 Conclusion
11
4 Hyperbolic Random Graphs
12
5 Efficient Algorithms for MIS/MM on HRGs (Theorem 1) 5.1 Efficient Maximal Independent Set Algorithm (MIS part of Theorem 1) . . . . . . . . . . . 5.2 Efficient Maximal Matching Algorithm (MM part of Theorem 1) . . . . . . . . . . . . . . .
14 14 20
6 Lower Bounds for MIS/MM & Substructures in HRGs (Theorem 2) 6.1 On 𝑑-ary Trees in Hyperbolic Random Graphs (Proof of Theorem 18) . . . . . . . . . . . . 6.2 Lower Bounds for MM and MIS (Proof of Theorem 2) . . . . . . . . . . . . . . . . . . . . .
23 23 32
7 Embedding-Aware Symmetry Breaking (Theorem 3) 7.1 Embedding-Aware Maximal Independent Set (MIS part of Theorem 3) . . . . . . . . . . . . 7.2 Embedding-Aware Maximal Matching (MM part of Theorem 3) . . . . . . . . . . . . . . . .
35 37 40
A Luby’s Algorithm Retains a Polynomial Degree After Constant Rounds
50
B Concentration Bounds
54
C Round Elimination Lower Bounds with General Error Probabilities
55
D Truncating Angular Coordinates
56
1
Introduction
Symmetry breaking problems play a key role in the theory of distributed computing. In this paper, we study the fundamental symmetry breaking problems maximal independent set (MIS) and maximal matching (MM). A maximal independent set is an independent set that cannot be extended by adding any vertex, while a maximal matching is a matching where no additional edge can be added. We study these problems through the lenses of the classic LOCAL model and the CONGEST model [72, 82]: A communication network is represented by a graph 𝐺 = (𝑉 , 𝐸) with |𝑉 | = 𝑛. In synchronous rounds, vertices exchange messages with their neighbours, and the round complexity of an algorithm is the number of rounds until all vertices have produced their output. We consider both the LOCAL model, where messages have unbounded size, and the CONGEST model, where each message is limited to (log 𝑛) bits. One of the classic results from the 1980’s is Luby’s Algorithm, giving a randomised algorithm that finds an MIS within (log 𝑛) rounds with high probability [2, 73]. The same approach can then also be extended to an MM. Remarkably, despite much progress on distributed computing since then, (log 𝑛) remains the best-known round complexity as a function of 𝑛 for general graphs [11, 12, 13, 44, 46,√ 47, 48, 50, 52, 56, 57, 70, 75, 85, 86]. Meanwhile, Khoury and Schild recently showed a lower bound of Ω( log 𝑛) for MIS and √ MM on worst-case general graphs [57], improving upon an earlier bound of Ω( log 𝑛/ log log 𝑛) rounds by Kuhn, Moscibroda, and Wattenhofer [69]. Worst-case graphs, however, may be a poor proxy for the communication networks that motivate many distributed problems. This raises the question of whether symmetry breaking becomes easier when the communication network is drawn from a model that captures structural features commonly observed in real-world networks. A recent step in this direction was taken by Maus and Ruff, who showed that a distributed colouring problem requiring Ω(log∗ 𝑛) rounds on worst-case graphs [71, 79] can be solved in just two rounds on hyperbolic random graphs, a common abstraction of real-world networks [74]. Their simple algorithm significantly outperforms the state of the art for general graphs. Their work raises the broader question of whether this dramatic speed-up is specific to colouring, or whether it reflects a more general phenomenon. Thus, in this paper, we further explore the following research question: How does the structure of real-world networks affect the complexity of symmetry breaking? While different real-world networks have different structures, e.g., the internet graph has a different topology than a road network, many real-world networks have been observed to share several topological features. For example, many networks exhibit a heterogeneous degree distribution, close to a power-law. 1 Examples include, among others, social networks [89], communication networks like the internet [39], and biological networks [65]. Another property observed in real-world networks is a high clustering coefficient [80, 87, 90]. We follow the lines drawn in [29, 66, 81, 88] using hyperbolic geometry to encapsulate both of these properties. In particular, we use the model of hyperbolic random graph (HRG) as introduced by Krioukov, Papadopoulos, Kitsak, Vahdat, and Boguñá [66]. At this point, HRGs are well established as a model for complex real-world networks, and many different centralised algorithmic problems have been studied [3, 18, 19, 20, 24, 25, 62]. Moreover, the excellent empirical work by Bläsius and Fischbeck suggests that the theoretical analysis of algorithms on HRGs provides a good predictor for performance on real-world networks [17], and HRGs also serve as the underlying model in the work of Maus and Ruff [74]. A threshold hyperbolic random graph is obtained by sampling 𝑛 vertices into a hyperbolic disk with radius 𝑅 ≈ 2 log 𝑛, and a pair of vertices share an edge if the hyperbolic distance between the two vertices is at most 𝑅. We provide a formal definition in Section 4 and refer the interested reader to [54, 67] for an in-depth introduction to HRGs. 1
That is, the number of vertices that have degree 𝑑 is roughly ≈ 𝑛 ⋅ 𝑑 −𝜏 (where 𝜏 ∈ (2, 3) is the power-law exponent).
1
Randomised LOCAL MIS and MM Landscape Theorem 3 (MM)
Θ(1)
O(log log log n) Ω
Theorem 2
log log n log log log n
Theorem 3 (MIS) Theorem 1
O(log log n) Õ(log5/3 log n)
√ Ω( log n)
O(log n)
Figure 1: Landscape of randomised LOCAL Maximal Independent Set (MIS) and Maximal Matching (MM). Green: our results for MIS/MM on hyperbolic random graphs. Black: current state of the art for MIS/MM on general graphs. Grey: distributed colouring on HRGs. Disks: upper bounds (Theorem 1). Squares: lower bounds (Theorem 2). Triangles: embedding-aware upper bounds (Theorem 3).
1.1
Our Contributions
We show that the complexity landscape of MIS and MM on HRGs differs dramatically from that of the distributed graph colouring problem studied in [74]; see also Figure 1 for visualisiation of our results: On the algorithmic side, we show that MIS and MM can be solved exponentially faster on HRGs than on worst-case graphs by giving log(1) log 𝑛-round algorithms (Theorem 1). But, on the lower-bound side, we show that this speed-up has inherent limits. In contrast to graph colouring, MIS and MM do not collapse to constant time on HRGs; in fact, our lower bounds show that any further improvement to our upper bounds is limited to a small polynomial improvement (Theorem 2). This impossibility result relies on new structural insights into HRGs: we prove that their giant component contains substructures (trees) on which faster distributed algorithms are impossible (Theorem 18). We believe the existence of these substructures is of independent interest, as it contributes to the structural understanding of HRGs as models of real-world networks. The lower bound above applies in the standard LOCAL model, where nodes do not know their position in the underlying hyperbolic geometry. This naturally raises the question of whether such geometric information can be exploited algorithmically. In the classic LOCAL model, the initial knowledge of nodes is limited to their own ID and potentially some coarse upper bounds on global parameters such as the maximum degree or the number of nodes. However, in real-world networks, nodes may have additional information about the network that may be exploited algorithmically. For maximal matching, we show that such extra information can indeed be useful: we design an algorithm that beats the aforementioned lower bound when nodes have access to their geometric HRG coordinates, giving a doubly-exponential improvement over the complexity on general graphs (Theorem 3). We next present our results in detail and provide further background. Efficient Symmetry Breaking Algorithms. We obtain the following algorithms for MIS and MM on HRGs that are exponentially faster than the best algorithms for general graphs [13, 44, 73]. Theorem 1 (Upper bounds for MIS and MM). There are randomised distributed algorithms that, for threshold hyperbolic random graphs, compute Maximal Independent Set and Maximal Matching 5/3 ̃ • in (log log 𝑛) rounds 𝑤.𝑒.ℎ.𝑝. 2 of the LOCAL model; 3 ̃ • in (log log 𝑛) rounds 𝑤.𝑒.ℎ.𝑝. of the CONGEST model. 3 2 3
We say an event occurs with extremely high probability (w.e.h.p.) if ℙ () ∈ 1 − 𝑛−𝜔(1) . For MM, we obtain the slightly stronger bound of (log3 log 𝑛).
2
All probabilistic statements in our theorems are with respect to both the random generation of the HRG and the random choices made by the algorithm. See Figure 1 for a visual representation of our results in comparison to runtimes of existing work. All algorithms of Theorem 1 use a two-step approach. For MIS, the first step consists of two iterations of a Luby-style algorithm in which certain nodes activate themselves, draw a random number, and nodes whose drawn numbers are local minima join the independent set. As a result, we obtain that the graph shatters into exponentially smaller remaining unsolved connected components, on each of which we can then run the best deterministic algorithm exploiting the component’s small size, namely the algorithm of Ghaffari and Grunau for MIS/MM in the LOCAL model [47] and the fastest deterministic algorithms in the CONGEST model [40]. Such a two-step approach is usually referred to as the shattering technique and has been used in essentially all state-of-the-art symmetry breaking algorithms, e.g., [13, 35, 44], and one also knows that the randomised complexity is lower bounded by the deterministic complexity on exponentially smaller instances [34]. A central difference in our work and the main contribution of Theorem 1 is that we use a fundamentally different argument than all these existing works to show that such a shattering phenomenon emerges. This is interesting as recently discovered flaws and missing details in existing shattering approaches ask for more different shattering approaches [49]. One might hope that ordinary Luby iterations already yield such a shattering. We show that this is not the case: for any constant number of Luby iterations, both large components and large degrees remain; see Section A for details. Lower bounds. Theorem 1 is not only faster than the known √ fastest algorithms for MIS and MM but also exponentially faster than the lower bound of Ω (min{log Δ, log 𝑛}) by Khoury and Schild [57] for general graphs, since the maximum degree Δ of an HRG is polynomial in 𝑛. Combined with the fact that the other central symmetry-breaking problem of Δ + 1-colouring, and even colourings with fewer colours, can be solved in constant time [74], suggests that the algorithms in Theorem 1 may be far from optimal. We show that this is not the case. Any improvements to Theorem 1 can only be polynomial in its runtime. More precisely, we prove the following theorem, providing a strong separation between the runtime of MIS/MM and colouring problems on HRGs. Theorem 2 (Lower bounds for MIS and MM). Asymptotically almost surely,4 the randomised complexity 5 for computing an MIS or an MM for the giant component of a hyperbolic random graph is Ω ( logloglogloglog𝑛 𝑛 ) rounds in the LOCAL model. On substructures of hyperbolic random graphs. To prove Theorem 2 we show that with high probability any HRG contains relatively large induced 𝑑-ary trees 6 and then leverage the fact that distributed algorithms for MIS/MM cannot be fast on tree-like graphs [5, 6, 7, 9, 38, 57, 69]. Theorem (Informal version of Theorem √ 18). In an HRG, asymptotically almost surely, there exist polynomially many induced 𝑑-ary trees with 𝑛′ ≈ log 𝑛 vertices, any degree 𝑑, depth ℎ ≈ log𝑑 log 𝑛 and where the root of each tree has one additional edge to a vertex that connects it to the giant component. Then Theorem 1 implies that Theorem 18 is in some sense almost-tight, i.e., significantly larger trees 2 cannot exist. For example, 𝑑-ary trees with degree 𝑑 ≈ 𝑒 log log 𝑛 and height ℎ ≈ log2 log 𝑛 cannot exist, as the resulting lower bound for computing MIS on HRGs would contradict the existence of the algorithm in Theorem 1. In fact, we consider Theorem 18 as a main technical contribution of our work that is of independent interest. More generally, these structural insights contribute to existing literature of analysing With probability 1 − 𝑜(1) over the draw of the hyperbolic random graph 𝐺. There exists an algorithm where the error probability is at most 1/𝑛𝑐 for some constant 𝑐 > 0. 6 A rooted tree where each vertex except for the leaves has branching factor 𝑑.
4 5
3
the structure of HRGs, like the use of “dangling paths” to obtain bounds on the cover and hitting times of random walks [62], bounds on the degeneracy to obtain efficient colouring approximations [3], the construction of multi-commodity flows to bound the spectral gap [61] or more broadly the connectivity of an HRG [1, 28, 42, 43, 60, 78]. Embedding-aware Algorithms. The lower bounds of Theorem 2 apply in the standard distributed setting, where nodes only interact through the graph and have no access to the underlying hyperbolic embedding. This raises the question of whether this hidden structure can be exploited when it is made available to the algorithm. We therefore also study a coordinate-aware variant of the model, in which each node initially knows its position in the hyperbolic disk and can communicate this information to its neighbours in one round. This is a strong assumption, but geometric information of this kind is available or can be inferred in several network settings [29]. Similar assumptions have also been considered for distributed MIS in Euclidean unit disk graphs, where they lead to deterministic (1)-round algorithms in the CONGEST model [77] and to efficient maximum independent set approximations for graphs embedded in the hyperbolic plane [25, 26]. Under this additional geometric information, the complexity landscape changes again. For maximal matching, we break the lower-bound barrier of Theorem 2 and obtain a randomised (log log log 𝑛)-round algorithm in the CONGEST model. This shows, similar to quantum algorithms which yield an advantage for some distributed problems [4, 8], that one can beat lower bounds if additional computational resources like that of a geometric embedding are available. For maximal independent set, we obtain a (log log 𝑛)-round CONGEST algorithm on HRGs with known geometric coordinates. Theorem 3 (Embedding-aware algorithms). There are distributed algorithms that, for threshold hyperbolic random graphs given in their geometric representation, compute • Maximal Independent Set in (log log 𝑛) rounds w.h.p. 7 of the CONGEST model; • Maximal Matching in (log log log 𝑛) rounds w.h.p. of the CONGEST model. While we do not break the lower bound barrier of Theorem 2 for MIS, we obtain a runtime of a “flat” log log 𝑛 for a deterministic algorithm. Moreover, the techniques do not rely on shattering as does Theorem 1 and, as such, provide a different approach for solving symmetry-breaking problems on real-world networks. Finally, we remark that Theorem 2 together with Theorem 3 imply that a distributed computation of the embedding for an HRG requires Ω ( logloglogloglog𝑛 𝑛 ) rounds.
1.2
Further Related Work
Hyperbolic random graphs. A hyperbolic random graph combines the non-vanishing clustering coefficient of random geometric graphs (RGGs) [84] and the power-law degree distribution exhibited by models like Chung–Lu graphs [36, 37] or the Barabási–Albert model [10]. Other properties like that of a giant component 8 [22, 28, 42, 53] and the small-world phenomena 9 [1, 14, 43, 59, 78] follow. From the algorithmic side problems like Shortest Path [19], Maximum Clique [24], Maximum Independent Set and Maximum Matching [25], Vertex Cover [18, 20], Random Walks [62] or Colouring [3, 74] have been studied. A closely related model which captures the same properties is Geometric Inhomogeneous Random Graphs (GIRGs) introduced by Bringmann, Keusch and Lengler [31]. While HRGs and GIRGs are often regarded as roughly equivalent [64], several differences between the two models have been identified [3, 21, 27]. We say an event occurs with high probability (w.h.p.) if ℙ () ∈ 1 − (1/𝑛). A unique connected component of size Θ(𝑛). 9 The largest distance between vertices is Θ(log 𝑛). 7
8
4
GIRGs have been used to analyse algorithms like routing [32], shortest paths [33], rumour spreading [55], community testing [15], geometry detection [76] or first passage percolation [63]. Another related model is the class of hyperbolic uniform disk graphs (HUDGs) [16, 23, 26]; previously pioneered by Kisfaludi-Bak [58]. In this model, vertices are placed arbitrarily in a hyperbolic disk of radius 𝑅, and two vertices are adjacent whenever their hyperbolic distance is at most 𝑅. Unlike hyperbolic random graphs, no probability distribution is used to generate the vertex positions. When 𝑅 = 2 log 𝑛, the model can be viewed as a deterministic or worst-case analogue of a hyperbolic random graph: the same geometric threshold is used, but the vertex positions are chosen adversarially rather than sampled from the hyperbolic random graph distribution. Distributed maximal independent set and matching. While Luby’s algorithm with (log 𝑛) rounds remains the fastest known algorithm on general graphs, substantial progress has been made on MIS and MM along other directions. From the algorithmic point of view, deterministic algorithms have been developed 5/3 ̃ where the current state of the art for the LOCAL model is (log 𝑛) due to Ghaffari and Grunau [47], and 2 in CONGEST (log Δ ⋅ log log Δ ⋅ log 𝑛) rounds for MIS [40] and (log2 Δ ⋅ log 𝑛) for MM [41]. Moreover, Barenboim, Elkin, Pettie and Schneider introduced a randomised algorithm that runs faster on graphs with small maximum degree Δ [13]. In his seminal paper, Ghaffari, improved on their MIS algorithm and accomplished a round complexity of (log Δ + poly log log 𝑛) in the LOCAL model [44, 47, 85] and (log Δ log log 𝑛 + poly log log 𝑛) in the CONGEST model √ [45]. Recently, it was shown by Khoury and Schild that these algorithms solve MIS on trees in 𝑜 ( log 𝑛) rounds [56] while MM on trees requires √ Θ( log 𝑛) rounds [13, 44, 57]. This shows that MM is harder than MIS on trees, while on general graphs, MIS is just as hard as MM. 10 Within the broader context {of lower √ bounds, } due to a classic construction by Kuhn, Moscibroda and log Δ log 𝑛 Wattenhofer there is an Ω (min log log Δ , log log 𝑛 ) lower bound for randomised MIS and MM on certain irregular trees [69] (see also [38] for a simplified version). For Maximal matching, work } { the breakthrough
by Balliu, Brandt, Hirvonen, Olivetti, Rabie and Suomela introduced an Ω (min Δ, logloglog𝑛 𝑛 ) deterministic 11 [5]. Recently Khoury and Schild improved the randomised lower bound lower bound trees √ { on regular } to Ω (min log Δ, log 𝑛 ) for randomised MM on regular trees [57]. For MIS on trees, Balliu, Ghaffari, { } √ Kuhn and Olivetti established a lower bound of Ω (min logloglogΔ Δ , logloglog𝑛 𝑛 ) for randomised algorithms √ [9]. As previously mentioned, MIS can be solved in 𝑜( log 𝑛) on trees, and thus, it is not a coincidence that this bound is weaker than that for MM on trees. For more specialised graph classes, further algorithms have been developed. If the input graph is a growth-bounded graph, Kuhn, Moscibroda, Nieberg and Wattenhofer showed that MIS can be solved in √ deterministic (log Δ⋅log∗ 𝑛) rounds in LOCAL [68]. Moreover, Barenboim and Elkin developed a 𝑜( log 𝑛) rounds algorithm for MIS in the LOCAL model if the input graph has bounded arboricity [12, 83]. MIS on bounded-independence graphs requires (log∗ 𝑛) rounds for the LOCAL model [86] and for unit disk graphs, MIS can even be solved in constant rounds by a deterministic CONGEST algorithm [77].
2
Technical Overview
The distinguishing feature of hyperbolic random graphs as compared to general graphs is their underlying hyperbolic geometry that causes two nodes to be adjacent if and only if they are also geometrically close. Thus, our results are based on three geometric mechanisms. First, for the upper bounds, we use short 10 11
This can be seen by taking the line graph 𝐻 of graph 𝐺 such that an MM on the line graph 𝐻 is equivalent to an MIS on 𝐺. This work was honoured with the FOCS’19 best paper award.
5
randomised procedures to create geometric separators in the hyperbolic disk; these separators confine every remaining connected component to a narrow angular sector and hence to polylogarithmic size. Second, for the lower bounds, we show that HRGs contain many induced regular trees attached to the giant component by a cut edge, allowing lower bounds from tree-like instances to transfer to HRGs. Third, when geometric coordinates are available, we replace shattering by an explicit tiling of the disk, which lets nodes process well-separated tiles or annuli in parallel. We discuss these three ideas in turn.
2.1
Efficient Algorithms for MIS and MM
The algorithms for MIS and MM in Theorem 1 follow the same high-level strategy. We first run a constantround randomised procedure that shatters the graph into connected components of size polylog 𝑛. We then solve each remaining component independently using the best available deterministic algorithms. In the 5/3 ̃ log 𝑛)-round bound via the algorithm of Ghaffari and Grunau [47], and LOCAL model, this gives the (log 3 ̃ in the CONGEST model, it gives the (log log 𝑛)-round bound via the deterministic CONGEST algorithms of [40]. Why don’t we use off-the-shelf algorithms and their analysis? Essentially all known sublogarithmictime distributed algorithms for MIS and MM rely on such a shattering framework: an initial randomised step solves most of the graph, leaving only small connected components to be handled deterministically. Existing shattering-based algorithms are not directly suitable for our setting for two reasons. First, their randomised step inherently takes Θ(log Δ) rounds, which is too slow on HRGs, where the maximum degree Δ is polynomial in 𝑛. Second, in reality, the standard shattering guarantees do not leave components of polylog 𝑛 size; rather, the residual components may have size poly(Δ) log 𝑛, together with additional structure that can be exploited algorithmically. Relying on this additional structure would lead to weaker final round complexities in our setting. We therefore develop a different geometric argument that establishes the desired shattering phenomenon directly. The key geometric target of the randomised step is the separator pattern shown in Figure 2. We want to remove all vertices in an inner disk (hatched area in Figure 2) and, in the remaining outer annulus, remove a collection of neighbourhoods (green areas in Figure 2) that cut the annulus into narrow angular sectors. If these remaining unsolved sectors have angular width at most 𝜙, for 𝜙 ≈ polylog(𝑛)/𝑛, then each sector contains only polylog 𝑛 vertices with high probability (blue regions in Figure 2b). Moreover, by the choice of the removed regions, any two vertices lying in different sectors are at hyperbolic distance larger than 𝑅, and hence are non-adjacent. Therefore, once this separator pattern is realised, every remaining connected component is contained in a single narrow sector and has size polylog 𝑛. The main challenge is to realise this separator pattern while producing a locally valid partial solution for MIS or MM. The way this is done differs substantially between the two problems. Geometric shattering for MIS. The main challenge in designing a fast shattering algorithm, ideally a constant-time algorithm, is dealing with the huge amount of dependencies that occur in algorithms for HRGs. On the positive side for MIS, a selected vertex removes all its neighbours, which makes it well suited for creating geometric separators: if we can make vertices in suitable annuli join the independent set, then their neighbourhoods carve out the desired removed regions, see the green disks in Figure 2a. The first step creates separators in the outer disk. We activate vertices in an annulus at radius roughly ≈ 𝑅 − 8 log log 𝑛 (see red annulus in Figure 2a), equivalently, vertices whose degrees lie in an appropriate polylogarithmic range. We then perform one Luby-style step on these active vertices: each active vertex draws a random value, and active vertices that are local winners join the independent set. The neighbourhoods of these winners remove angular intervals in the outer disk. With high probability, every angular interval of width about 𝜙 ≈ polylog 𝑛/𝑛 contains such a removed neighbourhood. Intuitively, this stems from the fact that active vertices have polylogarithmic degree and thus, given that within an interval of 6
ϕ
(a) Overview of first two rounds.
(b) Result after the first two rounds.
Figure 2: Shattering: (a) Vertices in the blue and red annuli are active in steps 1 and 2, respectively. (b) The hatched area and the green area together form the separator.
width 𝜙 there polylog 𝑛 vertices located, in expectation there will be also a winner vertex. Consequently, the outer annulus is split into angular sectors of width at most 𝜙 (see Figure 2b). The second step removes the inner disk (hatched region in Figure 2). Here we activate remaining low-degree vertices close to the boundary (blue annulus in Figure 2b). A vertex 𝑢 in the inner disk has many such active neighbours close to the boundary (that also survived the first step), and for the sake of analysis we can determine 𝜔(log) such neighbours for which the events of joining the independent set are independent. Each of these active neighbours has a constant probability of joining the independent set and thereby removing 𝑢. Since 𝑢 has 𝜔(log 𝑛) such independent chances, 𝑢 remains uncovered with probability 𝑛−𝜔(1) . A union bound then shows that the entire inner disk is removed with high probability. After these two steps, the remaining vertices lie only in the narrow sectors of the outer annulus. As argued above, different sectors are disconnected, and each sector contains at most polylog 𝑛 vertices with high probability. We then solve MIS independently on each remaining component using the deterministic algorithm for the corresponding models of LOCAL and CONGEST. Geometric shattering for MM. For maximal matching, the same separator pattern is needed, but it is harder to realise. In MIS, one selected vertex removes its whole neighbourhood. In MM, a matched edge removes only its two endpoints, and a vertex can be matched only once. Thus, removing an entire region requires assigning distinct matching partners without creating conflicts. We first remove the inner disk (Figure 2 hatched area). Vertices close to the boundary and of sufficiently small degree are activated (blue annulus in Figure 2a). Each active vertex samples one neighbour uniformly at random and proposes to it. We then consider the vertices in the inner disk, which have a sufficiently large degree. With high probability, every such vertex receives at least one proposal from an active neighbour. Each vertex in the inner disk accepts one proposal, and these accepted proposals form matching edges. This matches all vertices in the inner disk and removes them from further consideration. It remains to create separators in the outer annulus. As in the MIS case, neighbourhoods of vertices in a suitable annulus have the right geometry to separate the outer disk into narrow angular sectors. We activate such vertices (vertices in the red annulus in Figure 2a) and let them draw random values and select local maxima as in one iteration of Luby. By choosing the annulus carefully, we ensure that the relevant outer-disk portions of the 2-hop neighbourhoods of activated nodes are pairwise disjoint. Thus, in the LOCAL model, each activated vertex can learn its 2-hop neighbourhood and compute a maximal 7
r∗
R
log n/α
x
ψ
log log n
ϕ
ϕ
u
(a)
(b)
Figure 3: Excerpt of a hyperbolic disk with trees. (a) Sketch of a nice sector (blue) with angle 𝜙. The hatched area is empty, and the other area contains a 𝑑-ary tree (here 𝑑 = 2 ℎ = 3). Yellow areas are the “boxes” of root 𝑢. (b) Two neighbouring Ψ-sectors (red areas) with angle 𝜓. Both embed a Φ-sector with angle 𝜙 (blue areas); both Φ-sectors are nice containing a tree with a "bridge edge" to a vertex in their respective "buffer regions" Ψ ⧵ Φ connecting the tree to the giant component. If a Φ-sector is nice, then any vertex in it has distance larger than 𝑅 to the point 𝑥. The grey hatched area contains no vertex a.a.s.
matching. Removing the matched nodes from the graph disconnects the unsolved parts into small connected components (blue areas in Figure 2b). In the CONGEST model, 2-hop neighbourhoods cannot be learned efficiently; hence, we use additional structural information to compute the desired maximal matching efficiently.
2.2
Lower Bounds for MIS and MM
The lower bounds are based on showing that HRGs contain hard substructures aka trees. The goal is not merely to find trees as abstract subgraphs, but to find induced regular trees that are attached to the giant component in a controlled way. More precisely, we show that, asymptotically almost surely, the giant component contains polynomially many induced 𝑑-ary trees (trees with degree 𝑑) of depth ℎ. In particular, we use 𝑑-ary trees with parameters 𝑑 ≈ log log 𝑛
and
ℎ ≈ log log 𝑛/ log log log 𝑛.
Each such tree is attached to the giant component by a cut edge incident to its root, while all other vertices of the tree have no additional edges leaving the tree. Once such trees exist, known lower bounds for MIS and MM on regular trees can be extended and lifted to the stated lower bounds for HRGs. Geometric construction. The trees are located close to the boundary of the hyperbolic disk; see Figure 3 for an illustration. We consider a narrow angular sector of width 𝜙 = 𝑜 (log 𝑛/𝑛). Inside such a sector, we prescribe small regions, called boxes (see yellow area in Figure 3a for a sketch), where the vertices of the tree should appear. The root is placed at a distance about log log 𝑛 from the boundary (see vertex 𝑢 in Figure 3a). Its children are placed slightly closer to the boundary, at a radial offset of about 2 log 𝑑. This construction is then repeated recursively ℎ − 1 times: a vertex at level (i) has its 𝑑 children in boxes at the next radial level. The boxes are positioned so that three geometric conditions hold. First, each parent is adjacent to every vertex in its child boxes, i.e., within hyperbolic distance at most 𝑅. Second, vertices in child boxes of the same parent are not adjacent to one another. Third, boxes belonging to different branches are sufficiently separated so that no unintended edges are created. These conditions follow from the hyperbolic distance formula and the choice of the radial and angular spacing between boxes.
8
Thus, if every prescribed box contains exactly one vertex and the remainder of the sector is empty, then the graph induced by the sector is precisely the desired 𝑑-ary tree of depth ℎ. We call such a sector nice; later, we also ensure that the tree in a nice sector is also connected to the giant component in the desired way. The small but sufficient probability of a sector being nice. We show that a single sector is nice with √ probability 𝑛−𝑜(1) : to give intuition for why this is, we first remark that each of the 𝑛′ ≈ log 𝑛 prescribed boxes in a sector has at least constant expected occupancy. So we categorise two different types of boxes, namely 1. boxes where the expected number of vertices is constant, i.e., 𝜆 = Θ(1) and; 2. boxes where the expected number of vertices is larger than constant, i.e., 𝜆 = 𝜔(1). For Item 1, observe that the number of vertices 𝑋𝑖 in the 𝑖-th box is known to be exactly distributed as a Poisson distribution, i.e., 𝑃(𝑋𝑖 = 𝑘) = 𝜆𝑘 /𝑘! ⋅ 𝑒 −𝜆 . Here, 𝜆 is the expected number of vertices in the box and −𝜆 scales with the size of the box. √ For boxes where 𝜆 = Θ(1) we obtain 𝑃(𝑋𝑖 = 1) = 𝜆 ⋅ 𝑒 = 𝑝 = Ω(1). Thus, ′ since we have at most 𝑛 ≈ log 𝑛 boxes, the probability that all these boxes have exactly one vertex is ′ given by 𝑝𝑛 = 𝑛−𝑜(1) as desired. For Item 2, recall that all boxes lie in a sector that has angle 𝜙 = 𝑜(log 𝑛/𝑛). Focussing on boxes with expected number of vertices larger than 1, fix any such box 𝑖 , and let 𝑋𝑖 be the random variable with which we count the number of vertices in 𝑖 . Using that we have a Poisson distribution, it follows that 𝐏 (𝑋𝑖 = 1) = 𝜆 ⋅ exp(−𝜆) ≥ exp(−𝜆) = 𝐏 (𝑋𝑖 = 0) , since 𝜆 > 1. Hence, the probability that a box has exactly one vertex is basically lower bounded by the probability that a box is empty. Now, let 𝑘 be the number of boxes we consider, and we get from the equation above ∏𝑘𝑖=1 𝐏 (𝑋𝑖 = 1) ≥ ∏𝑘𝑖=1 𝐏 (𝑋𝑖 = 0) . On the other hand, since all boxes lie within a sector, the probability that all boxes are empty is lower bounded by the probability of the event that the entire sector is empty. Using that the sector has angle 𝜙 = 𝑜(log 𝑛/𝑛), the expected number of vertices in a sector is 𝜆sector ≈ 𝑛 ⋅ 𝜙 = 𝑜(log 𝑛). Thus, the probability of the event that all boxes are empty is ∏𝑘𝑖=1 𝐏 (𝑋𝑖 = 0) ≥ exp (−𝜆sector ) = 𝑛−𝑜(1) by another application of a Poisson distribution. Putting everything together, it now follows that ∏𝑘𝑖=1 𝐏 (𝑋𝑖 = 1) ≥ ∏𝑘𝑖=1 𝐏 (𝑋𝑖 = 0) = 𝑛−𝑜(1) as desired. Of course, finding a nice sector is not enough: the resulting tree must be induced in the full HRG, and it must be attached to the giant component in a controlled way. To ensure this, we embed each candidate sector Φ into a larger buffer sector Ψ. The buffer is chosen large enough so that, conditioned on Φ being nice and the relevant part of Ψ ⧵ Φ being empty, vertices of the tree have no additional neighbours outside the tree, except for a designated edge from the root to the giant component. We again show that this event holds with probability 𝑛−𝑜(1) and we use the standard fact that HRGs contain no vertices too close to the origin asymptotically almost surely to rule out long-range interference from the central part of the disk (see hatched area in Figure 3b). There are polynomially many disjoint buffer sectors Ψ, and the events of the Ψ-sectors are independent of each other since vertices in two distinct “nice sectors” have disjoint neighbourhoods given that there is no vertex in the hatched area of Figure 3b. Since each Ψ-sector succeeds with probability 𝑛−𝑜(1) , a Chernoff bound implies that polynomially many of them contain the desired tree structure with high probability. Since we conditioned on the event that the hatched area of Figure 3b is empty, an event that holds a.a.s., this proves the structural theorem and, via the lower-bound transfer from regular trees, yields Theorem 2.
9
O(log log n)
(a)
(b)
Figure 4: Sketch for our tiling. (a) Any pair of points in two different red tiles has a distance larger than 𝑅. (b) The induced subgraph of a tile is a clique, and there are no edges between the cliques of the red tiles.
2.3
Embedding-Aware Algorithms
We finally outline the algorithms of Theorem 3, where nodes are given access to geometric coordinates. This additional information changes the algorithmic approach. Instead of first producing random separators and then solving small residual components, the algorithms use the geometry directly. Embedding-aware deterministic algorithm for MIS. For the MIS algorithm, we first partition the outer part of the hyperbolic disk into tiles arranged in (log log 𝑛) radial layers. The tiling is chosen to have two useful properties. First, every tile induces a clique (see red tiles Figure 4b). Second, within each fixed layer, the tiles can be processed according to a constant-size schedule: in each step of the schedule, all currently active tiles are mutually non-adjacent and can therefore be handled in parallel; for a sketch, see red tiles in Figure 4a. The algorithm is then a simple layer-by-layer sweep. For each of the (log log 𝑛) layers, we execute the constant-size schedule for that layer. Whenever a tile is processed, we solve it locally by selecting one still-eligible vertex, if such a vertex exists, and adding it to the independent set. Since a tile is a clique, this is sufficient to resolve all the vertices of the tile. Since each layer requires only (1) rounds, the total runtime is (log log 𝑛). Correctness for the outer disk follows directly from the sweep: every processed tile is solved when it is considered. It remains to argue that the inner disk (hatched area in Figure 4b) is also dominated. Every inner-disk vertex has neighbours in many processed tiles; we show that by the tiling construction (with high probability over the draw of the HRG), any even adversarially chosen MIS (the algorithm is deterministic) within these tiles still contains at least one neighbour of the vertex. Hence, after the (log log 𝑛)-round sweep, every vertex is either selected or has a selected neighbour, and the resulting independent set is maximal. Embedding-aware randomised algorithm for MM. For MM, a layer-by-layer sweep would only give an (log log 𝑛)-round algorithm, which is slower than our target runtime. Moreover, the MIS strategy does not transfer directly: matching one vertex in a tile only removes one neighbour, rather than dominating an 10
entire neighbourhood. We therefore first remove the inner disk (hatched area in Figure 4b) with the same constant-round randomised proposal step as for Theorem 1. Afterwards, we use a bottom-up approach on the (log log 𝑛) remaining outer layers. Initially, we compute a maximal matching inside each single layer in (1) rounds using a tiling schedule that covers each intra-layer edge. We then repeatedly merge solved layers: when two neighbouring layers have already been solved separately, we may still need to add matching edges between them to obtain maximality for their union. Such merging steps can be performed in parallel for disjoint pairs of layers. The main technical work is to show that each individual merge can be implemented in (1) rounds as sketched in Figure 9. After 𝑡 merging steps, the algorithm has solved blocks of 2𝑡 consecutive layers. Since there are only (log log 𝑛) layers, (log log log 𝑛) steps suffice to solve the entire outer disk. Including the constant-round preprocessing of the inner disk, this gives the desired (log log log 𝑛)-round algorithm for MM.
3
Conclusion
In this work, we investigate classical symmetry-breaking problems through the lens of hyperbolic random graphs. In particular, we resolve an open question posed by [74] by showing that maximal independent set and maximal matching can be computed in poly log log 𝑛 rounds on hyperbolic random graphs. Thus, when the input graph is drawn from √ the hyperbolic random graph model, these problems admit substantially faster algorithms than the Ω( log 𝑛) round complexity known for worst-case instances [57]. Our result for the LOCAL model relies on a constant-round algorithm that shatters an HRG into polylogarithmicsize components. The runtime then follows from the state-of-the-art deterministic algorithm [47]; any improvements for the deterministic algorithm in [47] would also imply a faster algorithm for hyperbolic random graphs. Conversely, we show that MIS and MM are inherently harder than (Δ + 1)-colouring on hyperbolic random graphs. While (Δ+1)-colouring can be solved in just 2 rounds [74], MIS and MM remain substantially more difficult, and we prove a lower bound of Ω ( logloglogloglog𝑛 𝑛 ) rounds for both MIS and MM. Our lower bounds rely on new structural insights of hyperbolic random graphs that may be of independent interest. Specifically, we prove that the giant component of a hyperbolic random graph is likely to contain polynomially many logarithmic-size 𝑑-ary trees for a wide range of different degrees 𝑑 and height ℎ. Finally, for maximal matching, we demonstrate that access to the underlying geometric coordinates enables an exponentially faster algorithm than implied by this lower bound. Open Questions. Our work opens up several research questions and the identified structural insights may also improve the design and analysis of distributed algorithms beyond the HRG model. • How does Luby’s algorithm perform on HRGs? • Is there a separation between MIS and MM on HRGs, as is the case on trees? • For embedding-aware graphs, can we overcome the lower bound barrier of Theorem 2 for MIS? • How can we establish lower bounds in the setting of embedding-aware graphs? • What is the complexity of distributed approximation algorithms for Maximum Matching and Maximum Independent Set on HRGs? • Is the complexity landscape of other symmetry-breaking problems, such as edge colouring or vertex cover, similar to that of MIS/MM or (Δ + 1)-colouring on HRGs?
11
Outline of the rest of the paper The remainder of this article is structured as follows. In Section 4, we give a formal definition for the model of hyperbolic random graphs, and we collect important lemmas we make use of throughout this work. The analyses of our shattering algorithms can be found in Section 5. Our findings of 𝑑-ary trees and the lower bound implications are stated in Section 6.1. We conclude with our approach for algorithms where the embedding of an HRG is given (Section 7).
4
Hyperbolic Random Graphs
Hyperbolic plane. In the following, we introduce the model of hyperbolic random graphs and follow the lines drawn by Papadopoulos et al. [81]. Points are represented by their native representation in the hyperbolic plane ℍ2 = [0, ∞) × [0, 2𝜋). Thus, a point 𝑥 ∈ ℍ2 is identified by a radial coordinate 𝑟(𝑥) and an angular coordinate 𝜑(𝑥). We use exclusively the curvature -1 by which the hyperbolic distance dh (⋅, ⋅) for two points 𝑥, 𝑦 ∈ ℍ2 is given by cosh(dh (𝑥, 𝑦)) = cosh(𝑟(𝑥)) cosh(𝑟(𝑦)) − sinh(𝑟(𝑦)) sinh(𝑟(𝑥)) cos(𝜑(𝑥) − 𝜑(𝑦)),
(1)
and consequently, we use for ℍ2 the topology induced by dh . For a hyperbolic random graph, we consider a subregion of the hyperbolic plane ℍ2 : we operate on a disk with radius 𝑅 denoted by 𝑅 = [0, 𝑅] × [0, 2𝜋), centred at the origin (0, 0). Note that the set of points with distance 𝑟 to 𝑥 ∈ 𝑅 is given by the set 𝑥 (𝑟) = {𝑦 ∈ 𝑅 ∶ dh (𝑥, 𝑦) ≤ 𝑟}, as we restrict the hyperbolic plane to 𝑅 ⊂ ℍ2 . In order to obtain a power-law degree distribution, we introduce the parameter 𝛼 ∈ (1/2, 1) (see also [51, 81]). Then, the probability measure 𝜇 on 𝑅 for measurable ⊆ 𝑅 is defined by 𝜇() = ∫ 𝜌(𝑥) d𝑥,
𝜌(𝑥) =
𝑆
𝛼 sinh(𝛼𝑥) , 2𝜋(cosh(𝛼𝑅) − 1)
where 𝜌 is the density of 𝜇 with respect to the Lebesgue measure on 𝑅 . (Threshold) hyperbolic random graphs. Vertices 𝑉 are identified by their point coordinates in 𝑅 : for a subset of vertices that are identified by a set of points ⊆ 𝑅 , we write 𝑉 ∩ . Throughout this work, we exclusively work on the Poissonised version of (threshold) hyperbolic random graphs (see also [60, 61, 62]). This model allows us to analyse the number of vertices in disjoint areas of the hyperbolic disk independently. Let 𝑛 ∈ ℤ+ and 𝑁 be a Poisson random variable with expectation 𝐄 [𝑁 ] = 𝑛. Then, let 𝑅 ∶= 2 log(𝑛) + 𝐶 for some constant 𝐶 ∈ ℝ and we use an inhomogeneous Poisson point process on 𝑅 where for any ⊆ 𝑅 it holds that the number of expected vertices is given by 𝑛 ⋅ 𝜇() = 𝐄 [|𝑉 ∩ |]. That is, the intensity function at polar coordinates (𝑟, 𝜑) for 0 ≤ 𝑟 < 𝑅 is 𝜆(𝑟, 𝜑) ∶= 𝑛𝜌(𝑥) and the set of vertices is a random variable 𝑉 = {(𝑟1 , 𝜑1 ), (𝑟2 , 𝜑2 ), .., (𝑟𝑁 , 𝜑𝑁 )}. For a pair of vertices 𝑢, 𝑣 ∈ 𝑉 ∩ 𝑅 , there exists the edge {𝑢, 𝑣} ∈ 𝐸 in a threshold hyperbolic random graph, if and only if it holds dh (𝑢, 𝑣) ≤ 𝑅. In the following, we collect some results we make use of throughout this work. It will be convenient to characterise the connection of vertices in terms of their angular distance 𝛿𝜑 (⋅, ⋅). Since vertices are connected if and only if their distance is at most 𝑅, we define 𝜃𝑅 (𝑟1 , 𝑟2 ) = arccos
cosh(𝑟1 ) cosh(𝑟2 ) − cosh(𝑅) , ( ) sinh(𝑟1 ) sinh(𝑟2 )
(2)
which denotes by Equation (1) the angle distance for two points with radii 𝑟1 and 𝑟2 such that their hyperbolic distance is exactly 𝑅. Thus, two vertices with an angle distance of at most 𝜃𝑅 are connected. Throughout this work, we use for 𝜃𝑅 (⋅, ⋅) the following bounds, which are due to [23, Corollary 5]. 12
DR
DR · · ·ℓ − 2
B0 (r)
−
u
0
R
1
Bu (R)
R−
1
ℓ−
R
R−ℓ
R
0
ℓ−1
1
A Lℓ ···
r
L1
1 1
L0 (a)
(b)
Figure 5: (a) Illustration of the neighbourhood 𝑁 (𝑢) of a vertex 𝑢 given by 𝑉 ∩ 𝑢 (𝑅) (blue region) following the geometry of the hyperbolic disk. The red area is the ball 0 (𝑟) centred around the origin for some 𝑟. (b) Sketch of layer 0 (red area), layer 1 (yellow area) and some layer 𝓁 (blue area) for some 0 < 𝓁 < 𝑅. Lemma 4 (Angle distance). Let 𝑥, 𝑦 ∈ 𝑅 and 1 ≤ 𝑟(𝑥), 𝑟(𝑦) ≤ 𝑅 and 𝑟(𝑥) + 𝑟(𝑦) ≥ 𝑅. Then it holds √ √ 𝑒 𝑅−𝑟(𝑥)−𝑟(𝑦) ≤ 𝜃𝑅 (𝑟(𝑥), 𝑟(𝑦)) ≤ 𝜋 𝑒 𝑅−𝑟(𝑥)−𝑟(𝑦) . As remarked in [60, Remark 4], the function 𝜃𝑅 (⋅, ⋅) is decreasing in both arguments. Remark 5. 𝜃𝑅 (⋅, ⋅) is strictly decreasing in both arguments. Next, we look into the measure for different areas in 𝑅 . First, we consider a ball of radius 𝑟 with the origin as its centre point, as sketched by the red area in Figure 5a ([51, Lemma 3.2]). Lemma 6 (Measure of inner disk). For any 0 ≤ 𝑟 ≤ 𝑅 we have 𝜇 (0 (𝑟)) = (1 + 𝑜(1))𝑒 −𝛼(𝑅−𝑟) . We write 𝑁 (𝑢) ∶= {𝑣 ∈ 𝑉 ∶ {𝑢, 𝑣} ∈ 𝐸(𝐺)} for the neighbourhood of 𝑢 and deg(𝑢) ∶= |𝑁 (𝑢)| for the degree of 𝑢. Since a vertex 𝑢 has an edge to every vertex within distance 𝑅, it is adjacent to all vertices in 𝑢 (𝑅) ∩ 𝑅 (see blue area in Figure 5a). For the expected degree of a vertex, we use the following bounds ([74, Lemma 7]). Lemma 7 (Vertex Degree). Let 𝑢 ∈ 𝑉 ∩ 𝑅 be a vertex with radius 𝑟 ≥ 1. Then, the expected degree of 𝑢 in a threshold HRG is (1 − 𝑜(1))𝛼 (1 + 𝑜(1))𝛼 𝑛𝑒 −𝑟/2 ⋅ ≤ 𝐄 [deg(𝑢)] ≤ 𝑛𝑒 −𝑟/2 ⋅ . 𝜋(𝛼 − 1/2) 𝛼 − 1/2 Another sub-area of the disk we use are layers as used by Friedrich and Krohmer [43]. For 𝓁 ∈ [⌊𝑅⌋], a layer is defined by 𝓁 ∶= 0 (𝑅 − 𝓁) ⧵ 0 (𝑅 − 𝓁 − 1) (see Figure 5b for a sketch). Using Lemma 6 and Lemma 7, we obtain the following. Lemma 8 (Layer properties). Let 𝓁 ∈ [⌊𝑅⌋] and 𝑢 ∈ 𝑉 ∩ 𝓁 . Then 𝜇(𝓁 ) = (1 − 𝑒 −𝛼 + 𝑜(1))𝑒 −𝛼𝓁 , and 𝑒 𝓁/2 ⋅
(1 − 𝑜(1))𝛼𝑒 𝐶/2 (1 + 𝑜(1))𝛼𝑒 𝐶/2 ≤ 𝐄 [deg(𝑢)] ≤ 𝑒 𝓁/2 ⋅ . 𝜋(𝛼 − 1/2) 𝛼 − 1/2 13
(3)
(4)
For notational convenience, we sometimes write 𝑉𝓁 ∶= 𝑉 ∩ 𝓁 for the set of vertices in layer 𝓁. Finally, the following statement will be useful: it states that if two vertices share a neighbour with larger radius, then they form a connected triangle with that neighbour. Lemma 9. Let 𝑥, 𝑦, 𝑧 ∈ 𝑅 such that 1 ≤ 𝑟(𝑥) ≤ 𝑟(𝑦) ≤ 𝑟(𝑧) − 2 log(2𝜋) ≤ 𝑅 − 2 log(2𝜋). Then, if dh (𝑥, 𝑧) ≤ 𝑅 and dh (𝑦, 𝑧) ≤ 𝑅, it holds that dh (𝑥, 𝑦) ≤ 𝑅. Proof. By our hypothesis that dh (𝑥, 𝑧) ≤ 𝑅 and dh (𝑦, 𝑧) ≤ 𝑅, it follows for the angular distance between 𝑥 and 𝑦 by Lemma 4 that √ 𝛿𝜑 (𝑥, 𝑦) ≤ 𝜃𝑅 (𝑟(𝑥), 𝑟(𝑧)) + 𝜃𝑅 (𝑟(𝑦), 𝑟(𝑧)) ≤ 2𝜋 𝑒 𝑅−𝑟(𝑥)−𝑟(𝑧) , since 𝑟(𝑥) ≤ 𝑟(𝑦) and using Remark 5. Consequently, using our hypothesis that 𝑟(𝑧) ≥ 𝑟(𝑦) + 2 log(2𝜋), it follows √ 𝛿𝜑 (𝑥, 𝑦) ≤ 𝑒 𝑅−𝑟(𝑥)−𝑟(𝑦) ≤ 𝜃𝑅 (𝑟(𝑥), 𝑟(𝑦)), and thus, by Lemma 4 we have dh (𝑥, 𝑦) ≤ 𝑅 as desired. Further Notation. We write [𝑘] (where 𝑘 ∈ ℤ+ ) for the set {0, 1, … , 𝑘 − 1}. For the randomness over the graph distribution of a hyperbolic random graph, we use ℙ (⋅) and 𝔼 [⋅]. Conversely, we write 𝐏 (⋅) and 𝐄 [⋅] when we deal with the randomness of an algorithm on a sampled hyperbolic random graph 𝐺. A sector Φ ⊆ 𝑅 with angle 𝜙 and bisector 𝜑, is defined by the set of points Φ ∶= {𝑥 ∈ 𝑅 ∶ 𝜑−𝜙/2 ≤ 𝜑(𝑥) ≤ 𝜑+𝜙/2}. For a vertex 𝑢 ∈ 𝑉 , we write 𝐸(𝑢) ∶= {{𝑢, 𝑣} ∈ 𝐸 ∶ 𝑣 ∈ 𝑁 (𝑢)} for the set of incident edges to 𝑢.
5
Efficient Algorithms for MIS/MM on HRGs (Theorem 1)
The goal of this section is to prove the following theorem. Theorem 1 (Upper bounds for MIS and MM). There are randomised distributed algorithms that, for threshold hyperbolic random graphs, compute Maximal Independent Set and Maximal Matching 5/3 ̃ • in (log log 𝑛) rounds 𝑤.𝑒.ℎ.𝑝. 12 of the LOCAL model; 3 ̃ • in (log log 𝑛) rounds 𝑤.𝑒.ℎ.𝑝. of the CONGEST model. 13
All algorithms follow a shattering-based approach that exploits structural properties of hyperbolic random graphs to identify separators that shatter the graph into small components. These can then be solved independently and in parallel using any deterministic algorithm. The overall running time is determined by the algorithm used to solve the remaining components, as the shattering itself takes constant rounds. The proof for the MIS part can be found in Section 5.1. The MM part we show in Section 5.2.
5.1
Efficient Maximal Independent Set Algorithm (MIS part of Theorem 1)
We use Luby’s algorithm as a subroutine. In Luby’s algorithm, all (active) vertices draw a random ID. If a vertex 𝑢 has the largest ID among its neighbours 𝑁 (𝑢), then 𝑢 is added to the independent set 𝐼 . An iteration of Luby’s algorithm has 2 rounds: first, all active vertices send their random ID to all neighbours. Then any active vertex 𝑢 informs all its neighbours based on the IDs if 𝑢 is (a) in the independent set, (b) 12 13
We say an event occurs with extremely high probability (w.e.h.p.) if ℙ () ∈ 1 − 𝑛−𝜔(1) . For MM, we obtain the slightly stronger bound of (log3 log 𝑛).
14
A
R S
log30α (n)/n
ℓ̂
ϕ
c( C ,α )
ϕ̂
8 log log n
(a)
(b)
Figure 6: (a) Sketch of Lemma 10. All active vertices that join the independent set after the first step are in (blue annulus) w.e.h.p., and if a sector is large enough, there is a vertex in the sector that joined the independent set (yellow area). (b) Sketch of the area (hatched region). The sector Φ (red) is active if area contains a vertex that joins the independent set after the first step. has a neighbour that is part of the independent set, or (c) neither of the two. For 𝑡 ∈ ℤ+ , we denote by 𝑉(𝑡) the set of vertices that are neither part of the independent set nor have a neighbour in the independent set after the 𝑡-th step of HRG-Shattering-MIS, where by HRG-Shattering-MIS we refer to the following process. 4
(𝑛) 4 • Step 1: Activate all vertices of the set 𝑈(1) ∶= {𝑣 ∈ 𝑉 ∶ ⌊ log 1000 ⌋ ≤ deg(𝑣) ≤ ⌈1000 log (𝑛)⌉}. Execute one iteration of Luby’s algorithm on active vertices 𝑈(1) .
• Step 2: Activate all vertices of the set 𝑈(2) ∶= {𝑣 ∈ 𝑉(1) ∶ deg(𝑣) ≤ ⌈log3/2 (𝑛)⌉}. Execute one iteration of Luby’s algorithm on active vertices 𝑈(2) . We analyse step 1 in Lemma 10 and step 2 is addressed in Lemma 12. We then use the two lemmas to show that HRG-Shattering-MIS shatters a hyperbolic random graph into components that are all of size at most poly log 𝑛; see also Proposition 14. The following lemma tells us that when we consider the independent set 𝐼 generated after the first step of HRG-Shattering-MIS, that (1) all vertices of 𝐼 are contained in an annulus with constant thickness and (2) for any sector with a large enough angle, we find a vertex that is part of the independent set 𝐼 ; see also Figure 6a for a sketch. Lemma 10 (Step 1 of HRG-Shattering-MIS). Let 𝐺 be a threshold hyperbolic random graph and consider the set of vertices 𝐼(1) that is part of the independent set after step 1 of HRG-Shattering-MIS. Moreover, let 𝑐(𝐶, 𝛼) be a constant large enough and consider annulus ≔ 0 (𝑅 − 8 log log 𝑛 + 𝑐(𝐶, 𝛼)) ⧵ 0 (𝑅 − 8 log log 𝑛 − 𝑐(𝐶, 𝛼)). Then the following holds for 𝐼(1) with probability 1 − 𝑛−𝜔(1) : 1. All vertices contained in the independent set after the first step are in ; 𝐼(1) ⊆ 𝑈(1) ⊆ 𝑉 ∩ . 30𝛼
2. In any sector with angle log 𝑛 𝑛 there exists a vertex 𝑣 such that 𝑣 ∈ 𝐼(1) . Proof. We prove the first part of the lemma by showing that, w.e.h.p., no vertex outside the annulus has the same degree as an active vertex 𝑈(1) . Consequently, no such vertex joins the independent set in the first step. To this end, let 𝑐(𝐶, 𝛼) ∶= 100 + |𝐶| + 2 log(1/(𝛼 − 1/2)) chosen with hindsight, and consider any vertex
15
𝑢 ∈ 𝑉 ∩ 0 (𝑅 − 8 log log 𝑛 − 𝑐(𝐶, 𝛼)). Then, for 𝑢 it holds via Lemma 7 that (1 − 𝑜(1))𝛼 (𝑐(𝐶,𝛼)−𝐶)/2 4 𝑒 log 𝑛 𝜋(𝛼 − 1/2) ≥ 10000 log4 𝑛,
𝐄 [deg(𝑢)] ≥
by our choice of 𝑐. Thus, a Chernoff-bound (Lemma 43) and union bound yield that for any 𝑢 ∈ 𝑉 ∩ 0 (𝑅 − 8 log log 𝑛 − 𝑐(𝐶, 𝛼)), that deg(𝑢) > ⌈1000 log4 𝑛⌉ w.e.h.p. Analogously, we get for any vertex 𝑢 ∈ 𝑉 ∩ 𝑅 ⧵ 0 (𝑅 − 8 log log 𝑛 + 𝑐(𝐶, 𝛼)) that (1 + 𝑜(1))𝛼 −(𝑐(𝐶,𝛼)+𝐶)/2 4 𝑒 log 𝑛 (𝛼 − 1/2) log4 𝑛 ≤ . 10000
𝐄 [deg(𝑢)] ≤
Another combination of Chernoff bound with a union bound then reveals that for any 𝑢 ∈ 𝑉 ∩ 𝑅 ⧵ 0 (𝑅 − 4 𝑛 8 log log 𝑛 + 𝑐(𝐶, 𝛼)) that deg(𝑢) < ⌊ log 1000 ⌋ w.e.h.p. This concludes the proof for Item 1. We now turn to the second point of the lemma. Consider a sector Φ with angle 𝜙 = log16𝛼 (𝑛)/𝑛. W.l.o.g. let Φ have bisector 0. Then, let 𝓁̂ = ⌈8 log log 𝑛 + 2 log(𝛼 − 1/2) − 𝐶⌉, 𝜙̂ = log10𝛼 (𝑛)/𝑛 and consider the area ̂ ≤ 𝜑(𝑥) ≤ 𝜙/2} ̂ ∶= {𝑥 ∈ 𝓁̂ ∶ 2𝜋 − 𝜙/2 (see also Figure 6b for a sketch). We say Φ is active if 𝐼(1) ∩ ≠ ∅, i.e., there is a vertex in the area that joins the independent set after the first step of HRG-Shattering-MIS. Claim 11. A sector Φ with angle 𝜙 = log16𝛼 (𝑛)/𝑛 is active with probability Ω(1/ log4 𝑛). Proof of claim. We lower bound the probability that Φ is active as follows: first, we show that any vertex in is active in the first step w.e.h.p. Then, we show that contains at least one vertex w.e.h.p. The bound then follows using a union bound over the complementary of these two events and since any active vertex 𝑢 in step 1 of HRG-Shattering-MIS has degree deg(𝑢) ∈ Θ(log4 𝑛). By our choice of 𝓁̂ and ⊂ 𝓁̂, we get for any 𝑢 ∈ 𝑉 ∩ by using Lemma 8 that (1 − 𝑜(1))𝛼 ⋅ log4 𝑛 ≤ 𝐄 [deg(𝑢)] ≤ (1 + 𝑜(1))𝛼 ⋅ log4 𝑛. 𝜋 4
(𝑛) Since 𝛼 ∈ (1/2, 1), using Chernoff bounds then yields that for 𝑢 ∈ 𝑉 ∩ it holds that ⌊ log 1000 ⌋ ≤ deg(𝑢) ≤
⌈1000 log4 (𝑛)⌉ w.e.h.p. Hence, 𝑢 is active for the first step of Luby in HRG-Shattering-MIS and a union bound shows that any vertex in is active w.e.h.p. Next we use that spans an angle of 𝜙̂ = log10𝛼 (𝑛)/𝑛. This in conjunction with ⊂ 𝓁̂ and 𝓁̂ ∈ 8 log log 𝑛 + (1) then yields via Lemma 8 that 10𝛼
log ̂ 𝜇() = 𝜙/2𝜋 ⋅ 𝜇(𝓁̂) = Θ(1)
𝑛
𝑛
⋅ 𝑒 −8𝛼 log log 𝑛 ∈ 𝜔
log 𝑛 , ( 𝑛 )
since 𝛼 > 1/2. Consequently, by another Chernoff bound, is non-empty w.e.h.p. The claim now follows since any vertex in by our outline of the proof for Claim 11 since any active vertex 𝑢 joins 𝐼 with probability at least 1/(deg(𝑢) + 1) ∈ Ω(1/ log4 𝑛). ■ Now, partition the disk 𝑅 into ⌈2𝜋𝑛 ⋅ log−28𝛼 𝑛⌉ =∶ 𝑘 sectors such that each sector has angle 𝜓 ∈ Θ(log28𝛼 (𝑛)/𝑛). Note that if each such sector contains at least one vertex that joins the independent set 𝐼(1) , 30𝛼
then it also holds for any sector with angle at least log 𝑛 𝑛 that there exists a vertex that is in 𝐼(1) as desired for Item 2.
16
R−1
S
ϕ
Φ
S 2
u
2
k
ψ
ϕ
Φ 11
w
... u
k
4
r
ϕ
−
gn
R
R
o gl lo
Φ S
A
L0
A′
v (a)
(b)
Figure 7: (a) The hatched area is removed after the second step of HRG-Shattering-MIS (Lemma 12). Case 1: Vertex 𝑤 joined the independent set in the first round. If there exist the edges {𝑢, 𝑣} and {𝑣, 𝑤}, then there exists also the edge {𝑢, 𝑤}. (b) Case 2: Partition of a sector with angle 𝜓 and bisector 𝜑(𝑢) into sectors with angle 𝜙. A sector Φ𝑖 (red area) is active if there is a vertex in 𝑖 (green area) that joins the independent set. To show that this holds with the desired probabilistic guarantee, fix any sector Ψ with angle 𝜓 and partition Ψ into 𝑘 ′ ∈ Θ(log12𝛼 𝑛) sectors, such that each sector has angle 𝜙 = log16𝛼 (𝑛)/𝑛. For the 𝑖-th sector with angle 𝜙, we write Φ𝑖 and let 𝑋𝑖 be the indicator random variable that is 1 if the 𝑖-th sector is ′ active. Moreover, let 𝑋 = ∑𝑘𝑖 𝑋𝑖 so that by linearity of expectation the expected number of active sectors with angle 𝜙 in Ψ is 𝔼 [𝑋 ] = 𝑘 ′ ⋅ 𝔼 [𝑋𝑖 ] ∈ Ω(log 𝑛12𝛼−4 𝑛) ∈ 𝜔(log 𝑛), by applying Claim 11 and using that 𝛼 > 1/2. Next, for any pair of sectors Φ𝑖 and Φ𝑗 , we show that 𝑋𝑖 and 𝑋𝑗 are independent w.e.h.p. To see this, recall that Φ𝑖 is active if the area 𝑖 ⊂ Φ𝑖 with angle 𝜙̂ = log10𝛼 (𝑛)/𝑛 contains a vertex that draws the largest ID among active neighbours. W.l.o.g. let Φ𝑖 have bisector 0. Moreover, using Item 1, any active vertex 𝑣 has radius 𝑟(𝑣) ∈ 𝑅 − 8 log log 𝑛 − Θ(1) w.e.h.p. Hence, using Lemma 4 in conjunction with Remark 5, any active vertex 𝑣 that is a neighbour of 𝑢 ∈ 𝑉 ∩ 𝑖 has angle 𝜑(𝑣) ≤ 𝜙̂ + 𝜃𝑅 (𝑟(𝑢), 𝑟(𝑣)) ∈
log8 𝑛 + log10𝛼 𝑛 ∈ 𝑜(𝜙) w.e.h.p., ( ) 𝑛
where the last step follows since 𝜓 = log16𝛼 (𝑛)/𝑛 and 𝛼 > 1/2. Consequently the event only depends on the randomness in Φ𝑖 w.e.h.p. A union bound over 𝑘 ′ sectors with angle 𝜙 shows that this also holds for all 𝑘 ′ Φ-sectors in sector Ψ w.e.h.p. Thus, using that for any pair of sectors Φ𝑖 , Φ𝑗 ⊂ Ψ the respective random variables 𝑋𝑖 and 𝑋𝑗 are independent w.e.h.p. and using 𝔼 [𝑋 ] ∈ 𝜔(log 𝑛), we obtain via a Chernoff bound that Ψ contains at least 1 vertex that is in 𝐼(1) w.e.h.p. A union bound over the 𝑘 ∈ 𝑜(𝑛) Ψ-sectors with angle 𝜓 wraps up the proof since every sector with angle 𝜓 ∈ Θ(log28𝛼 (𝑛)/𝑛) ∈ 𝑜(log30𝛼 (𝑛)/𝑛) contains a vertex of 𝐼(1) w.e.h.p. Next, we show that after step two of HRG-Shattering-MIS, all vertices of degree larger than ≈ log7/2 𝑛 are removed by having a neighbour in the independent set 𝐼(2) (except for the vertices we included in the independent set after step one). For the area of these vertices, see also the hatched area in Figure 7a. Lemma 12 (Step 2 of HRG-Shattering-MIS). Let 𝑟 ∶= 𝑅 − 7 log log 𝑛. Then after the second step of HRGShattering-MIS, for any vertex 𝑢 ∈ 𝑉(1) ∩ 0 (𝑟) it holds with probability 1 − 𝑛−𝜔(1) that 𝑢 ∉ 𝑉(2) . Proof. Consider the annulus ′ ∶= 𝑅 ⧵ 0 (𝑅 − 4 log log 𝑛 − 𝐶). Then, by Lemma 7, any vertex 𝑣 ∈ 𝑉 ∩ (𝑅 ⧵ ′ ) has expected degree 𝐄 [deg(𝑣)] ∈ Ω(log2 𝑛). Using a Chernoff- and a union bound, all vertices 17
outside the annulus ′ have a degree larger than ⌈log3/2 (𝑛)⌉ w.e.h.p. Hence, all vertices that are active in the second step of HRG-Shattering-MIS are within the annulus ′ , i.e., 𝑈(2) ⊆ 𝑉(1) ∩ ′ w.e.h.p. Now, using 𝑟 = 𝑅 − log log 𝑛 as defined in our lemma statement, fix a vertex 𝑢 ∈ 𝑉(1) ∩ 0 (𝑟), i.e., a vertex in the inner disk that was not removed in the first round of HRG-Shattering-MIS. We prove our desired statement by the following case distinction: (1) there exists at least one vertex 𝑣 in the neighbourhood of 𝑢, such that 𝑣 lies in the annulus ′ and 𝑣 was removed after the first step of HRG-Shattering-MIS, i.e., (𝑁 (𝑢) ∩ ′ ) ⧵ (𝑉 ⧵ 𝑉(1) ) ≠ ∅ (see also Figure 7a), and (2) non of the neighbours of 𝑢, that lie in annulus ′ was removed after the first step of HRG-Shattering-MIS, i.e., (𝑁 (𝑢) ∩ ′ ) ⧵ (𝑉 ⧵ 𝑉(1) ) = ∅. Case 1 [(𝑁 (𝑢) ∩ ′ ) ⧵ (𝑉 ⧵ 𝑉(1) ) ≠ ∅]: Consider a vertex 𝑣 ∈ (𝑁 (𝑢) ∩ ′ ) ⧵ (𝑉 ⧵ 𝑉(1) ). Since 𝑣 ∉ 𝑉(1) , either (a) 𝑣 is in the independent set after the first step, 𝑣 ∈ 𝐼(1) , or (b) 𝑣 has a neighbour 𝑤 ∈ 𝐼(1) that is in the independent set after the first step. Using Lemma 10, no vertex in the set 𝐼(1) is in the annulus ′ w.e.h.p. and thus, case (a) does not occur w.e.h.p. Hence, only case (b) remains (see Figure 7a for a sketch). Using again Lemma 10, it follows that vertex 𝑤 ∈ 𝑁 (𝑣) ∩ 𝐼(1) has radius 𝑟(𝑤) ≤ 𝑅 − 8 log log 𝑛 + 𝑐 w.e.h.p. Then, since 𝑣 ∈ 𝑉 ∩ ′ , it holds 𝑟(𝑣) ≥ 𝑅 − 4 log log 𝑛 - C. Thus, using Lemma 9, 𝑢 ∈ 𝑁 (𝑤) since 𝑟(𝑢) ≤ 𝑅 − 7 log log 𝑛. It follows that 𝑢 ∉ 𝑉(1) w.e.h.p. since 𝑤 ∈ 𝐼(1) ; 𝑢 was removed after the first step of HRG-Shattering-MIS, and thus, we conclude by (a) and (b) that case 1 does not occur w.e.h.p. Case 2 [(𝑁 (𝑢) ∩ ) ⧵ (𝑉 ⧵ 𝑉(1) ) = ∅]: Consider the sector Ψ with angle 𝜓 = 𝑒 𝐶/2 ⋅ log7/2 𝑛/𝑛 and bisector 𝜑(𝑢). Note that, since 𝑟(𝑢) ≤ 𝑅 − 7 log log 𝑛, we obtain via Lemma 4 in conjunction with Remark 5 that Ψ ⊂ 𝑢 (𝑅), and thus, if a vertex 𝑣 ∈ 𝑉 ∩ Ψ joins the independent set, 𝑢 is removed since 𝑣 ∈ 𝑁 (𝑢). We partition Ψ into 𝑘 ∶= 𝑒 𝐶 ⋅ log3/2 𝑛/100 sectors, such that for 𝑖 ∈ [𝑘] each sector Φ𝑖 ⊂ Ψ has angle 𝜙 = 100 ⋅ 𝑒 −𝐶/2 log2 𝑛/𝑛. Let 𝜑𝑖 be the bisector of Φ𝑖 and let 𝑖 ∶= {𝑥 ∈ Φ𝑖 ∩ 0 ∶ 𝜑𝑖 − 1/𝑛 ≤ 𝜑(𝑥) ≤ 𝜑𝑖 + 1/𝑛}, i.e., a sub-area of sector Φ𝑖 in layer 0 , with the same bisector as Φ𝑖 that spans an angle of 2/𝑛 (see also green area in Figure 7b). We say that Φ𝑖 is active if there exists a vertex 𝑣 ∈ 𝑉 ∩ 𝑖 such that 𝑣 joins the independent set in the second step of HRG-Shattering-MIS, i.e., 𝐼(2) ∩ 𝑖 ≠ ∅. Claim 13. A sector Φ𝑖 is active with non-vanishing probability. Proof of claim. Recall that due to case 2, we condition on the event that no neighbour 𝑣 ∈ 𝑁 (𝑢) ∩ ′ has a neighbour 𝑤 ∈ 𝑁 (𝑤) ∩ 𝐼(1) in the independent set after the first step of HRG-Shattering-MIS. Thus, using that |𝑉 ∩ 𝑖 | follows a Poisson distribution and 𝜇(𝑖 ) =
𝜇(0 ) ∈ Ω(1/𝑛), 𝜋𝑛
by Lemma 8 and 𝑖 spanning an angle of 2/𝑛, it holds |𝑣 ∈ 𝑖 ∩ 𝑉(1) | = 1 with non vanishing probability. We write for this event 𝑖 ∶= {|𝑉 ∩ 𝑖 | = 1}. Moreover, since 𝑣 ∈ 𝑉 ∩ 0 it holds 𝐄 [deg(𝑣)] ∈ (1) by Lemma 8. Clearly, the number of active neighbours of 𝑣 is upper bounded by deg(𝑣). Thus, again it follows from a Poisson distribution that the number of active neighbours of 𝑣 is (1) with non-vanishing probability when conditioned on event 𝑖 (i.e., 𝑖 is empty except for 𝑣). The claim then follows since, given that 𝑣 has at most constant active neighbours, 𝑣 joins the independent set with non-vanishing probability. ■ To finish the proof, let 𝑋𝑖 be the indicator random variable that is 1 if sector Φ𝑖 is active and let 𝑋 = ∑𝑘−1 𝑖=0 𝑋𝑖 be the number of “active Φ-sectors in sector Ψ”. By linearity of expectation and Claim 13 in conjunction with 𝑘 ∈ Ω(log 𝑛3/2 ) it holds 𝔼 [𝑋 ] ∈ 𝜔(log 𝑛). Thus, if we can show for any 𝑋𝑖 and 𝑋𝑗 that they are independent, our desired statement follows from a Chernoff bound in conjunction with a union bound over the set of vertices 𝑉 ∩ 0 (𝑅 − 7 log log 𝑛). This is since an active Φ-sector implies that a neighbour 𝑣 ∈ 𝑁 (𝑢) joins the independent set which removes 𝑢.
18
We show that this independence holds for any two indicator random variables 𝑋𝑖 and 𝑋𝑗 w.e.h.p. Recall that 𝑋𝑖 is 1 if and only if there is a vertex 𝑣 ∈ 𝑉 ∩ 𝑖 that joins the independent set. Moreover, recall that w.e.h.p. only the area ′ = 𝑅 ⧵ 0 (𝑅 − 4 log log 𝑛 − 𝐶) contain active vertices. W.l.o.g., let sector Φ𝑖 have bisector 0. Thus, considering 𝑣 ∈ 𝑉 ∩ 𝑖 with radius 𝑟(𝑣) ≥ 𝑅 − 1, for any active neighbour 𝑤 ∈ 𝑁 (𝑣) we have 𝑟(𝑤) ≥ 𝑅 − 4 log log 𝑛 w.e.h.p., and it holds 𝜑(𝑤) ≤ 1/𝑛 + 𝜃𝑅 (𝑟(𝑣), 𝑟(𝑤)) ≤
𝜋 ⋅ 𝑒 (1−𝐶)/2 log2 𝑛 < 𝜙 w.e.h.p., 𝑛
using Lemma 4 and Remark 5 in conjunction with 𝜙 = 100 ⋅ 𝑒 −𝐶/2 log2 𝑛/𝑛 and 𝑖 spanning at most an angle of 1/𝑛. Thus, all active neighbours of the vertex 𝑣 ∈ 𝑉 ∩ 𝑖 are contained in sector Φ𝑖 w.e.h.p., yielding the independence w.e.h.p. as desired. A Chernoff bound yields 𝑋 ∈ 𝜔(log 𝑛) w.e.h.p. such that 𝑢 is removed w.e.h.p. and a union bound over all the set of vertices |𝑉 ∩ 0 (𝑅 − 7 log log 𝑛)| ∈ 𝑜(𝑛) w.e.h.p. wraps up the proof. We now have all ingredients to show that HRG-Shattering-MIS shatters a hyperbolic random graph into components of size at most poly log 𝑛. Proposition 14 (MIS Shattering). For a threshold hyperbolic random graph 𝐺, it holds with probability 1 − 𝑛−𝜔(1) that, after the second step of HRG-Shattering-MIS, the largest connected component in 𝐺[𝑉(2) ] is of size at most log(1) (𝑛). 14 The round complexity of HRG-Shattering-MIS for CONGEST is (1). Proof. The runtime (1) directly follows from the fact that one iteration of Luby’s algorithm requires (1) rounds in CONGEST. Now, consider the set of vertices 𝐼(1) , i.e., the set of vertices in the independent set after the first step of HRG-Shattering-MIS. Let 𝑘 ∶= |𝐼(1) | and consider for 𝐼(1) an ascending ordering by angular coordinates 𝑣0 , 𝑣1 , … , 𝑣𝑘−1 . For 𝑖 ∈ [𝑘], let Φ𝑖 be the sector defined by {𝑥 ∈ 𝑅 ∶ 𝜑(𝑣𝑖 ) ≤ 𝜑(𝑥) ≤ 𝜑(𝑣𝑖+1 )} where 𝑣𝑘 = 𝑣0 . Note that by Lemma 10, for 𝑖 ∈ [𝑘] it holds for any consecutive pair 𝑣𝑖 , 𝑣𝑖+1 that 𝛿𝜑 (𝑣𝑖 , 𝑣𝑖+1 ) ≤ 2 log30𝛼 (𝑛)/𝑛 w.e.h.p. and thus, the angle for any sector Φ𝑖 is at most (log30𝛼 (𝑛)/𝑛) w.e.h.p. Thus, it holds for any 𝑖 ∈ [𝑘] that 𝜇(Φ𝑖 ) ∈ (log30𝛼 (𝑛)/𝑛). Via Chernoff bound for |𝑉 ∩ Φ𝑖 | and a union bound over 𝑘 ∈ 𝑜(𝑛) sectors, we then obtain for all 𝑖 ∈ [𝑘] that |𝑉 ∩ Φ𝑖 | ∈ (log30𝛼 𝑛) w.e.h.p. Clearly, this implies that |𝑉(2) ∩ Φ𝑖 | ∈ (log30𝛼 𝑛) w.e.h.p. Thus, if we can show for any pair 𝑖 ≠ 𝑗 ∈ [𝑘] that for all pairs 𝑢 ∈ 𝑉(2) ∩ Φ𝑖 and 𝑣 ∈ 𝑉(2) ∩ Φ𝑗 it holds dh (𝑢, 𝑣) > 𝑅 w.e.h.p., this finishes the proof. To this end, fix any pair of sectors Φ𝑖 and Φ𝑗 , and w.l.o.g. let 𝑗 = 𝑖 + 1 since non-adjacent sectors are separated by an even larger angular interval. Consider any pair 𝑢 ∈ 𝑉(2) ∩ Φ𝑖 and 𝑣 ∈ 𝑉(2) ∩ Φ𝑖+1 . Using Lemma 12, it holds w.e.h.p. for both vertices 𝑢, 𝑣 ∈ 𝑉(2) that 𝑟(𝑢), 𝑟(𝑣) ≥ 𝑅 − 7 log log 𝑛. Moreover, let 𝑠 = 𝑣𝑖+1 be the vertex that lies on the intersecting ray of Φ𝑖 and Φ𝑗 . Then, by Lemma 4 in conjunction with Remark 5, it holds for the angular distance between 𝑢 and 𝑣 that 𝛿𝜑 (𝑢, 𝑣) ≥ 𝜃𝑅 (𝑟(𝑣), 𝑟(𝑠)) + 𝜃𝑅 (𝑟(𝑢), 𝑟(𝑠)) > 𝜃𝑅 (𝑟(𝑢), 𝑟(𝑣)) w.e.h.p., since 𝑢, 𝑣 ∉ 𝑁 (𝑠) and 𝑟(𝑣), 𝑟(𝑢) ∈ 𝑟(𝑠) + Ω(log log 𝑛) w.e.h.p. by Lemma 10. Thus, for all pairs 𝑢 ∈ 𝑉(2) ∩ Φ𝑖 and 𝑣 ∈ 𝑉(2) ∩ Φ𝑗 it holds dh (𝑢, 𝑣) > 𝑅 w.e.h.p.; taking a union bound over all pairs of sectors, the desired result follows: every connected component of 𝐺[𝑉(2) ] is contained in a single sector Φ𝑖 . Since each sector contains at most (log30𝛼 𝑛) vertices w.e.h.p., every connected component has poly-logarithmic size. This proves the proposition. Proof of Theorem 1 (MIS part). LOCAL: For LOCAL MIS, we obtain a shattering where each connected component is of size at most polylog 𝑛 w.e.h.p. after (1) using Proposition 14. Applying in parallel for 5/3 ̃ each component [47, Theorem 3.1], we obtain an MIS after (log log 𝑛) rounds w.e.h.p. By 𝑉(2) we refer to the set of vertices that are neither in the independent set nor have a neighbour in the independent set after step 2 of HRG-Shattering-MIS. 14
19
CONGEST: For CONGEST MIS, Proposition 14 implies that after (1) rounds each connected component induced by undecided nodes is of at most poly-logarithmic size w.e.h.p. Consequently, applying in parallel 3 ̃ for each connected component [40, Theorem 1.1], we obtain an MIS after (log log 𝑛) rounds w.e.h.p.
5.2
Efficient Maximal Matching Algorithm (MM part of Theorem 1)
In this section, we turn to our shattering algorithm, which we use to obtain a maximal matching 𝑀 ⊆ 𝐸 in polylog log 𝑛 rounds. For 𝑡 ∈ ℤ+ , let 𝑀𝑡 be the set of edges included in our matching after step 𝑡 of our algorithm HRG-Shattering-MM (see description below). We denote by 𝑉(𝑡) the set of unmatched vertices after step 𝑡: a vertex is unmatched if it has at least one incident edge that can be included without violating the matching condition after step 𝑡 of HRG-Shattering-MM, i.e., 𝑉(𝑡) ∶= {𝑢 ∈ 𝑉 ∶ ∃𝑣 ∈ 𝑁 (𝑢) such that 𝐸(𝑣)∩𝑀𝑡 = ∅ and 𝐸(𝑢) ∩ 𝑀𝑡 = ∅}. The following is a brief description of our algorithm, which we refer to as HRGShattering-MM: • Step 1 (Inner disk removal): Activate all vertices of the set 𝑈(1) ∶= {𝑣 ∈ 𝑉(1) ∶ deg(𝑣) ≤ ⌈log3/2 (𝑛)⌉}. In parallel, each active vertex 𝑢 ∈ 𝑈(1) marks one incident edge uniformly at random. Then, in parallel, each vertex 𝑢 ∈ 𝑉 chooses a marked edge {𝑢, 𝑣} ∈ 𝐸 uniform at random from its incident marked edges, and we add {𝑢, 𝑣} to the matching 𝑀. • Step 2 (Separating the outer disk): Activate all vertices of the set 𝑈(2) ∶= {𝑣 ∈ 𝑉 ∶ 4
log (𝑛) 4 ⌊ 1000 ⌋ ≤ deg(𝑣) ≤ ⌈1000 log (𝑛)⌉}. In parallel, each vertex 𝑢 ∈ 𝑈(2) draws a random ID, and we add 𝑢 to the set 𝑆 if 𝑢 has the largest ID among its neighbours in 𝑈(2) .
If LOCAL: In parallel, each vertex 𝑠 ∈ 𝑆 collects the adjacency matrix of the induced subgraph 𝐺𝑠 ∶= 𝐺[𝑁2 (𝑠) ∩ 𝑉(1) ]. a In parallel, each vertex 𝑠 ∈ 𝑆 computes a maximal matching 𝑀(𝑠) ⊆ 𝐸(𝐺𝑠 ) and we add 𝑀(𝑠) to the matching 𝑀. If CONGEST: In parallel, each vertex 𝑠 ∈ 𝑆 activates the set of vertices 𝑈 (𝑠) ∶= 𝑁2 (𝑠) ∩ 𝑉(1) . In parallel, for each 𝑠 ∈ 𝑆, compute a maximal matching 𝑀(𝑠) for 𝐺[𝑈 (𝑠)] via [41, Theorem 1.2] and we add 𝑀(𝑠) to the matching 𝑀. a
We write 𝑁2 (𝑢) for the two-hop neighbourhood 𝑁2 (𝑢) ∶= {𝑣 ∈ 𝑉 ∶ 𝑑𝐺 (𝑢, 𝑣) ≤ 2}.
The rest of this section is dedicated to proving that HRG-Shattering-MM shatters an HRG into polylogarithmic connected components; see also Proposition 17. We start by showing in Lemma 15 that after step 1, in constant rounds, all vertices of the inner disk 0 (𝑅 − 6 log log 𝑛) are matched w.e.h.p. We then continue by analysing step 2 and the properties it yields for set 𝑆 in Lemma 16. Lemma 15 (Step 1 of HRG-Shattering-MM). Let 𝐺 be a threshold hyperbolic random graph. Then in CONGEST after step 1 of HRG-Shattering-MM, the set of vertices 𝑉 ∩ 0 (𝑅 − 6 log log 𝑛) is matched in constant rounds w.e.h.p. Proof. In the step 1 of HRG-Shattering-MM, we first activate all vertices with degree at most ⌈log3/2 𝑛⌉. In parallel, all active vertices mark one incident edge uniformly at random. Fix a vertex 𝑢 ∈ 𝑉 ∩ 0 (𝑅 − 6 log log 𝑛) and let 𝑋𝑢 be the random variable with which we count the number of marked edges incident to 𝑢. Note that if we can show that 𝑋𝑢 ≥ 1 for all 𝑢 ∈ 𝑉 ∩0 (𝑅−6 log log 𝑛) with probability 1 − 𝑛−𝜔(1) , then this proves the claim since then any vertex in 𝑢 ∈ 𝑉 ∩ 0 (𝑅 − 6 log log 𝑛) can simply select one of the marked edges so that 𝑢 is matched. To show this, consider the set of vertices which form an 𝑒 edge with 𝑢 such that 𝑒 is potentially marked. Let us write 𝑁 ′ (𝑢) ∶= 𝑁 (𝑢) ∩ {𝑣 ∈ 𝑉 ∶ deg(𝑣) ≤ ⌈log3/2 𝑛⌉} for this set and note that for 𝑣 ∈ 𝑁 ′ (𝑢), the edge
20
{𝑢, 𝑣} is marked with probability 1/ deg(𝑣), as 𝑣 samples the edge uniform at random among its neighbours. Hence, it holds ℙ (𝑋𝑢 = 0) = ∏ (1 − 1/ deg(𝑣)).
(5)
𝑣∈𝑁 ′ (𝑢)
In the following, we lower bound |𝑁 ′ (𝑢)|. Since for any vertex 𝑣 ∈ 𝑉 ∩ 0 , it holds via Lemma 7 that 𝐄 [deg(𝑣)] ∈ (1), such that a Chernoff-bound with a subsequent union bound over at most (𝑛) vertices yields that deg(𝑣) ≤ log3/2 𝑛 and all vertices in layer 0 are active w.e.h.p. and participate in our marking process. Using this bound and that 𝑟(𝑢) ≤ 𝑅 − 6 log log 𝑛 in conjunction with the fact that 𝜃𝑅 (⋅, ⋅) is a monotonic decreasing function in both arguments (Remark 5), it holds via law of total expectation that 𝐄 [|𝑁 ′ (𝑢)|] ≥ (1 − 𝑜(1))𝑛 ⋅ 𝜃𝑅 (𝑅 − 6 log log 𝑛, 𝑅) ⋅ 𝜇(0 ) ∈ Ω(log3 (𝑛)), where in the last step we used Equation (3) and Lemma 4. Another combination of Chernoff and union bounds reveals that for any 𝑢 ∈ 𝑉 ∩0 (𝑅 −6 log log 𝑛) it holds |𝑁 ′ (𝑢)| ∈ Ω(log3 𝑛) with probability 1−𝑛−𝜔(1) . Let be the event that for all 𝑣 ∈ 𝑉 ∩ 0 it holds deg(𝑣) ∈ (log3/2 𝑛) and that for all 𝑢 ∈ 𝑉 ∩ 0 (𝑅 − 6 log log 𝑛) it holds |𝑁 ′ (𝑢)| ∈ Ω(log3 (𝑛)). By previous discussion it follows via union bound that 3/2 ℙ () ∈ 1 − 𝑛−𝜔(1) . Note that for our fixed 𝑢 ∈ 𝑉 ∩ 0 (𝑅 − 6 log log 𝑛) it holds ℙ (𝑋𝑢 = 0|) ∈ 𝑒 −Ω(log 𝑛) by Equation (5). Hence, we obtain using a union bound ℙ (∄𝑢 ∈ 𝑉 ∩ 0 (𝑅 − 6 log log 𝑛) ∶ 𝑋𝑢 = 0) ≥ ℙ () ⋅ (1 −
∑
ℙ (𝑋𝑢 = 0|)) ∈ 1 − 𝑛−𝜔(1) ,
𝑢∈𝑉 ∩0 (𝑅−6 log log 𝑛)
since |𝑉 ∩ 0 (𝑅 − 6 log log 𝑛)| ∈ (𝑛) w.e.h.p. That is, we showed that 𝑋𝑢 ≥ 1 for all 𝑢 ∈ 𝑉 ∩ 0 (𝑅 − 6 log log 𝑛) with probability 1 − 𝑛−𝜔(1) as desired. This finishes the proofs since the desired runtime (1) is immediate. The following is an analogue statement of Lemma 10. Additionally, we show that any pair of vertices in the set 𝑆 has a minimum angular distance (Item 3). Lemma 16 (Step 2 of HRG-Shattering-MM). Let 𝐺 be a threshold hyperbolic random graph and consider the set of vertices 𝑆 in step 2 of HRG-Shattering-MM. Moreover, let 𝑐(𝐶, 𝛼) be a constant large enough and consider annulus ≔ 0 (𝑅 − 8 log log 𝑛 + 𝑐(𝐶, 𝛼)) ⧵ 0 (𝑅 − 8 log log 𝑛 − 𝑐(𝐶, 𝛼)). Then the following holds for 𝑆 with probability 1 − 𝑛−𝜔(1) : 1. All vertices contained in the set 𝑆 in the second step of HRG-Shattering-MM are in ; 𝑆 ⊆ 𝑈(2) ⊆ 𝑉 ∩ . 30𝛼
2. In any sector with angle log 𝑛 𝑛 there exists a vertex 𝑣 such that 𝑣 ∈ 𝑆. 3. For any pair of vertices 𝑢, 𝑣 ∈ 𝑆 it holds that the angular distance is 𝛿𝜑 (𝑢, 𝑣) ∈ Ω(log8 𝑛/𝑛) and {𝑢, 𝑣} ∉ 𝐸. Proof. Items 1 and 2 follow directly from Lemma 10, since step 2 of HRG-Shattering-MM activates exactly the same set of vertices as step 1 of HRG-Shattering-MM and applies the same local selection rule. Therefore, the arguments used in the proof of Lemma 10 carry over verbatim: the set 𝑆 is equivalent to 𝐼(1) . To show that Item 3 holds, suppose for contradiction that {𝑢, 𝑣} ∈ 𝐸. Since both 𝑢 and 𝑣 belong to 𝑆, each has the largest ID in its closed neighbourhood. However, as 𝑢 ∈ 𝑁 (𝑣) and 𝑣 ∈ 𝑁 (𝑢), at most one of the two vertices can have the largest ID among the vertices of its closed neighbourhood, a contradiction. Hence 𝑢 and 𝑣 are not adjacent. Then, using that 𝑟(𝑢), 𝑟(𝑣) ∈ 𝑅 − 8 log log 𝑛 + (1) w.e.h.p. by Item 1, it holds w.e.h.p. using Lemma 4 in conjunction with Remark 5 that 𝛿𝜑 (𝑢, 𝑣) > 𝜃𝑅 (𝑟(𝑢), 𝑟(𝑣)) ∈ Ω(log8 𝑛/𝑛). Hence the claimed lower bound on the angular distance holds for every pair of vertices in 𝑆 whenever the event of Item 1 occurs. Since this event holds with probability 1 − 𝑛−𝜔(1) , the proof is complete. 21
We now show that after the second step of HRG-Shattering-MM, a hyperbolic random graph is shattered into components of size at most poly log 𝑛 for maximal matching. Proposition 17 (MM Shattering). For a threshold hyperbolic random graph 𝐺, it holds with probability 1 − 𝑛−𝜔(1) that, after the second step of HRG-Shattering-MM, the largest connected component in 𝐺[𝑉(2) ] is of size at most log(1) (𝑛). 15 The round complexity of HRG-Shattering-MM is (1) for LOCAL and (log3 log 𝑛) for CONGEST. Proof. LOCAL: We start by proving the LOCAL part. Consider any pair of vertices 𝑠, 𝑠 ′ ∈ 𝑆 in the second step of HRG-Shattering-MM. We show for any of the two sets of vertices 𝑁2 (𝑠) ∩ 𝑉(1) =∶ 𝑈 (𝑠) and 𝑁2 (𝑠 ′ ) ∩ 𝑉(1) =∶ 𝑈 (𝑠 ′ ), that for any pair 𝑣 ∈ 𝑈 (𝑠) and 𝑣′ ∈ 𝑈 (𝑠 ′ ) it holds {𝑣, 𝑣′ } ∉ 𝐸 w.e.h.p. This ensures that for any pair 𝑠, 𝑠 ′ ∈ 𝑆, there are no conflicts when 𝑠 and 𝑠 ′ compute in parallel 𝑀(𝑠) and 𝑀(𝑠 ′ ) in the LOCAL computation of the second step in HRG-Shattering-MM. To see this, note first that {𝑠, 𝑠 ′ } ∉ 𝐸 w.e.h.p. holds immediately by Lemma 16. Thus, it suffices to show that for any 𝑣 ∈ 𝑈 (𝑠) and 𝑣′ ∈ 𝑈 (𝑠 ′ ) ⧵ {𝑠 ′ } that {𝑣, 𝑣′ } ∉ 𝐸 w.e.h.p. Now, recall that by Lemma 15 it holds w.e.h.p. for any 𝑣, 𝑢 ∈ 𝑉(1) that 𝑟(𝑣), 𝑟(𝑢) ≥ 𝑅 − 6 log log 𝑛. Moreover, by Lemma 16 it holds for some constant 𝑐 that, 𝑟(𝑠) ≥ 𝑅 − 8 log log 𝑛 − 𝑐 w.e.h.p. Thus, for any vertices 𝑣, 𝑢 ∈ 𝑈 (𝑠) it holds w.e.h.p. that 𝛿𝜑 (𝑠, 𝑣) ≤ 𝜃𝑅 (𝑟(𝑠), 𝑟(𝑢)) + 𝜃𝑅 (𝑟(𝑣), 𝑟(𝑢)) < Θ(1) log7 𝑛/𝑛,
(6)
by Lemma 4. Moreover, using Lemma 16 Item 3, it holds w.e.h.p. for the pair 𝑠, 𝑠 ′ ∈ 𝑆 that 𝛿𝜑 (𝑠, 𝑠 ′ ) ∈ Ω(log8 𝑛/𝑛).
(7)
Consequently, we obtain w.e.h.p. for any pair 𝑣 ∈ 𝑈 (𝑠) and 𝑣′ ∈ 𝑈 (𝑠 ′ ) ⧵ {𝑠 ′ } by combining Equation (6) and Equation (7) that 𝛿𝜑 (𝑣, 𝑣′ ) = 𝛿𝜑 (𝑠, 𝑠 ′ ) − 𝛿𝜑 (𝑠, 𝑣) − 𝛿𝜑 (𝑠 ′ , 𝑣′ ) ∈ Ω(log8 𝑛/𝑛) ∈ 𝜔(𝜃𝑅 (𝑟(𝑣), 𝑟(𝑣′ ))) w.e.h.p.,
(8)
using Lemma 4 in conjunction with 𝑟(𝑣′ ) ≥ 𝑅 −6 log log 𝑛 w.e.h.p. by Lemma 15 and 𝑟(𝑣) ≥ 𝑅 −8 log log 𝑛−𝑐 w.e.h.p. by Lemma 16. It follows via Equation (8) that no two-hop neighbourhoods 𝑈 (𝑠 ′ ) ∩ 𝑈 (𝑠) share any edge w.e.h.p. as desired, which, by union bound then also holds for any pair 𝑠, 𝑠 ′ ∈ 𝑆 w.e.h.p. We conclude that w.e.h.p. there are no conflicts for any matchings 𝑀(𝑠) and 𝑀(𝑠 ′ ) and it is left to show that (a) we obtain the desired shattering and (b) the computation in HRG-Shattering-MM requires (1) rounds of the LOCAL model. (a) The shattering property follows by the same argument as in the proof of Proposition 14 after replacing the set 𝐼(1) with 𝑆. Indeed, by Lemma 15, every vertex in 𝑉 ∩ 0 (𝑅 − 6 log log 𝑛) is already matched after Step 1 of HRG-Shattering-MM w.e.h.p. Moreover, for every 𝑠 ∈ 𝑆, the algorithm computes a maximal matching on the induced subgraph 𝐺[𝑈 (𝑠)], where 𝑈 (𝑠) = 𝑁2 (𝑠) ∩ 𝑉(1) . Since 𝑁 (𝑠) ⊆ 𝑈 (𝑠), every neighbour of 𝑠 is either matched itself or matched to another vertex in 𝑈 (𝑠). Consequently, 𝑁 (𝑠) ∩ 𝑉(2) = ∅ for every 𝑠 ∈ 𝑆. Hence every unmatched vertex lies in the same outer annulus as in Proposition 14, and the remainder of the shattering argument applies verbatim. (b) By Lemma 15 step 1 of HRG-Shattering-MM requires constant rounds. The communication in step 2 of HRG-Shattering-MM also requires constant rounds so that active vertices are informed if they participate in the set 𝑆. Moreover, each vertex 𝑠 ∈ 𝑆 in parallel collects its two-hop neighbourhood of unmatched vertices in constant rounds and then, in further constant rounds, informs the vertices of the set 𝑈 (𝑠) about the matching 𝑀(𝑠) ⊆ 𝐸(𝐺2 ). Hence, at most (1) communication rounds are required. CONGEST: The correctness of the CONGEST part follows from the same arguments as for the LOCAL model. For the round complexity, we consider the following: first, for all 𝑠 ∈ 𝑆, in parallel, each induced 15
By 𝑉(2) we refer to the set of unmatched vertices after step 2 of HRG-Shattering-MM.
22
subgraph 𝐺(𝑈 (𝑠)) can be informed by 𝑠 to be active within 2 rounds in CONGEST. Next, fix a vertex 𝑠 ∈ 𝑆. Since there exists a constant 𝑐 such that 𝑟(𝑠) ≥ 𝑅 − 8 log log 𝑛 − 𝑐 by Lemma 16, it follows by Lemma 7 that 𝐄 [deg(𝑠)] ∈ Θ(log4 𝑛). Thus, by a Chernoff and union bound it holds for any 𝑠 ∈ 𝑆 that deg(𝑠) ∈ Θ(log4 𝑛) w.e.h.p. Moreover, it holds for any 𝑣 ∈ 𝑉(1) that 𝑟(𝑣) ≥ 𝑅 − 6 log log 𝑛 w.e.h.p. by Lemma 15. Subsequently, using Lemma 7 with a Chernoff and a union bound, we have for each 𝑣 ∈ 𝑉(1) that deg(𝑣) ∈ (log3 𝑛). Hence, for all 𝑈 (𝑠) it holds |𝑈 (𝑠)| ∈ (log7 𝑛) w.e.h.p. Then, recall that for any pair of vertices 𝑠, 𝑠 ′ ∈ 𝑆 we showed that there are no edges between 𝑈 (𝑠) and 𝑈 (𝑠 ′ ) w.e.h.p. Thus, using in parallel for each 𝑠 ∈ 𝑆 on the induced subgraph 𝐺[𝑈 (𝑠)] [41, Theorem 1.2], we obtain a maximal matching for all such induced subgraphs 𝐺[𝑈 (𝑠)] in (log3 log 𝑛) rounds without conflicts w.e.h.p. Proof of Theorem 1 (MM part). LOCAL: For MM, we obtain a shattering where each connected component is of size at most polylog 𝑛 w.e.h.p. after (1) using Proposition 17. Applying in parallel for each component 5/3 ̃ [47, Theorem 3.1], yields (log log 𝑛) rounds w.e.h.p.. CONGEST: The shattering into poly-logarithmic components in (log3 log 𝑛) rounds follows similarly from Proposition 17 w.e.h.p. Consequently, by applying in parallel for each connected component the maximal matching algorithm from [41, Theorem 1.2], resulting in a round complexity of (log3 log 𝑛).
6
Lower Bounds for MIS/MM & Substructures in HRGs (Theorem 2)
In this section, we prove our lower bounds for MIS and MM on HRGs. We show the following statement. Theorem 2 (Lower bounds for MIS and MM). Asymptotically almost surely,16 the randomised complexity 17 for computing an MIS or an MM for the giant component of a hyperbolic random graph is Ω ( logloglogloglog𝑛 𝑛 ) rounds in the LOCAL model. To accomplish our lower bounds, we first establish that there exist many 𝑑-ary trees in HRGs with relatively large degree 𝑑 and height ℎ (Theorem 18 in Section 6.1). We then use these substructures to obtain our lower bounds of Theorem 2 in Section 6.2.
6.1
On 𝑑-ary Trees in Hyperbolic Random Graphs (Proof of Theorem 18)
√ In this section, we prove the existence of (polynomially many) 𝑑-ary trees with 𝑛′ ≈ log 𝑛 vertices, of any degree 𝑑 ≤ 𝑛′ growing in 𝑛 and height ℎ ≈ log(𝑛′ )/ log(𝑑) in an HRG. Specifically, we show the following. Theorem 18 (𝑑-ary √ trees in hyperbolic random graphs). Let 𝐺 be a threshold hyperbolic random graph and let 𝑚 ∶= 𝑚(𝑛) ≤ log 𝑛 be a function growing in 𝑛. Then, a.a.s., there exist 𝑛Ω(1) disjoint sectors Φ𝑖 such that √ for 𝑇𝑖 ∶= 𝐺[𝑉 ∩ Φ𝑖 ], 𝑇𝑖 is a balanced 𝑑-ary tree 18 with 𝑛′ ∈ Ω( log 𝑛) vertices, degree 𝑑 ∈ Ω(𝑚) and height ℎ ∈ Ω(log𝑚 log 𝑛′ ). In particular, for each such tree 𝑇𝑖 with root 𝑢,19 there exists a vertex 𝑣 ∈ 𝑉 (𝐻 ) in the giant component 𝐻 of 𝐺 such that {𝑢, 𝑣} ∈ 𝐸(𝐻 ) is the unique edge between 𝑇𝑖 and 𝐺 ⧵ 𝑉 (𝑇𝑖 ). The parameter 𝑚 of Theorem 18 can be tuned √ to adjust the degree 𝑑 and also implicitly the √ height ℎ for a desired 𝑑-ary tree. For example, setting 𝑚 = log 𝑛 gives a "star graph" with degree Ω( log 𝑛) and height 1. For our purposes, we will set 𝑚 = log log 𝑛 later on in Section 6.2. To prove Theorem 18, we partition the hyperbolic disk into 𝑘-many sectors where 𝑘 is polynomial in 𝑛. For polynomially many such sectors, we reveal that they contain a 𝑑-ary tree with the parameters 𝑛′ , 𝑑, With probability 1 − 𝑜(1) over the draw of the hyperbolic random graph 𝐺. There exists an algorithm where the error probability is at most 1/𝑛𝑐 for some constant 𝑐 > 0. 18 A rooted tree where each vertex, except for the leaves, has 𝑑 children. 19 The root node 𝑢 is the vertex with graph distance 𝑑𝐺 (𝑢, 𝑤) = ℎ to each leaf 𝑤 ∈ 𝑉 (𝑇𝑖 ). 16 17
23
ℓ1 ℓ0
u
ϕ ℓ1
√ 2 log m Bu,1 ...
v0
...
v1
2i ·
u
log m
ℓ0
√
ℓi
ϕ ℓ1
Bu,0 ϕ ℓ1
ϕ ℓ1
ℓi
(a)
(b)
ϕℓ ϕℓ ϕℓ i i i
ϕℓ ϕℓ ϕℓ i i i
Figure 8: Sketch of our tree construction with degree 𝑑 = 2. (a) Layer 𝓁0 contains the root vertex 𝑢 which has children 𝑣0 and 𝑣1 in layer 𝓁1 . (b) Illustration of the boxes 𝑢,0 and 𝑢,1 of 𝑢. A sector with angle 𝜙 is nice if the hatched area is empty and each box contains exactly one vertex.
and ℎ. The rough idea of how we find this structure goes as follows. We fix a sector Φ with angle 𝜙 and aim to find a root node 𝑢 located in layer 𝓁0 intersecting sector Φ (where 𝓁0 ≈ log log 𝑛; see also Figure 3a). Next we consider 𝑑 equally sized boxes in a layer 𝓁1 with 𝓁1 < 𝓁0 , where each box has width 𝜙𝓁1 and height 1. We choose these parameters such that they fulfil the following property: if a vertex 𝑣 lies in a box in layer 𝓁1 , then it is adjacent to the root node 𝑢 and 𝑣 has distance at least 𝑅 to any point in layer 𝓁1 if the angular distance is larger than 𝜙𝓁1 (see Figure 8 for a visualisation). For each box in layer 𝓁1 , we find exactly one vertex such that the degree of 𝑢 is 𝑑 (𝑢 has 𝑑 children). Moreover, for any pair of boxes in 𝓁1 , by our parameter choice 𝜙𝓁1 , any pair of “children” of 𝑢 has distance at least 𝑅 and thus does not share an edge. Then we recursively build the tree by “assigning” any vertex 𝑣 in layer 𝓁1 a set of 𝑑 boxes in a layer 𝓁2 , such that each box contains a vertex. We repeat this for each vertex in the boxes in 𝓁2 , obtaining boxes in layer 𝓁3 and so on until we have boxes in layer 𝓁ℎ , yielding a tree of height ℎ. To prove that this indeed yields the sought-after 𝑑-ary tree structure, we first show that the graph resulting from the geometric embedding, given that we have exactly one vertex in each assigned box while the rest of the sector is empty, indeed results in a 𝑑-ary tree Lemma 20. Afterwards, we show that this event occurs with a small but not polynomial-decaying probability (Lemma 21). This, in conjunction with the event that all vertices used to build the tree have no further neighbours, occurs for a fixed, slightly larger sector with probability 𝑛−𝑜(1) . Since we have polynomial many sectors, there are, in expectation, 𝑛Ω(1) many sectors where the desired 𝑑-ary tree occurs. This, the bridge of the root to the giant component and the concentration result are addressed in the proof of Theorem 18. To make this formal, we first define for any vertex 𝑢 the boxes where we wish to find exactly one vertex each, representing the children of 𝑢 (see also Figure 8b for a sketch of the definition). √ Definition 19 (Boxes). Let 𝑅 be a hyperbolic disk with radius 𝑅 = 2 log 𝑛 + 𝐶 and 10000 ≤ 𝑚 ≤ log 𝑛. Moreover, define • (root layer) 𝓁0 ∶= ⌈log log 𝑛⌉, • (layer of tree level 𝑖) 𝓁𝑖 ∶= 𝓁0 − ⌈2𝑖 ⋅ log 𝑚⌉, 𝓁𝑖 +𝐶/2
• (box width in tree level 𝑖) 𝜙𝓁𝑖 ∶= 100𝑒𝑛
,
• (height of tree) ℎ ∶= ⌊log log 𝑛/(2 log 𝑚)⌋ and • (degree in tree) 𝑑 ∶= ⌊𝑚/10000⌋.
24
Consider any 𝑖 ∈ [ℎ] and a vertex 𝑢 ∈ 𝑉𝓁𝑖 . Then for every 𝑗 ∈ [𝑑], the 𝑗-th box of vertex 𝑢 is defined by the set of points { } 𝑒 𝓁𝑖 +𝐶/2 𝑒 𝓁𝑖 +𝐶/2 𝑢,𝑗 ∶= 𝑥 ∈ 𝓁𝑖+1 ∶ 𝜑(𝑢) + − (2𝑗 + 1) ⋅ 𝜙𝓁𝑖+1 ≤ 𝜑(𝑥) ≤ 𝜑(𝑢) + − 2𝑗 ⋅ 𝜙𝓁𝑖+1 . 10𝑛 ⋅ 𝑚 10𝑛 ⋅ 𝑚 Before embarking on the proof of our desired geometric properties, let us give some further intuition 𝑒 𝓁𝑖 for our choice of parameters. Placing the "first" box of 𝑢 at angular distance ≈ 𝑛⋅𝑚 ensures by Lemma 4 that 𝑢 "barely" has an edge to a vertex in this box. Then, "moving" the subsequent boxes of 𝑢 by angular 𝓁𝑖 difference ≈ 𝑒𝑛 ensures that the hyperbolic distance between 𝑢 and any vertex contained in one of its boxes is at most 𝑅 as well. Moreover, by “skipping” every second box and by our choice 𝜙𝓁𝑖 we achieve that any pair of vertices in two different boxes on the same level does not have an edge. The multiplicative constant factors of 𝜙𝓁𝑖 and 𝑑 are chosen for convenience so that these properties are fulfilled. This gives us the desired property of a tree that 𝑢 is a “parent” to all vertices in its “own” boxes 𝑢,𝑗 while vertices that lie in boxes of 𝑢 are the “children” of 𝑢 and do not have an edge among each other. To formalise our construction, we consider Algorithm 1, which defines a nice sector. We shall prove that the construction indeed gives a 𝑑-ary tree in a sector Φ 20 (see also Figure 8). Algorithm 1 Nice sector Φ log 𝑛 Require: Sector Φ ⊆ 𝑅 with bisector 𝜑 and angular width 𝜙 = 𝑛5 log 𝑚. ′ ′ 1: assert |𝑉𝓁0 ∩ Φ | = 1 where Φ = {Φ ∈ 𝑅 ∶ 𝜑 − 𝜙/5 ≤ 𝜑(𝑥) ≤ 𝜑 + 𝜙/5} //Check for root node 2: 𝑈 ← {𝑉𝓁0 ∩ Φ′ } //Add root node 3: 𝑈𝑎𝑙𝑙 ← ∅ //All vertices of the tree 4: for 𝑖 = 0 to ℎ − 1 do //Iterate through the levels of the tree 5: 𝑈all ← 𝑈all ∪ 𝑈 //Update the set of all vertices in 6: 𝑈next ← ∅ //Next level of the tree 7: for each 𝑣 ∈ 𝑈 do //Iterate through the vertices of a level 8: for 𝑗 = 0 to 𝑑 − 1 do //Iterate through the boxes of a vertex 9: assert |𝑉 ∩ 𝑣,𝑗 | = 1 //Check that there is exactly one vertex in each box of 𝑣 10: 𝑈next ← 𝑈next ∪ (𝑉 ∩ 𝑣,𝑗 ) //Add vertex of the box 11: end for 12: end for 13: 𝑈 ← 𝑈next 14: end for 15: assert (𝑉 ∩ Φ) ⧵ 𝑈all = ∅ //Check if sector is empty except for the tree
5 log 𝑛 Lemma 20 (𝑑-ary tree geometry). Let 𝑚 ∈ 𝜔(1) and Φ ⊆ 𝑅 be a sector with angular width 𝜙 = 𝑛⋅log 𝑚 . Then, if Φ is nice according to Algorithm 1, the induced sub-graph 𝐺[𝑉 ∩ Φ] is a 𝑑-ary tree with degree 𝑑 ∈ Ω(𝑚), √ height ℎ ∈ Ω(log log 𝑛/ log 𝑚) and 𝑛′ ∈ Ω( log 𝑛) vertices.
Proof. We show the desired statement as follows: first, we show that all boxes are within the sector Φ. Then, we establish for any vertex 𝑢 ∈ 𝑉 ∩ Φ that any point in a box of 𝑢 has distance at most 𝑅 to 𝑢. Note that this already suffices to prove that all desired edges for a tree exist such that every vertex has 𝑑 children (except for the leaves of the tree). Afterwards, we show that any vertex 𝑢 has a distance larger than 𝑅 to any point of a box that is not the box of 𝑢 according to Definition 19. Since the rest of the sector is empty, this ensures that we also have all non-edges. Using that we have ℎ layers through which we iterate in line 4 20
The value for 𝑚 in Algorithm 1 is here the same as the parameter 𝑚 in Theorem 18.
25
of Algorithm 1, this yields a tree of depth ℎ where each vertex has 𝑑 children because of the loop in line 8. For the desired properties√of our tree, 𝑑 and ℎ follow directly from Definition 19 and the number of vertices is given by 𝑛′ ≥ 𝑑 ℎ ∈ Ω( log 𝑛). All boxes are contained in the sector. By Definition 19, a vertex 𝑢 in layer 𝓁𝑖 has boxes with angular 𝓁𝑖 +𝐶/2 distance at most 𝑒10𝑛⋅𝑚 since 𝑑 ⋅ 𝜙𝓁𝑖+1 ≤ exp(𝐶/2 + 𝓁𝑖 )/(100𝑛 ⋅ 𝑚). Hence, the maximal angle that is spanned by any pair of points 𝑥, 𝑦 in two different boxes is at most ℎ−1
𝑒 𝓁0 𝑒 𝓁𝑖 +𝐶/2 ≤ Θ(1) ⋅ ∈ 𝑜(𝜙), 10𝑛 ⋅ 𝑚 𝑛⋅𝑚 𝑖=0
𝛿𝜑 (𝑥, 𝑦) ≤ ∑
where we used that 𝓁𝑖 = ⌈log log 𝑛⌉ − ⌈2𝑖 ⋅ log 𝑚⌉, 𝜙 = 5 ⋅ log 𝑛/(𝑛 ⋅ log 𝑚) and 𝑚 ∈ 𝜔(1) in the last step. Thus, all boxes are contained in sector Φ with angular width 𝜙. Edges. Recall that 𝑅 = 2 log 𝑛 + 𝐶. To show that all desired edges exist, consider any vertex 𝑢 ∈ 𝑉𝓁𝑖 . Note that any box 𝑢,𝑗 is in layer 𝓁𝑖+1 . Hence, using that 𝑑 ⋅ 𝜙𝓁𝑖+1 ≤ exp(𝐶/2 + 𝓁𝑖 )/(100𝑛 ⋅ 𝑚) it follows by the definition of 𝑢,𝑗 that the angular distance between 𝑢 and 𝑥 ∈ 𝑢,𝑗 is at most 𝛿𝜑 (𝑢, 𝑥) ≤
𝑒 𝓁𝑖 +𝐶/2 ≤ 𝑒 (𝑅−𝑟(𝑢)−𝑟(𝑥))/2 ≤ 𝜃𝑅 (𝑟(𝑢), 𝑟(𝑥)), 10𝑛 ⋅ 𝑚
using that 𝑟(𝑢) ≤ 𝑅 − 𝓁𝑖 , 𝑟(𝑣) ≤ 𝑅 − 𝓁𝑖 + 2 log 𝑚 + 1 and Lemma 4 in conjunction with 𝜃𝑅 (𝑟(𝑢), 𝑟(𝑥)) being monotonically decreasing by Remark 5. Thus, all desired edges exist. Non-edges. Next, let 𝑢 ∈ 𝑉𝓁𝑖 and 𝑣 ∈ 𝑉𝓁𝑗 . W.l.o.g. let 𝓁𝑖 ≥ 𝓁𝑗 . Then, if 𝑣 is not in a box of 𝑢, we have to show that 𝑑ℎ (𝑢, 𝑣) > 𝑅 to finish the proof. To this end, we distinguish two cases. Case 1 [Vertex 𝑢 is an ancestor of 𝑣]: Let 𝑤 be the vertex that is in the (𝑑 − 1)-th box of 𝑢, i.e., 𝑢,𝑑−1 and note that, since 𝑑 ⋅ 𝜙𝓁𝑖+1 ≤ exp(𝐶/2 + 𝓁𝑖 )/(100𝑛 ⋅ 𝑚), 𝛿𝜑 (𝑢, 𝑣) ≥ 𝛿𝜑 (𝑢, 𝑤) > (1/10 − 1/100)
𝑒 𝐶/2+𝓁𝑖 , 𝑚⋅𝑛
(9)
using the definition for the box 𝑢,𝑗 (Definition 19). On the other hand, using that 𝑢 is an ancestor of 𝑣 but 𝑣 is not in a box of 𝑢, we observe that 𝓁𝑖 ≥ 𝓁𝑗 + 4 log 𝑚. Thus, we obtain 𝜃𝑅 (𝑟(𝑢), 𝑟(𝑣)) ≤ Θ(1)
𝑒 𝐶/2+𝓁𝑖 , 𝑚2 ⋅ 𝑛
(10)
by Lemma 4. Hence, by combining Equation (9) and Equation (10) we have by 𝑚 ∈ 𝜔(1) 𝛿𝜑 (𝑢, 𝑣) > Θ(1)
𝑒 𝐶/2+𝓁𝑖 𝑒 𝐶/2+𝓁𝑖 > Θ(1) 2 ∈ 𝜔(𝜃𝑅 (𝑟(𝑢), 𝑟(𝑣))), 𝑚⋅𝑛 𝑚 ⋅𝑛
and there is no edge between 𝑢 and 𝑣 by Lemma 4. This concludes our first case. Case 2 [Vertex 𝑢 is not an ancestor of 𝑣]: Let 𝑤 be the vertex that is the lowest common ancestor of 𝑢 and 𝑣. First, consider the case that 𝑤 is the parent of both 𝑢 and 𝑣. In this case, 𝑤 ∈ 𝑉 ∩ 𝓁𝑖−1 and as such, the minimal angular distance between 𝑢 and 𝑣, by Definition 19, is 𝛿𝜑 (𝑢, 𝑣) ≥ 𝜙𝓁𝑖 =
100𝑒 𝓁𝑖 +𝐶/2 > 𝜃𝑅 (𝑟(𝑢), 𝑟(𝑣)), 𝑛 26
where we applied Lemma 4 and 𝑟(𝑢), 𝑟(𝑣) ≥ 𝑅 − 𝓁𝑖 − 2. Hence, there is no edge between 𝑢 and 𝑣. To finalise the case, consider now that 𝑢 and 𝑣 do not share the same parent such that 𝓁𝑖 > 𝓁𝑗 . Let the lowest common ancestor 𝑤 be in layer 𝓁𝑘 and consider the two children 𝑢′ and 𝑣′ of 𝑤, (where both 𝑢′ and 𝑣′ are in layer 𝓁𝑘+1 ), that are ancestors of 𝑢 and 𝑣 respectively (possibly 𝑢′ = 𝑢). Note that by 𝑑 ⋅ 𝜙𝓁𝑖+1 ≤ exp(𝐶/2 + 𝓁𝑖 )/(100𝑛 ⋅ 𝑚) and using Definition 19 it follows that 𝛿𝜑 (𝑢′ , 𝑣′ ) ≥ 𝜙𝓁𝑘+1 =
100 ⋅ 𝑒 𝓁𝑘 +𝐶/2 . 𝑚2 ⋅ 𝑛
𝑒 Then, using that 𝜑(𝑢) ≥ 𝜑(𝑢′ ) and that 𝜑(𝑣) ≤ 𝜑(𝑣′ ) + ∑𝑘−1 𝑡=𝑗
(11)
(𝐶+𝓁𝑡 +𝓁𝑡−1 )/2
𝑛
by Definition 19, it follows
𝑘−1
𝑒 (𝐶+𝓁𝑡 +𝓁𝑡−1 )/2 . 𝑛 𝑡=𝑗 ⏟⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏟⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏟
𝛿𝜑 (𝑢, 𝑣) ≥ 𝛿𝜑 (𝑢′ , 𝑣′ ) − ∑
(12)
𝓁
( 𝑚𝑒 3𝑘𝑛 )
Plugging Equation (11) into Equation (12) and upper bounding the sum of exponentials by (exp (𝓁𝑘 − 3 log 𝑚)/𝑛) we obtain via 𝑚 ∈ 𝜔(1) 𝛿𝜑 (𝑢, 𝑣) ≥
(100 − 𝑜(1))𝑒 𝓁𝑘 +𝐶/2 > 𝜃𝑅 (𝑟(𝑢), 𝑟(𝑣)), 𝑚2 ⋅ 𝑛
using that 𝓁𝑘 ≥ 𝓁𝑖 + 2 log 𝑚 ≥ 𝓁𝑗 + 4 log 𝑚 and 𝑟(𝑢) ≥ 𝑅 − 𝓁𝑖 − 2, 𝑟(𝑣) ≥ 𝑅 − 𝓁𝑗 − 2 in conjunction with Lemma 4. Hence, there is no edge between 𝑢 and 𝑣 as desired. This concludes the case and the proof. We now prove that a fixed sector is nice with a small but not polynomial decaying probability. √ Lemma 21 (𝑑-ary tree probability). Let 𝑚 ∈ 𝜔(1) and 𝑚 ≤ log 𝑛. Moreover, let Φ ⊆ 𝑅 be a sector with log 𝑛 −𝑜(1) . angular width 𝜙 = 𝑛5 log 𝑚 . Then, Φ is nice according to Algorithm 1 with probability 𝑛 Proof. We show that all boxes of a nice sector according to Algorithm 1 have exactly one vertex with the desired probability 𝑛−𝑜(1) . To this end, fix any 𝑖 ∈ [ℎ + 1] ⧵ {0} and consider any "non-root" layer 𝓁𝑖 . Then, to fulfil the property of a nice sector according to Algorithm 1, all 𝑑 𝑖 boxes include exactly one vertex. Let 𝑢 be a vertex in layer 𝓁𝑖−1 . Using Definition 19 it holds for any single box in layer 𝓁𝑖 𝜇(𝑢,𝑗 ) =
𝜙𝓁 𝑒 𝓁𝑖 (1−𝛼) ⋅ 𝜇(𝓁𝑖 ) = Θ(1) ∈ Ω(1/𝑛), 2𝜋 𝑛
where we used Equation (3) and for the last step that 𝓁𝑖 ≥ 0. Thus, using the fact that the number of vertices in a box follows a Poisson point distribution, the probability that there is exactly one vertex in a box in layer 𝓁𝑖 is 𝑝𝑖 = 𝑛 ⋅ 𝜇(𝑢,𝑗 ) ⋅ 𝑒 −𝑛⋅𝜇(𝑢,𝑗 ) ≥ 𝑒 𝓁𝑖 (1−𝛼) ⋅ exp (−Θ(1)𝑒 𝓁𝑖 (1−𝛼) ) .
(13)
Hence, using that any pair of boxes is disjoint, the probability that all 𝑑 𝑖 boxes in layer 𝓁𝑖 have exactly one vertex is given by 𝑑𝑖
𝑖
𝐏 (𝑖 ) = (𝑝𝑖 )𝑑 ≥ exp (−Θ(1)𝑒 𝓁𝑖 (1−𝛼) ) . Next, we bound the probability that the desired "root" vertex in layer 𝓁0 exists. Since the "box" of the "root" in Algorithm 1 has angle 𝜙/5 = log 𝑛/𝑛 log(𝑚) the probability that exactly one root vertex exists is by a Poisson distribution and Equation (3) 𝑝0 =
𝑛⋅𝜙 𝑛⋅𝜙 ⋅ 𝜇(𝓁0 ) ⋅ exp − ⋅ 𝜇(𝓁0 ) ≥ exp (−Θ(1)𝑒 𝓁0 (1−𝛼) ) . ( 2𝜋 ) 2𝜋 27
(14)
√ since 𝑚 ≤ log 𝑛 and 𝛼 < 1. This implies that sector Φ has vertices that are required to be nice, i.e., there is the root vertex and every box has exactly one vertex as required in Algorithm 1, with probability ℎ
ℎ
ℎ
𝑖
𝑑𝑖
𝐏 () ≥ 𝑝0 ⋅ ∏ ℙ (𝓁𝑖 ) ≥ ∏ ((𝑝𝑖 )𝑑 ) ≥ ∏ exp (−Θ(1)𝑒 𝓁𝑖 (1−𝛼) ) , 𝑖=1
𝑖=0
𝑖=0
where we used Equation (13) and Equation (14) in the last step. Next, we use that 𝛼 > 1/2 which yields ℎ
𝐏 () ≥ ∏ exp (−Θ(1)𝑑 𝑖 𝑒 𝓁𝑖 /2 ) .
(15)
𝑖=0
Since 𝓁𝑖 ≤ log log 𝑛 − 2𝑖 ⋅ log 𝑚 + 1, we obtain ℎ ℎ √ √ 𝐏 () ≥ ∏ exp (−Θ(1)𝑑 𝑖 ⋅ log 𝑛/𝑚𝑖 ) ≥ ∏ exp (−Θ(1) ⋅ log 𝑛/10000𝑖 ) , 𝑖=0
𝑖=0
where we used 𝑑 𝑖 ≤ (𝑚/10000)𝑖 . Applying a geometric series, the above yields ℎ √ √ 𝐏 () ≥ exp −Θ(1) ⋅ ∑ log 𝑛/10000𝑖 ≥ 𝑒 −Θ(1) log 𝑛 ∈ 𝑛−𝑜(1) , ( ) 𝑖=0
and we conclude that Φ has all vertices that are required to be nice with a probability that is decaying more slowly than polynomial in 𝑛. Finally, we lift this to the statement that the sector is also nice with probability 𝑛−𝑜(1) : we obtain a nice sector by showing that the sector, except for the boxes, is empty with essentially the same probability. To see this, note that by our choice of 𝜙 ∈ (log 𝑛/(𝑚𝑛)) and using that the number of vertices in sector Φ follow a Poisson distribution with expectation 𝐄 [|𝑉 ∩ Φ|] = 𝑛𝜙/2𝜋, the probability that the sector is empty is given by 𝐏 (𝑉 ∩ Φ = ∅) = 𝑒 −𝐄[|𝑉 ∩Φ|] ∈ 𝑒 −(log 𝑛/𝑚) ∈ 𝑛−𝑜(1) , using 𝑚 ∈ 𝜔(1). Hence, given any area ⊆ 𝑅 , the probability that Φ ⧵ is empty is at least 𝑛−𝑜(1) (using the fact that the probability of an area being empty is monotonically increasing if the considered area is shrinking). Then, let be the area that we need to reveal for event and it follows that a sector Φ is nice with probability 𝐏 (Φ is nice) ≥ 𝐏 () ⋅ 𝐏 (𝑉 ∩ (Φ ⧵ ) = ∅|) ≥ 𝐏 () ⋅ 𝐏 (𝑉 ∩ Φ = ∅) ∈ 𝑛−𝑜(1) , as claimed. Next, we “embed” a nice sector in a larger “buffer” sector (see Figure 3b for a sketch). This allows us, given that the “buffer sector” is large enough, to get independent probabilities among nice sectors to be disconnected from any other vertex in the disk. We use this to show that (polynomially) many 𝑑-ary trees exist and that they basically form their own component (except for a “cut edge” that goes from the root vertex of the tree to the giant, which is addressed in the “in particular” part of the statement ). Theorem 18 (𝑑-ary √ trees in hyperbolic random graphs). Let 𝐺 be a threshold hyperbolic random graph and let 𝑚 ∶= 𝑚(𝑛) ≤ log 𝑛 be a function growing in 𝑛. Then, a.a.s., there exist 𝑛Ω(1) disjoint sectors Φ𝑖 such that √ for 𝑇𝑖 ∶= 𝐺[𝑉 ∩ Φ𝑖 ], 𝑇𝑖 is a balanced 𝑑-ary tree 21 with 𝑛′ ∈ Ω( log 𝑛) vertices, degree 𝑑 ∈ Ω(𝑚) and height ℎ ∈ Ω(log𝑚 log 𝑛′ ). In particular, for each such tree 𝑇𝑖 with root 𝑢,22 there exists a vertex 𝑣 ∈ 𝑉 (𝐻 ) in the giant component 𝐻 of 𝐺 such that {𝑢, 𝑣} ∈ 𝐸(𝐻 ) is the unique edge between 𝑇𝑖 and 𝐺 ⧵ 𝑉 (𝑇𝑖 ). 21 22
A rooted tree where each vertex, except for the leaves, has 𝑑 children. The root node 𝑢 is the vertex with graph distance 𝑑𝐺 (𝑢, 𝑤) = ℎ to each leaf 𝑤 ∈ 𝑉 (𝑇𝑖 ).
28
1− 1
Proof. Throughout the proof, we partition the disk 𝑅 into 𝑘 = ⌈ 𝑛log2𝛼𝑛 ⌉ sectors such that for 𝑖 ∈ [𝑘], the 1
𝑛 2𝛼 log 𝑛 ; see red sector in Figure 3b for an illustration. Moreover, ( 𝑛 ) ∗ let 𝑟 ∶= 𝑅 − log 𝑛/𝛼 − log log 𝑛/2 and throughout the proof, we consider the area 0 (𝑟 ∗ ); see hatched
angle 𝜓 of any such sector Ψ𝑖 is 𝜓 ∈ Θ
area in Figure 3. We prove our theorem in two steps. In the first step of the proof, we show that any sector Ψ𝑖 ⧵ 0 (𝑟 ∗ ) contains a desired 𝑑-ary tree 𝑇𝑖 with probability 𝑛−𝑜(1) if it contains a nice sector Φ𝑖 ; blue sector in Figure 3. This is addressed in Claim 22. Then, in a second step, we show that we have 𝑛Ω(1) "buffer sectors" Ψ𝑖 w.e.h.p. that contain a tree 𝑇𝑖 and that if the area 0 (𝑟 ∗ ) is empty, then the neighbourhood of any 𝑑-ary tree 𝑇𝑖 does not contain a vertex of any vertex of any other "buffer sector" Ψ𝑗 . Showing that 0 (𝑟 ∗ ) is empty a.a.s. then gives the desired probabilistic guarantee of any 𝑇𝑖 not having any undesired edges. Finally, we finish the proof by showing that the edge of the "root" in 𝑇𝑖 which exists due to Claim 22 connects 𝑇𝑖 to the giant in the desired fashion of the "in particular" statement of our theorem. log 𝑛 Now, for Claim 22, we consider any Ψ𝑖 and let Φ𝑖 ⊂ Ψ𝑖 be the sector of width 𝜙 = 𝑛5 log 𝑚 ∈ 𝑜(log 𝑛/𝑛) as demanded in Lemma 21 that has the same bisector as Ψ𝑖 . In particular we consider a sector Ψ𝑖 where the corresponding sector Φ𝑖 is nice. We introduce the following event 𝑖 which says that no vertex in a nice sector Φ𝑖 has an edge to a vertex in Ψ𝑖 ⧵ Φ𝑖 except for the “root” vertex 𝑢 ∈ 𝑉𝓁0 ∩ Φ𝑖 which has exactly one edge to a "special" vertex 𝑣 in Ψ𝑖 ⧵ Φ𝑖 where 𝑣 lies in layer 𝓁 ∶= ⌈2 log log 𝑛/(1 − 𝛼)⌉. We later show that 𝑣 is part of the giant component. Event 𝑖 : let 𝑈 ∶= 𝑉 ∩ (Φ𝑖 ⧵ 𝓁0 ), i.e., all vertices in Φ𝑖 except for the “root” vertex in layer 𝓁0 , and let 𝑈 ∶= {No vertex in 𝑈 has any neighbour in Ψ𝑖 ⧵ (Φ𝑖 ∪ 0 (𝑟 ∗ ))}. Moreover, let 𝑢 ∈ 𝑉 ∩ (Φ𝑖 ∩ 𝓁0 ), i.e., the root vertex of Φ𝑖 , and let root ∶= {Vertex 𝑢 has exactly one neighbour 𝑣 in Ψ𝑖 ⧵ (Φ𝑖 ∪ 0 (𝑟 ∗ )), and 𝑣 is in layer 𝓁 }. We define 𝑖 ∶= 𝑈 ∩ root and we will show that this event holds with probability 𝑛−𝑜(1) . Claim 22. 𝐏 (𝑖 | Φ𝑖 is nice) ∈ 𝑛−𝑜(1) . Proof of claim. Event 𝑈 : We start by showing the desired properties for all "non-root" vertices. Conditioning on the property that Φ𝑖 is nice according to Algorithm 1, the probability for a vertex 𝑣 ∈ 𝑉𝓁𝑗 in a layer 𝓁𝑗 < 𝓁0 to have no neighbour in Ψ𝑖 ⧵ Φ𝑖 is at least 𝐏 (𝑁 (𝑣) ∩ (Ψ𝑖 ⧵ Φ𝑖 ) = ∅ | 𝑣 ∈ 𝑉𝓁𝑗 , Φ𝑖 is nice) ≥ 𝑒 −𝑛⋅𝜇(𝑣 (𝑅)∩0 (𝑅)) ≥ exp (−Θ(1)𝑒 𝓁𝑗 /2 ),
(16)
using that we have a Poisson distribution in conjunction with Equation (4). Now, given that Φ𝑖 is nice, let {𝑣1 , 𝑣2 , … 𝑣𝑛′ −1 } be our set 𝑉 ∩ (Φ𝑖 ⧵ 𝓁0 ) =∶ 𝑈 , i.e., vertices in a nice sector except for the “root”, in no particular order. Moreover, let 𝑡 be the event that the set of vertices {𝑣1 , 𝑣2 , … 𝑣𝑡−1 } have no neighbour in Ψ𝑖 ⧵ Φ𝑖 . Since we use a Poisson distribution, the probability of an area being empty is monotonically increasing if the considered area is shrinking and it holds for any 𝑡 that 𝐏 (𝑣𝑡 has no neighbour in Ψ𝑖 ⧵ Φ𝑖 |𝑡 , Φ𝑖 is nice) ≥ 𝐏 (𝑁 (𝑣𝑡 ) ∩ (Ψ𝑖 ⧵ Φ𝑖 ) = ∅ | 𝑣 ∈ 𝑉𝓁𝑗 , Φ𝑖 is nice) .
(17)
Then, we obtain via Equation (16) and Equation (17) for the event 𝑈 = {No vertex in 𝑈 has any neighbour in Ψ𝑖 ⧵ (Φ𝑖 ∪ 0 (𝑟 ∗ ))} that 𝑛′ −1
𝐏 (𝑈 ) ≥ ∏ 𝐏 (𝑣𝑡 has no neighbour in Ψ𝑖 ⧵ Φ𝑖 |𝑡 , Φ𝑖 is nice) 𝑡=1 ℎ
ℎ
𝑗
≥ ∏ ∏ 𝐏 (𝑁 (𝑣) ∩ (Ψ𝑖 ⧵ Φ𝑖 ) = ∅ | 𝑣 ∈ 𝑉𝓁𝑗 , Φ𝑖 is nice) ≥ ∏ exp (−Θ(1)𝑒 𝓁𝑗 /2 )𝑑 , 𝑗=1
𝑗=1 𝑣∈𝑉𝓁𝑗 ∩Φ𝑖
29
where we used in the last step that the number of vertices in layer 𝓁𝑗 of a nice sector Φ𝑖 is 𝑑 𝑗 . By the same arguments we applied for Equation (15), we then get that 𝐏 (𝑈 ) ∈ 𝑛−𝑜(1) .
(18)
This concludes the part for "non-root" vertices. Event root : Next, we consider the root vertex 𝑢 and establish our “cut edge” {𝑢, 𝑣} which we later show, connects 𝑢 to the giant. Let 𝑢 be the vertex in Φ𝑖 that lies in layer 𝓁0 , i.e., the root of our tree in the nice sector Φ𝑖 . W.l.o.g. let 𝜑(𝑢) = 0 and consider for 𝓁 = ⌈2 log log 𝑛/(1 − 𝛼)⌉ the set of points } { 1 1 1 1 𝑒 𝐶/2 log 2 + 1−𝛼 (𝑛) 𝑒 𝐶/2 log 2 + 1−𝛼 (𝑛) ≤ 𝜑(𝑥) ≤ − ⊂ Ψ𝑖 . = 𝑥 ∈ 𝓁 ∶ − 𝑛 2𝑛 We proceed by setting out the following goals. (G1) We show that any point in 𝑥 has distance at most 𝑅 to 𝑢 while any other vertex in Φ𝑖 , i.e., 𝑣 ∈ (𝑉 ∩ Φ𝑖 ) ⧵ {𝑢} , has distance at least 𝑅 to any point in . (G2) We show that there is exactly one vertex in with probability 𝑛−𝑜(1) . (G3) We show that, under the condition of event 𝑈 , the probability of the event that 𝑢 has no neighbour in Ψ𝑖 ⧵ (Φ𝑖 ∪ ) is 𝑛−𝑜(1) . Note that if all goals are accomplished, then root 𝑢 has all desired properties for event root . Moreover, if event 𝑈 occurs, there are no undesired edges of “non-root” vertices in Ψ𝑖 ⧵ Φ𝑖 . Thus, since the events of (G2) and (G3) are holding independently with probability 𝑛−𝑜(1) while the event of (G1) is deterministic, we get that the intersection of the event of all goals combined occur with probability 𝑛−𝑜(1) such that 𝐏 (𝑖 | Φ𝑖 is nice) = 𝐏 (root ∩ 𝑈 | Φ𝑖 is nice) ≥ 𝐏 (𝑈 ) ⋅ 𝐏 (root |Φ𝑖 is nice and event 𝑈 occurs.) ∈ 𝑛−𝑜(1) , as desired by using that event 𝑈 and root are positively correlated and we previously established 𝐏 (𝑈 ) ∈ 𝑛−𝑜(1) in Equation (18). We continue by accomplishing each goal. Goal 1.
To tackle that 𝑢 has distance at most 𝑅 to 𝑥 ∈ , note that 1
1
𝑒 𝐶/2 log 2 + 1−𝛼 (𝑛) 𝑒 (𝐶+𝓁0 +𝓁)/2 𝛿𝜑 (𝑢, 𝑥) ≤ ≤ < 𝜃𝑅 (𝑟(𝑢), 𝑟(𝑥)), 𝑛 𝑛 using that 𝓁0 = ⌈log log 𝑛⌉ and 𝓁 = ⌈2 log log 𝑛/(1 − 𝛼)⌉ in conjunction with Lemma 4. Thus, 𝑢 would have an edge to any potential vertex in . Next, to see that any other vertex in Φ𝑖 does not have an edge to a potential 𝑣 ∈ 𝑉 ∩ , note that any vertex 𝑤 ∈ 𝑉 ∩ Φ𝑖 has angle 𝜑(𝑤) > 𝜑(𝑢) = 0, since Φ𝑖 is nice. Hence, it holds for any 𝑥 ∈ , (by 𝓁𝑗 < 𝓁0 ), that for any 𝑤 ∈ 𝑉 ∩ (Φ𝑖 ∩ 𝓁𝑗 ) the angular distance is 1
1
𝑒 𝐶/2 log 2 + 1−𝛼 (𝑛) 1000𝑒 (𝐶+𝓁𝑗 +𝓁)/2 𝛿𝜑 (𝑤, 𝑥) ≥ > > 𝜃𝑅 (𝑟(𝑤), 𝑟(𝑥)), 2𝑛 𝑛 since 𝑟(𝑤) ≥ 𝑅 − 𝓁𝑗 − 1 ≥ 𝑅 − log log 𝑛 + 2 log 𝑚 − 2, 𝑚 ∈ 𝜔(1) and 𝑟(𝑥) ≥ 𝑅 − 𝓁 − 1 ≥ 𝑅 − 2 log log /(1 − 𝛼) − 2. Thus, any vertex in Φ𝑖 , other than the “root” 𝑢 ∈ 𝑉 ∩ 𝓁0 , would not have an edge to any vertex in by Lemma 4. This concludes the first goal.
30
Goal 2.
For the second goal, we calculate the measure for area and obtain 1
𝜇() = 𝜇(𝓁 ) ⋅
1
𝑒 𝐶/2 log 2 + 1−𝛼 (𝑛) ∈ 1/(𝑛 logΘ(1) 𝑛), 4𝜋𝑛
using the angle spanned by area and using Equation (3) in conjunction with 𝓁 ∈ Θ(log log 𝑛). Hence, the expected number of vertices in is 𝐄 [|𝑉 ∩ |] ∈ 1/ logΘ(1) 𝑛. Then, we apply the Poisson distribution and obtain for the probability that the number of vertices in is exactly 1 that 𝐏 (|𝑉 ∩ | = 1) = 𝐄 [|𝑉 ∩ |] ⋅ 𝑒 −𝐄[|𝑉 ∩|] ∈ 𝑛−𝑜(1) , as set out by our second goal. Goal 3.
For our third and final goal, note that we have 𝜇(𝑢 (𝑅) ∩ (Ψ𝑖 ⧵ (Φ𝑖 ∪ ))) ≤ 𝜇(𝑢 (𝑅) ∩ 0 (𝑅)) ≤ Θ(1)𝑒 𝓁0 /2 /𝑛,
(19)
using that 𝑢 ∈ 𝑉 ∩ 𝓁0 and Equation (4). Using the fact that the random variable of the number of vertices in 𝑢 (𝑅) ∩ 0 (𝑅) follows a Poisson distribution and that 𝓁0 = ⌈log log 𝑛⌉, we then conclude that 𝐏 (𝑉 ∩ 𝑢 (𝑅) ∩ (Ψ𝑖 ⧵ (Φ𝑖 ∪ )) = ∅|𝑈 ) ≥ 𝑒 −𝑛⋅𝜇(𝑢 (𝑅)∩0 (𝑅)) ∈ 𝑛−𝑜(1) , as we sought to show for the third goal, and in conclusion, it follows that 𝐏 (𝑖 = 1 | Φ𝑖 is nice) ∈ 𝑛−𝑜(1) as desired. ■ 1
To finish the proof of our statement, recall that Ψ𝑖 has angle 𝜓 ∈ Θ
𝑛 2𝛼 log 𝑛 and thus, we have ( 𝑛 )
𝑘 ∈ 𝑛Ω(1) such sectors in our entire disk. Now, let 𝑋𝑖 be the indicator random variable that is 1 if the event {𝑖 ∩ Φ𝑖 is nice} occurs. Moreover, let 𝑋 ∶= ∑𝑘𝑖=1 𝑋𝑖 , i.e., the number of "buffer sectors" Ψ𝑖 that have the desired induced subgraph tree 𝑇𝑖 = 𝐺[𝑉 ∩ Φ𝑖 ]. In the following, we obtain a lower bound for 𝑋 . Recall that 𝑟 ∗ = 𝑅 − log 𝑛/𝛼 − log log 𝑛/2. Then, using linearity of expectation, Lemma 21 and Claim 22 we have 𝑘
𝐄 [𝑋 | 𝑉 ∩ 0 (𝑟 ∗ ) = ∅] = ∑ 𝐏 (𝑖 ∩ Φ𝑖 is nice | 𝑉 ∩ 0 (𝑟 ∗ ) = ∅) 𝑖=1
≥ 𝑘 ⋅ 𝐏 (Φ𝑖 is nice | 𝑉 ∩ 0 (𝑟 ∗ ) = ∅) ⋅ 𝐏 (𝑖 | Φ𝑖 is nice, 𝑉 ∩ 0 (𝑟 ∗ ) = ∅) ∈ 𝑛Ω(1) using that a nice sector according to Algorithm 1 has only vertices outside the area 0 (𝑟 ∗ ) and 𝑖 is independent of the event 𝑉 ∩ 0 (𝑟 ∗ ) = ∅. To obtain concentration for 𝑋 , note that the sectors Ψ𝑖 are disjoint and the events that they are nice are mutually independent: determining whether Φ𝑖 is nice only requires revealing the randomness within Φ𝑖 . In similar fashion, event 𝑖 also only depends on the randomness in sector Ψ𝑖 ⧵ 0 (𝑟 ∗ ). Therefore, a Chernoff bound applies and we obtain 𝐏 (𝑋 ∈ 𝑛Ω(1) | 𝑉 ∩ 0 (𝑟 ∗ ) = ∅) ∈ 1 − 𝑛−𝜔(1) .
(20)
Next, we show for a sector Ψ𝑖 where event 𝑖 occurs, that all neighbours of the nice sector Φ𝑖 are contained in Ψ𝑖 if we condition on the event that 𝑉 ∩ 0 (𝑟 ∗ ) = ∅. Note that if Φ𝑖 is nice, it holds for any vertex
31
𝑢 ∈ 𝑉 ∩ Φ𝑖 that 𝑟(𝑢) ≥ 𝑅 − log log 𝑛 − 2. As such, the largest possible angle spanned among a vertex 𝑢 ∈ 𝑉 ∩ Φ𝑖 and any vertex 𝑣 ∈ 𝑉 ∩ 𝑅 ⧵ 0 (𝑟 ∗ ) is 1
𝑛 2𝛼 ⋅ log3/4 𝑛 ∈ 𝑜(𝜓), 𝜃𝑅 (𝑟(𝑢), 𝑟(𝑣)) ≤ 𝜃𝑅 (𝑅 − log log 𝑛 − 2, 𝑅 − log 𝑛/𝛼 − log log 𝑛/2) ∈ 𝑛 ⏟⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏟⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏞⏟ ( )
(21)
𝑟∗
by Lemma 4. Hence, for any 𝑢 ∈ 𝑉 ∩ Φ𝑖 it holds that 𝑁 (𝑢) ⊆ 𝑉 ∩ (Ψ𝑖 ⧵ 0 (𝑟 ∗ )). In the next step, we bound the probability of the event that the area 0 (𝑟 ∗ ) is empty (see hatched area in Figure 3b). Note that by Lemma 6 the expected number of vertices in this area is 𝑛 ⋅ 𝜇(𝐵0 (𝑟 ∗ )) ∈ 𝑜(1). Hence, it holds via Poisson distribution that 𝐏 (𝑉 ∩ 0 (𝑟 ∗ ) = ∅) ∈ 𝑒 −𝑜(1) ∈ 1 − 𝑜(1).
(22)
Thus, using Equation (20), Equation (22), and law of total probability we then get that 𝐏 (𝑋 ∈ 𝑛𝑜(1) ) ≤ 𝐏 (𝑉 ∩ 0 (𝑟 ∗ ) ≠ ∅) + 𝐏 (𝑉 ∩ 0 (𝑟 ∗ ) = ∅) ⋅ 𝐏 (𝑋 ∈ 𝑛𝑜(1) | 𝑉 ∩ 0 (𝑟 ∗ ) = ∅) ∈ 𝑜(1).
(23)
It follows that, a.a.s., non of the induced subgraph tree 𝑇𝑖 = 𝐺[𝑉 ∩ Φ𝑖 ] has any edge outside Ψ𝑖 using Equation (21). To wrap things up, consider the event that 𝑋 ∈ 𝑛Ω(1) and let giant be the event that any vertex in layer 𝓁 = ⌈2 log log 𝑛/(1 − 𝛼)⌉ is connected to the giant component of 𝐺. Note that the intersection of the two events implies our theorem if also 0 (𝑟 ∗ ) contains no vertex, since event 𝑖 ensures that 𝑇𝑖 is connected to the giant component in the desired way of the "in particular" statement of Theorem 18. To bound the probability of event giant we observe the following: using [67, Lemma 5.3] any vertex 𝑣 ∈ 𝑉 ∩ 𝓁 is connected to the set of vertices in 𝑉 ∩ 0 (𝑅/2) with probability 1 − 𝑜(1). Moreover, by [28, Theorem 1.4], all vertices of the set 𝑉 ∩ 0 (𝑅/2) are part of the giant component with probability 1 − 𝑜(1). Thus, we conclude that also any 𝑣 ∈ 𝑉 ∩ 𝓁 is part of the giant component with probability 𝐏 (giant ) ∈ 1 − 𝑜(1).
(24)
Though, the three events 𝑋 ∈ 𝑛Ω(1) , giant and 𝑉 ∩ 0 (𝑟 ∗ ) = ∅ are not independent, a union bound of the complements yields via Equation (22), Equation (23) and Equation (24) 𝐏 (𝑋 ∈ 𝑛Ω(1) ∩ giant ∩ 𝑉 ∩ 0 (𝑟 ∗ ) = ∅) ∈ 1 − 𝑜(1).
(25)
Using Equation (25) then finishes the proof as the desired structural properties of a 𝑑-ary tree in a nice sector now follow from Lemma 20.
6.2
Lower Bounds for MM and MIS (Proof of Theorem 2)
In this section, we present a lower bound on the runtime of any distributed algorithm for solving MM and MIS on HRGs in the form of Theorem 2. Our proof strategy is as follows: first we show that an 𝑟-round randomised algorithm for MIS/MM on HRGs would imply an 𝑟-round randomised algorithm for MIS/MM on 𝑑-regular trees; this is addressed in Lemma 24. Then, we state a lemma for an established lower bound for MIS/MM on 𝑑-regular trees; see Lemma 25 for the statement. By stacking these two lemmas together, we obtain the desired lower bound. To accomplish our goal, we make use of the following tree substructure in HRGs, which follows from Theorem 18 by setting the parameter 𝑚(𝑛) = log log 𝑛.
32
Corollary 23 (MIS and MM obstruction). Let 𝐺 be a threshold hyperbolic random graph. Then, a.a.s. there exists induced subgraph 𝑇hrg that is a balanced 𝑑-ary tree with degree 𝑑hrg ∈ Θ(log log 𝑛), height √ ℎhrg ∈ Θ(log𝑑 log 𝑛) and 𝑛′hrg ∈ Θ( log 𝑛) vertices. Additionally, for each such tree 𝑇hrg there exists exactly one vertex 𝑢 ∈ 𝑉 (𝑇hrg ) with a neighbour in 𝑣 ∈ 𝑉 (𝐺) ⧵ 𝑉 (𝑇hrg ) where 𝑣 is a vertex of the giant component of 𝐺. In particular, vertex 𝑢 has graph distance ℎhrg to all leaves of 𝑇hrg . The following lemma shows that if there existed a randomised algorithm that solves MIS/MM in 𝑜(log log 𝑛/ log log log 𝑛) rounds on hyperbolic random graphs, then this would imply a randomised algorithm that solves MIS/MM in 𝑜(log log 𝑛/ log log log 𝑛) rounds on balanced 𝑑-regular trees with degree 𝑑 ≈ log log 𝑛 and height ℎ ≈ log log 𝑛/ log log log 𝑛. Lemma 24 (HRG-to-tree coupling). Let 𝐺 ∼ (𝑛, 𝛼, 𝐶) be a threshold hyperbolic random graph with the properties of induced trees 𝑇hrg as stated in Corollary 23 and let 𝐴hrg be a LOCAL algorithm that solves MIS (MM) in 𝑟 < ℎhrg /200 rounds with error probability 𝑝(𝑛) on the giant component of 𝐺. Then, there exist an 𝑟-round LOCAL algorithm 𝐴tree , which solves MIS (MM) on a balanced 𝑑-regular tree 𝑇 with degree 𝑑 = 𝑑hrg + 1 and height ℎ = ⌊ℎhrg /100⌋ with error probability at most 2𝑝(𝑛). Proof. We aim to design an algorithm 𝐴tree for our infinite family of balanced 𝑑-regular trees with degree 𝑑 and height ℎ, such that 𝐴tree has error probability at most 2𝑝(𝑛). To do so, we run algorithm 𝐴hrg on the vertices of 𝑇 , pretending that 𝑇 is an HRG 𝐺 ∼ (𝑛, 𝛼, 𝐶) where 𝑛 is suitably chosen such that 𝑛′hrg , 𝑑hrg , and ℎhrg satisfy the conditions of Corollary 23. To prove that algorithm 𝐴tree is well-defined, we consider its behaviour on a 𝑑-regular tree 𝑇 with 𝑛′ vertices, and also consider the giant component of an HRG 𝐺 that contains an induced tree substructure 𝑇hrg as stated in Corollary 23. Note that 𝑇hrg contains 𝑇 as an induced subgraph, and to show that the execution of 𝐴tree is well-defined, we next consider a mapping of the vertices from 𝑇 to 𝑇hrg . Let 𝑈 ⊆ 𝑉 (𝑇 ) be the set of vertices that are at a distance at most 𝑟 from the leaves of 𝑇 , and let 𝐼 = 𝑉 (𝑇 ) ⧵ 𝑈 . Let 𝑁𝑟 [𝑈 ], 𝑁𝑟 [𝐼 ] be the 𝑟-hop neighbourhood of 𝑈 , 𝐼 , respectively. For 𝑟 < ℎ, we will map each of these subgraphs from 𝑇 to 𝑇hrg such that the 𝑟-hop local view of each vertex 𝑢 ∈ 𝑉 (𝑇 ) is the same as the 𝑟-hop local view of a vertex 𝑣 ∈ 𝑉 (𝑇hrg ). Since 𝑁𝑟 [𝑈 ] contains the vertices up to distance 𝑟 from the leaves, if we assume that 𝑁𝑟 [𝑈 ] contains 𝑘 leaves, we map the 𝑘 leaves of 𝑁𝑟 [𝑈 ] to the 𝑘 “leftmost” leaves of 𝑇hrg . After that, we map the rest of the vertices 𝑁𝑟 [𝑈 ] to vertices 𝑇hrg so that the mapping preserves the 𝑟-hop neighbourhoods of the vertices in 𝑈 . Let 𝑀(𝑈 ) be the set of vertices in 𝑇hrg that 𝑁𝑟 [𝑈 ] was mapped to. With this partial mapping, we have guaranteed that if we run 𝐴tree on 𝑇 , every vertex 𝑢 ∈ 𝑈 has a copy vertex 𝑣 ∈ 𝑉 (𝑇hrg ) with the same view. Additionally, by the choice of 𝑟 < ℎ/2 ≤ ℎhrg /200, no vertex in 𝑈 can identify that they are not in an HRG 𝐺. We will now map the vertices from 𝑁𝑟 [𝐼 ]. First, note that the diameter of the induced subgraph 𝑇 ′ ∶= 𝑁𝑟 [𝐼 ] is the same as 𝑇 , if we first remove the leaves of 𝑇 . Therefore, the induced subgraph of 𝑁𝑟 [𝐼 ] has height ℎ − 1. Now let 𝑤 ∈ 𝑉 (𝑇 ′ ) be the unique vertex that is at distance ℎ − 1 from every leaf of 𝑇 ′ . Also, among the vertices of 𝑇hrg that are part of the partial mapping of 𝑁𝑟 [𝑈 ], let 𝑣 ∈ 𝑀(𝑈 ) be one of the vertices that are furthest away from the leaves in 𝑇hrg . Starting from 𝑣, we traverse ℎ − 1 hops towards the “root” of the 𝑇hrg , and let 𝑤′ ∈ 𝑉 (𝑇hrg) be the vertex we arrive at. We map 𝑤 ∈ 𝑉 (𝑇 ′ ) to 𝑤′ ∈ 𝑉 (𝑇hrg ). After that, we map the rest of the vertices 𝑁𝑟 [𝑈 ] to vertices 𝑇hrg so that the mapping preserves the 𝑟-hop neighbourhoods of the vertices in 𝐼 . Let 𝑀(𝐼 ) be the set of vertices in 𝑇hrg that 𝑁𝑟 [𝐼 ] was mapped to. Note that by our choice of 𝑤, 𝑤′ , and 𝑟, every vertex in 𝑀(𝐼 ) is neither a leaf nor a root. This guarantees that the vertices in 𝐼 ⊂ 𝑉 (𝑇 ) cannot distinguish that they are not on an HRG 𝐺 after the execution of 𝐴tree . Additionally, every vertex in 𝑁𝑟 [𝐼 ] has an identical 𝑟-hop local view to its mapped vertex in 𝑀(𝐼 ). We now proceed by bounding the error probability of 𝐴tree . To this end, we utilise the mapping we laid out above. Since MIS and MM are locally checkable problems, if 𝐴tree fails on 𝑇 , then there is a local 33
witness of failure centred either at a vertex of 𝑈 or at a vertex of 𝐼 . Denote these two events by 𝐹𝑈 and 𝐹𝐼 . Thus, by union bound, we have ℙ (𝐴tree fails on 𝑇 ) ≤ ℙ (𝐹𝑈 ) + ℙ (𝐹𝐼 ) . We first bound ℙ (𝐹𝑈 ). To achieve this, we couple the randomness of the algorithm 𝐴hrg on the vertices 𝑁𝑟 [𝑈 ] with the randomness of the algorithm 𝐴tree on the mapped vertices in 𝑀(𝑈 ). Since 𝑟 ≤ ℎ(𝑛)/200, no vertex in 𝑀(𝑈 ) “sees” the unique attachment vertex of 𝑇hrg to 𝐺 ⧵ 𝑇hrg . Hence, the radius-𝑟 views used by 𝐴tree in 𝑇hrg and the radius-𝑟 views seen by 𝐴hrg in 𝐺 are identical for all vertices relevant to a failure witness centred in 𝑈 . Therefore, under this coupling, every occurrence of 𝐹𝑈 yields a local MIS, respectively, MM, violation in the output of 𝐴hrg on 𝐺. Consequently, by the hypothesis of our lemma statement, it holds ℙ (𝐹𝑈 ) ≤ ℙ (𝐴hrg fails on 𝐺) ≤ 𝑝(𝑛). It remains to bound ℙ (𝐹𝐼 ). For vertices in 𝐼 , the relevant 𝑁𝑟 [𝐼 ] are far from the leaves. We couple the algorithm 𝐴tree for 𝑁𝑟 [𝐼 ] with the algorithm 𝐴hrg for the mapped vertices in 𝑀(𝐼 ) that are also far from both the leaves and the unique attachment point to 𝐺 ⧵ 𝑇hrg . Thus, all radius-𝑟 views used by 𝐴tree around a potential failure witness in 𝐼 are identical to the corresponding views of 𝐴hrg in an execution on 𝐺. Hence every occurrence of 𝐹𝐼 also yields a local violation of the output of 𝐴hrg on 𝐺, and therefore again ℙ (𝐹𝐼 ) ≤ ℙ (𝐴hrg fails on 𝐺) ≤ 𝑝(𝑛). Combining the two bounds gives ℙ (𝐴tree fails on 𝑇 ) ≤ ℙ (𝐹𝑈 ) + ℙ (𝐹𝐼 ) ≤ 2𝑝(𝑛). Equivalently, if 𝐴tree failed with probability greater than 2𝑝(𝑛), then either 𝐹𝑈 or 𝐹𝐼 would occur with probability greater than 𝑝(𝑛), contradicting the correctness guarantee of 𝐴hrg under the corresponding coupling. Next, we show a statement which will imply that any randomised algorithm on a balanced 𝑑-regular tree with degree 𝑑 ≈ log log 𝑛 and height ℎ ≈ log log 𝑛/ log log log 𝑛 requires Ω(log log 𝑛/ log log log 𝑛) rounds to solve MIS and MM respectively. Lemma 25 ([6]). The randomised complexity with error probability 𝑝 of MIS/MM on a balanced 𝑑-regular tree with 𝑛 vertices is Ω(min{𝑑, log𝑑 𝑛, log𝑑 log 1/𝑝 − (1)}). Proof sketch: The result directly follows with Theorem 44 (see Appendix Section C for a discussion), given that [6] show that the respective sequences to apply the theorem exist for MIS and MM. More detailed, [6] shows that such a sequence with 𝑡 = Θ(𝑑) and 𝑓 (𝑑) = 2𝑑+1 exists for MIS. The main idea of the proof is that they construct a sequence and each problem in their sequence come with a fingerprint vector 𝑧. For MIS the vector is of length 2 (formally 𝑙𝑒𝑛(𝑧) = 1 in their terminology) and the fingerprint vector of the original MIS problem is [1, 0]. Then, fingerprint vectors can be obtained iteratively. The 𝑗-entry of the fingerprint for the 𝑖-th problem in the sequence is the 𝑗-prefix sum of the 𝑖−1-st fingerprint. Thus, the fingerprint vectors evolve like [1, 0], [1, 1],[1, 2], until [1, 𝑡]. They show that the sequence can be extended by yet another problem whenever the 𝑙1-norm of the vector is ≤ Δ. So, for MIS we can do Δ−1 such steps. The precise interpretation of the fingerprint vector and the actual description of the problems in the sequence is technical and we refer to their paper for more details. We obtain that [6, Lemma 6.1] shows that the sequence for MIS is of length Θ(𝑑) with 𝑓 (𝑑) ≤ 2𝑑 (1 + 𝑙𝑒𝑛(𝑧)) where 𝑙𝑒𝑛(𝑧) = 1 for the MIS problem (in their paper 𝑙𝑒𝑛(𝑧) = 𝛽 which equals 1 for MIS, see Section 5.1 in the arxiv version{of their work. Thus, via Theorem 44 the } runtime bound 𝑑+1 for error probability 𝑝 for MIS simplifies to Ω (min 𝑑, log𝑑 𝑛, log𝑑 log 1/𝑝 − log𝑑 log 2 ). In particular, the term log𝑑 log 2𝑑+1 = log𝑑 (𝑑 + 1) ∈ (1). For MM [30] (see e.g. Theorem 4.5) shows that the respective sequence with length 𝑡 = 2𝑑 − 1 and 𝑓 (𝑑) = 5 exists. For the latter, we cite from their work: Crucially, all the problems of the family 34
are described using only 5 labels, and while the result of the round elimination technique may contain more than 5 labels, we will provide relaxations that allow us{ to map these problems back to this family } exists, and hence, Theorem 44 yields a lower bound of Ω (min 2𝑑 − 1, log𝑑 𝑛, log𝑑 log 1/𝑝 − log𝑑 log 5 ) ∈ { } Ω (min 𝑑, log𝑑 𝑛, log𝑑 log 1/𝑝 − (1) ). We now put Corollary 23, Lemma 24 and Lemma 25 together to obtain our lower bounds of Theorem 2. Theorem 2 (Lower bounds for MIS and MM). Asymptotically almost surely,23 the randomised complexity 24 for computing an MIS or an MM for the giant component of a hyperbolic random graph is Ω ( logloglogloglog𝑛 𝑛 ) rounds in the LOCAL model. Proof. Using Corollary 23 in conjunction with Lemma 24, it follows a.a.s. over the draw of 𝐺 ∼ (𝑛, 𝛼, 𝐶) that any 𝑜(log log 𝑛/ log log log 𝑛)-round randomised algorithm for MIS or MM on 𝐺 that has an error probability of at most 𝑝 would imply the existence of a 𝑜(log log 𝑛/ log log log 𝑛)-round randomised algorithm for MIS or MM on balanced 𝑑-regular trees, where the degree is 𝑑 ∈ Θ(log log 𝑛) and the tree has height ℎ ∈ Θ(log log 𝑛/ log log log 𝑛), with error probability at most 2𝑝. Therefore, it suffices to show that no such algorithm exists on any such 𝑑-regular tree with running time 𝑜(log log 𝑛/ log log log 𝑛) and error probability at most 2/𝑛𝑐 , for every constant 𝑐 > 0. Indeed, this immediately implies that a.a.s. over the draw of 𝐺, there does not exist an 𝑜(log log 𝑛/ log log log 𝑛)-round randomised algorithm on 𝐺 for MIS or MM with error probability 𝑝 = 1/𝑛𝑐 . Consequently, to establish our main result, it remains to prove that no such algorithm exists for balanced 𝑑-regular trees. We show this by using Lemma 25. Fix any constants 𝑐, 𝑐𝑑 , 𝑐ℎ > 0 and consider a balanced 𝑑-regular tree 𝑇 with degree 𝑑 = 𝑐𝑑 ⋅log log 𝑛 and height ℎ = 𝑐ℎ ⋅log𝑑 log 𝑛 giving a 𝑑-regular tree of size 𝑛′ ≥ (𝑑−1)ℎ ≥ log𝑐𝑛 𝑛 for some constant 𝑐𝑛 > 0. Since the runtime for any algorithm with error probability 𝑝′ for MIS or MM on a balanced 𝑑-regular tree with 𝑛′ vertices is Ω(min{𝑑, log𝑑 𝑛′ , log𝑑 log 1/𝑝′ − (1)}) using Lemma 25, the runtime 𝑡 for our tree 𝑇 with parameters 𝑑 = 𝑐𝑑 ⋅ log log 𝑛, ℎ = 𝑐ℎ ⋅ log𝑑 log 𝑛 and 𝑛′ ≥ log𝑐𝑛 𝑛 is { } log log 𝑛 log log 𝑛 𝑡 ∈ Ω min log log 𝑛, , ( log log log 𝑛 log log log 𝑛 ) setting 𝑝′ = 2/𝑛𝑐 . Hence, 𝑡 ∈ Ω ( logloglogloglog𝑛 𝑛 ) and the theorem follows as this implies that a.a.s. for 𝐺, an algorithm requires at least 𝑡 rounds to obtain a probabilistic guarantee of 1 − 𝑛−𝑐 for MIS or MM for the giant component of 𝐺.
7
Embedding-Aware Symmetry Breaking (Theorem 3)
In this section, we assume that each vertex knows its geometric position. So a vertex 𝑣 ∈ 𝑉 (𝐺) can also communicate its geometric coordinate (𝑟(𝑣), 𝜑(𝑣)) to any neighbour within one round. We prove the following. Theorem 3 (Embedding-aware algorithms). There are distributed algorithms that, for threshold hyperbolic random graphs given in their geometric representation, compute • Maximal Independent Set in (log log 𝑛) rounds w.h.p. 25 of the CONGEST model; With probability 1 − 𝑜(1) over the draw of the hyperbolic random graph 𝐺. There exists an algorithm where the error probability is at most 1/𝑛𝑐 for some constant 𝑐 > 0. 25 We say an event occurs with high probability (w.h.p.) if ℙ () ∈ 1 − (1/𝑛). 23 24
35
• Maximal Matching in (log log log 𝑛) rounds w.h.p. of the CONGEST model. The Maximal Independent Set part we show in Section 7.1 and the Maximal Matching part in Section 7.2. Throughout the section we assume that radial and angular coordinates are unique to vertices; a property that holds almost surely. To describe our algorithms in both sections, we make use of a tiling which ensures that vertices in the same tile form a clique. Moreover, for any two vertices 𝑢 and 𝑣 in the same layer, if the tiles containing 𝑢 and 𝑣 are separated by sufficiently many intermediate tiles, then there is no edge between 𝑢 and 𝑣. This is useful since all vertices in a tile can communicate with each other within one round, finding a local solution that is globally valid if active tiles are far enough apart. Tiling.
Throughout this section, let 𝓁 ∈ [⌈log 𝑛/ log log 𝑛⌉]. Recall the definition of a layer 𝓁 ∶= 0 (𝑅 − 𝓁) ⧵ 0 (𝑅 − 𝓁 − 1),
and for layer level 𝓁, let 𝑁𝓁 ∶= 40 ⋅
𝑛 ⋅ 𝜋𝑒 𝐶/2 , ⌈ 20𝑒 𝓁 ⌉
where the constant 40 is chosen for later convenience. Then, for any 𝓁 and 𝑖 ∈ [𝑁𝓁 ] we define a tile 𝓁,𝑖 by the set of points 𝓁,𝑖 ∶= {𝑥 ∈ 𝓁 ∶ (𝑖 ⋅ 2𝜋)/𝑁𝓁 ≤ 𝜑(𝑥) < ((𝑖 + 1) ⋅ 2𝜋)/𝑁𝓁 }.
(26)
For a sketch of the tiling, see also Figure 4a. We remark that 𝑁𝓁 , the number of tiles per layer, is divisible by 40. Remark 26. For any 𝓁 it holds 𝑁𝓁 ≡ 0
(mod 40).
We sum up the key properties of our tiling in the following lemma. The first property tells us that vertices in the same tile form a clique, and the second property tells us that vertices in the same layer but with a constant number of tiles between them do not have an edge. Finally, the third property says that if a vertex 𝑢 has a neighbour 𝑣 which is located in a tile in a “smaller” layer, then 𝑣 is not a neighbour to another vertex 𝑢′ in the same layer as 𝑢, if the number of tiles between 𝑢 and 𝑢′ is a large enough constant. Lemma 27 (Tiling properties). The following holds for any 𝓁 of our tiling: i. for any 𝑖 ∈ [𝑁𝓁 ], it holds for any 𝑢 ∈ 𝑉 ∩ 𝓁,𝑖 and 𝑣 ∈ 𝑉 ∩ 𝓁,𝑖 that {𝑢, 𝑣} ∈ 𝐸(𝐺); ii. for any pair 𝑖, 𝑗 such that |𝑖 − 𝑗| ≥ 20, it holds for any 𝑢 ∈ 𝑉 ∩ 𝓁,𝑖 and 𝑣 ∈ 𝑉 ∩ 𝓁,𝑗 that {𝑢, 𝑣} ∉ 𝐸(𝐺); iii. let 𝓁 ≥ 𝓁′ and consider any pair 𝑖, 𝑗 such that |𝑖 − 𝑗| ≥ 40. Moreover, let 𝑢 ∈ 𝑉 ∩ 𝓁,𝑖 , 𝑢′ ∈ 𝑉 ∩ 𝓁,𝑗 and let 𝑣 ∈ 𝑁 (𝑢) ∩ 𝓁′ . Then, it also holds {𝑢′ , 𝑣} ∉ 𝐸(𝐺). 𝐶/2
2𝑛⋅𝜋𝑒 Proof. Item 1: W.l.o.g. let 𝑅 − 𝓁 − 1 < 𝑟(𝑢) ≤ 𝑟(𝑣) ≤ 𝑅 − 𝓁. Then, using that 𝑁𝓁 = 40 ⋅ ⌈ 𝑛⋅𝜋𝑒 20𝑒 𝓁 ⌉ ≥ 𝑒𝓁 holds for the angular distance between 𝑢, 𝑣 that
𝛿𝜑 (𝑢, 𝑣) ≤ 2𝜋/𝑁𝓁 ≤
𝐶/2
, it
𝑒𝓁 ≤ 𝜃𝑅 (𝑅 − 𝓁, 𝑅 − 𝓁) ≤ 𝜃𝑅 (𝑟(𝑢), 𝑟(𝑣)), 𝑛𝑒 𝐶/2
by applying the lower bound of Lemma 4 and 𝜃𝑅 (⋅, ⋅) is monotonically decreasing in both arguments (see e.g. [60, Remark 4]). Hence, 𝑢 and 𝑣 have an edge as desired. 36
Item 2: W.l.o.g. let 𝑅 − 𝓁 − 1 < 𝑟(𝑢) ≤ 𝑟(𝑣) ≤ 𝑅 − 𝓁. Then, using that there are at least 19 tiles in between 𝐶/2 2𝑛⋅𝜋𝑒 𝐶/2 𝑢 and 𝑣 and that 𝑁𝓁 = 40 ⋅ ⌈ 𝑛⋅𝜋𝑒 + 1, it holds for the angular distance between 𝑢, 𝑣 that 20𝑒 𝓁 ⌉ ≤ 𝑒𝓁 𝛿𝜑 (𝑢, 𝑣) ≥ 38𝜋/𝑁𝓁 ≥
𝜋𝑒 𝓁+1 18𝑒 𝓁 > ≥ 𝜃𝑅 (𝑅 − 𝓁 − 1, 𝑅 − 𝓁 − 1) ≥ 𝜃𝑅 (𝑟(𝑢), 𝑟(𝑣)), 𝑛𝑒 𝐶/2 𝑛𝑒 𝐶/2
by applying the upper bound of Lemma 4 and the monotonicity of 𝜃𝑅 (⋅, ⋅). Hence, 𝑢 and 𝑣 have no edge as desired. Item 3: Since 𝑣 ∈ 𝑁 (𝑢), it holds 𝜃𝑅 (𝑟(𝑢), 𝑟(𝑣)) ≤ 𝜋𝑒 (𝑅−𝑟(𝑣)−𝑟(𝑢))/2 , using Lemma 4. W.l.o.g. let 𝑢 have angular coordinate 𝜑(𝑢) = 0 such that 𝜑(𝑣) ≤
𝜋 ⋅ 𝑒 𝓁+1−𝐶/2 , 𝑛
using that 𝜃𝑅 (⋅, ⋅) is monotonically decreasing in both arguments and 𝑟(𝑢), 𝑟(𝑣) ≥ 𝑅 − 𝓁 − 1. On the other hand, we have 38𝑒 𝓁 𝜑(𝑢′ ) ≥ 78𝜋/𝑁𝓁 ≥ 𝐶/2 , 𝑛𝑒 ′ using that 𝜑(𝑢) = 0 and between 𝑢 and 𝑢 there are at least 39 tiles as |𝑖 − 𝑗| ≥ 40. Combining these bounds on the angle, we get for the angular distance between 𝑢′ and 𝑣 that 𝛿𝜑 (𝑢′ , 𝑣) = |𝜑(𝑢′ ) − 𝜑(𝑣)| ≥
38𝑒 𝓁 𝜋 ⋅ 𝑒 𝓁+1−𝐶/2 10𝑒 𝓁 𝜋 ⋅ 𝑒 𝓁+1−𝐶/2 − > > > 𝜃𝑅 (𝑟(𝑢′ ), 𝑟(𝑣)), 𝑛 𝑛 𝑛𝑒 𝐶/2 𝑛𝑒 𝐶/2
using the monotonocity of 𝜃𝑅 (⋅, ⋅), 𝑟(𝑢′ ), 𝑟(𝑣) ≥ 𝑅 − 𝓁 − 1 and Lemma 4. Subsequently, 𝑣 ∉ 𝑁 (𝑢′ ) which is what we sought to prove.
7.1
Embedding-Aware Maximal Independent Set (MIS part of Theorem 3)
We now exploit the knowledge of the coordinates, which implies the knowledge of which tile a vertex belongs to, in order to find an independent set in an HRG. We use the geometry and the coordinates in an algorithm we refer to as Embedding-aware-MIS, for which we first give an informal description. We iterate through the layers in bottom-up fashion, starting with layer 0 as follows: we “activate” tiles in the current layer such that “active tiles” are far enough apart from each other so that vertices in different active tiles do not have an edge. Thus, in parallel, we can then select one vertex in every active tile to participate in the independent set (as long as none of its neighbours already participates in the independent set). Since vertices in the same tile form a clique, this removes all vertices from a tile. We then iterate in this fashion through all tiles of a layer such that all vertices in a layer either participate in the independent set or have a neighbour that is part of the independent set. The key observation here is that we only need to iterate through (log log 𝑛) layers, since after iterating through layer 0 , every vertex with radius at most 𝑅 − 4 log log 𝑛 has a neighbour that participates in the independent set (this is addressed in Lemma 29). Indeed, we shall show in this section that this procedure, which is formalised in Algorithm 2, gives a maximal independent set within (log log 𝑛) rounds. We first observe that every 40-th tile in layer 0 contains a vertex that is part of the independent set (if there is at least one vertex in this tile). Observation 28. If |𝑉 ∩ 0,𝑖 | ≥ 1 such that 𝑖 ≡ 0 (mod 40), then 𝑉 ∩ 0,𝑖 contains a vertex that is in the set 𝐼 .
37
Algorithm 2 Embedding-aware-MIS 1: Input: Graph 𝐺 = (𝑉 , 𝐸) 2: Output: Independent set 𝐼 ⊆ 𝑉 3: 𝐼 ← ∅ // Initialise independent set 4: for 𝓁 = 0 to ⌈4 log log 𝑛⌉ do // Iterate through layers bottom-up
for 𝑚 = 0 to 39 do // Activate every 40th tile in layer 𝓁 6: (Executed in parallel at all nodes 𝑢 ∈ 𝑉 ) 7: 𝑈 ← ∅ // Deactivate all previously active vertices 8: Activation step 9: for all 𝑢 ∈ 𝑉 do 10: if 𝑢 ∈ 𝑉 ∩ 𝑖,𝑗 such that 𝑖 ≡ 𝑚 (mod 40) then // Check if vertex 𝑢 is in active tile 11: if 𝑁 (𝑢) ∩ 𝐼 = ∅ then // Check if vertex 𝑢 has no neighbour in the independent set 12: 𝑈 ← 𝑈 ∪ {𝑢} // Activate vertex 𝑢 13: end if 14: end if 15: end for 16: Communication step 17: for all 𝑢 ∈ 𝑈 do 18: send 𝜑(𝑢) to all 𝑣 ∈ 𝑁 (𝑢) ∩ 𝑈 // Send angular coordinate to all active neighbours 19: end for 20: Selection step 21: for all 𝑢 ∈ 𝑈 do 22: let 𝑣1 ≺ 𝑣2 ≺ … be 𝑁 (𝑢) ∩ 𝑈 sorted by 𝜑(𝑣𝑖 ) // Ordering by angular coordinates 23: if 𝑢 = 𝑣1 then // Select vertex 𝑢 with smallest angular coordinate 24: 𝐼 ← 𝐼 ∪ {𝑢} // Add vertex 𝑢 to independent set 25: end if 26: end for 27: end for 28: end for 29: Return 𝐼 5:
38
Proof. Throughout the proof, we call a tile that contains at least one active vertex an active tile. Note that the tiles for which we wish to show the desired property are the tiles that are active in Embedding-aware-MIS if 𝓁, 𝑚 = 0, i.e., the first active tiles in the algorithm such that 𝐼 = ∅. We fix any active tile, i.e., a tile 0,𝑖 such that 𝑖 ≡ 0 (mod 40). Since all vertices that share the same tile form a clique by Lemma 27 Item 1, in the Selection step, every active tile with at least one vertex has exactly one vertex 𝑢 that tries to be part of the set 𝐼 . So it is sufficient to show that 𝑢 has no active neighbour in any other active tile. By the Activation step and using Remark 26, it follows that between two active tiles there are at least 39 non-active tiles between two active tiles. Thus, since any other active tile is in the same layer as the tile 0,𝑖 , any vertex 𝑣 that is included in any other active tile is not a neighbour of 𝑢 by Lemma 27 Item 2. We make use of this observation to show that, after iterating through layer 0 , vertices with radial coordinate larger than 𝑅 − 4 log log 𝑛 have a neighbour that is part of the independent set. Lemma 29 (First iteration of Embedding-aware-MIS). When 𝓁 ≥ 1 in Embedding-aware-MIS, any vertex 𝑢 ∈ 𝑉 with radial coordinate 𝑟(𝑢) ≥ 𝑅 − 4 log log 𝑛 has a neighbour that is included in the set 𝐼 with probability 1 − 𝑛−𝜔(1) . Proof. Using Observation 28, it is sufficient to show that for any vertex 𝑢 with radius 𝑟(𝑢) ≥ 𝑅 − 4 log log 𝑛, there exists at least one neighbour 𝑣 ∈ 𝑁 (𝑢) ∩ 0,𝑖 such that 𝑖 ≡ 0 (mod 40). To show this, fix any vertex 𝑢 with radius 𝑟(𝑢) ≥ 𝑅 − 4 log log 𝑛 and note that, since 𝜃𝑅 (𝑟(𝑢), 𝑅) ∈ Ω(log2 (𝑛)/𝑛) (using Lemma 4) and the angular width of a tile 0,𝑖 is at most Θ(1/𝑛) (by Equation (26)), there are at least Ω(log2 𝑛) tiles 0,𝑖 such that 𝑖 ≡ 0 (mod 40) in the neighbourhood disk 𝑢 (𝑅). Hence, it is sufficient to show that at least one of the Ω(log2 𝑛) tiles contains any vertex. Since tiles do not overlap and 𝜇(0,𝑖 ) = 𝜇(0 )/𝑁0 ∈ Ω(1/𝑛) (using Equation (3) and angle 1/𝑁0 ∈ Θ(1/𝑛) of a tile 0,𝑖 ), we conclude that the expected number of vertices in distinct active tiles (tiles 0,𝑖 tiles such that 𝑖 ≡ 0 (mod 40)) in the neighbourhood disk 𝑢 (𝑅) is Ω(log2 𝑛). Since the number of vertices in each tile follow a Poissondistribution, a Chernoff-bound yields that there is at least one active tile in the neighbourhood radius of 𝑢 with probability 1 − 𝑛−𝜔(1) . Hence,𝑢 has a neighbour 𝑣 ∈ 𝑁 (𝑢) ∩ 0,𝑖 that participates in the set 𝐼 with probability 1 − 𝑛−𝜔(1) and a union bound over all vertices gives the desired result. Next, we show that Embedding-aware-MIS produces an MIS on the vertices that were not removed by the previous lemma. Lemma 30 (Embedding-aware-MIS gives MIS). After Embedding-aware-MIS has terminated, any vertex 𝑢 ∈ 𝑉 with radial coordinate 𝑟(𝑢) ≤ 𝑅 − 4 log log 𝑛 is either in the set 𝐼 or has a neighbour 𝑣 ∈ 𝑁 (𝑢) that is in the set 𝐼 . Proof. Note that if for all 𝓁 ∈ [⌈4 log log 𝑛⌉ + 1] it holds that after iteration 𝓁 all vertices up to radius 𝑅 − 𝓁 are either part of the independent set or have a neighbour that is in the independent set, we are done. We prove this by induction. For 𝓁 = 0, observe that for any 𝑚 in Algorithm 2 that for any pair of active vertices 𝑢, 𝑣, either (a) 𝑢 and 𝑣 lie in the same tile, or (b) there are at least 39 tiles between 𝑢 and 𝑣. This follows from the Activation step of Embedding-aware-MIS together with Remark 26. Hence, by Lemma 27, every active vertex belongs to a connected component that forms a clique among active vertices in the same tile. Thus, for any active tile, we can select any vertex 𝑢 to be included in the 𝐼 , and all other vertices in the same tile will have 𝑢 as a neighbour that is included in the set 𝐼 . This is achieved by the Selection step in Embedding-aware-MIS and as such, for 𝓁 = 0, all vertices 𝑉 ∩ 𝓁=0 are either part of the set 𝐼 , or they have a neighbour that is in the set 𝐼 since every tile gets processed exactly once. Thus, after iteration 𝓁 = 0, the set 𝐼 is a maximal independent set for 𝐺[𝑉 ∩ 0 ] since any tile in 0 is exactly once active.
39
For the induction step, fix any 𝓁 and suppose that, by the induction hypothesis, after processing layers 0, … , 𝓁 − 1, the set 𝐼 is a maximal independent set of 𝐺 [𝑉 ∩ (𝑅 ⧵ 0 (𝑅 − 𝓁 − 1))] . Consider iteration 𝓁 of Algorithm 2. Any vertex 𝑢 ∈ 𝑉𝓁 that already has a neighbour in 𝐼 is not activated by the algorithm and is therefore already dominated. Hence, it remains to consider the active vertices, namely those in 𝑉𝓁 ⧵ 𝑁 (𝐼 ). On the induced subgraph 𝐺[𝑉𝓁 ⧵ 𝑁 (𝐼 )], the same arguments as in the base case apply. For any fixed value of 𝑚, active vertices are either contained in the same tile or are separated by at least 39 tiles. Thus, by Lemma 27, active vertices in different active tiles are non-adjacent, while active vertices within the same tile form a clique. Consequently, the Selection step chooses exactly one active vertex from every non-empty active tile, and every other active vertex in that tile has a neighbour that is added to 𝐼 . Therefore, after iteration 𝓁, every vertex in 𝑉𝓁 either already had a neighbour in 𝐼 before the iteration or is itself added to 𝐼 or has a neighbour that is added to 𝐼 during the iteration. Hence, after processing every tile in layer 𝓁 exactly once, every vertex up to radius 𝑅 − 𝓁 is either contained in 𝐼 or has a neighbour in 𝐼 , completing the induction. The following algorithm gives us a bound on the number of rounds for Embedding-aware-MIS Lemma 31 (Embedding-aware-MIS Runtime). The algorithm Embedding-aware-MIS requires (log log 𝑛) rounds w.h.p. for CONGEST. Proof. This follows from noting that Embedding-aware-MIS iterates through (log log 𝑛) layers and 𝑚 ∈ (1) in line 4 of Algorithm 2. Moreover, each iteration there is only one communication step where vertices communicate their angular coordinate in the Communication step. Though angular coordinates are a real number, it suffices to send (log 𝑛) bits w.h.p. by Lemma 45 to obtain an ordering that is required for the Selection step. Hence (1) communication rounds per iteration are sufficient w.h.p. for CONGEST. Thus, we obtain that the number of rounds is (log log 𝑛) w.h.p. as claimed. We finish the section by using the established results to show that Embedding-aware-MIS produces a maximal independent set in (log log 𝑛) rounds. Proposition 32 (Embedding-aware Maximal Independent Set). There exists a deterministic (log log 𝑛)round CONGEST algorithm to find a Maximal Independent Set on HRGs w.h.p. if the vertices have access to their geometric coordinates. Proof. Note that set 𝐼 fulfils the properties of an MIS and thus, the result that Embedding-aware-MIS produces an MIS follows from Lemma 29 and Lemma 30. The runtime for CONGEST follows from Lemma 31.
7.2
Embedding-Aware Maximal Matching (MM part of Theorem 3)
In this section, we use geometry to find a maximal matching for a hyperbolic random graph in (log log log 𝑛) rounds. We do this as follows: First, in a preprocessing step, we match all vertices with degree at least ≈ log3 (𝑛) with a vertex in layer 0 . This is accomplished by only marking vertices with degree ⌈log3/2 𝑛⌉ and letting them draw one random neighbour and mark this incident edge. Thereafter, we consider all vertices with radius at most 𝑅 − 6 log log 𝑛 and show that all vertices such vertices are matched by this preprocessing step. This is shown in Lemma 15. Thereafter, all that is left to do is to match all unmatched vertices which have radius at least 𝑅−6 log log 𝑛. We partition the outer disk 𝑅 ⧵ 0 (𝑅 − 6 log log 𝑛) into 6 log log 𝑛 layers. We then apply our tiling with the properties shown in Lemma 27 to obtain for each induced subgraph of a layer a maximal matching in constant rounds, which can be done for each layer in parallel (see also Lemma 33).
40
Next, we use a divide-and-conquer approach to find a maximal matching for the outer disk. It can be shown that, if we have two annuli 1 and 2 for which we have each a maximal matching for the induced subgraphs, then we can extent these two matchings to a maximal matching for the induced subgraph of vertices in 1 ∪ 2 in constant rounds. We show this in Lemma 35. Using Lemma 33 as a base case, and using that by Lemma 35 we can “merge” the matchings of two annuli in constant rounds, we then merge pairs of annuli in parallel in constant rounds. By this, we can double the size of the induced subgraph of an annulus that is matched in constant rounds, and we can do this for all disjoint annuli in parallel. Thus, since the outer disk consists of (log log 𝑛) layers, after (log log log 𝑛) merging iterations, each of which takes constant rounds, we have found a maximal matching for the outer disk in (log log log 𝑛) rounds. The following shows that we can compute a maximal matching for an induced subgraph of a layer in constant rounds. Lemma 33 (Maximal matching within a layer). Let 𝐺 be a threshold hyperbolic random graph where vertices are given their geometric coordinates as an input. Let 𝐺𝓁 ∶= 𝐺[𝑉𝓁 ]. Then for all layers we can compute a maximal matching 𝑀𝓁 ⊆ 𝐸(𝐺𝓁 ) for 𝐺𝓁 in (1) rounds w.h.p. for CONGEST. Proof. We use the following claim, which says that in constant rounds we can compute a matching such that each tile 26 contains at most one unmatched vertex.27 Claim 34. For any 𝓁 let 𝑖 ∈ [𝑁𝓁 ] and let 𝑉 ′ ⊆ 𝑉 be a set of unmatched vertices. Moreover, let 𝐺′ ∶= 𝐺[𝑉 ′ ∩𝓁,𝑖 ]. Then we can compute a matching 𝑀 ′ ⊆ 𝐸(𝐺′ ) with probability 1 − 𝑛−10 for CONGEST in (1) rounds, such that there exists at most one vertex in 𝑉 ′ that is not incident to an edge of 𝑀 ′ . Proof of claim. Consider any tile 𝓁,𝑖 and let 𝑈 ∶= 𝑉 ′ ∩ 𝓁,𝑖 . In constant communication rounds, any vertex 𝑢 ∈ 𝑈 can communicate the tile 𝓁,𝑖 based on its radial and angular coordinate to all its neighbours 𝑁 (𝑢). Thus, after constant rounds, every vertex 𝑢 has learned all vertices of 𝑈 (the set of vertices located in the same tile as 𝑢) since the induced subgraph of a tile forms a clique (Lemma 27). Next, every vertex 𝑢 sends the first ⌈13 ⋅ log 𝑛⌉ bits of 𝜑(𝑢) to all neighbour. Then, using Lemma 45, it holds with probability 1 − 𝑛−10 that every vertex is able to compute an ordering 𝑣1 ≺ 𝑣2 ≺ … which is the set 𝑈 , ordered by angular coordinates 𝜑(𝑣𝑖 ). Then, consider 𝑢 = 𝑣𝑗 in this ordering. If it has an odd index 𝑗 based on our ordering, we add the edge {{𝑢, 𝑣𝑗+1 }} to the matching 𝑀 ′ . We now distinguish two cases which show that by this procedure, at most one vertex remains unmatched within a tile. Case 1 [Number of vertices in a tile 𝓁,𝑖 is even]: all vertices can be paired with any neighbour in the same tile 𝓁,𝑖 using Lemma 27. By our procedure of pairing odd-even pairs, every vertex is matched. Case 2 [Number of vertices in a tile 𝓁,𝑖 is odd]: Observe that the vertex 𝑢 with the largest angular coordinate is the only vertex in 𝓁,𝑖 after our pairing procedure that has no matching partner. Thus, there is exactly one vertex which is unmatched. Since our described procedure requires constant rounds and vertices communicate in any round at most (log 𝑛) bits, the claim follows from the above two cases and that angular coordinates used are unique with probability 1 − 𝑛−10 . ■ Now, applying Claim 34 to each tile of layer 𝓁 in parallel, after constant rounds, there is at most 1 unmatched vertex in each tile 𝓁,𝑖 . Given this property, we iterate through 𝓁 as follows: for 𝑡 ∈ [40] we attempt to match any possible unmatched vertex 𝑢 ∈ 𝑉 ∩ 𝓁,𝑖 where 𝑖 ≡ 𝑡 (mod 40), i.e., we “activate” every 40-th tile. We do so by first letting every unmatched vertex 𝑣 send its layer 𝓁 ∈ (log 𝑛) to every neighbour 26
Recall Equation (26) for the definition of our tiling. We call a vertex 𝑢 unmatched if ∃𝑣 ∈ 𝑁 (𝑢) such that 𝐸(𝑣) ∩ 𝑀 = ∅ and 𝐸(𝑢) ∩ 𝑀 = ∅, i.e., under current matching 𝑀, it is still possible to add an edge 𝑒 incident to 𝑢 such that 𝑀 ∪ 𝑒 is a valid matching. 27
41
R−j
R−i
k
R−i
k
R−j
Ai,k AAi,k 1
k′
Ai,k
A2
Aj,k′
Aj,k′
(a)
(b)
Figure 9: (a) Illustration of unmatched vertices in two annuli (blue and yellow area) and the set of edges available to enhance the matching 𝑀1 ∪ 𝑀2 . (b) The hatched area is the only area where conflicts for the matching might occur when merging two annuli. 𝑁 (𝑣) in constant rounds. Thereafter, we activate any vertex 𝑢 ∈ 𝑉 ∩ 𝓁,𝑖 where 𝑖 ≡ 𝑡 (mod 40). Let 𝑁 ′ (𝑢) be the set of unmatched neighbours of 𝑢 and 𝑢 marks the set of unmatched vertices 𝑁 ′ (𝑢) ∩ 𝑉𝓁 . Then 𝑢 picks a vertex 𝑣 uniform at random from 𝑁 ′ (𝑢) ∩ 𝑉𝓁 and {u,v} is added to 𝑀𝓁 . Since in each iteration 𝑡, we have for any pair of active vertices 𝑢 ∈ 𝑉 ∩ 𝓁,𝑖 and 𝑢′ ∈ 𝑉 ∩ 𝓁,𝑗 that |𝑖 − 𝑗| ≥ 40, it follows by Lemma 27 that 𝑁 (𝑢) ∩ 𝑁 (𝑢′ ) = ∅. Therefore, no conflict can occur: no unmatched vertex can receive matching requests from two distinct active vertices during the same iteration phase 𝑡. Since after 40 iterations we tried to match any unmatched vertex in 𝓁 and each iteration requires (1) rounds while also 𝑡 ∈ (1), the procedure terminates after constant rounds. Moreover, 𝑀𝓁 is maximal for 𝐺𝓁 : when a tile 𝓁,𝑖 is processed, the unique unmatched vertex of tile 𝓁,𝑖 is matched whenever it has an unmatched neighbour. Therefore, after tile 𝓁,𝑖 has been processed, either it has become matched or every neighbour remaining in later tiles is already matched (or non-existent). Hence, using that each tile gets processed exactly once, no edge can remain between two unmatched vertices and we obtain a maximal matching 𝑀𝓁 for 𝐺𝓁 as desired. In the following, let 𝑖,𝑘 ∶= ⋃𝑘+𝑖−1 𝓁 . We refer to 𝑖,𝑘 as an annulus of size 𝑘 with starting layer 𝑖. 𝓁=𝑖 That is, an annulus of size 𝑘 with starting layer 𝑖 contains layer 𝑖 up to layer 𝑘 − 𝑖 and in total 𝑘 layers. Note that an annulus of size 1 is equivalent to a layer. The following lemma says that if we are given two disjoint annuli for which we have a local maximal matching each, then we can enhance such matchings to a maximal matching for the induced subgraph of the two annuli combined in constant rounds (see also Figure 9a for a sketch). Lemma 35 (Merging two annuli). Let 𝐺 be a threshold hyperbolic random graph where vertices are given their geometric coordinates as an input. Let 𝑖 − 𝑗 ≥ 𝑘 ≥ 𝑘 ′ such that 𝑈1 ∶= 𝑉 ∩ 𝑖,𝑘 , 𝑈2 ∶= 𝑉 ∩ 𝑗,𝑘′ , 𝐺1 ∶= 𝐺[𝑈1 ] and 𝐺2 ∶= 𝐺[𝑈2 ]. If we are given matchings 𝑀1 ⊆ 𝐸(𝐺1 ) and 𝑀2 ⊆ 𝐸(𝐺2 ) such that 𝑀1 is a maximal matching for 𝐺1 and 𝑀2 a maximal matching for 𝐺2 , then in CONGEST, we can compute in (1) rounds a matching 𝑀 ⊆ 𝐸(𝐺1 ∪ 𝐺2 ) ⧵ (𝑀1 ∪ 𝑀2 ) such that 𝑀1 ∪ 𝑀2 ∪ 𝑀 is a maximal matching for 𝐺[𝑈1 ∪ 𝑈2 ]. Proof. We consider two cases. First, if the two annuli 𝑖,𝑘 and 𝑗,𝑘′ have distance larger than 4, i.e., for any pair of points 𝑥 ∈ 𝑖,𝑘 and 𝑦 ∈ 𝑗,𝑘′ it holds dh (𝑥, 𝑦) ≥ 4. Case 1 [For the two annuli it holds 𝑖 − 𝑗 ≥ 𝑘 + 4]: consider the given matchings 𝑀1 and 𝑀2 . Under these matchings, all unmatched vertices 𝑣 ∈ 𝑉 ∩ 𝑗,𝑘′ send to any neighbour 𝑤 ∈ 𝑁 (𝑣) their layer 𝓁 in constant rounds. Then, if an unmatched vertex 𝑢 ∈ 𝑉 ∩ 𝑖,𝑘 has at least one unmatched neighbour in 𝑉 ∩ 𝑗,𝑘′ , let 𝑁 ′ (𝑢) ∶= 𝑁 (𝑢) ∩ 𝑗,𝑘′ and 𝑢 picks uniform at random a neighbour 𝑣 from 𝑁 ′ (𝑢) and {𝑢, 𝑣} is included in our matching 𝑀 such that 𝑣 ∈ 𝑉 ∩ 𝑗,𝑘′ . It is left to show that no unmatched vertex 𝑣 ∈ 𝑉 ∩ 𝑗,𝑘′ can receive matching requests from two distinct vertices 𝑢, 𝑢′ ∈ 𝑉 ∩ 𝑖,𝑘 in the same round. To see this, recall 42
that under matching 𝑀1 , for any unmatched pair 𝑢 and 𝑢′ , there is no edge {𝑢, 𝑢′ } ∈ 𝐸 since 𝑀1 is maximal such that two unmatched vertices cannot be adjacent. Hence, it holds dh (𝑢, 𝑢′ ) ≥ 𝑅. Now, for the sake of contradiction, assume that 𝑣 ∈ 𝑁 (𝑢) ∩ 𝑁 (𝑢′ ). By our case assumption, it holds 𝑟(𝑢), 𝑟(𝑢′ ) ≤ 𝑟(𝑣) − 4. By an application of Lemma 9, 𝑣 has distance at most 𝑅 to both 𝑢 and 𝑢′ if and only if dh (𝑢, 𝑢′ ) ≤ 𝑅. A contradiction, and thus, we can obtain the desired matching 𝑀 in constant rounds. Case 2 [For the two annuli it holds 𝑖 − 𝑗 < 𝑘 + 4]: let 𝑚 ∶= min(𝑖 + 3, 𝑘) and 𝑚′ ∶= max(𝑗, 𝑘 ′ − 3). We consider the two "border" annuli 𝑘′
𝑚
1 ∶= ⋃(𝓁 ) ⊆ 𝑖,𝑘 and 2 ∶= ⋃ (𝓁 ) ⊆ 𝑗,𝑘′ . 𝓁=𝑚′
𝓁=𝑖
For a visualisation, see the hatched area in Figure 9b. Note that we can find a maximal matching 𝑀 ′ for the induced subgraph 𝐺′ = (𝑉 ∩ (𝑖,𝑘 ∪ (𝑗,𝑘′ ⧵ 2 )), 𝐸 ⧵ (𝑀1 ∪ 𝑀2 )) in constant rounds by the previous case when 𝑖 − 𝑗 ≥ 𝑘 + 4. Analogously, we can find a matching 𝑀 ′′ for the induced subgraph 𝐺′′ = (𝑉 ∩ (𝑗,𝑘′ ∪ (𝑖,𝑘 ⧵ 1 )), 𝐸 ⧵ (𝑀1 ∪ 𝑀2 ∪ 𝑀 ′ )) in constant rounds. Hence, after constant rounds, ̃ such that for a maximal matching 𝑀 ⊇ 𝑀̃ where we can obtain a matching 𝑀1 ∪ 𝑀2 ∪ 𝑀 ′ ∪ 𝑀 ′′ =∶ 𝑀, ̃ 𝑀 ⊆ 𝐸(𝐺1 ∪ 𝐺2 ), all edges 𝑀 ⧵ 𝑀 are formed among vertex pairs 𝑢, 𝑣 where 𝑢 ∈ 𝑉 ∩ 1 and 𝑣 ∈ 𝑉 ∩ 2 . We then find such a set of edges 𝑀 ⧵ 𝑀̃ in additional constant rounds as follows: we use 𝑚 − 𝑖 + 1 iterations (iterating layer by layer through 1 ), where we consider in iteration 𝑡 ∈ [𝑚 − 𝑖 + 1] all unmatched vertices of the set 𝑉 ∩ 𝑚−𝑡 . That is, we iterate through the layers of 1 in top-down fashion. By using Claim 34, we can assume that each tile in 𝑚−𝑡 contains at most 1 unmatched vertex after constant rounds. Then, for 𝑡 ′ ∈ [40], in step (𝑡, 𝑡 ′ ), we activate the set of unmatched vertices where 𝑢 ∈ 𝑉 ∩ 𝓁,𝑏 fulfils 𝑏 ≡ 𝑡 ′ (mod 40). That is, we activate every 40-th tile. We then match in parallel any such active vertex 𝑢 with an unmatched vertex 𝑣 ∈ 𝑉 ∩ 2 uniform at random from the set of unmatched neighbours of 𝑢 in 2 . This can be done in (1) rounds. Using Lemma 27, it holds for any pair of active vertices 𝑢, 𝑢′ that 𝑁 (𝑢) ∩ 𝑁 (𝑢′ ) ∩ 2 = ∅ and thus, no conflict occurs by this procedure since any active tile contains at most one unmatched vertex. Since (40 ⋅ (𝑚 − 𝑖 + 1)) is constant, this procedure requires (1) rounds. Using the obtained matching by this procedure in conjunction with our matching 𝑀̃ (which we acquired in constant rounds), we obtain our desired matching 𝑀 in (1) rounds, which is maximal by similar arguments as used in Lemma 33: in iteration (𝑡, 𝑡 ′ ), after processing a tile, its unique unmatched vertex has either been matched or has no unmatched neighbour in 2 . Since every tile of 1 is processed exactly once, no unmatched edge remains between the border annulli 1 and 2 . Together with the maximality of 𝑀̃ on all remaining vertex pairs, this implies that 𝑀 is a maximal matching of 𝐺[𝑈1 ∪ 𝑈2 ] as desired. We now put everything together to obtain a maximal matching in (log log log 𝑛) rounds if the embedding of the graph is given. Proposition 36 (Embedding-aware Maximal Matching). There exists a (log log log 𝑛)-round CONGEST algorithm to find a Maximal Matching on HRGs w.h.p., if the vertices have access to their geometric coordinates Proof. Match inner-disk. By applying Lemma 15, in constant rounds we can find a matching 𝑀 ⊆ 𝐸, such that for any 𝑢 ∈ 𝑉 ∩ 0 (𝑅 − 6 log log 𝑛), there exists an edge 𝐸(𝑢) ∈ 𝑀 w.e.h.p. For the rest of the proof we condition on this matching and focus on matching vertices outside 0 (𝑅 − 6 log log 𝑛) since all vertices in 𝑉 ∩ 0 (𝑅 − 6 log log 𝑛) are matched in constant rounds. Match within layers. Next, we consider the ⌈6 log log 𝑛⌉ layers of the outer disk 𝑅 ⧵ 0 (𝑅 − ⌈6 log log 𝑛⌉). Using Lemma 33, we compute in parallel, for every layer 𝓁 contained in 𝑅 ⧵ 0 (𝑅 − ⌈6 log log 𝑛⌉), a maximal matching in 𝐺[𝑉𝓁 ] in constant rounds w.h.p. Match annuli. Now, we finish the proof by induction.
43
Base case: For each 𝑖 ∈ [⌈3 log log 𝑛⌉], consider the annuli 2𝑖,2 = 2𝑖 ∪ 2𝑖+1 . That is, each annulus consists of two consecutive layers. Using Lemma 35, we compute in parallel, for every 𝑖 ∈ [⌈3 log log 𝑛⌉], a maximal matching for the annulus 2𝑖,2 in constant rounds. Induction step: Consequently, we can repeat this process 𝑡 times, doubling the annulus size in each step. More formally, in iteration 𝑡 ∈ [⌈log2 log log 𝑛 + 3⌉] ⧵ {0}, for 𝑖 ∈ [⌈6 ⋅ 2−𝑡 log log 𝑛⌉] and 𝑘 = 2𝑡 we consider the annuli 𝑘⋅𝑖,𝑘 . By our induction hypothesis, for all 𝑖′ ∈ [⌈6 ⋅ 2−(𝑡−1) log log 𝑛⌉] and 𝑘 ′ = 2𝑡−1 we have a maximal matching for all the annuli 𝑘′ ⋅𝑖′ ,𝑘′ after (𝑡 − 1) rounds. Thus, by an application of Lemma 35, we obtain, after an additional constant number of rounds, a maximal matching for all annuli 𝑘⋅𝑖,𝑘 after iteration 𝑡. That is, we “merge” two “neighbouring” annuli in constant rounds. Setting 𝑡 = ⌈log2 log log 𝑛 + 3⌉ we obtain for an annulus of size 𝑘 ≥ ⌈6 log log 𝑛⌉ a maximal matching in (log log log 𝑛) rounds. Thus, we can find a maximal matching for the outer disk 𝑅 ⧵ 0 (𝑅 − ⌈6 log log 𝑛⌉) in (log log log 𝑛) rounds. This, in conjunction with Lemma 15, yields a maximal matching for 𝐺 in (log log log 𝑛) rounds w.h.p. as claimed.
References [1] Mohammed Amin Abdullah, Nikolaos Fountoulakis, and Michel Bode. “Typical distances in a geometric model for complex networks”. In: Internet Math. (2017). doi: 10.24166/IM.13.2017. [2] Noga Alon, László Babai, and Alon Itai. “A fast and simple randomized parallel algorithm for the maximal independent set problem”. In: Journal of Algorithms (1986). doi: 10.1016/0196-6774(86) 90019-2. url: http://dx.doi.org/10.1016/0196-6774(86)90019-2. [3] Samuel Baguley, Yannic Maus, Janosch Ruff, and George Skretas. “Hyperbolic Random Graphs: Clique Number and Degeneracy with Implications for Colouring”. In: STACS’25. 2025. doi: 10.4230/ LIPICS.STACS.2025.13. [4] Alkida Balliu, Sebastian Brandt, Xavier Coiteux-Roy, Francesco d’Amore, Massimo Equi, François Le Gall, Henrik Lievonen, Augusto Modanese, Dennis Olivetti, Marc-Olivier Renou, Jukka Suomela, Lucas Tendick, and Isadora Veeren. “Distributed Quantum Advantage for Local Problems”. In: STOC’25. 2025. [5] Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, Mikaël Rabie, and Jukka Suomela. “Lower Bounds for Maximal Matchings and Maximal Independent Sets”. In: J. ACM (2021). doi: 10.1145/3461458. url: https://doi.org/10.1145/3461458. [6] Alkida Balliu, Sebastian Brandt, Fabian Kuhn, and Dennis Olivetti. “Distributed Δ-coloring plays hide-and-seek”. In: STOC’22. 2022. doi: 10.1145/3519935.3520027. url: https://doi.org/ 10.1145/3519935.3520027. [7] Alkida Balliu, Filippo Casagrande, Francesco d’Amore, and Dennis Olivetti. “New Hardness Results for the LOCAL Model via a Simple Self-Reduction”. In: PODC’26 (2026). doi: 10.48550/ARXIV. 2510.19972. [8] Alkida Balliu, Filippo Casagrande, Francesco d’Amore, Massimo Equi, Barbara Keller, Henrik Lievonen, Dennis Olivetti, Gustav Schmid, and Jukka Suomela. “Distributed Quantum Advantage in Locally Checkable Labeling Problems”. In: SODA’26. doi: 10.1137/1.9781611978971.49. url: https://epubs.siam.org/doi/abs/10.1137/1.9781611978971.49. [9] Alkida Balliu, Mohsen Ghaffari, Fabian Kuhn, and Dennis Olivetti. “Node and edge averaged complexities of local graph problems”. In: Distributed Comput. (2023). doi: 10.1007/S00446-023-00453-1. url: https://doi.org/10.1007/s00446-023-00453-1.
44
[10]
Albert-László Barabási and Réka Albert. “Emergence of Scaling in Random Networks”. In: Science (1999). doi: 10.1126/science.286.5439.509.
[11]
Leonid Barenboim and Michael Elkin. Distributed Graph Coloring: Fundamentals and Recent Developments. Morgan & Claypool Publishers, 2013.
[12]
Leonid Barenboim and Michael Elkin. “Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition”. In: Distributed Computing (2009). doi: 10.1007/s00446009-0088-2. url: http://dx.doi.org/10.1007/s00446-009-0088-2.
[13]
Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schneider. “The Locality of Distributed Symmetry Breaking”. In: Journal of the ACM (JACM) (2016). doi: 10.1145/2903137.
[14]
Zylan Benjert, Kostas Lakis, Johannes Lengler, and Raghu Raman Ravi. “The Diameter of (Threshold) Geometric Inhomogeneous Random Graphs”. In: STACS’26. 2026.
[15]
Gianmarco Bet, Riccardo Michielan, and Clara Stegehuis. “Localized geometry detection in scale-free random graphs”. In: Journal of Applied Probability (2025). doi: 10.1017/jpr.2025.10038.
[16]
Thomas Bläsius, Emil Dohse, Deborah Haun, and Laura Merker. “Product Structure and Treewidth of Hyperbolic Uniform Disk Graphs”. In: SoCG’26. 2026. doi: 10.4230/LIPICS.SOCG.2026.18. url: https://doi.org/10.4230/LIPIcs.SoCG.2026.18.
[17]
Thomas Bläsius and Philipp Fischbeck. “On the External Validity of Average-case Analyses of Graph Algorithms”. In: ACM Transactions on Algorithms (TALG) (2024). doi: 10.1145/3633778.
[18]
Thomas Bläsius, Philipp Fischbeck, Tobias Friedrich, and Maximilian Katzmann. “Solving Vertex Cover in Polynomial Time on Hyperbolic Random Graphs”. In: Theory Comput. Syst. (2023).
[19]
Thomas Bläsius, Cedric Freiberger, Tobias Friedrich, Maximilian Katzmann, Felix Montenegro-Retana, and Marianne Thieffry. “Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry”. In: ACM Transactions on Algorithms (TALG) (2022). doi: 10.1145/3516483.
[20]
Thomas Bläsius, Tobias Friedrich, and Maximilian Katzmann. “Efficiently Approximating Vertex Cover on Scale-Free Networks with Underlying Hyperbolic Geometry”. In: Algorithmica (2023).
[21]
Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann, Ulrich Meyer, Manuel Penschuck, and Christopher Weyand. “Efficiently generating geometric inhomogeneous and hyperbolic random graphs”. In: Network Science (2022). doi: 10.1017/nws.2022.32.
[22]
Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann, Janosch Ruff, and Ziena Zeif. “On the Giant Component of Geometric Inhomogeneous Random Graphs”. In: ESA’23. 2023. doi: 10.4230/ LIPICS.ESA.2023.20.
[23]
Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann, and Daniel Stephan. “Strongly Hyperbolic Unit Disk Graphs”. In: STACS’23. 2023. doi: 10.4230/LIPIcs.STACS.2023.13.
[24]
Thomas Bläsius, Tobias Friedrich, and Anton Krohmer. “Cliques in Hyperbolic Random Graphs”. In: Algorithmica (2018). doi: 10.1007/s00453-017-0323-3.
[25]
Thomas Bläsius, Tobias Friedrich, and Anton Krohmer. “Hyperbolic Random Graphs: Separators and Treewidth”. In: ESA. 2016. doi: 10.4230/LIPIcs.ESA.2016.15.
[26]
Thomas Bläsius, Jean-Pierre von der Heydt, Sándor Kisfaludi-Bak, Marcus Wilhelm, and Geert van Wordragen. “Structure and Independence in Hyperbolic Uniform Disk Graphs”. In: SoCG’25. 2025. doi: 10.4230/LIPICS.SOCG.2025.21. url: https://doi.org/10.4230/LIPIcs.SoCG. 2025.21.
[27]
Thomas Bläsius, Maximilian Katzmann, and Clara Stegehuis. “Maximal cliques in scale-free random graphs”. In: Network Science (2024). doi: 10.1017/nws.2024.13. 45
[28]
Michel Bode, N. Fountoulakis, and Tobias Müller. “On the largest component of a hyperbolic model of complex networks”. In: Electronic Journal of Combinatorics (2015). doi: 10.1214/17-AAP1314.
[29]
Marián Boguñá, Fragkiskos Papadopoulos, and Dmitri Krioukov. “Sustaining the Internet with hyperbolic mapping”. In: Nature Communications (2010). doi: 10.1038/ncomms1063.
[30]
Sebastian Brandt and Dennis Olivetti. “Truly Tight-in-Δ Bounds for Bipartite Maximal Matching and Variants”. In: PODC’20. 2020. doi: 10.1145/3382734.3405745. url: https://doi.org/10. 1145/3382734.3405745.
[31]
Karl Bringmann, Ralph Keusch, and Johannes Lengler. “Geometric inhomogeneous random graphs”. In: Theoretical Computer Science (2019). doi: 10.1016/j.tcs.2018.08.014. url: http://dx. doi.org/10.1016/j.tcs.2018.08.014.
[32]
Karl Bringmann, Ralph Keusch, Johannes Lengler, Yannic Maus, and Anisur R. Molla. “Greedy routing and the algorithmic small-world phenomenon”. In: Journal of Computer and System Sciences (2022). doi: https : / / doi . org / 10 . 1016 / j . jcss . 2021 . 11 . 003. url: https : / / www . sciencedirect.com/science/article/pii/S0022000021001112.
[33]
Sacha Cerf, Benjamin Dayan, Umberto De Ambroggio, Marc Kaufmann, Johannes Lengler, and Ulysse Schaller. “Balanced Bidirectional Breadth-First Search on Scale-Free Networks”. In: arXiv (2024). doi: 10.48550/ARXIV.2410.22186. url: https://arxiv.org/abs/2410.22186.
[34]
Yi-Jun Chang, Tsvi Kopelowitz, and Seth Pettie. “An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model”. In: SIAM J. Comput. (2019). doi: 10.1137/ 17M1117537. url: https://doi.org/10.1137/17M1117537.
[35]
Yi-Jun Chang, Wenzheng Li, and Seth Pettie. “An optimal distributed (Δ+1)-coloring algorithm?” In: STOC’18. 2018.
[36]
Fan Chung and Linyuan Lu. “Connected Components in Random Graphs with Given Expected Degree Sequences”. In: Annals of Combinatorics (2002). doi: 10.1007/PL00012580.
[37]
Fan Chung and Linyuan Lu. “The Average Distances in Random Graphs with Given Expected Degrees”. In: Proceedings of the National Academy of Sciences (2002). doi: 10.1073/pnas.252631999.
[38]
Corinna Coupette and Christoph Lenzen. “A Breezing Proof of the KMW Bound”. In: SOSA’21. 2021. doi: 10 . 1137 / 1 . 9781611976496 . 21. url: http : / / dx . doi . org / 10 . 1137 / 1 . 9781611976496.21.
[39]
Michalis Faloutsos, Petros Faloutsos, and Christos Faloutsos. “On power-law relationships of the internet topology”. In: ACM SIGCOMM computer communication review (1999).
[40]
Salwa Faour, Mohsen Ghaffari, Christoph Grunau, Fabian Kuhn, and Václav Rozhon. “Local Distributed Rounding: Generalized to MIS, Matching, Set Cover, and Beyond”. In: SODA’23. 2023. doi: 10.1137/1.9781611977554.CH168. url: https://doi.org/10.1137/1.9781611977554. ch168.
[41]
Manuela Fischer. “Improved deterministic distributed matching via rounding”. In: Distributed Computing (2020).
[42]
Nikolaos Fountoulakis and Tobias Müller. “Law of large numbers for the largest component in a hyperbolic model of complex networks”. In: The Annals of Applied Probability (2018). url: https: //www.jstor.org/stable/26542317.
[43]
Tobias Friedrich and Anton Krohmer. “On the Diameter of Hyperbolic Random Graphs”. In: SIAM Journal on Discrete Mathematics (2018). doi: 10.1137/17M1123961.
46
[44]
Mohsen Ghaffari. “An Improved Distributed Algorithm for Maximal Independent Set”. In: SODA’16. 2016. doi: 10 . 1137 / 1 . 9781611974331 . CH20. url: https : / / doi . org / 10 . 1137 / 1 . 9781611974331.ch20.
[45]
Mohsen Ghaffari. “Distributed Maximal Independent Set using Small Messages”. In: SODA’19. 2019. doi: 10.1137/1.9781611975482.50. url: https://doi.org/10.1137/1.9781611975482. 50.
[46]
Mohsen Ghaffari and Christoph Grunau. “Faster deterministic distributed MIS and approximate matching”. In: STOC’23. 2023.
[47]
Mohsen Ghaffari and Christoph Grunau. “Near-Optimal Deterministic Network Decomposition and Ruling Set, and Improved MIS”. In: FOCS’24. 2024. doi: 10.1109/FOCS61266.2024.00007.
[48]
Mohsen Ghaffari, Christoph Grunau, Bernhard Haeupler, Saeed Ilchi, and Václav Rozhoň. “Improved Distributed Network Decomposition, Hitting Sets, and Spanners, via Derandomization”. In: SODA’23. 2023. doi: 10.1137/1.9781611977554.ch97. url: https://epubs.siam.org/doi/abs/10. 1137/1.9781611977554.ch97.
[49]
Mohsen Ghaffari, Magnús M. Halldórsson, Yannic Maus, and Alexandre Nolin. Robust Shattering Arguments. 2026. arXiv: 2606.27847. url: https://arxiv.org/abs/2606.27847.
[50]
Mohsen Ghaffari and Julian Portmann. “Improved Network Decompositions Using Small Messages with Applications on MIS, Neighborhood Covers, and Beyond”. In: DISC’19. 2019. doi: 10.4230/ LIPIcs . DISC . 2019 . 18. url: https : / / drops . dagstuhl . de / entities / document / 10 . 4230/LIPIcs.DISC.2019.18.
[51]
Luca Gugelmann, Konstantinos Panagiotou, and Ueli Peter. “Random Hyperbolic Graphs: Degree Sequence and Clustering”. In: ICALP’12. 2012. doi: 10.1007/978-3-642-31585-5_51.
[52]
David G. Harris, Johannes Schneider, and Hsin-Hao Su. “Distributed (Δ +1)-Coloring in Sublogarithmic Rounds”. In: J. ACM (2018). url: https://doi.org/10.1145/3178120.
[53]
Joost Jorritsma, Júlia Komjáthy, and Dieter Mitsche. “Cluster-size decay in supercritical kernel-based spatial random graphs”. In: The Annals of Probability (2025). doi: 10 . 1214 / 24 - aop1742. url: http://dx.doi.org/10.1214/24-AOP1742.
[54]
Maximilian Katzmann. “About the analysis of algorithms on networks with underlying hyperbolic geometry”. PhD thesis. Universität Potsdam, 2023. doi: 10 . 25932 / PUBLISHUP - 58296. url: https://publishup.uni-potsdam.de/58296.
[55]
Marc Kaufmann, Kostas Lakis, Johannes Lengler, Raghu Raman Ravi, Ulysse Schaller, and Konstantin Sturm. “Rumour Spreading Depends on the Latent Geometry and Degree Distribution in Social Network Models”. In: SODA’26. 2026. doi: 10.1137/1.9781611978971.226. url: https://doi. org/10.1137/1.9781611978971.226.
[56]
Seri Khoury and Aaron Schild. “Breaking Barriers for Distributed MIS by Faster Degree Reduction”. In: STOC’26 (2026). doi: 10 . 1145 / 3798129 . 3800816. url: https : / / doi . org / 10 . 1145 / 3798129.3800816.
[57]
Seri Khoury and Aaron Schild. “Round Elimination via Self-Reduction: Closing Gaps for Distributed Maximal Matching”. In: FOCS’25 (2025). doi: 10.1109/FOCS63196.2025.00120. url: https: //doi.org/10.1109/FOCS63196.2025.00120.
[58]
Sándor Kisfaludi-Bak. “Hyperbolic intersection graphs and (quasi)-polynomial time”. In: SODA’20. 2020. doi: 10 . 1137 / 1 . 9781611975994 . 100. url: https : / / doi . org / 10 . 1137 / 1 . 9781611975994.100.
47
[59]
Marcos Kiwi and Dieter Mitsche. “A Bound for the Diameter of Random Hyperbolic Graphs”. In: ANALCO’15. 2015. doi: 10.1137/1.9781611973761.3.
[60]
Marcos Kiwi and Dieter Mitsche. “On the Second Largest Component of Random Hyperbolic Graphs”. In: SIAM Journal on Discrete Mathematics (2019). doi: 10.1137/18M121201X.
[61]
Marcos Kiwi and Dieter Mitsche. “Spectral gap of random hyperbolic graphs and related parameters”. In: The Annals of Applied Probability (2018). doi: 10.1214/17-aap1323.
[62]
Marcos Kiwi, Markus Schepers, and John Sylvester. “Cover and hitting times of hyperbolic random graphs”. In: Random Structures & Algorithms (2024). doi: 10.1002/rsa.21249.
[63]
Júlia Komjáthy, John Lapinskas, Johannes Lengler, and Ulysse Schaller. “Polynomial growth in degreedependent first passage percolation on spatial random graphs”. In: Electronic Journal of Probability (2024). doi: 10.1214/24-ejp1216. url: http://dx.doi.org/10.1214/24-EJP1216.
[64]
Júlia Komjáthy and Bas Lodewijks. “Explosion in weighted hyperbolic random graphs and geometric inhomogeneous random graphs”. In: Stochastic Processes and their Applications (2020). doi: 10.1016/ j.spa.2019.04.014. url: http://dx.doi.org/10.1016/j.spa.2019.04.014.
[65]
Eugene V. Koonin, Yuri I. Wolf, and Georgy P. Karev. Power Laws, Scale-Free Networks and Genome Biology. Springer US, 2006. doi: 10.1007/0- 387- 33916- 7. url: http://dx.doi.org/10. 1007/0-387-33916-7.
[66]
Dmitri Krioukov, Fragkiskos Papadopoulos, Maksim Kitsak, Amin Vahdat, and Marián Boguñá. “Hyperbolic Geometry of Complex Networks”. In: Physical Review E (2010). doi: 10.1103/PhysRevE. 82.036106.
[67]
Anton Krohmer. “Structures & algorithms in hyperbolic random graphs”. doctoralthesis. Universität Potsdam, 2016. url: https : / / publishup . uni - potsdam . de / frontdoor / index / index / docId/39597.
[68]
Fabian Kuhn, Thomas Moscibroda, Tim Nieberg, and Roger Wattenhofer. “Fast Deterministic Distributed Maximal Independent Set Computation on Growth-Bounded Graphs”. In: DISC’05. 2005. url: https://www.microsoft.com/en- us/research/publication/fast- deterministicdistributed-maximal-independent-set-computation-growth-bounded-graphs/.
[69]
Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. “Local Computation: Lower and Upper Bounds”. In: J. ACM (2016). doi: 10.1145/2742012. url: https://doi.org/10.1145/2742012.
[70]
Christoph Lenzen and Roger Wattenhofer. “MIS on trees”. In: PODC’11. 2011.
[71]
Nathan Linial. “Distributive graph algorithms Global solutions from local data”. In: FOCS’87. 1987. doi: 10.1109/SFCS.1987.20.
[72]
Nathan Linial. “Locality in Distributed Graph Algorithms”. In: SIAM Journal on Computing (1992). doi: 10.1137/0221015.
[73]
M. Luby. “A Simple Parallel Algorithm for the Maximal Independent Set Problem”. In: SIAM Journal on Computing (1986).
[74]
Yannic Maus and Janosch Ruff. “On Distributed Colouring of Hyperbolic Random Graphs”. In: SODA’26. 2026. doi: 10.1137/1.9781611978971.91. url: https://doi.org/10.1137/1. 9781611978971.91.
[75]
Y. Métivier, J. M. Robson, N. Saheb-Djahromi, and A. Zemmari. “An optimal bit complexity randomized distributed MIS algorithm”. In: Distributed Computing (2010). doi: 10.1007/s00446-010-0121-5. url: http://dx.doi.org/10.1007/s00446-010-0121-5.
48
[76]
Riccardo Michielan and Clara Stegehuis. “Cliques in geometric inhomogeneous random graphs”. In: J. Complex Networks (2021). doi: 10.1093/COMNET/CNAC002. url: https://doi.org/10. 1093/comnet/cnac002.
[77]
Anisur Rahaman Molla, Supantha Pandit, and Sasanka Roy. “Optimal deterministic distributed algorithms for maximal independent set in geometric graphs”. In: Journal of Parallel and Distributed Computing (2019). doi: 10.1016/j.jpdc.2019.05.012.
[78]
Tobias Müller and Merlijn Staps. “The Diameter of KPKVB Random Graphs”. In: Advances in Applied Probability (2019). doi: 10.1017/apr.2019.23.
[79]
M. Naor. “A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring”. In: SIAM J. Discrete Math. (1991).
[80]
M. E. J. Newman and Juyong Park. “Why social networks are different from other types of networks”. In: Phys. Rev. E (2003). doi: 10.1103/physreve.68.036122.
[81]
Fragkiskos Papadopoulos, Dmitri V. Krioukov, Marián Boguñá, and Amin Vahdat. “Greedy Forwarding in Dynamic Scale-Free Networks Embedded in Hyperbolic Metric Spaces”. In: INFOCOM’10. 2010. doi: 10.1109/INFCOM.2010.5462131.
[82]
David Peleg. Distributed computing: a locality-sensitive approach. 2000.
[83]
Sriram V. Pemmaraju and Talal Riaz. “Using Read-k Inequalities to Analyze a Distributed MIS Algorithm”. In: OPODIS’16. 2016. doi: 10.4230/LIPICS.OPODIS.2016.9. url: https://doi. org/10.4230/LIPIcs.OPODIS.2016.9.
[84]
Mathew Penrose. Random Geometric Graphs. Oxford University Press, 2003. isbn: 9780198506263.
[85]
Václav Rozhoň and Mohsen Ghaffari. “Polylogarithmic-time deterministic network decomposition and distributed derandomization”. In: STOC’20. 2020.
[86]
Johannes Schneider and Roger Wattenhofer. “An optimal maximal independent set algorithm for bounded-independence graphs”. In: Distributed Computing (2010). doi: 10.1007/s00446- 0100097-1. url: http://dx.doi.org/10.1007/s00446-010-0097-1.
[87]
M. Ángeles Serrano and Marián Boguñá. “Clustering in complex networks. I. General formalism”. In: Phys. Rev. E (2006). doi: 10.1103/PhysRevE.74.056114.
[88]
M. Ángeles Serrano, Dmitri Krioukov, and Marián Boguñá. “Self-Similarity of Complex Networks and Hidden Metric Spaces”. In: Physical Review Letters (2008). doi: 10.1103/physrevlett.100. 078701.
[89]
Ivan Voitalov, Pim van der Hoorn, Remco van der Hofstad, and Dmitri Krioukov. “Scale-free Networks Well Done”. In: Physical Review Research (2019). doi: 10.1103/PhysRevResearch.1.033034.
[90]
Duncan J. Watts and Steven H. Strogatz. “Collective dynamics of ‘small-world’ networks”. In: Nature (1998). doi: 10.1038/30918.
49
A
Luby’s Algorithm Retains a Polynomial Degree After Constant Rounds
In this section, we show that a standard Luby algorithm requires more than constant rounds so that the degree of every remaining vertex is at most 𝑛𝑜(1) (see Proposition 40 for a formal statement). Throughout the section, we call a vertex 𝑣 ∈ 𝑉 a leaf if deg(𝑣) = 1. We use the following fact of HRGs ([74, Lemma 10]). Lemma 37 (Layer-leaves). Let 𝐺 ∼ (𝑛, 𝛼, 𝐶) be a threshold hyperbolic random graph and let 𝑢 ∈ 𝑉 (𝐺) be a vertex in 𝐺 with radius 𝑟 ∈ 𝑅−𝜔(1). Moreover, let 𝑁0 ∶= 0 ∩𝑁 (𝑢) and let 𝐿0 (𝑢) ∶= {𝑣 ∈ 𝑁0 (𝑢) ∶ deg(𝑣) = 1}. Then, with non-vanishing probability, |𝐿0 (𝑢)| ∈ Θ(𝑛 ⋅ 𝑒 −𝑟/2 ). Let 𝑘, 𝑑 ∈ ℤ+ and let 𝑊 = {𝑤1 , 𝑤2 , … , 𝑤𝑘 } be a set of vertices. We say that 𝑊 is a similar degree path of length 𝑘 if the induced subgraph 𝐺[𝑊 ] is a path and if the degree of any vertex 𝑤 ∈ 𝑊 is deg(𝑤) ∈ Θ(𝑑). Moreover, we say that a vertex 𝑢 ∈ 𝑉 ⧵ 𝑊 with degree deg(𝑢) = 𝑑 has a similar degree path 𝑊 of length 𝑘, if 𝐺[𝑊 ∪ {𝑢}] is a path. The following lemma says that most vertices have a similar degree path, where the upper bound on 𝑟 guarantees expected degree at least polylogarithmic, while the lower bound ensures that the sectors contain polylogarithmically many vertices. Lemma 38 (Similar degree path). Let 𝐺 ∼ (𝑛, 𝛼, 𝐶) be a threshold hyperbolic random graph and let log 𝑛 log 𝑛 𝑢 ∈ 𝑉 (𝐺) be a vertex in 𝐺 with radius log 𝑛−log ≤ 𝑟 ≤ 2 log 𝑛 − 2 log 𝛼 1−𝛼 . Then, for any constant 𝑐 ∈ (1), 𝑢 −𝑟/2 has a similar degree path 𝑊 of length 𝑐 and degree Θ(𝑛 ⋅ 𝑒 ) w.e.h.p. In particular, the similar degree path 𝑊 is contained in the area {𝑥 ∈ 𝑅 ∶ 𝑟 − 1/1000 ≤ 𝑟(𝑥) ≤ 𝑟 and 𝜑(𝑢) ≤ 𝜑(𝑥) ≤ 𝜑(𝑢) + 6𝑐 ⋅ (1 − 1/1000)𝑒 𝑅/2−𝑟 }. Proof. Chosen with hindsight, let 𝜓 ∶= 2(1 − 1/1000)𝑒 𝑅/2−𝑟 and, w.l.o.g., let 𝜑(𝑢) = 0. Then consider the sector Φ ∶= {𝑥 ∈ 𝑅 ∶ 0 ≤ 𝜑(𝑥) ≤ 3𝑐 ⋅ 𝜓}, i.e., the sector that lies counter-clockwise to vertex 𝑢, where one ray of Φ intersects 𝑢. We partition Φ into 3𝑐 equally sized sub-sectors, such that for all 𝑖 ∈ [3𝑐 +1]⧵{0}, sector Φ𝑖 has angle 𝜓. Now, let 𝑖 ∶= Φ𝑖 ∩ (0 (𝑟) ⧵ 0 (𝑟 − 1/1000)). We show that for ∶= ⋃3𝑐 𝑖=1 , there exists a subset of vertices 𝑊 ⊆ 𝑉 ∩ , s.t. 𝐺[𝑊 ] induces the desired similar degree path of 𝑢 w.e.h.p. First, we note log 𝑛 that by Lemma 7, every vertex 𝑤 ∈ 𝑊 ∪ {𝑢} has degree 𝐄 [deg(𝑤)] ∈ Θ(𝑛 ⋅ 𝑒 −𝑟/2 ). Since 𝑟 ≤ 2 log 𝑛 − 2 log 1−𝛼 , and for every 𝑤 ∈ 𝑊 it holds 𝑟 − 1/1000 ≤ 𝑟(𝑤) ≤ 𝑟 a Chernoff and union bound reveals for all 𝑤 ∈ 𝑊 that deg(𝑤) ∈ Θ(deg(𝑢)) with probability 1 − 𝑛−𝜔(1) Next, we observe that the expected number of vertices in 𝑖 is 𝑛𝜓 𝐄 [|𝑉 ∩ 𝑖 |] = 𝑛𝜇(𝑖 ) = 𝜇(0 (𝑟) ⧵ 0 (𝑟 − 1/1000)) = Θ(1)𝑛 ⋅ 𝑒 𝑅/2−𝑟 ⋅ 𝑒 −𝛼(𝑅−𝑟) , 2𝜋 log 𝑛 by our choice of 𝜓 and Lemma 6. Using that hypothesis that 𝑟 ≤ 2 log 𝑛 − 2 log and 𝑅 = 2 log 𝑛 + 𝐶 we 1−𝛼 2 then have 𝐄 [|𝑉 ∩ 𝑖 |] ∈ Ω(log 𝑛). Using Poisson distribution for each 𝑖 and a union bound for 3𝑐 areas 𝑖 , we have that each 𝑖 contains a vertex with probability 1 − 𝑛−𝜔(1) . We proceed by showing that, given that each 𝑖 contains at least one vertex, 𝑢 has a similar degree path 𝑊 of length 𝑐, which finishes the proof. To this end, we use [51, Lemma 3.1] and by our angular width 𝜓, it follows for any 𝑥 ∈ 𝑖 and 𝑦 ∈ 𝑗 that dh (𝑥, 𝑦) ≤ 𝑅 if |𝑖 − 𝑗| ≤ 3 while dh (𝑥, 𝑦) > 𝑅 if |𝑖 − 𝑗| ≥ 5 since 𝑟 − 1/1000 ≤ 𝑟(𝑥), 𝑟(𝑦) ≤ 𝑟. Consequently, if for every 𝑖 where 𝑖 is divisible by 3 we include exactly one vertex 𝑤 ∈ 𝑉 ∩ 𝑖 in the set 𝑊 , this ensures that 𝐺[𝑊 ] induces a path of length 𝑐. Moreover, 𝑢 has an edge to the unique selected vertex 𝑤 ∈ 𝑉 ∩ 3 , but not to any 𝑤 ∈ 𝑉 ∩ 𝑖 if 𝑖 ≥ 6. It follows that 𝑊 is a similar degree path of length 𝑐 of 𝑢. Since every 𝑖 contains at least one vertex w.e.h.p. and all vertices 𝑤 ∈ 𝑊 have degree deg(𝑤) ∈ Θ(deg(𝑢)) w.e.h.p., a union bound over both events finishes the proof, where the ’in particular’ statement directly follows from our construction of 𝑊 .
We now show that an HRG has many vertices that have both polynomially many leaves and a similar degree path of constant length. This structure will be useful to show that Luby does not shatter an HRG in constant rounds.
50
Lemma 39 (Luby Obstruction). Let 𝐺 ∼ (𝑛, 𝛼, 𝐶) be a threshold hyperbolic random graph and let 𝜀 < 1 − 1/(2𝛼) be a constant larger than 0. Then, a.a.s. there exist a set of vertices 𝑈 (𝜀) ⊆ 𝑉 of size |𝑈 (𝜀)| ∈ Ω (𝑛1−1/2𝛼−𝜀 ), where a vertex 𝑢 ∈ 𝑈 (𝜀) has the following properties. 1. Degree of 𝑢: The degree of 𝑢 is deg(𝑢) ∈ Θ(𝑛𝜀/2 ). 2. Leaves of 𝑢: Vertex 𝑢 has Θ(𝑛𝜀/2 ) neighbours that are leaves. 3. Similar degree path of 𝑢: For any constant 𝑡 ∈ (1), 𝑢 has a similar degree path 𝑊 (𝑢) of length at least 2𝑡. Moreover, for any pair 𝑢, 𝑢′ ∈ 𝑈 (𝜀) it holds that for any pair 𝑣 ∈ 𝐿(𝑢)∪𝑊 (𝑢)∪{𝑢} and 𝑣′ ∈ 𝐿(𝑢′ )∪𝑊 (𝑢′ )∪{𝑢′ } that {𝑣, 𝑣′ } ∉ 𝐸(𝐺). 𝑛⋅2𝜋 1−1/2𝛼−𝜀 ∈ 𝑛Ω(1) due to our choice Proof. We partition the disk 𝑅 into ⌊ 𝑛1/(2𝛼)+𝜀 ⌋ =∶ 𝑘 sectors, (where 𝑘 ≥ 𝑛 of 𝜀 < 1 − 1/(2𝛼)), such that for 𝑖 ∈ [𝑘], a sector Φ𝑖 has angle 𝜙 ∈ Θ(𝑛1/(2𝛼)+𝜀 /𝑛). We consider one such sector Φ𝑖 and let 𝑋𝑖 be the indicator random variable that is 1 if Φ𝑖 contains a vertex 𝑢 with properties Item 1, Item 2 and Item 3. We first show that 𝐏 (𝑋𝑖 = 1) > 0. Thereafter, we show for 𝑋 ∶= ∑𝑘𝑖=1 𝑋𝑖 that 𝑋 ∈ Ω(𝑘) a.a.s. what proves our desired statement.
Item 1: Without loss of generality, let Φ𝑖 have bisector 0. Then, for 𝓁̂ ∶= ⌈𝜀 ⋅ log 𝑛⌉, let ∶= {𝑥 ∈ 𝓁̂ ∶ −𝑛𝛼⋅𝜀 /𝑛 < 𝜑(𝑥) < 𝑛𝛼⋅𝜀 /𝑛} ⊂ Φ𝑖 . Hence, using Equation (3), we obtain ̂
𝐄 [|𝑉 ∩ |] = 𝑛 ⋅ 𝜇() = Θ(1) ⋅ 𝑛𝛼⋅𝜀 ⋅ 𝑒 −𝛼 𝓁 ∈ Θ(1). Thus, since |𝑉 ∩ | follows a Poisson-distribution, we get ∶= {|𝑉 ∩ | = 1}.
𝐏 () > 0,
(27)
Next, condition on event and let let 𝑢 denote the unique vertex in 𝑉 ∩ . Then it follows 𝐏 (1 |) ∈ 1 − 𝑛−𝜔(1) ,
1 ∶= {deg(𝑢) ∈ Θ(𝑛𝜀/2 )},
(28)
by Equation (4) and a Chernoff-bound since 𝑢 ∈ 𝑉𝓁̂ where 𝓁̂ = ⌈𝜀 ⋅ log 𝑛⌉. Item 2:
Let |𝐿0 (𝑢)| ∶= |{𝑣 ∈ 𝑁0 (𝑢) ∶ deg(𝑣) = 1}| as in Lemma 37. Then, using Lemma 37 it follows 𝐏 (2 |) > 0,
2 ∶= {|𝐿0 (𝑢)| ∈ Θ(𝑛𝜀/2 )},
(29)
since 𝑢 is in layer 𝓁̂ = ⌈𝜀 log 𝑛⌉ and thus, 𝑟(𝑢) ≤ 𝑅 − ⌈𝜀 log 𝑛⌉. Item 3:
Applying Lemma 38, it follows that 𝐏 (3 |) ∈ 1 − 𝑛−𝜔(1) ,
3 ∶= {|𝑊 (𝑢)| ≥ 2𝑡},
(30)
and we remark that for event 3 , the vertices of 𝑊 (𝑢) are within an area ′ ∶= {𝑥 ∈ 𝑅 ∶ 𝑅 − 𝓁̂ − ̂ (1 + 1/1000) ≤ 𝑟(𝑥) ≤ 𝑅 − 𝓁̂ and 𝜑(𝑢) ≤ 𝜑(𝑥) ≤ 𝜑(𝑢) + 6𝑡 ⋅ (1 − 1/1000)𝑒 −𝑅/2+𝓁+1+1/1000 } by the ’in 1/(2𝛼)+𝜀 particular’ statement in Lemma 38. Thus, ⊂ Φ𝑖 , since Φ𝑖 has an angle of Θ(𝑛 /𝑛) while ′ spans an angle Θ(𝑛𝜀 /𝑛) ∈ 𝑜(𝑛1/(2𝛼)+𝜀 /𝑛), using that 𝑅 = 2 log 𝑛 + 𝐶, 𝑡 ∈ (1) and 𝓁̂ = ⌈𝜀 log 𝑛⌉. Our desired ’moreover’ statement then follows since for any pair of sectors Φ𝑖 and Φ𝑗 where ∩ 1 ∩ 2 ∩ 3 occur, we consider 𝑢 ∈ 𝑉 ∩ Φ𝑖 and 𝑢′ ∈ 𝑉 ∩ Φ𝑗 to be the vertices occurring due to event and it holds for any 51
pair 𝑣 ∈ 𝐿(𝑢) ∪ 𝑊 (𝑢) ∪ {𝑢} and 𝑣′ ∈ 𝐿(𝑢′ ) ∪ 𝑊 (𝑢′ ) ∪ {𝑢′ } that {𝑣, 𝑣′ } ∉ 𝐸(𝐺). This is since every object associated with 𝑢 that is contained in Φ𝑖 , and distinct sector Φ𝑗 are separated by an angular distance exceeding the maximal adjacency angle of Lemma 4 for any pair of vertices 𝑣 ∈ 𝐿(𝑢) ∪ 𝑊 (𝑢) ∪ {𝑢} and 𝑣′ ∈ 𝐿(𝑢′ ) ∪ 𝑊 (𝑢′ ) ∪ {𝑢′ }; there are no edges between distinct structures belonging to different sectors. Subsequently, if 𝑋 ∈ Θ(𝑘) a.a.s. this finishes the proof. To obtain this result, note first that 𝐏 (𝑋𝑖 = 1) = 𝐏 ( ∩ 1 ∩ 2 ∩ 3 ) . Then, using Equation (27), Equation (28), Equation (29) and Equation (30) in conjunction with a union bound and conditional probabilities, we have that 𝐏 ( ∩ 1 ∩ 2 ∩ 3 ) ≥ (1 − 𝐏 (1𝐶 | ) − 𝐏 (2𝐶 | ) − 𝐏 (3𝐶 | )) 𝐏 () > 0, and we conclude that 𝐄 [𝑋 ] ∈ Θ(𝑘) ∈ 𝑛Ω(1) . We wrap up the proof as follows: we show for any 𝑖 ≠ 𝑗 that 𝑋𝑖 and 𝑋𝑗 are independent so that a Chernoff bound yields 𝑋 ∈ Ω(𝑘). To this end, we show that events , 1 , 2 , and 3 in a sector Φ𝑖 only depends on the randomness of the Poisson point process in Φ𝑖 . Event :
For event this is immediate since ⊂ Φ𝑖 .
Event 1 : For event 1 , note that by Equation (22) there is no vertex in 0 (𝑟 ∗ ) a.a.s. where 𝑟 ∗ = 𝑅 − log 𝑛/𝛼 − log log 𝑛/2. Thus, since 𝑢 ∈ 𝑉𝓁̂ and 𝓁̂ = ⌈𝜀 log 𝑛⌉, the sector that we need to reveal to obtain the degree of 𝑢 has angle at most ∗
̂ 𝑛𝛼⋅𝜀 /𝑛 + 2𝜃𝑅 (𝑟 ∗ , 𝑅 − 𝓁̂ − 2) ∈ (𝑒 (𝓁−𝑟 )/2 ) ∈ 𝑜(𝜙) a.a.s.,
using 𝜙 ∈ Θ(𝑛1/(2𝛼)+𝜀 /𝑛) and Lemma 4 in conjunction with Remark 5. That is, a smaller angle than the angle spanned by Φ𝑖 . Event 2 : By a similar argument we get for 2 , using that a leaf 𝑣 ∈ 𝐿0 (𝑢) has radius 𝑟(𝑣) ≥ 𝑅 − 1 and thus 𝛿𝜑 (𝑢, 𝑣) ≤ 𝜃𝑅 (𝑅 − 𝓁̂ − 2, 𝑟(𝑣)) ∈ (𝑛−𝜀/2 ), a.a.s. that we do not require to reveal a sector with an angle that is larger than (𝑛−𝜀/2 ) + 𝜃𝑅 (𝑅 − 1, 𝑟 ∗ ) ∈ 𝑜(𝜙) using Lemma 4. Event 3 :
For event 3 , recall that we remarked that the vertices of 𝑊 (𝑢) are within an area
̂ ̂ ′ ∶= {𝑥 ∈ 𝑅 ∶ 𝑅−𝓁−(1+1/1000) ≤ 𝑟(𝑥) ≤ 𝑅−𝓁̂ and 𝜑(𝑢) ≤ 𝜑(𝑥) ≤ 𝜑(𝑢)+6𝑡⋅(1−1/1000)𝑒 −𝑅/2+𝓁+1+1/1000 }.
Thus, a.a.s., we need to reveal a sector of angle at most (𝑒 −𝑅/2+𝓁̂) + 𝜃𝑅 (𝑟 ∗ , 𝑅 − 𝓁̂ − 2). Using Lemma 4, 𝓁̂ = ⌈𝜀 log 𝑛⌉ and 𝑟 ∗ = 𝑅 − log 𝑛/𝛼 − log log 𝑛/2, this angle is again 𝑜(𝜙) and thus, also completely contained within sector Φ𝑖 . Finally, using that 𝐄 [𝑋 ] ∈ Θ(𝑘) ∈ 𝑛Ω(1) , it follows by a Chernoff bound 𝐏 (0 (𝑟 ∗ ) ∩ 𝑉 = ∅) 𝐏 (𝑋 ∈ Ω(𝑘)|0 (𝑟 ∗ ) ∩ 𝑉 = ∅) ∈ (1 − 𝑜(1)) ⋅ (1 − 𝑒 −Ω(𝑘) ). That is, |𝑈 (𝜀)| ∈ Ω(𝑘) ∈ Ω (𝑛1−1/2𝛼−𝜀 ) a.a.s. as desired.
52
We now use Lemma 39 to show that for any constant 𝑡 ∈ (1) number of iterations of Luby’s algorithm, there remains a vertex 𝑢 with polynomial degree a.a.s. To formalise this, we write 𝑉(𝑡) for the set of vertices that are not removed by Luby after iteration 𝑡, let 𝐺𝑡 = [𝑉𝑡 ] and Δ(𝐺𝑡 ) ∶= max𝑣∈𝑉𝑡 deg𝑡 (𝑣) where for 𝑣 ∈ 𝑉𝑡 we used deg𝑡 (𝑣) ∶= |{𝑢 ∈ 𝑁 (𝑣) ∶ 𝑢 ∈ 𝑉𝑡 }|. Proposition 40. Let 𝐺 ∼ (𝑛, 𝛼, 𝐶) be a threshold hyperbolic random graph and let 𝑡 ∈ (1) be any fixed constant. Then Δ(𝐺𝑡 ) ∈ 𝑛Ω(1) a.a.s. 1− 1
2𝛼 Proof. With hindsight, we set 𝜀 ∶= 2𝑡(𝑡+2) and consider the set of vertices 𝑈 (𝜀) of Lemma 39. We show that after 𝑡 rounds there exists a.a.s. a vertex 𝑢 ∈ 𝑈 (𝜀) such that deg𝑡 (𝑢) ∈ 𝑛Ω(1) . To this end, for 𝑖 ∈ [𝑡], let 𝐿(𝑖) (𝑢) ∶= {𝑣 ∈ 𝑁 (𝑢) ∩ 𝑉(𝑖) ∶ deg(𝑣) = 1} (the “remaining leaves” of 𝑢 after
28 round 𝑖), 𝑊(𝑖) (𝑢) ∶= (⋃2(𝑡−𝑖) 𝑗=1 {𝑤𝑗 }) ∩ 𝑉(𝑖) (the “remaining” similar degree path of 𝑢 after round 𝑖) and we define the random variable
𝐾(𝑖) ∶= |{𝑢 ∈ 𝑈 (𝜀) ∩ 𝑉(𝑖) ∶ |𝐿(𝑖) (𝑢)| ∈ 𝑛Ω(1) and |𝑊(𝑖) (𝑢)| ≥ 2(𝑡 − 𝑖)}|.
(31) 1 1− 2𝛼
Note that if 𝐾(𝑡) ≥ 1 a.a.s. this is sufficient to prove our desired statement and that 𝐾(0) ∈ Ω 𝑛1−1/2𝛼− 2𝑡(𝑡+2) ( ) a.a.s. due to Lemma 39 and our choice of 𝜀. In order to prove 𝐾(𝑡) ≥ 1 a.a.s., we will use the following claim, which tells us that if 𝐾(𝑖) is polynomial in 𝑛, then so is 𝐾(𝑖+1) a.a.s. given that 𝑖 < 𝑡. 1− 1
2𝛼 Claim 41. Let 𝜀 ∶= 2𝑡(𝑡+2) . Then, for 𝑖 ∈ [𝑡] it holds
ℙ (𝐾(𝑖+1) ∈ Ω (𝑛1−1/2𝛼−𝜀−(𝑖+1)𝜀(2𝑡+1) ) |𝐾(𝑖) ∈ Ω (𝑛1−1/2𝛼−𝜀−𝑖𝜀(2𝑡+1) )) ∈ 1 − 𝑜(1). Proof of claim. Let 𝑈(𝑖) = {𝑢 ∈ 𝑈 (𝜀) ∩ 𝑉(𝑖) ∶ |𝐿(𝑖) (𝑢)| ∈ 𝑛Ω(1) and |𝑊(𝑖) (𝑢)| ≥ 2(𝑡 − 1)}, i.e., |𝑈(𝑖) | = 𝐾(𝑖) . We analyse one round of Luby on 𝑈(𝑖) . To this end, we fix a vertex 𝑢 ∈ 𝑈(𝑖) and consider the following events: 2𝑡 (𝑢 ) Vertex 𝑢 draws a random number for Luby that lies in the open interval (1 − 2𝑡+1 𝑛𝜀 , 1 − 𝑛𝜀 ).
(path ) For 𝑗 ∈ [2(𝑡 − 𝑖) + 1] ⧵ {0}, vertex 𝑤𝑗 ∈ 𝑊 (𝑢) 29 draws a random number for Luby that lies in the open 2𝑡−𝑖 interval (1 − 2𝑡+1−𝑖 𝑛𝜀 , 1 − 𝑛𝜀 ). (leaves ) Any vertex 𝑣 ∈ 𝑁 ((𝑊 (𝑢) ∪ {𝑢}) ⧵ (𝑊 (𝑢)) ∪ {𝑢}) draws a random number for Luby that lies in the open interval (0, 1 − 2𝑡+1 𝑛𝜀 ). Observe that if event 𝑢 ∩ path ∩ leaves =∶ occurs, then 𝑢 ∈ 𝑈(𝑖+1) . To see this, note that all leaves of 𝑢 draw a smaller number than 𝑢 and 𝑢 is not removed as it is the largest number among neighbours, except for 𝑤1 ∈ 𝑁 (𝑢), which does not join the independent set since 𝑤2 ∈ 𝑁 (𝑤1 ) draws a larger number than 𝑤1 . This “chain” of events continues for the entire similar degree path 𝑊(𝑖) (𝑢) by the intersection of the two events path and leaves . Hence, only the "terminal" vertex 𝑤2(𝑡−𝑖) of 𝑊(𝑖) (𝑢) that might join the independent set, removing all its neighbours including the neighbour 𝑤2(𝑡−𝑖−1) but no other vertex of the similar degree path 𝑊(𝑖) (𝑢). Since 𝑢 has polynomially many leaves, all necessary conditions for 𝑢 ∈ 𝑈(𝑖+1) are fulfilled. We continue by lower bounding the probability of event . Event 𝑢 :
Since the range of the open interval is 𝑛−𝜀 we have ℙ (𝑢 ) = 𝑛−𝜀 .
28 29
Recall that 𝑊 (𝑢) ∶= {𝑤1 , 𝑤2 , … 𝑤𝑘 } is the similar degree path of 𝑢 such that for 𝑗 ∈ [𝑘] it holds {𝑤𝑗 , 𝑤𝑗+1 } ∈ 𝐸. Where 𝑤𝑗 ∈ 𝑊 (𝑢) is the 𝑗-th vertex of the similar degree path 𝑊 (𝑢) such that {𝑢, 𝑤1 } ∈ 𝐸 and {𝑤𝑗 , 𝑤𝑗+1 } ∈ 𝐸.
53
(32)
Event path : Similar the event 𝑢 , the range of the interval of each random number is 𝑛−𝜀 . Since each draw is independent and we draw at most 2𝑡 random numbers, we obtain ℙ (path ) ≥ 𝑛−2𝑡𝜀 .
(33)
Event leaves : Since for any 𝑤 ∈ 𝑊 (𝑢) ∪ {𝑢} we have deg(𝑤) ∈ (𝑛𝜀/2 ), we can upper bound 𝑚 ∶= |𝑁 ((𝑊 (𝑢) ∪ {𝑢}) ⧵ (𝑊 (𝑢)) ∪ {𝑢})| ∈ (𝑛𝜀/2 ) using that |𝑊 (𝑢)| is constant since 𝑡 ∈ (1). Applying this with the fact that the desired event for every vertex 𝑣 of drawing a random number within the interval 2𝑡+1 (0, 1 − 2𝑡+1 𝑛𝜀 ) has probability 1 − 𝑛𝜀 , we obtain via independence among the events for each 𝑣 𝑚
ℙ (leaves ) ≥
(
1−
2𝑡 + 1 ∈ Ω(1), 𝑛𝜀 )
(34)
where we used that 𝑡 is constant and 𝑚 ∈ (𝑛𝜀/2 ). Putting Equation (32), Equation (33) and Equation (34) together and using independence we then obtain ℙ () = ℙ (𝑢 ∩ path ∩ leaves ) ∈ Ω(𝑛−(2𝑡+1)𝜀 ).
(35)
To finish the proof of our claim, let 𝑋𝑢 be the indicator random variable that event occurs for vertex 𝑢 ∈ 𝑈(𝑖) and define the random variable 𝑋 ∶= ∑𝑢∈𝑈(𝑖) 𝑋𝑢 ≥ 𝐾 (𝑖 + 1). We then get by linearity of expectation 𝔼 [𝑋 ] ≥ ℙ () ⋅ |𝑈(𝑖) | ∈ Ω (𝑛1−1/2𝛼−𝜀−(𝑖+1)𝜀(2𝑡+1) ) by the assumption that 𝐾(𝑖) ∈ Ω (𝑛1−1/2𝛼−𝜀−𝑖𝜀(2𝑡+1) ) and Equation (35). Since the random variables 𝑋𝑢 are independent by the ’moreover’ statement of Lemma 39, a Chernoff bound gives the desired result that 𝐾(𝑖+1) ∈ Ω (𝑛1−1/2𝛼−𝜀−(𝑖+1)𝜀(2𝑡+1) ) a.a.s. ■ 1 1− 2𝛼
Now, using that 𝐾(0) ∈ Ω 𝑛1−1/2𝛼− 2𝑡(𝑡+2) a.a.s. by Lemma 39, and applying Claim 41iteratively for ( ) 𝑡 ∈ (1) rounds, a union bound over the 𝑡 induction steps yields 1 1− 2𝛼
ℙ (𝐾(𝑡) ∈ Ω (𝑛1−1/2𝛼−𝜀−(𝑡+1)𝜀(2𝑡+1) )) ≥ 1 − ℙ 𝐾(0) ∉ Ω 𝑛1−1/2𝛼− 2𝑡(𝑡+2) ( ( )) 𝑡−1
− ℙ ⋃ 𝐾(𝑖+1) ∉ Ω (𝑛1−1/2𝛼−𝜀−(𝑖+1)𝜀(2𝑡+1) ) |𝐾(𝑖) ∈ Ω (𝑛1−1/2𝛼−𝜀−𝑖𝜀(2𝑡+1) ) ( 𝑖=0 ) ∈ 1 − 𝑜(1). 1− 1
2𝛼 > 0, 𝐾(𝑡) ∈ 𝑛Ω(1) a.a.s. This finishes the proof since by our choice 𝜀 ∶= 2𝑡(𝑡+2)
B
Concentration Bounds
Lemma 42 (Chernoff bound). For 𝑖 ∈ [𝑘], let 𝑋𝑖 ∈ {0, 1} be independent random variables and 𝑋 = ∑𝑖 𝑋𝑖 . Then 3 𝔼 [𝑋 ] 1 𝔼 [𝑋 ] ℙ 𝑋 ≥ 𝔼 [𝑋 ] ≤ exp − and ℙ 𝑋 ≤ 𝔼 [𝑋 ] ≤ exp − . ) ( 12 ) ( ) ( ( 2 2 8 ) The following is a Chernoff 30 type deviation bound (see e.g. [62, Lemma 6]) which is necessary for the distribution of vertices as it follows a Poisson point distribution. Lemma 43 (Poisson Chernoff bound). Let 𝑋 have a Poisson distribution with mean 𝐄 [𝑋 ]. Then for 𝑎 ≥ 𝑒 3/2 , 1 𝐏 𝑋 ≤ 𝐄 [𝑋 ] ≤ exp (−𝐄 [𝑋 ] /8) and 𝐏 (𝑋 ≥ 𝑎 ⋅ 𝐄 [𝑋 ]) ≤ exp (−𝑎 ⋅ 𝐄 [𝑋 ] /2). ( ) 2 30
For convenience, we refer to both as a Chernoff bound whenever using either of the two.
54
C
Round Elimination Lower Bounds with General Error Probabilities
We extend Theorem 7.1 from [6] that can provide lower bounds for randomised algorithms in the LOCAL model for problems that meet the prerequisites of the theorem. We emphasise that we do not claim any major contribution here; we only change their theorem to work with a general error probability instead of a hard-coded error probability of 1/𝑛. Thus, we refer to [6] for more background and formal definitions, and here we focus on the differences in the proof. In their work, graph problems are modelled using the black-white formalism, where a locally checkable problem Π = (Σ, , ) is defined by a label space Σ, node (white) constraints , and hyperedge (black) constraints [6]. The goal in some computational models, like the LOCAL model, is to compute a labelling that satisfies all constraints. MIS and MM can both easily be modelled in this formalism [6, 30]. Within this framework, Round Elimination (RE) acts as a mechanical operator, denoted by ((Π)), which transforms a given problem into a new variant that is exactly one round easier to solve [6]. In a nutshell, if one starts with a problem Π0 and applies this operator 𝑡 times and obtains a problem Π𝑡 that cannot be solved in 0 rounds, one obtains a 𝑡 round lower bound for Π0 . However, as analysed in [6], the allowed error probabilities also increase with each step of applying the operator and also the label space required to describe the problems increases doubly exponentially with each naïve application of the operator. Thus, to prevent the state space from expanding uncontrollably with each iteration, a relaxation is applied. A relaxation is a mapping to a structurally simpler problem Π′ where any valid solution for Π remains a valid solution for Π′ [6]. The label complexity function 𝑓 (Δ) serves as a strict upper bound on the size of the label alphabet (|Σ| ≤ 𝑓 (Δ)) across all intermediate problems and their relaxations throughout a sequence [6]. The main challenge is finding these relaxations such that the label complexity remains small and such that the sequence is long. For MIS and MM, one can limit the label complexity to 2Δ+1 and for MM to 5 while providing sequences of length Θ(Δ) [6, 30] (see Lemma 25). The following theorem implies that such round elimination lower bound sequences provide lower bounds for solving the respective problem in the randomised LOCAL model with a certain error probability 𝑝. Theorem 44 (Extension of Theorem 7.1 in [6]). Let Π0 → Π1 → ⋯ → Π𝑡 be a sequence of problems. Assume that, for all 0 ≤ 𝑖 < 𝑡, and for some function 𝑓 , the following holds: • There exists a problem Π′𝑖 that is a relaxation of (Π𝑖 ); • Π𝑖+1 is a relaxation of (Π′𝑖 ); • The number of labels of Π𝑖 , and the ones of Π′𝑖 , are upper bounded by 𝑓 (Δ). Also, assume that Π𝑡 has at most 𝑓 (Δ) labels and is not 0-round solvable in the deterministic port numbering model, even if the port numbering assignment satisfies some local constraints 𝐶 port . Then, Π0 requires { } Ω (min 𝑡, logΔ 𝑛, logΔ log 1/𝑝 − logΔ log 𝑓 (Δ) ) rounds in the randomised LOCAL model with local error probability 𝑝, even if the port numbering satisfies some local constraints 𝐶 port . Proof. The proof is almost verbatim along the proof of the almost identical claim in [6, Theorem 7.1]. Thus, we focus on the changes to their proof that are limited to the following two aspects: • Change 1: In their proof, the error probability is hardcoded to 𝑝 = 1/𝑛. This is done in [6, A.5]. Instead, doing similar calculations with a general parameter 𝑝 for the error probability leads to the following claim:
55
Modified A.5: Let Π0 → Π1 → ⋯ → Π𝑡 be a sequence of problems satisfying the conditions of Theorem 44. Any randomised algorithm in the port numbering model 31 running in strictly less than 1 (logΔ (log(1/𝑝)) − logΔ log 𝑓 (Δ))} rounds must fail with probability at least 𝑝. min{𝑡, 10 Proof. Applying [6, Lemma A.4], after 𝑡 rounds the error probability of any randomised algorithm is 𝑝Error ≥
1 1 ≥ 𝑝, ≥ 10𝑡 log(1/𝑝)/ log 𝑓 (Δ) 𝑓 (Δ) 𝑓 (Δ)Δ
1 where in the second step we used our hypothesis 𝑡 < 10 (logΔ (log(1/𝑝)) − logΔ log 𝑓 (Δ)). So we obtain 𝑝Error ≥ 𝑝 as desired.
• Change 2: In the proof of [6, A.6], the previous claim is lifted to the LOCAL model using an indistinguishability argument. This argument only works if nodes cannot see the whole graph, requiring to cap the lower bound at Ω(logΔ 𝑛), which is the diameter of an 𝑛-node Δ-regular tree. In their work, this does not appear in their theorem as the cap is always larger than the bound logΔ (log(1/𝑝)) − logΔ log 𝑓 (Δ)) imposed when used with a hardcoded 𝑝 = 1/𝑛. Thus, for our theorem, the lower bound cannot exceed logΔ 𝑛, to which we adjust by adding it as a third argument in the min function. Modified A.6: Let Π0 → Π1 → ⋯ → Π𝑡 be a sequence of problems satisfying the conditions ofTheorem 44. Any randomised algorithm running in the LOCAL that { model, in Δ-regular balanced trees of 𝑛 nodes, } fails with probability at most 𝑝, requires Ω (min 𝑡, logΔ (log(1/𝑝)) − logΔ log 𝑓 (Δ), logΔ 𝑛 ) rounds. Note that this is exactly our desired statement Theorem 44.
D
Truncating Angular Coordinates
By the following lemma, (log 𝑛) bits per angular coordinate suffice so that each angular coordinate is unique w.h.p. Lemma 45. Let 𝐺 be a threshold hyperbolic random graph and for any pair of vertices 𝑢, 𝑣 ∈ 𝑉 (𝐺), let 𝜑𝑏 (𝑢) and 𝜑𝑏 (𝑣) be the first 𝑏 random bits of the angular coordinates 𝜑(𝑢) and 𝜑(𝑣) respectively. Then, for any pair 𝑢, 𝑣, any constant 𝑐 > 0 and 𝑏 = ⌈𝑐 ⋅ log 𝑛⌉, it holds 𝜑𝑏 (𝑢) ≠ 𝜑𝑏 (𝑣) with probability 1 − (𝑛−𝑐+5/2 ). Proof. Throughout the proof, we work with the binomial model of hyperbolic random graphs, in which the number of vertices is fixed to be 𝑛. At the end of the proof, the result is transferred to the Poisson model with 𝔼[𝑁 ] = 𝑛, incurring only a minor additional error probability (see also [54, §3.3.4, Lemma 3.9] for a detailed discussion). Let 𝑏 = ⌈𝑐 ⋅ log 𝑛⌉ as given by our hypothesis and let be the event that there exists a pair of vertices 𝑢, 𝑣 ∈ [𝑛] where 𝜑𝑏 (𝑢) = 𝜑𝑏 (𝑣). Since the angular coordinates are sampled independently and uniformly from [0, 2𝜋), the first 𝑏 bits of every angular coordinate form an independent uniformly distributed bit string in {0, 1}𝑏 . Hence, for every fixed pair of distinct vertices 𝑢, 𝑣 ∈ [𝑛] we have 𝐏 (𝜑𝑏 (𝑢) = 𝜑𝑏 (𝑣)) = 2−𝑏 . Subsequently, it holds for our "collision" event by a union bound 𝐏 () ≤
𝑛 ⋅ 2−𝑏 ∈ (𝑛−𝑐+2 ), (2)
where in the last step we plugged in 𝑏 = ⌈𝑐 ⋅ log 𝑛⌉. We then obtain the desired probability bound by the transfer from the binomial model to Poisson [54, Lemma 3.9] which yields 𝐏 () ⋅ (𝑛1/2 ) ∈ (𝑛−𝑐+5/2 ). 31
See [6] for the precise definition of the port numbering model.
56