Proof. By our hypothesis that \(\mathop{\mathrm{d_h}}(x,z) \leq R\) and \(\mathop{\mathrm{d_h}}(y,z) \leq R\), it follows for the angular distance between \(x\) and \(y\) by 1 that \[\begin{align} \delta_\varphi(x,y) \leq \theta_R(r(x), r(z)) + \theta_R(r(y), r(z)) \leq 2\pi\sqrt{e^{R-r(x)-r(z)}}, \end{align}\] since \(r(x) \leq r(y)\) and using [rmk:theta-monotonicity]. Consequently, using our hypothesis that \(r(z) \geq r(y) + 2\log(2\pi)\), it follows \[\begin{align} \delta_\varphi(x,y) \leq \sqrt{e^{R-r(x)-r(y)}} \leq \theta_R(r(x), r(y)), \end{align}\] and thus, by 1 we have \(\mathop{\mathrm{d_h}}(x,y) \leq R\) as desired. ◻

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 \(U_{(1)}\). Consequently, no such vertex joins the independent set in the first step.

To this end, let \(c(C, \alpha) \mathrel{\vcenter{:}}= 100 + |C| + 2\log(1/(\alpha - 1/2))\) chosen with hindsight, and consider any vertex \(u \in V \cap \mathcal{B}_0(R - {8\log\log n} - c(C, \alpha))\). Then, for \(u\) it holds via 3 that \[\begin{align} \mathbf{E}\left[\deg(u)\right] &\geq \frac{(1-o(1))\alpha}{\pi(\alpha - 1/2)} e^{(c(C, \alpha) - C)/2} \log^{4}n\\ &\geq 10000 \log^{4}n, \end{align}\] by our choice of \(c\). Thus, a Chernoff-bound (24) and union bound yield that for any \(u \in V \cap \mathcal{B}_0(R - {8\log\log n} - c(C, \alpha))\), that \(\deg(u) > \lceil1000\log^{4} n \rceil\) w.e.h.p.

Analogously, we get for any vertex \(u \in V \cap \mathcal{D}_R \setminus \mathcal{B}_0(R - {8\log\log n} + c(C, \alpha))\) that \[\begin{align} \mathbf{E}\left[\deg(u)\right] & \leq \frac{(1+o(1))\alpha}{(\alpha - 1/2)} e^{-(c(C, \alpha) + C)/2} \log^{4}n\\ & \leq \frac{\log^{4} n}{10000} . \end{align}\] Another combination of Chernoff bound with a union bound then reveals that for any \(u \in V \cap \mathcal{D}_R \setminus \mathcal{B}_0(R - {8\log\log n} + c(C, \alpha))\) that \(\deg(u) < \lfloor\frac{\log^{4} n}{1000}\rfloor\) w.e.h.p. This concludes the proof for [item:ring].

We now turn to the second point of the lemma. Consider a sector \(\Phi\) with angle \(\phi = \log ^{16\alpha }(n) /n\). W.l.o.g. let \(\Phi\) have bisector \(0\). Then, let \(\hat{\ell} = \lceil 8\log\log n + 2\log(\alpha - 1/2) - C \rceil\), \(\hat{\phi} = \log^{10\alpha}(n)/n\) and consider the area \(\mathcal{S} := \{x \in \mathcal{L}_{\hat{\ell}} : 2\pi - \hat{\phi} /2 \leq \varphi(x) \leq \hat{\phi}/2 \}\) (see also 6b for a sketch). We say \(\Phi\) is active if \(I_{(1)} \cap \mathcal{S} \neq \emptyset\), i.e., there is a vertex in the area \(\mathcal{S}\) that joins the independent set after the first step of HRG-Shattering-MIS.

Now, partition the disk \(\mathcal{D}_R\) into \(\lceil 2\pi n \cdot \log ^{-28\alpha } n\rceil =: k\) sectors such that each sector has angle \(\psi \in \Theta( \log ^{28\alpha } (n)/n)\). Note that if each such sector contains at least one vertex that joins the independent set \(I_{(1)}\), then it also holds for any sector with angle at least \(\frac{\log^{30\alpha}n}{n}\) that there exists a vertex that is in \(I_{(1)}\) as desired for [item:active-sector].

To show that this holds with the desired probabilistic guarantee, fix any sector \(\Psi\) with angle \(\psi\) and partition \(\Psi\) into \(k' \in \Theta(\log ^{12\alpha }n)\) sectors, such that each sector has angle \(\phi = \log ^{16\alpha }(n) /n\). For the \(i\)-th sector with angle \(\phi\), we write \(\Phi_i\) and let \(X_i\) be the indicator random variable that is \(1\) if the \(i\)-th sector is active. Moreover, let \(X = \sum_{i}^{k'}{X_i}\) so that by linearity of expectation the expected number of active sectors with angle \(\phi\) in \(\Psi\) is \[\mathbb{E}\left[X\right] = k' \cdot\mathbb{E}\left[X_i\right] \in \Omega(\log n^{12\alpha - 4}n) \in \omega(\log n),\] by applying Claim [claim:active-sector] and using that \(\alpha > 1/2\). Next, for any pair of sectors \(\Phi_i\) and \(\Phi_j\), we show that \(X_i\) and \(X_j\) are independent w.e.h.p.

To see this, recall that \(\Phi_i\) is active if the area \(\mathcal{S}_i \subset \Phi_i\) with angle \(\hat{\phi} = \log^{10\alpha}(n)/n\) contains a vertex that draws the largest ID among active neighbours. W.l.o.g. let \(\Phi_i\) have bisector \(0\). Moreover, using [item:ring], any active vertex \(v\) has radius \(r(v) \in R - 8\log\log n - \Theta(1)\) w.e.h.p. Hence, using 1 in conjunction with [rmk:theta-monotonicity], any active vertex \(v\) that is a neighbour of \(u \in V \cap \mathcal{S}_i\) has angle \[\varphi(v) \leq \hat{\phi} + \theta_R(r(u) , r(v)) \in \mathcal{O}\left(\frac{\log^8 n +\log^{10\alpha} n }{n} \right) \in o(\phi) \text{ w.e.h.p.},\] where the last step follows since \(\psi = \log ^{16\alpha }(n) /n\) and \(\alpha > 1/2\). Consequently the event only depends on the randomness in \(\Phi_i\) w.e.h.p. A union bound over \(k'\) sectors with angle \(\phi\) shows that this also holds for all \(k'\) \(\Phi\)-sectors in sector \(\Psi\) w.e.h.p.

Thus, using that for any pair of sectors \(\Phi_i, \Phi_j \subset \Psi\) the respective random variables \(X_i\) and \(X_j\) are independent w.e.h.p. and using \(\mathbb{E}\left[X\right] \in \omega(\log n)\), we obtain via a Chernoff bound that \(\Psi\) contains at least \(1\) vertex that is in \(I_{(1)}\) w.e.h.p. A union bound over the \(k \in o(n)\) \(\Psi\)-sectors with angle \(\psi\) wraps up the proof since every sector with angle \(\psi \in \Theta(\log^{28\alpha}(n)/n) \in o(\log^{30\alpha}(n)/n)\) contains a vertex of \(I_{(1)}\) w.e.h.p. ◻

Proof. Consider the annulus \(\mathcal{A}' := \mathcal{D}_R\setminus \mathcal{B}_0(R - 4 \log\log n - C)\). Then, by 3, any vertex \(v \in V \cap (\mathcal{D}_R\setminus\mathcal{A}' )\) has expected degree \(\mathbf{E}\left[\deg(v)\right] \in \Omega(\log^2 n)\). Using a Chernoff- and a union bound, all vertices outside the annulus \(\mathcal{A}'\) have a degree larger than \(\lceil \log^{3/2}(n)\rceil\) w.e.h.p. Hence, all vertices that are active in the second step of HRG-Shattering-MIS are within the annulus \(\mathcal{A}'\), i.e., \(U_{(2)} \subseteq V_{(1)} \cap \mathcal{A}'\) w.e.h.p.

Now, using \(r= R- \log\log n\) as defined in our lemma statement, fix a vertex \(u \in V_{(1)} \cap \mathcal{B}_0(r)\), 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 \(v\) in the neighbourhood of \(u\), such that \(v\) lies in the annulus \(\mathcal{A}'\) and \(v\) was removed after the first step of HRG-Shattering-MIS, i.e., \((N(u) \cap \mathcal{A}' )\setminus (V \setminus V_{(1)}) \neq \emptyset\) (see also 7a), and (2) non of the neighbours of \(u\), that lie in annulus \(\mathcal{A}'\) was removed after the first step of HRG-Shattering-MIS, i.e., \((N(u) \cap \mathcal{A}' )\setminus (V \setminus V_{(1)}) = \emptyset\).

Case 1 [\((N(u) \cap \mathcal{A}' )\setminus (V \setminus V_{(1)}) \neq \emptyset\)]: Consider a vertex \(v \in (N(u) \cap \mathcal{A}' )\setminus (V \setminus V_{(1)})\). Since \(v \notin V_{(1)}\), either (a) \(v\) is in the independent set after the first step, \(v \in I_{(1)}\), or (b) \(v\) has a neighbour \(w \in I_{(1)}\) that is in the independent set after the first step. Using 6, no vertex in the set \(I_{(1)}\) is in the annulus \(\mathcal{A}'\) w.e.h.p. and thus, case (a) does not occur w.e.h.p. Hence, only case (b) remains (see 7a for a sketch). Using again 6, it follows that vertex \(w \in N(v) \cap I_{(1)}\) has radius \(r(w) \leq R - 8\log\log n + c\) w.e.h.p. Then, since \(v \in V \cap \mathcal{A}'\), it holds \(r(v) \geq R - 4\log\log n\) - C. Thus, using 5, \(u \in N(w)\) since \(r(u) \leq R - 7\log\log n\). It follows that \(u \not\in V_{(1)}\) w.e.h.p. since \(w \in I_{(1)}\); \(u\) 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 [\((N(u) \cap \mathcal{A})\setminus (V \setminus V_{(1)}) = \emptyset\)]: Consider the sector \(\Psi\) with angle \(\psi = e^{C/2} \cdot \log^{7/2} n /n\) and bisector \(\varphi(u)\). Note that, since \(r(u) \leq R - 7\log\log n\), we obtain via 1 in conjunction with [rmk:theta-monotonicity] that \(\Psi \subset \mathcal{B}_u(R)\), and thus, if a vertex \(v \in V \cap \Psi\) joins the independent set, \(u\) is removed since \(v \in N(u)\). We partition \(\Psi\) into \(k:= e^{C}\cdot\log^{3/2}n / 100\) sectors, such that for \(i \in [k]\) each sector \(\Phi_i \subset \Psi\) has angle \(\phi = 100\cdot e^{-C/2}\log^2 n /n\). Let \(\varphi_i\) be the bisector of \(\Phi_i\) and let \(\mathcal{S}_i := \{x \in \Phi_i \cap \mathcal{L}_{0} : \varphi_i - 1/n \leq \varphi(x) \leq \varphi_i + 1/n \}\), i.e., a sub-area of sector \(\Phi_i\) in layer \(\mathcal{L}_{0}\), with the same bisector as \(\Phi_i\) that spans an angle of \(2/n\) (see also green area in 7b). We say that \(\Phi_i\) is active if there exists a vertex \(v \in V \cap \mathcal{S}_i\) such that \(v\) joins the independent set in the second step of HRG-Shattering-MIS, i.e., \(I_{(2)} \cap \mathcal{S}_i \neq \emptyset\).

To finish the proof, let \(X_i\) be the indicator random variable that is \(1\) if sector \(\Phi_i\) is active and let \(X = \sum_{i=0}^{k-1}X_i\) be the number of “active \(\Phi\)-sectors in sector \(\Psi\)”. By linearity of expectation and Claim [claim:active-sector2] in conjunction with \(k \in \Omega(\log n^{3/2})\) it holds \(\mathbb{E}\left[X\right] \in \omega(\log n)\). Thus, if we can show for any \(X_i\) and \(X_j\) that they are independent, our desired statement follows from a Chernoff bound in conjunction with a union bound over the set of vertices \(V \cap \mathcal{B}_0(R - 7\log\log n)\). This is since an active \(\Phi\)-sector implies that a neighbour \(v \in N(u)\) joins the independent set which removes \(u\).

We show that this independence holds for any two indicator random variables \(X_i\) and \(X_j\) w.e.h.p. Recall that \(X_i\) is \(1\) if and only if there is a vertex \(v \in V \cap \mathcal{S}_i\) that joins the independent set. Moreover, recall that w.e.h.p. only the area \(\mathcal{A}' = \mathcal{D}_R\setminus \mathcal{B}_0(R-4\log\log n -C)\) contain active vertices. W.l.o.g., let sector \(\Phi_i\) have bisector \(0\). Thus, considering \(v \in V \cap \mathcal{S}_i\) with radius \(r(v) \geq R - 1\), for any active neighbour \(w \in N(v)\) we have \(r(w) \geq R - 4\log\log n\) w.e.h.p., and it holds \[\varphi(w) \leq 1/n + \theta_R(r(v), r(w)) \leq \frac{\pi \cdot e^{(1-C)/2} \log^2 n}{n} < \phi \text{ w.e.h.p.,}\] using 1 and [rmk:theta-monotonicity] in conjunction with \(\phi = 100 \cdot e^{-C/2} \log ^2 n /n\) and \(\mathcal{S}_i\) spanning at most an angle of \(1/n\). Thus, all active neighbours of the vertex \(v \in V \cap \mathcal{S}_i\) are contained in sector \(\Phi_i\) w.e.h.p., yielding the independence w.e.h.p. as desired. A Chernoff bound yields \(X \in \omega(\log n)\) w.e.h.p. such that \(u\) is removed w.e.h.p. and a union bound over all the set of vertices \(|V \cap \mathcal{B}_0(R - 7\log\log n)| \in o(n)\) w.e.h.p. wraps up the proof. ◻

Proof. The runtime \(\mathcal{O}(1)\) directly follows from the fact that one iteration of Luby’s algorithm requires \(\mathcal{O}(1)\) rounds in \(\mathsf{CONGEST}\). Now, consider the set of vertices \(I_{(1)}\), i.e., the set of vertices in the independent set after the first step of HRG-Shattering-MIS. Let \(k := |I_{(1)}|\) and consider for \(I_{(1)}\) an ascending ordering by angular coordinates \(v_0, v_1,\dots, v_{k-1}\). For \(i \in [k]\), let \(\Phi_i\) be the sector defined by \(\{x \in \mathcal{D}_R: \varphi (v_{i}) \leq \varphi(x) \leq \varphi(v_{i+1})\}\) where \(v_k = v_0\). Note that by 6, for \(i \in [k]\) it holds for any consecutive pair \(v_i, v_{i+1}\) that \(\delta_\varphi(v_{i},v_{i+1}) \leq 2 \log^{30\alpha}(n)/n\) w.e.h.p. and thus, the angle for any sector \(\Phi_i\) is at most \(\mathcal{O}(\log^{30\alpha}(n)/n)\) w.e.h.p. Thus, it holds for any \(i \in [k]\) that \(\mu(\Phi_i) \in \mathcal{O}(\log^{30\alpha}(n)/n)\). Via Chernoff bound for \(|V \cap \Phi_i|\) and a union bound over \(k \in o(n)\) sectors, we then obtain for all \(i \in [k]\) that \(|V \cap \Phi_i| \in \mathcal{O}(\log^{30\alpha}n)\) w.e.h.p. Clearly, this implies that \(|V_{(2)} \cap \Phi_i| \in \mathcal{O}(\log^{30\alpha}n)\) w.e.h.p. Thus, if we can show for any pair \(i \neq j \in [k]\) that for all pairs \(u \in V_{(2)} \cap \Phi_i\) and \(v \in V_{(2)} \cap \Phi_j\) it holds \(\mathop{\mathrm{d_h}}(u,v) > R\) w.e.h.p., this finishes the proof.

To this end, fix any pair of sectors \(\Phi_i\) and \(\Phi_{j}\), and w.l.o.g. let \(j = i+1\) since non-adjacent sectors are separated by an even larger angular interval. Consider any pair \(u \in V_{(2)} \cap \Phi_i\) and \(v \in V_{(2)} \cap \Phi_{i+1}\). Using 7, it holds w.e.h.p. for both vertices \(u, v \in V_{(2)}\) that \(r(u), r(v) \geq R - 7 \log\log n\). Moreover, let \(s = v_{i+1}\) be the vertex that lies on the intersecting ray of \(\Phi_i\) and \(\Phi_j\). Then, by 1 in conjunction with [rmk:theta-monotonicity], it holds for the angular distance between \(u\) and \(v\) that \[\delta_\varphi(u,v) \geq \theta_R(r(v), r(s)) + \theta_R(r(u), r(s)) > \theta_R(r(u), r(v)) \text{ w.e.h.p.,}\] since \(u, v \not\in N(s)\) and \(r(v), r(u) \in r(s) + \Omega(\log \log n)\) w.e.h.p. by 6. Thus, for all pairs \(u \in V_{(2)} \cap \Phi_i\) and \(v \in V_{(2)} \cap \Phi_j\) it holds \(\mathop{\mathrm{d_h}}(u,v) > R\) w.e.h.p.; taking a union bound over all pairs of sectors, the desired result follows: every connected component of \(G[V_{(2)}]\) is contained in a single sector \(\Phi_i\). Since each sector contains at most \(\mathcal{O}(\log ^{30\alpha}n)\) vertices w.e.h.p., every connected component has poly-logarithmic size. This proves the proposition. ◻

Proof of [thm:mainpolylog] (MIS part). \(\mathsf{LOCAL}\): For \(\mathsf{LOCAL}\) MIS, we obtain a shattering where each connected component is of size at most \(\mathop{\mathrm{polylog}}n\) w.e.h.p. after \(\mathcal{O}(1)\) using [pro:shattering-mis]. Applying in parallel for each component [13], we obtain an MIS after \(\tilde{\mathcal{O}}(\log^{5/3}\log n)\) rounds w.e.h.p.

\(\mathsf{CONGEST}\): For \(\mathsf{CONGEST}\) MIS, [pro:shattering-mis] implies that after \(\mathcal{O}(1)\) rounds each connected component induced by undecided nodes is of at most poly-logarithmic size w.e.h.p. Consequently, applying in parallel for each connected component [44], we obtain an MIS after \(\tilde{\mathcal{O}}(\log^{3}\log n)\) rounds w.e.h.p. ◻

Proof. In the step 1 of HRG-Shattering-MM, we first activate all vertices with degree at most \(\lceil\log^{3/2} n\rceil\). In parallel, all active vertices mark one incident edge uniformly at random.

Fix a vertex \(u \in V \cap \mathcal{B}_0(R- 6\log\log n)\) and let \(X_u\) be the random variable with which we count the number of marked edges incident to \(u\). Note that if we can show that \(X_u \geq 1\) for all \(u \in V \cap \mathcal{B}_0(R- 6\log\log n)\) with probability \(1 - n^{-\omega(1)}\), then this proves the claim since then any vertex in \(u \in V \cap \mathcal{B}_0(R- 6\log\log n)\) can simply select one of the marked edges so that \(u\) is matched.

To show this, consider the set of vertices which form an \(e\) edge with \(u\) such that \(e\) is potentially marked. Let us write \(N'(u) := N(u) \cap \{v \in V : \deg(v) \leq \lceil\log^{3/2} n\rceil\}\) for this set and note that for \(v \in N'(u)\), the edge \(\{u,v\}\) is marked with probability \(1/\deg(v)\), as \(v\) samples the edge uniform at random among its neighbours. Hence, it holds \[\begin{align} \label{eq:prob-bad-event} \mathbb{P}\left(X_u = 0\right) = \prod_{v \in N'(u)}(1-1/\deg(v)). \end{align}\tag{3}\] In the following, we lower bound \(|N'(u)|\). Since for any vertex \(v \in V \cap \mathcal{L}_{0}\), it holds via 3 that \(\mathbf{E}\left[\deg(v)\right] \in \mathcal{O}(1)\), such that a Chernoff-bound with a subsequent union bound over at most \(\mathcal{O}(n)\) vertices yields that \(\deg(v) \leq \log^{3/2}n\) and all vertices in layer \(\mathcal{L}_{0}\) are active w.e.h.p. and participate in our marking process. Using this bound and that \(r(u) \leq R - 6\log\log n\) in conjunction with the fact that \(\theta_R(\cdot, \cdot)\) is a monotonic decreasing function in both arguments ([rmk:theta-monotonicity]), it holds via law of total expectation that \[\begin{align} \mathbf{E}\left[|N'(u)|\right] \geq (1-o(1)) n\cdot \theta_R(R - 6\log\log n, R)\cdot \mu(\mathcal{L}_{0}) \in \Omega(\log^3(n)), \end{align}\] where in the last step we used ?? and 1. Another combination of Chernoff and union bounds reveals that for any \(u \in V \cap \mathcal{B}_0(R- 6\log\log n)\) it holds \(|N'(u)| \in \Omega(\log^3 n)\) with probability \(1 - n^{-\omega(1)}\).

Let \(\mathcal{E}\) be the event that for all \(v \in V \cap \mathcal{L}_{0}\) it holds \(\deg(v) \in \mathcal{O}(\log^{3/2}n)\) and that for all \(u \in V \cap \mathcal{B}_0(R- 6\log\log n)\) it holds \(|N'(u)| \in \Omega(\log^3(n))\). By previous discussion it follows via union bound that \(\mathbb{P}\left(\mathcal{E}\right) \in 1 - n^{-\omega(1)}\). Note that for our fixed \(u \in V \cap \mathcal{B}_0(R- 6\log\log n)\) it holds \(\mathbb{P}\left(X_u = 0 |\mathcal{E}\right) \in e^{-\Omega(\log^{3/2}n)}\) by 3 . Hence, we obtain using a union bound \[\begin{align} \mathbb{P}\left(\not\exists u \in V \cap \mathcal{B}_0(R- 6\log\log n) : X_u = 0\right) \geq \mathbb{P}\left(\mathcal{E}\right)\cdot(1 - \sum_{u \in V \cap \mathcal{B}_0(R- 6\log\log n) }\mathbb{P}\left(X_u = 0|\mathcal{E}\right)) \in 1-n^{-\omega(1)}, \end{align}\] since \(|V \cap \mathcal{B}_0(R- 6\log\log n)| \in \mathcal{O}(n)\) w.e.h.p. That is, we showed that \(X_u \geq 1\) for all \(u \in V \cap \mathcal{B}_0(R- 6\log\log n)\) with probability \(1 - n^{-\omega(1)}\) as desired. This finishes the proofs since the desired runtime \(\mathcal{O}(1)\) is immediate. ◻

Proof. Items [item:ring2] and [item:active-sector2] follow directly from 6, 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 6 carry over verbatim: the set \(S\) is equivalent to \(I_{(1)}\).

To show that [item:min95angle] holds, suppose for contradiction that \(\{u,v\}\in E\). Since both \(u\) and \(v\) belong to \(S\), each has the largest ID in its closed neighbourhood. However, as \(u\in N(v)\) and \(v\in N(u)\), at most one of the two vertices can have the largest ID among the vertices of its closed neighbourhood, a contradiction. Hence \(u\) and \(v\) are not adjacent. Then, using that \(r(u), r(v) \in R - 8 \log\log n +\mathcal{O}(1)\) w.e.h.p. by [item:ring2], it holds w.e.h.p. using 1 in conjunction with [rmk:theta-monotonicity] that \[\delta_\varphi(u,v) > \theta_R(r(u),r(v)) \in \Omega(\log^8 n / n).\] Hence the claimed lower bound on the angular distance holds for every pair of vertices in \(S\) whenever the event of Item [item:ring2] occurs. Since this event holds with probability \(1-n^{-\omega(1)}\), the proof is complete. ◻

Proof. \(\mathsf{LOCAL}\): We start by proving the \(\mathsf{LOCAL}\) part. Consider any pair of vertices \(s, s' \in S\) in the second step of HRG-Shattering-MM. We show for any of the two sets of vertices \(N_2(s) \cap V_{(1)} =: U(s)\) and \(N_2(s') \cap V_{(1)} =: U(s')\), that for any pair \(v \in U(s)\) and \(v' \in U(s')\) it holds \(\{v,v'\} \not \in E\) w.e.h.p. This ensures that for any pair \(s, s' \in S\), there are no conflicts when \(s\) and \(s'\) compute in parallel \(M(s)\) and \(M(s')\) in the \(\mathsf{LOCAL}\) computation of the second step in HRG-Shattering-MM. To see this, note first that \(\{s,s'\} \not\in E\) w.e.h.p. holds immediately by 9. Thus, it suffices to show that for any \(v \in U(s)\) and \(v' \in U(s')\setminus\{s'\}\) that \(\{v,v'\} \not \in E\) w.e.h.p. Now, recall that by 8 it holds w.e.h.p. for any \(v,u \in V_{(1)}\) that \(r(v),r(u) \geq R - 6\log\log n\). Moreover, by 9 it holds for some constant \(c\) that, \(r(s) \geq R - 8\log\log n -c\) w.e.h.p. Thus, for any vertices \(v, u \in U(s)\) it holds w.e.h.p. that \[\begin{align} \label{eq:two-hop-angle} \delta_\varphi(s,v) \leq \theta_R(r(s), r(u)) + \theta_R(r(v), r(u)) < \Theta(1) \log^{7} n / n, \end{align}\tag{4}\] by 1. Moreover, using 9 [item:min95angle], it holds w.e.h.p. for the pair \(s, s' \in S\) that \[\begin{align} \label{eq:separator-angle} \delta_\varphi(s,s') \in \Omega(\log^8 n / n). \end{align}\tag{5}\] Consequently, we obtain w.e.h.p. for any pair \(v \in U(s)\) and \(v' \in U(s')\setminus\{s'\}\) by combining 4 and 5 that \[\begin{align} \label{eq:two-hop-intersection} \delta_\varphi(v,v') = \delta_\varphi(s,s') - \delta_\varphi(s,v) - \delta_\varphi(s',v') \in \Omega(\log^8 n / n) \in \omega(\theta_R(r(v), r(v'))) \text{ w.e.h.p.,} \end{align}\tag{6}\] using 1 in conjunction with \(r(v') \geq R - 6\log\log n\) w.e.h.p. by 8 and \(r(v) \geq R - 8\log\log n -c\) w.e.h.p. by 9. It follows via 6 that no two-hop neighbourhoods \(U(s') \cap U(s)\) share any edge w.e.h.p. as desired, which, by union bound then also holds for any pair \(s, s' \in S\) w.e.h.p. We conclude that w.e.h.p. there are no conflicts for any matchings \(M(s)\) and \(M(s')\) and it is left to show that (a) we obtain the desired shattering and (b) the computation in HRG-Shattering-MM requires \(\mathcal{O}(1)\) rounds of the \(\mathsf{LOCAL}\) model.

(a) The shattering property follows by the same argument as in the proof of [pro:shattering-mis] after replacing the set \(I_{(1)}\) with \(S\). Indeed, by 8, every vertex in \(V \cap \mathcal{B}_0(R-6\log\log n)\) is already matched after Step 1 of HRG-Shattering-MM w.e.h.p. Moreover, for every \(s \in S\), the algorithm computes a maximal matching on the induced subgraph \(G[U(s)]\), where \(U(s)=N_2(s)\cap V_{(1)}\). Since \(N(s)\subseteq U(s)\), every neighbour of \(s\) is either matched itself or matched to another vertex in \(U(s)\). Consequently, \(N(s)\cap V_{(2)}=\emptyset\) for every \(s\in S\). Hence every unmatched vertex lies in the same outer annulus as in [pro:shattering-mis], and the remainder of the shattering argument applies verbatim.

(b) By 8 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 \(S\). Moreover, each vertex \(s \in S\) 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 \(U(s)\) about the matching \(M(s) \subseteq E(G_2)\). Hence, at most \(\mathcal{O}(1)\) communication rounds are required.

\(\mathsf{CONGEST}\): The correctness of the \(\mathsf{CONGEST}\) part follows from the same arguments as for the \(\mathsf{LOCAL}\) model. For the round complexity, we consider the following: first, for all \(s \in S\), in parallel, each induced subgraph \(G(U(s))\) can be informed by \(s\) to be active within \(2\) rounds in \(\mathsf{CONGEST}\). Next, fix a vertex \(s \in S\). Since there exists a constant \(c\) such that \(r(s) \geq R - 8\log\log n -c\) by 9, it follows by 3 that \(\mathbf{E}\left[\deg(s)\right] \in \Theta(\log^4 n)\). Thus, by a Chernoff and union bound it holds for any \(s \in S\) that \(\deg(s) \in \Theta(\log^4 n)\) w.e.h.p. Moreover, it holds for any \(v \in V_{(1)}\) that \(r(v) \geq R - 6\log\log n\) w.e.h.p. by 8. Subsequently, using 3 with a Chernoff and a union bound, we have for each \(v \in V_{(1)}\) that \(\deg(v) \in \mathcal{O}(\log^3 n)\). Hence, for all \(U(s)\) it holds \(|U(s)|\in \mathcal{O}(\log^7 n)\) w.e.h.p. Then, recall that for any pair of vertices \(s, s' \in S\) we showed that there are no edges between \(U(s)\) and \(U(s')\) w.e.h.p. Thus, using in parallel for each \(s \in S\) on the induced subgraph \(G[U(s)]\) [85], we obtain a maximal matching for all such induced subgraphs \(G[U(s)]\) in \(\mathcal{O}(\log^3\log n)\) rounds without conflicts w.e.h.p. ◻

Proof of [thm:mainpolylog] (MM part). \(\mathsf{LOCAL}\): For MM, we obtain a shattering where each connected component is of size at most \(\mathop{\mathrm{polylog}}n\) w.e.h.p. after \(\mathcal{O}(1)\) using [pro:shattering-mm]. Applying in parallel for each component [13], yields \(\tilde{\mathcal{O}}(\log^{5/3}\log n)\) rounds w.e.h.p..

\(\mathsf{CONGEST}\): The shattering into poly-logarithmic components in \(\mathcal{O}(\log^3\log n)\) rounds follows similarly from [pro:shattering-mm] w.e.h.p. Consequently, by applying in parallel for each connected component the maximal matching algorithm from [85], resulting in a round complexity of \(\mathcal{O}(\log^3\log n)\). ◻

Proof. We show the desired statement as follows: first, we show that all boxes are within the sector \(\Phi\). Then, we establish for any vertex \(u \in V \cap \Phi\) that any point in a box of \(u\) has distance at most \(R\) to \(u\). Note that this already suffices to prove that all desired edges for a tree exist such that every vertex has \(d\) children (except for the leaves of the tree). Afterwards, we show that any vertex \(u\) has a distance larger than \(R\) to any point of a box that is not the box of \(u\) according to 1. Since the rest of the sector is empty, this ensures that we also have all non-edges. Using that we have \(h\) layers through which we iterate in line 4 of 9, this yields a tree of depth \(h\) where each vertex has \(d\) children because of the loop in line 8. For the desired properties of our tree, \(d\) and \(h\) follow directly from 1 and the number of vertices is given by \(n' \geq d^{h} \in \Omega(\sqrt{\log n})\).

6.1.0.1 All boxes are contained in the sector.

By 1, a vertex \(u\) in layer \(\mathcal{L}_{\ell_i}\) has boxes with angular distance at most \(\frac{e^{\ell_i + C/2}}{10 n\cdot m}\) since \(d\cdot \phi_{\ell_{i+1}} \leq \exp(C/2 + \ell_i)/(100n\cdot m)\). Hence, the maximal angle that is spanned by any pair of points \(x,y\) in two different boxes is at most \[\delta_\varphi(x,y) \leq \sum_{i=0}^{h-1} \frac{e^{\ell_i + C/2}}{10 n\cdot m} \leq \Theta(1)\cdot \frac{e^{\ell_0}}{n\cdot m} \in o(\phi),\] where we used that \(\ell_i = \lceil \log\log n \rceil - \lceil 2i \cdot {\log m} \rceil\), \(\phi = 5\cdot \log n / (n\cdot \log m)\) and \(m \in \omega(1)\) in the last step. Thus, all boxes are contained in sector \(\Phi\) with angular width \(\phi\).

6.1.0.2 Edges.

Recall that \(R = 2\log n + C\). To show that all desired edges exist, consider any vertex \(u \in V_{\ell_{i}}\). Note that any box \(\mathcal{B}_{u, j}\) is in layer \(\mathcal{L}_{\ell_{i+1}}\). Hence, using that \(d\cdot \phi_{\ell_{i+1}} \leq \exp(C/2 + \ell_i)/(100n\cdot m)\) it follows by the definition of \(\mathcal{B}_{u, j}\) that the angular distance between \(u\) and \(x \in \mathcal{B}_{u, j}\) is at most \[\begin{align} \delta_\varphi(u,x) \leq \frac{e^{\ell_i + C/2}}{10 n\cdot m} \leq e^{(R - r(u) - r(x))/2} \leq \theta_R(r(u), r(x)), \end{align}\] using that \(r(u) \leq R - \ell_i\), \(r(v) \leq R - \ell_i + 2\log m + 1\) and 1 in conjunction with \(\theta_R(r(u), r(x))\) being monotonically decreasing by [rmk:theta-monotonicity]. Thus, all desired edges exist.

6.1.0.3 Non-edges.

Next, let \(u \in V_{\ell_i}\) and \(v \in V_{\ell_j}\). W.l.o.g. let \(\ell_i \geq \ell_j\). Then, if \(v\) is not in a box of \(u\), we have to show that \(d_h(u,v) > R\) to finish the proof. To this end, we distinguish two cases.

Case 1 [Vertex \(u\) is an ancestor of \(v\)]: Let \(w\) be the vertex that is in the \((d-1)\)-th box of \(u\), i.e., \(\mathcal{B}_{u, d-1}\) and note that, since \(d\cdot \phi_{\ell_{i+1}} \leq \exp(C/2 + \ell_i)/(100n\cdot m)\), \[\begin{align} \label{eq:lower-bound-angle} \delta_\varphi(u,v) \geq \delta_\varphi(u,w) > (1/10 -1/100)\frac{e^{C/2 + \ell_i}}{m\cdot n} , \end{align}\tag{7}\] using the definition for the box \(\mathcal{B}_{u, j}\) (1). On the other hand, using that \(u\) is an ancestor of \(v\) but \(v\) is not in a box of \(u\), we observe that \(\ell_i \geq \ell_j + 4\log m\). Thus, we obtain \[\begin{align} \label{eq:lower-bound-angle2} \theta_R(r(u), r(v)) \leq \Theta(1) \frac{e^{C/2 + \ell_i}}{m^2 \cdot n}, \end{align}\tag{8}\] by 1. Hence, by combining 7 and 8 we have by \(m \in \omega(1)\) \[\delta_\varphi(u,v) > \Theta(1)\frac{e^{C/2 + \ell_i}}{m\cdot n} > \Theta(1) \frac{e^{C/2 + \ell_i}}{m^2 \cdot n} \in \omega(\theta_R(r(u), r(v))),\] and there is no edge between \(u\) and \(v\) by 1. This concludes our first case.

Case 2 [Vertex \(u\) is not an ancestor of \(v\)]: Let \(w\) be the vertex that is the lowest common ancestor of \(u\) and \(v\). First, consider the case that \(w\) is the parent of both \(u\) and \(v\). In this case, \(w \in V \cap \mathcal{L}_{\ell_{i-1}}\) and as such, the minimal angular distance between \(u\) and \(v\), by 1, is \[\delta_\varphi(u,v) \geq \phi_{\ell_i} = \frac{100e^{\ell_{i} + C/2}}{n} > \theta_R(r(u), r(v)),\] where we applied 1 and \(r(u), r(v) \geq R - \ell_i -2\). Hence, there is no edge between \(u\) and \(v\).

To finalise the case, consider now that \(u\) and \(v\) do not share the same parent such that \(\ell_i > \ell_j\). Let the lowest common ancestor \(w\) be in layer \(\mathcal{L}_{\ell_k}\) and consider the two children \(u'\) and \(v'\) of \(w\), (where both \(u'\) and \(v'\) are in layer \(\mathcal{L}_{\ell_{k+1}}\)), that are ancestors of \(u\) and \(v\) respectively (possibly \(u' = u\)). Note that by \(d\cdot \phi_{\ell_{i+1}} \leq \exp(C/2 + \ell_i)/(100n\cdot m)\) and using 1 it follows that \[\begin{align} \label{eq:case2-part1} \delta_\varphi(u',v') \geq \phi_{\ell_{k+1}} = \frac{100 \cdot e^{\ell_k + C/2 }}{m^2 \cdot n}. \end{align}\tag{9}\] Then, using that \(\varphi(u)\geq \varphi(u')\) and that \(\varphi(v) \leq \varphi(v') + \sum_{t = j}^{k-1} \frac{e^{(C+ \ell_t + \ell_{t -1})/2}}{n}\) by 1, it follows \[\begin{align} \label{eq:case2-part2} \delta_\varphi(u,v) \geq \delta_\varphi(u',v') - \underbrace{\sum_{t = j}^{k-1} \frac{e^{(C+ \ell_t + \ell_{t -1})/2}}{n}}_{\mathcal{O}\left(\frac{e^{\ell_k}}{m^3 n}\right)}. \end{align}\tag{10}\] Plugging 9 into 10 and upper bounding the sum of exponentials by \(\mathcal{O}(\exp{(\ell_k - 3\log m)} /n)\) we obtain via \(m \in \omega(1)\) \[\begin{align} \delta_\varphi(u,v) \geq \frac{(100 - o(1)) e^{\ell_k + C/2}}{m^2 \cdot n} > \theta_R(r(u), r(v)), \end{align}\] using that \(\ell_k \geq \ell_i + 2\log m \geq \ell_j + 4\log m\) and \(r(u) \geq R - \ell_i - 2, r(v) \geq R - \ell_j - 2\) in conjunction with 1. Hence, there is no edge between \(u\) and \(v\) as desired. This concludes the case and the proof. ◻

Proof. We show that all boxes of a nice sector according to 9 have exactly one vertex with the desired probability \(n^{-o(1)}\). To this end, fix any \(i \in [h+1]\setminus\{0\}\) and consider any "non-root" layer \(\mathcal{L}_{\ell_i}\). Then, to fulfil the property of a nice sector according to 9, all \(d^i\) boxes include exactly one vertex. Let \(u\) be a vertex in layer \(\mathcal{L}_{\ell_{i-1}}\). Using 1 it holds for any single box in layer \(\mathcal{L}_{\ell_i}\) \[\begin{align} \mu(\mathcal{B}_{u, j}) = \frac{\phi_{\ell}}{2\pi} \cdot \mu(\mathcal{L}_{\ell_i}) = \Theta(1)\frac{e^{\ell_i(1-\alpha)}}{n} \in \Omega(1/n), \end{align}\] where we used ?? and for the last step that \(\ell_i \geq 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 \(\mathcal{L}_{\ell_i}\) is \[\begin{align} \label{eq:non-root-prob} p_i = n\cdot \mu(\mathcal{B}_{u, j}) \cdot e^{-n\cdot\mu(\mathcal{B}_{u, j})}\geq e^{\ell_i(1-\alpha)} \cdot \exp\left(-\Theta(1){e^{\ell_i(1-\alpha)}}\right). \end{align}\tag{11}\] Hence, using that any pair of boxes is disjoint, the probability that all \(d^i\) boxes in layer \(\mathcal{L}_{\ell_i}\) have exactly one vertex is given by \[\mathbf{P}\left(\mathcal{E}_{i}\right) = (p_i)^{d^i} \geq \exp\left(-\Theta(1){e^{\ell_i(1-\alpha)}}\right)^{d^i}.\] Next, we bound the probability that the desired "root" vertex in layer \(\mathcal{L}_{\ell_0}\) exists. Since the "box" of the "root" in 9 has angle \(\phi/5 = \log n /n\log(m)\) the probability that exactly one root vertex exists is by a Poisson distribution and ?? \[\begin{align} \label{eq:root-prob} p_0 = \frac{n\cdot\phi}{2\pi} \cdot \mu(\mathcal{L}_{\ell_0})\cdot \exp{\left(-\frac{n\cdot\phi}{2\pi} \cdot \mu(\mathcal{L}_{\ell_0})\right)} \geq \exp\left(-\Theta(1){e^{\ell_0(1-\alpha)}}\right). \end{align}\tag{12}\] since \(m \leq \sqrt{\log n}\) and \(\alpha < 1\). This implies that sector \(\Phi\) 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 9, with probability \[\begin{align} \mathbf{P}\left(\mathcal{E}\right) \geq p_0 \cdot \prod_{i=1}^{h} \mathbb{P}\left(\mathcal{E}_{\ell_i}\right) \geq \prod_{i=0}^{h} \left((p_i)^{d^i}\right) \geq \prod_{i=0}^{h} \exp\left(-\Theta(1){e^{\ell_i(1-\alpha)}}\right)^{d^i}, \end{align}\] where we used 11 and 12 in the last step. Next, we use that \(\alpha > 1/2\) which yields \[\begin{align} \label{eq:probability-product} \mathbf{P}\left(\mathcal{E}\right) \geq \prod_{i=0}^{h} \exp\left(-\Theta(1){d^i}{e^{\ell_i/2}}\right). \end{align}\tag{13}\] Since \(\ell_i \leq \log\log n - 2i\cdot\log m + 1\), we obtain \[\begin{align} \; \mathbf{P}\left(\mathcal{E}\right) \geq \prod_{i=0}^{h} \exp\left(-\Theta(1){d^i}\cdot \sqrt{\log n}/m^i\right) \geq \prod_{i=0}^{h} \exp\left(-\Theta(1)\cdot \sqrt{\log n}/10000^i\right), \end{align}\] where we used \(d^i \leq (m/10000)^i\). Applying a geometric series, the above yields \[\begin{align} \; \mathbf{P}\left(\mathcal{E}\right) \geq \exp\left(-\Theta(1)\cdot\sum_{i=0}^{h} \sqrt{\log n}/10000^i\right) \geq e^{-\Theta(1)\sqrt{\log n}} \in n^{-o(1)}, \end{align}\] and we conclude that \(\Phi\) has all vertices that are required to be nice with a probability that is decaying more slowly than polynomial in \(n\).

Finally, we lift this to the statement that the sector is also nice with probability \(n^{-o(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 \(\phi \in \mathcal{O}(\log n /(m n))\) and using that the number of vertices in sector \(\Phi\) follow a Poisson distribution with expectation \(\mathbf{E}\left[|V \cap \Phi|\right] = n \phi /2\pi\), the probability that the sector is empty is given by \[\mathbf{P}\left(V \cap \Phi = \emptyset\right) = e^{-\mathbf{E}\left[|V \cap \Phi|\right]} \in e^{-\mathcal{O}(\log n /m)} \in n^{-o(1)},\] using \(m \in \omega(1)\). Hence, given any area \(\mathcal{S} \subseteq \mathcal{D}_R\), the probability that \(\Phi\setminus \mathcal{S}\) is empty is at least \(n^{-o(1)}\) (using the fact that the probability of an area being empty is monotonically increasing if the considered area is shrinking). Then, let \(\mathcal{S}\) be the area that we need to reveal for event \(\mathcal{E}\) and it follows that a sector \(\Phi\) is nice with probability \[\mathbf{P}\left(\Phi \text{ is nice}\right) \geq \mathbf{P}\left(\mathcal{E}\right)\cdot\mathbf{P}\left(V \cap (\Phi\setminus \mathcal{S}) = \emptyset | \mathcal{E}\right) \geq \mathbf{P}\left(\mathcal{E}\right)\cdot\mathbf{P}\left(V \cap \Phi = \emptyset\right) \in n^{-o(1)},\] as claimed. ◻

Proof. Throughout the proof, we partition the disk \(\mathcal{D}_R\) into \(k = \big\lceil \frac{n^{1-\frac{1}{2\alpha}}}{\log n}\rceil\) sectors such that for \(i \in [k]\), the angle \(\psi\) of any such sector \(\Psi_i\) is \(\psi \in \Theta\left(\frac{n^{\frac{1}{2\alpha}}\log n}{n}\right)\); see red sector in 3b for an illustration. Moreover, let \(r^* := R - \log n/\alpha - \log\log n /2\) and throughout the proof, we consider the area \(\mathcal{B}_0(r^*)\); see hatched area in 3.

We prove our theorem in two steps. In the first step of the proof, we show that any sector \(\Psi_i\setminus\mathcal{B}_0(r^*)\) contains a desired \(d\)-ary tree \(T_i\) with probability \(n^{-o(1)}\) if it contains a nice sector \(\Phi_i\); blue sector in 3. This is addressed in Claim [claim:indicator].

Then, in a second step, we show that we have \(n^{\Omega(1)}\) "buffer sectors" \(\Psi_i\) w.e.h.p. that contain a tree \(T_i\) and that if the area \(\mathcal{B}_0(r^*)\) is empty, then the neighbourhood of any \(d\)-ary tree \(T_i\) does not contain a vertex of any vertex of any other "buffer sector" \(\Psi_j\). Showing that \(\mathcal{B}_0(r^*)\) is empty a.a.s. then gives the desired probabilistic guarantee of any \(T_i\) not having any undesired edges. Finally, we finish the proof by showing that the edge of the "root" in \(T_i\) which exists due to Claim [claim:indicator] connects \(T_i\) to the giant in the desired fashion of the "in particular" statement of our theorem.

Now, for Claim [claim:indicator], we consider any \(\Psi_i\) and let \(\Phi_i \subset \Psi_i\) be the sector of width \(\phi = \frac{5\log n}{n\log m} \in o(\log n / n)\) as demanded in 11 that has the same bisector as \(\Psi_i\). In particular we consider a sector \(\Psi_i\) where the corresponding sector \(\Phi_i\) is nice. We introduce the following event \(\mathcal{E}_i\) which says that no vertex in a nice sector \(\Phi_i\) has an edge to a vertex in \(\Psi_i \setminus \Phi_i\) except for the “root” vertex \(u \in V_{\ell_0} \cap \Phi_i\) which has exactly one edge to a "special" vertex \(v\) in \(\Psi_i\setminus \Phi_i\) where \(v\) lies in layer \(\overline{\ell} := \lceil 2\log\log n/(1-\alpha)\rceil\). We later show that \(v\) is part of the giant component.

1. let \(U: = V \cap (\Phi_i \setminus \mathcal{L}_{\ell_0})\), i.e., all vertices in \(\Phi_i\) except for the “root” vertex in layer \(\ell_0\), and let \(\mathcal{E}_U:= \{\)No vertex in \(U\) has any neighbour in \(\Psi_i \setminus (\Phi_i \cup \mathcal{B}_0(r^*))\}\). Moreover, let \(u \in V \cap (\Phi_i \cap \mathcal{L}_{\ell_0})\), i.e., the root vertex of \(\Phi_i\), and let \(\mathcal{E}_{\text{root}}:= \{\text{Vertex } u \text{ has exactly one neighbour v in } \Psi_i \setminus (\Phi_i \cup \mathcal{B}_0(r^*)), \text{ and } v \text{ is in layer } \mathcal{L}_{\overline{\ell}}\}\).

We define \(\mathcal{E}_i := \mathcal{E}_U \cap \mathcal{E}_{\text{root}}\) and we will show that this event holds with probability \(n^{-o(1)}\).

To finish the proof of our statement, recall that \(\Psi_i\) has angle \(\psi \in \Theta\left(\frac{n^{\frac{1}{2\alpha}}\log n}{n}\right)\) and thus, we have \(k \in n^{\Omega(1)}\) such sectors in our entire disk. Now, let \(X_i\) be the indicator random variable that is \(1\) if the event \(\{\mathcal{E}_i \cap \Phi_i\) is nice\(\}\) occurs. Moreover, let \(X:= \sum_{i=1}^k X_i\), i.e., the number of "buffer sectors" \(\Psi_i\) that have the desired induced subgraph tree \(T_i = G[V \cap \Phi_i]\). In the following, we obtain a lower bound for \(X\). Recall that \(r^* = R - \log n / \alpha - \log\log n /2\). Then, using linearity of expectation, 11 and Claim [claim:indicator] we have \[\begin{align} \mathbf{E}\left[X\text{ }|\text{ }V \cap \mathcal{B}_0(r^*) = \emptyset\right] &= \sum_{i=1}^k \mathbf{P}\left(\mathcal{E}_i \cap \Phi_i \text{ is nice} \text{ }|\text{ }V \cap \mathcal{B}_0(r^*) = \emptyset\right) \\ &\geq k\cdot \mathbf{P}\left(\Phi_i \text{ is nice}\text{ }|\text{ }V \cap \mathcal{B}_0(r^*) = \emptyset\right)\cdot\mathbf{P}\left(\mathcal{E}_i \text{ }|\text{ } \Phi_i \text{ is nice}, V \cap \mathcal{B}_0(r^*) = \emptyset\right)\in n^{\Omega(1)} \end{align}\] using that a nice sector according to 9 has only vertices outside the area \(\mathcal{B}_0(r^*)\) and \(\mathcal{E}_i\) is independent of the event \(V \cap \mathcal{B}_0(r^*) = \emptyset\). To obtain concentration for \(X\), note that the sectors \(\Psi_i\) are disjoint and the events that they are nice are mutually independent: determining whether \(\Phi_i\) is nice only requires revealing the randomness within \(\Phi_i\). In similar fashion, event \(\mathcal{E}_i\) also only depends on the randomness in sector \(\Psi_i \setminus \mathcal{B}_0(r^*)\). Therefore, a Chernoff bound applies and we obtain \[\begin{align} \label{eq:X-concentration} \mathbf{P}\left(X \in n^{\Omega(1)} \text{ }|\text{ }V \cap \mathcal{B}_0(r^*) = \emptyset\right) \in 1 - n^{-\omega(1)}. \end{align}\tag{17}\] Next, we show for a sector \(\Psi_i\) where event \(\mathcal{E}_i\) occurs, that all neighbours of the nice sector \(\Phi_i\) are contained in \(\Psi_i\) if we condition on the event that \(V \cap \mathcal{B}_0(r^*) = \emptyset\). Note that if \(\Phi_i\) is nice, it holds for any vertex \(u \in V \cap \Phi_i\) that \(r(u) \geq R - \log\log n -2\). As such, the largest possible angle spanned among a vertex \(u \in V \cap \Phi_i\) and any vertex \(v \in V \cap \mathcal{D}_R\setminus\mathcal{B}_0(r^*)\) is \[\begin{align} \label{eq:angle-neighbour-bound} \theta_R(r(u), r(v)) \leq \theta_R(R - \log\log n - 2, \underbrace{R - \log n/\alpha - \log\log n /2}_{r^*}) \in \mathcal{O}\left(\frac{n^{\frac{1}{2\alpha}}\cdot \log^{3/4}n}{n}\right) \in o(\psi), \end{align}\tag{18}\] by 1. Hence, for any \(u \in V \cap \Phi_i\) it holds that \(N(u) \subseteq V \cap (\Psi_i\setminus \mathcal{B}_0(r^*))\).

In the next step, we bound the probability of the event that the area \(\mathcal{B}_0(r^*)\) is empty (see hatched area in 3b). Note that by 2 the expected number of vertices in this area is \(n\cdot\mu(B_0(r^*)) \in o(1)\). Hence, it holds via Poisson distribution that \[\begin{align} \label{eq:empty-inner-disk} \mathbf{P}\left(V \cap \mathcal{B}_0(r^*) = \emptyset\right) \in e^{-o(1)} \in 1 - o(1). \end{align}\tag{19}\] Thus, using 17 , 19 , and law of total probability we then get that \[\begin{align} \label{eq:X-concentration2} \mathbf{P}\left(X \in n^{o(1)}\right) \leq \mathbf{P}\left(V \cap \mathcal{B}_0(r^*) \neq \emptyset\right) + \mathbf{P}\left(V \cap \mathcal{B}_0(r^*) = \emptyset\right)\cdot \mathbf{P}\left(X \in n^{o(1)} \text{ }|\text{ }V \cap \mathcal{B}_0(r^*) = \emptyset\right) \in o(1). \end{align}\tag{20}\] It follows that, a.a.s., non of the induced subgraph tree \(T_i = G[V \cap \Phi_i]\) has any edge outside \(\Psi_i\) using 18 .

To wrap things up, consider the event that \(X \in n^{\Omega(1)}\) and let \(\mathcal{E}_{\text{giant}}\) be the event that any vertex in layer \(\overline{\ell} =\lceil 2\log\log n/(1-\alpha)\rceil\) is connected to the giant component of \(G\). Note that the intersection of the two events implies our theorem if also \(\mathcal{B}_0(r^*)\) contains no vertex, since event \(\mathcal{E}_i\) ensures that \(T_i\) is connected to the giant component in the desired way of the "in particular" statement of [pro:d-regular-trees].

To bound the probability of event \(\mathcal{E}_{\text{giant}}\) we observe the following: using [42] any vertex \(v \in V \cap \mathcal{L}_{\overline{\ell}}\) is connected to the set of vertices in \(V \cap \mathcal{B}_0(R/2)\) with probability \(1-o(1)\). Moreover, by [54], all vertices of the set \(V \cap \mathcal{B}_0(R/2)\) are part of the giant component with probability \(1-o(1)\). Thus, we conclude that also any \(v \in V \cap \mathcal{L}_{\overline{\ell}}\) is part of the giant component with probability \[\begin{align} \label{eq:giant} \mathbf{P}\left(\mathcal{E}_{\text{giant}}\right) \in 1-o(1). \end{align}\tag{21}\] Though, the three events \(X \in n^{\Omega(1)}\), \(\mathcal{E}_{\text{giant}}\) and \(V\cap \mathcal{B}_0(r^*) = \emptyset\) are not independent, a union bound of the complements yields via 19 , 20 and 21 \[\begin{align} \label{eq:wrap-up} \mathbf{P}\left(X \in n^{\Omega(1)} \cap \mathcal{E}_{\text{giant}} \cap V \cap \mathcal{B}_0(r^*) = \emptyset\right) \in 1 - o(1). \end{align}\tag{22}\] Using 22 then finishes the proof as the desired structural properties of a \(d\)-ary tree in a nice sector now follow from 10. ◻

Proof. We aim to design an algorithm \(A_{\text{tree}}\) for our infinite family of balanced \(d\)-regular trees with degree \(d\) and height \(h\), such that \(A_{\text{tree}}\) has error probability at most \(2p(n)\). To do so, we run algorithm \(A_{\text{hrg}}\) on the vertices of \(T\), pretending that \(T\) is an HRG \(G\sim\mathcal{G}(n, \alpha, C)\) where \(n\) is suitably chosen such that \(n'_{\text{hrg}}\), \(d_{\text{hrg}}\), and \(h_{\text{hrg}}\) satisfy the conditions of 1. To prove that algorithm \(A_{\text{tree}}\) is well-defined, we consider its behaviour on a \(d\)-regular tree \(T\) with \(n'\) vertices, and also consider the giant component of an HRG \(G\) that contains an induced tree substructure \(T_{\text{hrg}}\) as stated in 1. Note that \(T_{\text{hrg}}\) contains \(T\) as an induced subgraph, and to show that the execution of \(A_{\text{tree}}\) is well-defined, we next consider a mapping of the vertices from \(T\) to \(T_{\text{hrg}}\).

Let \(U\subseteq V(T)\) be the set of vertices that are at a distance at most \(r\) from the leaves of \(T\), and let \(I=V(T)\setminus U\). Let \(N_{r}[U],N_{r}[I]\) be the \(r\)-hop neighbourhood of \(U,I\), respectively. For \(r < h\), we will map each of these subgraphs from \(T\) to \(T_{\text{hrg}}\) such that the \(r\)-hop local view of each vertex \(u\in V(T)\) is the same as the \(r\)-hop local view of a vertex \(v\in V(T_{\text{hrg}})\).

Since \(N_{r}[U]\) contains the vertices up to distance \(r\) from the leaves, if we assume that \(N_{r}[U]\) contains \(k\) leaves, we map the \(k\) leaves of \(N_{r}[U]\) to the \(k\) “leftmost” leaves of \(T_{\text{hrg}}\). After that, we map the rest of the vertices \(N_{r}[U]\) to vertices \(T_{\text{hrg}}\) so that the mapping preserves the \(r\)-hop neighbourhoods of the vertices in \(U\). Let \(M(U)\) be the set of vertices in \(T_{\text{hrg}}\) that \(N_{r}[U]\) was mapped to. With this partial mapping, we have guaranteed that if we run \(A_{\text{tree}}\) on \(T\), every vertex \(u\in U\) has a copy vertex \(v\in V(T_{\text{hrg}})\) with the same view. Additionally, by the choice of \(r<h/2\leq h_{\text{hrg}}/200\), no vertex in \(U\) can identify that they are not in an HRG \(G\).

We will now map the vertices from \(N_{r}[I]\). First, note that the diameter of the induced subgraph \(T':= N_{r}[I]\) is the same as \(T\), if we first remove the leaves of \(T\). Therefore, the induced subgraph of \(N_{r}[I]\) has height \(h-1\). Now let \(w\in V(T')\) be the unique vertex that is at distance \(h-1\) from every leaf of \(T'\). Also, among the vertices of \(T_{\text{hrg}}\) that are part of the partial mapping of \(N_{r}[U]\), let \(v\in M(U)\) be one of the vertices that are furthest away from the leaves in \(T_{\text{hrg}}\). Starting from \(v\), we traverse \(h-1\) hops towards the “root” of the \(T_{\text{hrg}}\), and let \(w'\in V(T_{\text{hrg})}\) be the vertex we arrive at. We map \(w\in V(T')\) to \(w'\in V(T_{\text{hrg}})\). After that, we map the rest of the vertices \(N_{r}[U]\) to vertices \(T_{\text{hrg}}\) so that the mapping preserves the \(r\)-hop neighbourhoods of the vertices in \(I\). Let \(M(I)\) be the set of vertices in \(T_{\text{hrg}}\) that \(N_{r}[I]\) was mapped to. Note that by our choice of \(w\), \(w'\), and \(r\), every vertex in \(M(I)\) is neither a leaf nor a root. This guarantees that the vertices in \(I \subset V(T)\) cannot distinguish that they are not on an HRG \(G\) after the execution of \(A_{\text{tree}}\). Additionally, every vertex in \(N_{r}[I]\) has an identical \(r\)-hop local view to its mapped vertex in \(M(I)\).

We now proceed by bounding the error probability of \(A_{\text{tree}}\). To this end, we utilise the mapping we laid out above. Since MIS and MM are locally checkable problems, if \(A_{\text{tree}}\) fails on \(T\), then there is a local witness of failure centred either at a vertex of \(U\) or at a vertex of \(I\). Denote these two events by \(F_U\) and \(F_I\). Thus, by union bound, we have \[\begin{align} \mathbb{P}\left(A_{\text{tree}}\text{ fails on } T\right) \le \mathbb{P}\left(F_U\right)+\mathbb{P}\left(F_I\right). \end{align}\] We first bound \(\mathbb{P}\left(F_U\right)\). To achieve this, we couple the randomness of the algorithm \(A_{\text{hrg}}\) on the vertices \(N_r[U]\) with the randomness of the algorithm \(A_{\text{tree}}\) on the mapped vertices in \(M(U)\). Since \(r\le h(n)/200\), no vertex in \(M(U)\) “sees” the unique attachment vertex of \(T_{\text{hrg}}\) to \(G\setminus T_{\text{hrg}}\). Hence, the radius-\(r\) views used by \(A_{\text{tree}}\) in \(T_{\text{hrg}}\) and the radius-\(r\) views seen by \(A_{\text{hrg}}\) in \(G\) are identical for all vertices relevant to a failure witness centred in \(U\). Therefore, under this coupling, every occurrence of \(F_U\) yields a local MIS, respectively, MM, violation in the output of \(A_{\text{hrg}}\) on \(G\). Consequently, by the hypothesis of our lemma statement, it holds \[\begin{align} \mathbb{P}\left(F_U\right)\le \mathbb{P}\left(A_{\text{hrg}}\text{ fails on } G\right)\le p(n). \end{align}\] It remains to bound \(\mathbb{P}\left(F_I\right)\). For vertices in \(I\), the relevant \(N_r[I]\) are far from the leaves. We couple the algorithm \(A_{\text{tree}}\) for \(N_r[I]\) with the algorithm \(A_{\text{hrg}}\) for the mapped vertices in \(M(I)\) that are also far from both the leaves and the unique attachment point to \(G\setminus T_{\text{hrg}}\). Thus, all radius-\(r\) views used by \(A_{\text{tree}}\) around a potential failure witness in \(I\) are identical to the corresponding views of \(A_{\text{hrg}}\) in an execution on \(G\). Hence every occurrence of \(F_I\) also yields a local violation of the output of \(A_{\text{hrg}}\) on \(G\), and therefore again \[\begin{align} \mathbb{P}\left(F_I\right)\le \mathbb{P}\left(A_{\text{hrg}}\text{ fails on } G\right)\le p(n). \end{align}\] Combining the two bounds gives \(\mathbb{P}\left(A_{\text{tree}}\text{ fails on } T\right) \le \mathbb{P}\left(F_U\right)+\mathbb{P}\left(F_I\right) \le 2p(n).\) Equivalently, if \(A_{\text{tree}}\) failed with probability greater than \(2p(n)\), then either \(F_U\) or \(F_I\) would occur with probability greater than \(p(n)\), contradicting the correctness guarantee of \(A_{\text{hrg}}\) under the corresponding coupling. ◻

Proof sketch:. The result directly follows with 1 (see Appendix 10 for a discussion), given that [52] show that the respective sequences to apply the theorem exist for MIS and MM. More detailed, [52] shows that such a sequence with \(t=\Theta(d)\) and \(f(d)=2^{d+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 \(z\). For MIS the vector is of length \(2\) (formally \(len(z)=1\) in their terminology) and the fingerprint vector of the original MIS problem is \([1,0]\). Then, fingerprint vectors can be obtained iteratively. The \(j\)-entry of the fingerprint for the \(i\)-th problem in the sequence is the \(j\)-prefix sum of the \(i-1\)-st fingerprint. Thus, the fingerprint vectors evolve like \([1,0]\), \([1,1]\),\([1,2]\), until \([1,t]\). They show that the sequence can be extended by yet another problem whenever the \(l1\)-norm of the vector is \(\leq \Delta\). So, for MIS we can do \(\Delta-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 [52] shows that the sequence for MIS is of length \(\Theta(d)\) with \(f(d)\leq 2^d(1+len(z))\) where \(len(z)=1\) for the MIS problem (in their paper \(len(z)=\beta\) which equals \(1\) for MIS, see Section 5.1 in the arxiv version of their work. Thus, via 1 the runtime bound for error probability \(p\) for MIS simplifies to \(\Omega\left(\min\left\{d,\log_{d}n, \log_{d}\log 1/p-\log_{d}\log 2^{d+1}\right\}\right)\). In particular, the term \(\log_{d}\log 2^{d+1} = \log_{d}({d+1}) \in \mathcal{O}(1)\).

For MM [90] (see e.g. Theorem 4.5) shows that the respective sequence with length \(t=2d-1\) and \(f(d)=5\) exists. For the latter, we cite from their work: Crucially, all the problems of the family 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, 1 yields a lower bound of \(\Omega\left(\min\left\{2d-1,\log_{d}n, \log_{d}\log 1/p-\log_{d}\log 5\right\}\right) \in \Omega\left(\min\left\{d,\log_{d}n, \log_{d}\log 1/p-\mathcal{O}(1)\right\}\right)\). ◻

Proof. Using 1 in conjunction with 12, it follows a.a.s. over the draw of \(G\sim\mathcal{G}(n, \alpha, C)\) that any \(o(\log\log n / \log\log\log n)\)-round randomised algorithm for MIS or MM on \(G\) that has an error probability of at most \(p\) would imply the existence of a \(o(\log\log n / \log\log\log n)\)-round randomised algorithm for MIS or MM on balanced \(d\)-regular trees, where the degree is \(d \in \Theta(\log\log n)\) and the tree has height \(h\in \Theta(\log\log n / \log\log\log n)\), with error probability at most \(2p\). Therefore, it suffices to show that no such algorithm exists on any such \(d\)-regular tree with running time \(o(\log\log n / \log\log\log n)\) and error probability at most \(2/n^{c}\), for every constant \(c>0\). Indeed, this immediately implies that a.a.s. over the draw of \(G\), there does not exist an \(o(\log\log n / \log\log\log n)\)-round randomised algorithm on \(G\) for MIS or MM with error probability \(p = 1/n^{c}\). Consequently, to establish our main result, it remains to prove that no such algorithm exists for balanced \(d\)-regular trees.

We show this by using 13. Fix any constants \(c, c_d, c_h > 0\) and consider a balanced \(d\)-regular tree \(T\) with degree \(d = c_d \cdot \log\log n\) and height \(h = c_h \cdot \log_d\log n\) giving a \(d\)-regular tree of size \(n' \geq (d-1)^{h} \geq \log^{c_n} n\) for some constant \(c_n > 0\). Since the runtime for any algorithm with error probability \(p'\) for MIS or MM on a balanced \(d\)-regular tree with \(n'\) vertices is \[\Omega(\min\{d, \log_d n', \log_d \log {1/p'}-\mathcal{O}(1)\})\] using 13, the runtime \(t\) for our tree \(T\) with parameters \(d = c_d \cdot \log\log n\), \(h = c_h \cdot \log_d\log n\) and \(n' \geq \log^{c_n} n\) is \[t\in \Omega\left(\min\left\{\log\log n, \frac{\log\log n}{\log\log\log n},\frac{\log\log n}{\log\log\log n}\right\}\right)\] setting \(p'=2/n^c\). Hence, \(t \in \Omega\left(\frac{\log\log n}{\log\log\log n}\right)\) and the theorem follows as this implies that a.a.s. for \(G\), an algorithm requires at least \(t\) rounds to obtain a probabilistic guarantee of \(1 - n^{-c}\) for MIS or MM for the giant component of \(G\). ◻

Proof. [item:one]: W.l.o.g. let \(R - \ell - 1 < r(u) \leq r(v) \leq R - \ell\). Then, using that \(N_\ell = 40\cdot \left\lceil \frac{n \cdot \pi e^{C/2}}{20e^{\ell}}\right\rceil \geq \frac{2 n \cdot \pi e^{C/2}}{e^{\ell}}\), it holds for the angular distance between \(u, v\) that \[\begin{align} \delta_\varphi(u,v) &\leq 2\pi/ N_\ell \leq \frac{e^{\ell}}{ne^{C/2}} \leq \theta_R(R- \ell, R - \ell) \leq \theta_R(r(u), r(v)), \end{align}\] by applying the lower bound of 1 and \(\theta_R(\cdot, \cdot)\) is monotonically decreasing in both arguments (see e.g. [56]). Hence, \(u\) and \(v\) have an edge as desired.

[item:two]: W.l.o.g. let \(R - \ell - 1 < r(u) \leq r(v) \leq R - \ell\). Then, using that there are at least \(19\) tiles in between \(u\) and \(v\) and that \(N_\ell = 40\cdot \left\lceil \frac{n \cdot \pi e^{C/2}}{20e^{\ell}}\right\rceil \leq \frac{2 n \cdot \pi e^{C/2}}{e^{\ell}} + 1\), it holds for the angular distance between \(u, v\) that \[\begin{align} \delta_\varphi(u,v) &\geq 38\pi/ N_\ell \geq \frac{18 e^{\ell}}{ne^{C/2}} > \frac{\pi e^{\ell+1}}{ne^{C/2}} \geq \theta_R(R- \ell - 1, R - \ell - 1) \geq \theta_R(r(u), r(v)), \end{align}\] by applying the upper bound of 1 and the monotonicity of \(\theta_R(\cdot, \cdot)\). Hence, \(u\) and \(v\) have no edge as desired.

[item:three]: Since \(v \in N(u)\), it holds \[\theta_R(r(u), r(v)) \leq \pi e^{(R-r(v) -r(u))/2},\] using 1. W.l.o.g. let \(u\) have angular coordinate \(\varphi(u) = 0\) such that \[\varphi(v) \leq \frac{\pi \cdot e^{\ell+1-C/2}}{n},\] using that \(\theta_R(\cdot, \cdot)\) is monotonically decreasing in both arguments and \(r(u), r(v) \geq R - \ell - 1\).

On the other hand, we have \[\varphi(u') \geq 78\pi/ N_\ell \geq \frac{38 e^{\ell}}{ne^{C/2}} ,\] using that \(\varphi(u) = 0\) and between \(u\) and \(u'\) there are at least \(39\) tiles as \(|i-j|\geq 40\).

Combining these bounds on the angle, we get for the angular distance between \(u'\) and \(v\) that \[\delta_\varphi(u',v) = |\varphi(u') - \varphi(v)| \geq \frac{38 e^{\ell}}{ne^{C/2}} - \frac{\pi \cdot e^{\ell+1-C/2}}{n} > \frac{10 e^{\ell}}{ne^{C/2}} > \frac{\pi \cdot e^{\ell+1-C/2}}{n} > \theta_R(r(u'), r(v)),\] using the monotonocity of \(\theta_R(\cdot, \cdot)\), \(r(u'), r(v) \geq R - \ell - 1\) and 1. Subsequently, \(v \not\in N(u')\) which is what we sought to prove. ◻

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 \(\ell, m = 0\), i.e., the first active tiles in the algorithm such that \(I = \emptyset\).

We fix any active tile, i.e., a tile \(\mathcal{T}_{0,i}\) such that \(i \equiv 0 \pmod{40}\). Since all vertices that share the same tile form a clique by 14 [item:one], in the Selection step, every active tile with at least one vertex has exactly one vertex \(u\) that tries to be part of the set \(I\). So it is sufficient to show that \(u\) has no active neighbour in any other active tile. By the Activation step and using [rem:divisible], 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 \(\mathcal{T}_{0,i}\), any vertex \(v\) that is included in any other active tile is not a neighbour of \(u\) by 14 [item:two]. ◻

Proof. Using Observation [obs:tile-layer0], it is sufficient to show that for any vertex \(u\) with radius \(r(u) \geq R - 4\log\log n\), there exists at least one neighbour \(v \in N(u) \cap \mathcal{T}_{0,i}\) such that \(i \equiv 0 \pmod{40}\).

To show this, fix any vertex \(u\) with radius \(r(u) \geq R - 4\log\log n\) and note that, since \(\theta_R(r(u), R) \in \Omega(\log^2(n)/n)\) (using 1) and the angular width of a tile \(\mathcal{T}_{0,i}\) is at most \(\Theta(1/n)\) (by 23 ), there are at least \(\Omega(\log^2 n)\) tiles \(\mathcal{T}_{0,i}\) such that \(i \equiv 0 \pmod{40}\) in the neighbourhood disk \(\mathcal{B}_u(R)\). Hence, it is sufficient to show that at least one of the \(\Omega(\log^2 n)\) tiles contains any vertex. Since tiles do not overlap and \(\mu(\mathcal{T}_{0,i}) = \mu(\mathcal{L}_{0})/{N_0} \in \Omega(1/n)\) (using ?? and angle \(1/N_0 \in \Theta(1/n)\) of a tile \(\mathcal{T}_{0,i}\)), we conclude that the expected number of vertices in distinct active tiles (tiles \(\mathcal{T}_{0,i}\) tiles such that \(i \equiv 0 \pmod{40}\)) in the neighbourhood disk \(\mathcal{B}_u(R)\) is \(\Omega(\log^2 n)\). Since the number of vertices in each tile follow a Poisson-distribution, a Chernoff-bound yields that there is at least one active tile in the neighbourhood radius of \(u\) with probability \(1 - n^{-\omega(1)}\). Hence,\(u\) has a neighbour \(v \in N(u) \cap \mathcal{T}_{0,i}\) that participates in the set \(I\) with probability \(1 - n^{-\omega(1)}\) and a union bound over all vertices gives the desired result. ◻

Proof. Note that if for all \(\ell \in [\lceil 4\log\log n\rceil + 1]\) it holds that after iteration \(\ell\) all vertices up to radius \(R - \ell\) 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 \(\ell = 0\), observe that for any \(m\) in 10 that for any pair of active vertices \(u,v\), either (a) \(u\) and \(v\) lie in the same tile, or (b) there are at least \(39\) tiles between \(u\) and \(v\). This follows from the Activation step of Embedding-aware-MIS together with [rem:divisible]. Hence, by 14, 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 \(u\) to be included in the \(I\), and all other vertices in the same tile will have \(u\) as a neighbour that is included in the set \(I\). This is achieved by the Selection step in Embedding-aware-MIS and as such, for \(\ell = 0\), all vertices \(V \cap \mathcal{L}_{\ell = 0}\) are either part of the set \(I\), or they have a neighbour that is in the set \(I\) since every tile gets processed exactly once. Thus, after iteration \(\ell = 0\), the set \(I\) is a maximal independent set for \(G[V \cap \mathcal{L}_{0}]\) since any tile in \(\mathcal{L}_{0}\) is exactly once active.

For the induction step, fix any \(\ell\) and suppose that, by the induction hypothesis, after processing layers \(0,\dots,\ell-1\), the set \(I\) is a maximal independent set of \(G\left[V \cap \left(\mathcal{D}_R\setminus \mathcal{B}_0(R-\ell-1)\right)\right].\) Consider iteration \(\ell\) of 10. Any vertex \(u \in V_\ell\) that already has a neighbour in \(I\) is not activated by the algorithm and is therefore already dominated. Hence, it remains to consider the active vertices, namely those in \(V_\ell \setminus N(I)\).

On the induced subgraph \(G[V_\ell \setminus N(I)]\), the same arguments as in the base case apply. For any fixed value of \(m\), active vertices are either contained in the same tile or are separated by at least \(39\) tiles. Thus, by 14, 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 \(I\).

Therefore, after iteration \(\ell\), every vertex in \(V_\ell\) either already had a neighbour in \(I\) before the iteration or is itself added to \(I\) or has a neighbour that is added to \(I\) during the iteration. Hence, after processing every tile in layer \(\ell\) exactly once, every vertex up to radius \(R-\ell\) is either contained in \(I\) or has a neighbour in \(I\), completing the induction. ◻

Proof. This follows from noting that Embedding-aware-MIS iterates through \(\mathcal{O}(\log\log n)\) layers and \(m \in \mathcal{O}(1)\) in line 4 of 10. 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 \(\mathcal{O}(\log n)\) bits w.h.p. by 25 to obtain an ordering that is required for the Selection step. Hence \(\mathcal{O}(1)\) communication rounds per iteration are sufficient w.h.p. for \(\mathsf{CONGEST}\). Thus, we obtain that the number of rounds is \(\mathcal{O}(\log\log n)\) w.h.p. as claimed. ◻

Proof. Note that set \(I\) fulfils the properties of an MIS and thus, the result that Embedding-aware-MIS produces an MIS follows from 15 and 16. The runtime for \(\mathsf{CONGEST}\) follows from 17. ◻

Proof. We use the following claim, which says that in constant rounds we can compute a matching such that each tile²⁰ contains at most one unmatched vertex²¹.

Now, applying Claim [claim:tile-single-vertex] to each tile of layer \(\ell\) in parallel, after constant rounds, there is at most \(1\) unmatched vertex in each tile \(\mathcal{T}_{\ell,i}\). Given this property, we iterate through \(\mathcal{L}_{\ell}\) as follows: for \(t \in [40]\) we attempt to match any possible unmatched vertex \(u \in V \cap \mathcal{T}_{\ell,i}\) where \(i \equiv t \;(\mathrm{mod}\;40)\), i.e., we “activate” every 40-th tile. We do so by first letting every unmatched vertex \(v\) send its layer \(\ell \in \mathcal{O}(\log n)\) to every neighbour \(N(v)\) in constant rounds. Thereafter, we activate any vertex \(u \in V \cap \mathcal{T}_{\ell,i}\) where \(i \equiv t \;(\mathrm{mod}\;40)\). Let \(N'(u)\) be the set of unmatched neighbours of \(u\) and \(u\) marks the set of unmatched vertices \(N'(u) \cap V_{\ell}\). Then \(u\) picks a vertex \(v\) uniform at random from \(N'(u) \cap V_{\ell}\) and {u,v} is added to \(M_{\ell}\). Since in each iteration \(t\), we have for any pair of active vertices \(u \in V \cap \mathcal{T}_{\ell,i}\) and \(u' \in V \cap \mathcal{T}_{\ell,j}\) that \(|i-j|\geq 40\), it follows by 14 that \(N(u) \cap N(u') = \emptyset\). Therefore, no conflict can occur: no unmatched vertex can receive matching requests from two distinct active vertices during the same iteration phase \(t\). Since after \(40\) iterations we tried to match any unmatched vertex in \(\mathcal{L}_{\ell}\) and each iteration requires \(\mathcal{O}(1)\) rounds while also \(t \in \mathcal{O}(1)\), the procedure terminates after constant rounds. Moreover, \(M_{\ell}\) is maximal for \(G_{\ell}\): when a tile \(\mathcal{T}_{\ell,i}\) is processed, the unique unmatched vertex of tile \(\mathcal{T}_{\ell,i}\) is matched whenever it has an unmatched neighbour. Therefore, after tile \(\mathcal{T}_{\ell,i}\) 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 \(M_{\ell}\) for \(G_{\ell}\) as desired. ◻

Proof. We consider two cases. First, if the two annuli \(\mathcal{A}_{i,k}\) and \(\mathcal{A}_{j,k'}\) have distance larger than \(4\), i.e., for any pair of points \(x \in \mathcal{A}_{i,k}\) and \(y \in \mathcal{A}_{j,k'}\) it holds \(\mathop{\mathrm{d_h}}(x,y) \geq 4\).

Case 1 [For the two annuli it holds \(i-j \geq k + 4\)]: consider the given matchings \(M_1\) and \(M_2\). Under these matchings, all unmatched vertices \(v \in V \cap \mathcal{A}_{j,k'}\) send to any neighbour \(w \in N(v)\) their layer \(\ell\) in constant rounds. Then, if an unmatched vertex \(u \in V \cap \mathcal{A}_{i,k}\) has at least one unmatched neighbour in \(V \cap \mathcal{A}_{j,k'}\), let \(N'(u):= N(u) \cap \mathcal{A}_{j,k'}\) and \(u\) picks uniform at random a neighbour \(v\) from \(N'(u)\) and \(\{u,v\}\) is included in our matching \(M\) such that \(v \in V \cap \mathcal{A}_{j,k'}\). It is left to show that no unmatched vertex \(v \in V \cap \mathcal{A}_{j,k'}\) can receive matching requests from two distinct vertices \(u, u' \in V \cap \mathcal{A}_{i,k}\) in the same round. To see this, recall that under matching \(M_1\), for any unmatched pair \(u\) and \(u'\), there is no edge \(\{u,u'\} \in E\) since \(M_1\) is maximal such that two unmatched vertices cannot be adjacent. Hence, it holds \(\mathop{\mathrm{d_h}}(u,u') \geq R\). Now, for the sake of contradiction, assume that \(v \in N(u) \cap N(u')\). By our case assumption, it holds \(r(u), r(u') \leq r(v) - 4\). By an application of 5, \(v\) has distance at most \(R\) to both \(u\) and \(u'\) if and only if \(\mathop{\mathrm{d_h}}(u,u') \leq R\). A contradiction, and thus, we can obtain the desired matching \(M\) in constant rounds.

Case 2 [For the two annuli it holds \(i-j < k + 4\)]: let \(m := \min(i+3, k)\) and \(m' := \max(j, k'-3)\). We consider the two "border" annuli \[\mathcal{A}_1 := \bigcup_{\ell = i}^m (\mathcal{L}_{\ell}) \subseteq \mathcal{A}_{i,k} \text{ and } \mathcal{A}_2 := \bigcup_{\ell = m'}^{k'} (\mathcal{L}_{\ell}) \subseteq \mathcal{A}_{j,k'}.\]

For a visualisation, see the hatched area in 11b. Note that we can find a maximal matching \(M'\) for the induced subgraph \(G' = (V \cap (\mathcal{A}_{i,k} \cup (\mathcal{A}_{j,k'} \setminus \mathcal{A}_2)), E \setminus (M_1 \cup M_2))\) in constant rounds by the previous case when \(i-j \geq k + 4\). Analogously, we can find a matching \(M''\) for the induced subgraph \(G'' = (V \cap ( \mathcal{A}_{j,k'} \cup (\mathcal{A}_{i,k} \setminus \mathcal{A}_1)), E \setminus (M_1 \cup M_2 \cup M'))\) in constant rounds. Hence, after constant rounds, we can obtain a matching \(M_1 \cup M_2 \cup M' \cup M'' =: \tilde{M}\), such that for a maximal matching \(M \supseteq \tilde{M}\) where \(M \subseteq E(G_1 \cup G_2)\), all edges \(M\setminus \tilde{M}\) are formed among vertex pairs \(u,v\) where \(u \in V \cap \mathcal{A}_1\) and \(v \in V \cap \mathcal{A}_2\).

We then find such a set of edges \(M\setminus \tilde{M}\) in additional constant rounds as follows: we use \(m-i+1\) iterations (iterating layer by layer through \(\mathcal{A}_1\)), where we consider in iteration \(t \in [m-i+1]\) all unmatched vertices of the set \(V \cap \mathcal{L}_{m-t}\). That is, we iterate through the layers of \(\mathcal{A}_1\) in top-down fashion. By using Claim [claim:tile-single-vertex], we can assume that each tile in \(\mathcal{L}_{m-t}\) contains at most \(1\) unmatched vertex after constant rounds. Then, for \(t' \in [40]\), in step \((t, t')\), we activate the set of unmatched vertices where \(u \in V \cap \mathcal{T}_{\ell,b}\) fulfils \(b \equiv t' \;(\mathrm{mod}\;40)\). That is, we activate every \(40\)-th tile. We then match in parallel any such active vertex \(u\) with an unmatched vertex \(v \in V \cap \mathcal{A}_2\) uniform at random from the set of unmatched neighbours of \(u\) in \(\mathcal{A}_2\). This can be done in \(\mathcal{O}(1)\) rounds. Using 14, it holds for any pair of active vertices \(u,u'\) that \(N(u) \cap N(u') \cap \mathcal{A}_2 = \emptyset\) and thus, no conflict occurs by this procedure since any active tile contains at most one unmatched vertex. Since \(\mathcal{O}(40\cdot(m-i+1))\) is constant, this procedure requires \(\mathcal{O}(1)\) rounds. Using the obtained matching by this procedure in conjunction with our matching \(\tilde{M}\) (which we acquired in constant rounds), we obtain our desired matching \(M\) in \(\mathcal{O}(1)\) rounds, which is maximal by similar arguments as used in 18: in iteration \((t,t')\), after processing a tile, its unique unmatched vertex has either been matched or has no unmatched neighbour in \(\mathcal{A}_2\). Since every tile of \(\mathcal{A}_1\) is processed exactly once, no unmatched edge remains between the border annulli \(\mathcal{A}_1\) and \(\mathcal{A}_2\). Together with the maximality of \(\tilde{M}\) on all remaining vertex pairs, this implies that \(M\) is a maximal matching of \(G[U_1 \cup U_2]\) as desired. ◻

Proof. Match inner-disk. By applying 8, in constant rounds we can find a matching \(M \subseteq E\), such that for any \(u \in V \cap \mathcal{B}_0(R - 6\log\log n)\), there exists an edge \(E(u) \in M\) w.e.h.p. For the rest of the proof we condition on this matching and focus on matching vertices outside \(\mathcal{B}_0(R - 6\log\log n)\) since all vertices in \(V \cap \mathcal{B}_0(R - 6\log\log n)\) are matched in constant rounds.

Match within layers. Next, we consider the \(\lceil 6\log\log n\rceil\) layers of the outer disk \(\mathcal{D}_R\setminus \mathcal{B}_0(R - \lceil 6\log\log n\rceil)\). Using 18, we compute in parallel, for every layer \(\mathcal{L}_{\ell}\) contained in \(\mathcal{D}_R\setminus \mathcal{B}_0(R - \lceil 6\log\log n\rceil)\), a maximal matching in \(G[V_\ell]\) in constant rounds w.h.p.

Match annuli. Now, we finish the proof by induction.

Base case: For each \(i \in [\lceil 3 \log\log n\rceil]\), consider the annuli \(\mathcal{A}_{2i,2} = \mathcal{L}_{2i} \cup \mathcal{L}_{2i+1}.\) That is, each annulus consists of two consecutive layers. Using 19, we compute in parallel, for every \(i \in [\lceil 3 \log\log n\rceil]\), a maximal matching for the annulus \(\mathcal{A}_{2i,2}\) in constant rounds.

Induction step: Consequently, we can repeat this process \(t\) times, doubling the annulus size in each step. More formally, in iteration \(t \in [\lceil \log_2\log\log n + 3 \rceil] \setminus\{0\}\), for \(i \in [\lceil 6\cdot 2^{-t} \log\log n\rceil]\) and \(k = 2^t\) we consider the annuli \(\mathcal{A}_{k \cdot i,k}\). By our induction hypothesis, for all \(i' \in [\lceil 6\cdot 2^{-(t-1)} \log\log n\rceil]\) and \(k' = 2^{t-1}\) we have a maximal matching for all the annuli \(\mathcal{A}_{k' \cdot i',k'}\) after \(\mathcal{O}(t-1)\) rounds. Thus, by an application of 19, we obtain, after an additional constant number of rounds, a maximal matching for all annuli \(\mathcal{A}_{k \cdot i,k}\) after iteration \(t\). That is, we “merge” two “neighbouring” annuli in constant rounds.

Setting \(t= \lceil \log_2\log\log n + 3 \rceil\) we obtain for an annulus of size \(k\geq \lceil 6\log\log n\rceil\) a maximal matching in \(\mathcal{O}(\log\log\log n)\) rounds. Thus, we can find a maximal matching for the outer disk \(\mathcal{D}_R\setminus \mathcal{B}_0(R - \lceil 6\log\log n\rceil)\) in \(\mathcal{O}(\log\log\log n)\) rounds. This, in conjunction with 8, yields a maximal matching for \(G\) in \(\mathcal{O}(\log\log\log n)\) rounds w.h.p. as claimed. ◻

Proof. Chosen with hindsight, let \(\psi := 2(1 - 1/1000)e^{R/2-r}\) and, w.l.o.g., let \(\varphi(u) = 0\). Then consider the sector \(\Phi := \{x \in \mathcal{D}_R: 0 \leq \varphi(x) \leq 3c \cdot\psi\}\), i.e., the sector that lies counter-clockwise to vertex \(u\), where one ray of \(\Phi\) intersects \(u\). We partition \(\Phi\) into \(3c\) equally sized sub-sectors, such that for all \(i \in [3c+1]\setminus\{0\}\), sector \(\Phi_i\) has angle \(\psi\). Now, let \(\mathcal{S}_i := \Phi_i \cap (\mathcal{B}_0(r)\setminus\mathcal{B}_0(r-1/1000))\). We show that for \(\mathcal{S}:= \bigcup_{i=1}^{3c}\), there exists a subset of vertices \(W \subseteq V \cap \mathcal{S}\), s.t. \(G[W]\) induces the desired similar degree path of \(u\) w.e.h.p. First, we note that by 3, every vertex \(w \in W\cup \{u\}\) has degree \(\mathbf{E}\left[\deg(w)\right] \in \Theta(n\cdot e^{-r/2})\). Since \(r \leq 2\log n - \frac{2\log\log n}{1-\alpha}\), and for every \(w \in W\) it holds \(r - 1/1000 \leq r(w) \leq r\) a Chernoff and union bound reveals for all \(w \in W\) that \(\deg(w) \in \Theta(\deg(u))\) with probability \(1 - n^{-\omega(1)}\) Next, we observe that the expected number of vertices in \(\mathcal{S}_i\) is \[\mathbf{E}\left[|V \cap \mathcal{S}_i|\right] = n \mu(\mathcal{S}_i) = \frac{n\psi}{2\pi}\mu(\mathcal{B}_0(r)\setminus\mathcal{B}_0(r-1/1000)) = \Theta(1)n\cdot e^{R/2-r}\cdot e^{-\alpha(R-r)},\] by our choice of \(\psi\) and 2. Using that hypothesis that \(r \leq 2\log n - \frac{2\log\log n}{1-\alpha}\) and \(R = 2\log n + C\) we then have \(\mathbf{E}\left[|V \cap \mathcal{S}_i|\right] \in \Omega(\log^2 n)\). Using Poisson distribution for each \(\mathcal{S}_i\) and a union bound for \(3c\) areas \(\mathcal{S}_i\), we have that each \(\mathcal{S}_i\) contains a vertex with probability \(1 - n^{-\omega(1)}\). We proceed by showing that, given that each \(\mathcal{S}_i\) contains at least one vertex, \(u\) has a similar degree path \(W\) of length \(c\), which finishes the proof. To this end, we use [89] and by our angular width \(\psi\), it follows for any \(x \in \mathcal{S}_{i}\) and \(y \in \mathcal{S}_{j}\) that \(\mathop{\mathrm{d_h}}(x,y) \leq R\) if \(|i - j| \leq 3\) while \(\mathop{\mathrm{d_h}}(x,y) > R\) if \(|i - j| \geq 5\) since \(r - 1/1000 \leq r(x), r(y) \leq r\). Consequently, if for every \(\mathcal{S}_i\) where \(i\) is divisible by \(3\) we include exactly one vertex \(w \in V \cap \mathcal{S}_i\) in the set \(W\), this ensures that \(G[W]\) induces a path of length \(c\). Moreover, \(u\) has an edge to the unique selected vertex \(w\in V\cap\mathcal{S}_3\), but not to any \(w \in V \cap \mathcal{S}_i\) if \(i\geq 6\). It follows that \(W\) is a similar degree path of length \(c\) of \(u\). Since every \(\mathcal{S}_i\) contains at least one vertex w.e.h.p. and all vertices \(w \in W\) have degree \(\deg(w) \in \Theta(\deg(u))\) w.e.h.p., a union bound over both events finishes the proof, where the ‘in particular’ statement directly follows from our construction of \(W\). ◻

Proof. We partition the disk \(\mathcal{D}_R\) into \(\left\lfloor\frac{n\cdot 2\pi}{n^{1/(2\alpha) + \varepsilon}} \right\rfloor =: k\) sectors, (where \(k \geq n^{1 - 1/2\alpha -\varepsilon}\in n^{\Omega(1)}\) due to our choice of \(\varepsilon< 1 - 1/(2\alpha)\)), such that for \(i \in [k]\), a sector \(\Phi_i\) has angle \(\phi \in \Theta(n^{1/(2\alpha) + \varepsilon}/n)\). We consider one such sector \(\Phi_i\) and let \(X_i\) be the indicator random variable that is \(1\) if \(\Phi_i\) contains a vertex \(u\) with properties [item:property1], [item:property2] and [item:property3]. We first show that \(\mathbf{P}\left(X_i =1\right) >0\). Thereafter, we show for \(X:= \sum_{i=1}^k X_i\) that \(X \in \Omega(k)\) a.a.s. what proves our desired statement.

8.0.0.1 [item:property1]:

Without loss of generality, let \(\Phi_i\) have bisector \(0\). Then, for \(\hat{\ell} := \lceil \varepsilon\cdot \log n \rceil\), let \(\mathcal{S} := \{x \in \mathcal{L}_{\hat{\ell}}: - n^{\alpha \cdot \varepsilon}/n < \varphi(x) < n^{\alpha \cdot \varepsilon}/n\} \subset \Phi_i\). Hence, using ?? , we obtain \[\mathbf{E}\left[|V\cap \mathcal{S}|\right] = n\cdot\mu(\mathcal{S}) = \Theta(1)\cdot n^{\alpha\cdot \varepsilon}\cdot e^{-\alpha\hat{\ell}} \in \Theta(1).\] Thus, since \(|V\cap \mathcal{S}|\) follows a Poisson-distribution, we get \[\begin{align} \label{eq:Prob-event1} \mathbf{P}\left(\mathcal{E}\right) >0, \qquad \mathcal{E} := \{|V \cap \mathcal{S}|=1\}. \end{align}\tag{24}\] Next, condition on event \(\mathcal{E}\) and let let \(u\) denote the unique vertex in \(V\cap\mathcal{S}\). Then it follows \[\begin{align} \label{eq:Prob-event2} \mathbf{P}\left(\mathcal{E}_1 | \mathcal{E}\right) \in 1 - n^{-\omega(1)}, \qquad \mathcal{E}_1 := \{\deg(u) \in \Theta(n^{\varepsilon/ 2})\}, \end{align}\tag{25}\] by ?? and a Chernoff-bound since \(u \in V_{\hat{\ell}}\) where \(\hat{\ell} = \lceil \varepsilon\cdot \log n \rceil\).

8.0.0.2 [item:property2]:

Let \(|L_0(u)| := |\{v \in N_0(u) : \deg(v) = 1 \}|\) as in 20. Then, using 20 it follows \[\begin{align} \label{eq:Prob-event3} \mathbf{P}\left(\mathcal{E}_2 | \mathcal{E}\right) >0, \qquad \mathcal{E}_2 := \{|L_0(u)| \in \Theta(n^{\varepsilon/ 2})\}, \end{align}\tag{26}\] since \(u\) is in layer \(\hat{\ell} = \lceil\varepsilon\log n\rceil\) and thus, \(r(u) \leq R - \lceil\varepsilon\log n \rceil\).

8.0.0.3 [item:property3]:

Applying 21, it follows that \[\begin{align} \label{eq:Prob-event4} \mathbf{P}\left(\mathcal{E}_3 | \mathcal{E}\right) \in 1 - n^{-\omega(1)}, \qquad \mathcal{E}_3 := \{|W(u)| \geq 2t\}, \end{align}\tag{27}\] and we remark that for event \(\mathcal{E}_3\), the vertices of \(W(u)\) are within an area \(\mathcal{S}' := \{x \in \mathcal{D}_R: R- \hat{\ell} - (1 + 1/1000) \leq r(x) \leq R - \hat{\ell} \text{ and } \varphi(u) \leq \varphi(x) \leq \varphi(u) + 6t\cdot (1 - 1/1000)e^{-R/2 +\hat{\ell} + 1 + 1/1000}\}\) by the ‘in particular’ statement in 21. Thus, \(\mathcal{S} \subset \Phi_i\), since \(\Phi_i\) has an angle of \(\Theta(n^{1/(2\alpha) + \varepsilon}/n)\) while \(\mathcal{S}'\) spans an angle \(\Theta(n^{\varepsilon}/n) \in o(n^{1/(2\alpha) + \varepsilon}/n)\), using that \(R = 2\log n +C\), \(t \in \mathcal{O}(1)\) and \(\hat{\ell} = \lceil \varepsilon\log n \rceil\). Our desired ‘moreover’ statement then follows since for any pair of sectors \(\Phi_i\) and \(\Phi_j\) where \(\mathcal{E} \cap \mathcal{E}_1 \cap \mathcal{E}_2 \cap \mathcal{E}_3\) occur, we consider \(u \in V \cap \Phi_i\) and \(u' \in V \cap \Phi_j\) to be the vertices occurring due to event \(\mathcal{E}\) and it holds for any pair \(v \in L(u) \cup W(u) \cup \{u\}\) and \(v' \in L(u') \cup W(u') \cup \{u'\}\) that \(\{v,v'\} \not\in E(G)\). This is since every object associated with \(u\) that is contained in \(\Phi_i\), and distinct sector \(\Phi_j\) are separated by an angular distance exceeding the maximal adjacency angle of 1 for any pair of vertices \(v \in L(u) \cup W(u) \cup \{u\}\) and \(v' \in L(u') \cup W(u') \cup \{u'\}\); there are no edges between distinct structures belonging to different sectors. Subsequently, if \(X \in \Theta(k)\) a.a.s. this finishes the proof.

To obtain this result, note first that \[\mathbf{P}\left(X_i = 1\right) = \mathbf{P}\left(\mathcal{E} \cap \mathcal{E}_1 \cap \mathcal{E}_2 \cap \mathcal{E}_3\right).\]

Then, using 24 , 25 , 26 and 27 in conjunction with a union bound and conditional probabilities, we have that \[\mathbf{P}\left(\mathcal{E} \cap \mathcal{E}_1 \cap \mathcal{E}_2 \cap \mathcal{E}_3\right) \geq \left(1 - \mathbf{P}\left(\mathcal{E}_1^C | \mathcal{E}\right) - \mathbf{P}\left(\mathcal{E}_2^C | \mathcal{E}\right) -\mathbf{P}\left(\mathcal{E}_3^C | \mathcal{E}\right)\right)\mathbf{P}\left(\mathcal{E}\right) > 0,\] and we conclude that \(\mathbf{E}\left[X\right] \in \Theta(k) \in n^{\Omega(1)}\).

We wrap up the proof as follows: we show for any \(i \neq j\) that \(X_i\) and \(X_j\) are independent so that a Chernoff bound yields \(X \in \Omega(k)\). To this end, we show that events \(\mathcal{E}, \mathcal{E}_1, \mathcal{E}_2,\) and \(\mathcal{E}_3\) in a sector \(\Phi_i\) only depends on the randomness of the Poisson point process in \(\Phi_i\).

8.0.0.4 Event \(\mathcal{E}\):

For event \(\mathcal{E}\) this is immediate since \(\mathcal{S} \subset \Phi_i\).

8.0.0.5 Event \(\mathcal{E}_1\):

For event \(\mathcal{E}_1\), note that by 19 there is no vertex in \(\mathcal{B}_0(r^*)\) a.a.s. where \(r^* = R - \log n/\alpha - \log\log n /2\). Thus, since \(u \in V_{\hat{\ell}}\) and \(\hat{\ell} = \lceil \varepsilon\log n \rceil\), the sector that we need to reveal to obtain the degree of \(u\) has angle at most \[n^{\alpha \cdot \varepsilon}/n + 2\theta_R(r^*, R - \hat{\ell} -2) \in \mathcal{O}\left(e^{(\hat{\ell} - r^* )/2}\right) \in o(\phi) \text{ a.a.s.,}\] using \(\phi \in \Theta(n^{1/(2\alpha) + \varepsilon}/n)\) and 1 in conjunction with [rmk:theta-monotonicity]. That is, a smaller angle than the angle spanned by \(\Phi_i\).

8.0.0.6 Event \(\mathcal{E}_2\):

By a similar argument we get for \(\mathcal{E}_2\), using that a leaf \(v \in L_0(u)\) has radius \(r(v) \geq R - 1\) and thus \(\delta_\varphi(u,v) \leq \theta_R(R- \hat{\ell} - 2, r(v)) \in \mathcal{O}(n^{-\varepsilon/2})\), a.a.s. that we do not require to reveal a sector with an angle that is larger than \(\mathcal{O}(n^{-\varepsilon/2}) + \theta_R(R-1, r^*) \in o(\phi)\) using 1.

8.0.0.7 Event \(\mathcal{E}_3\):

For event \(\mathcal{E}_3\), recall that we remarked that the vertices of \(W(u)\) are within an area \[\mathcal{S}' := \{x \in \mathcal{D}_R: R- \hat{\ell} - (1 + 1/1000) \leq r(x) \leq R - \hat{\ell} \text{ and } \varphi(u) \leq \varphi(x) \leq \varphi(u) + 6t\cdot (1 - 1/1000)e^{-R/2 +\hat{\ell} + 1 + 1/1000}\}.\] Thus, a.a.s., we need to reveal a sector of angle at most \(\mathcal{O}\left(e^{-R/2 +\hat{\ell}}\right) + \theta_R(r^*, R - \hat{\ell} -2)\). Using 1, \(\hat{\ell} = \lceil \varepsilon\log n \rceil\) and \(r^* = R - \log n/\alpha - \log\log n /2\), this angle is again \(o(\phi)\) and thus, also completely contained within sector \(\Phi_i\).

Finally, using that \(\mathbf{E}\left[X\right] \in \Theta(k) \in n^{\Omega(1)}\), it follows by a Chernoff bound \[\mathbf{P}\left(\mathcal{B}_0(r^*) \cap V = \emptyset\right) \mathbf{P}\left(X \in \Omega(k) | \mathcal{B}_0(r^*) \cap V = \emptyset\right) \in (1-o(1)) \cdot (1-e^{-\Omega(k)}).\] That is, \(|U(\varepsilon)| \in \Omega(k) \in \Omega\left(n^{1 - 1/2\alpha -\varepsilon}\right)\) a.a.s. as desired. ◻

Proof. With hindsight, we set \(\varepsilon:= \frac{1 - \frac{1}{2\alpha}}{2t(t+2)}\) and consider the set of vertices \(U(\varepsilon)\) of 22. We show that after \(t\) rounds there exists a.a.s. a vertex \(u \in U(\varepsilon)\) such that \(\deg_t(u) \in n^{\Omega(1)}\).

To this end, for \(i \in [t]\), let \(L_{(i)}(u) := \{v \in N(u) \cap V_{(i)} : \deg(v) = 1\}\) (the “remaining leaves” of \(u\) after round \(i\)), \(W_{(i)}(u):= \left(\bigcup_{j=1}^{2(t-i)}\{w_j\}\right)\cap V_{(i)}\)²² (the “remaining” similar degree path of \(u\) after round \(i\)) and we define the random variable \[\begin{align} K_{(i)} := |\{u \in U(\varepsilon) \cap V_{(i)} : |L_{(i)}(u)| \in n^{\Omega(1)} \text{ and } |W_{(i)}(u)| \geq 2(t-i)\}|. \end{align}\] Note that if \(K_{(t)} \geq 1\) a.a.s. this is sufficient to prove our desired statement and that \(K_{(0)} \in \Omega\left(n^{1 - 1/2\alpha - \frac{1 - \frac{1}{2\alpha}}{2t(t+2)}}\right)\) a.a.s. due to 22 and our choice of \(\varepsilon\). In order to prove \(K_{(t)} \geq 1\) a.a.s., we will use the following claim, which tells us that if \(K_{(i)}\) is polynomial in \(n\), then so is \(K_{(i+1)}\) a.a.s. given that \(i < t\).

Now, using that \(K_{(0)} \in \Omega\left(n^{1 - 1/2\alpha - \frac{1 - \frac{1}{2\alpha}}{2t(t+2)}}\right)\) a.a.s. by 22, and applying Claim [claim:appendix]iteratively for \(t \in \mathcal{O}(1)\) rounds, a union bound over the \(t\) induction steps yields \[\begin{align} \mathbb{P}\left(K_{(t)} \in \Omega\left(n^{1 - 1/2\alpha - \varepsilon-(t+1)\varepsilon(2t+1)} \right)\right) &\geq 1 - \mathbb{P}\left(K_{(0)} \not \in \Omega\left(n^{1 - 1/2\alpha - \frac{1 - \frac{1}{2\alpha}}{2t(t+2)}}\right)\right)\\ &- \mathbb{P}\left(\bigcup_{i=0}^{t-1} K_{(i+1)} \not \in \Omega\left(n^{1 - 1/2\alpha - \varepsilon-(i+1)\varepsilon(2t+1)} \right) | K_{(i)}\in \Omega\left(n^{1 - 1/2\alpha - \varepsilon-i\varepsilon(2t+1)} \right)\right)\\ &\in 1- o(1). \end{align}\] This finishes the proof since by our choice \(\varepsilon:= \frac{1 - \frac{1}{2\alpha}}{2t(t+2)} > 0\), \(K_{(t)} \in n^{\Omega(1)}\) a.a.s. ◻

Proof. The proof is almost verbatim along the proof of the almost identical claim in [52]. 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 \(p=1/n\). This is done in [52]. Instead, doing similar calculations with a general parameter \(p\) for the error probability leads to the following claim:

  Modified A.5: Let \(\Pi_0 \rightarrow \Pi_1 \rightarrow \cdots \rightarrow \Pi_t\) be a sequence of problems satisfying the conditions of 1. Any randomised algorithm in the port numbering model²⁵ running in strictly less than \(\min\{t, \frac{1}{10} (\log_{\Delta}(\log(1/p)) - \log_{\Delta} \log f(\Delta))\}\) rounds must fail with probability at least \(p\).

  Proof. Applying [52], after \(t\) rounds the error probability of any randomised algorithm is \[p_{\text{Error}} \geq \frac{1}{{f(\Delta)^{\Delta}}^{10 t}} \geq \frac{1}{{f(\Delta)^{\log (1/ p) / \log f(\Delta)}}} \geq p,\] where in the second step we used our hypothesis \(t < \frac{1}{10} (\log_{\Delta}( \log( 1/p)) - \log_{\Delta} \log f(\Delta))\). So we obtain \(p_{\text{Error}} \geq p\) as desired. ◻

• Change 2: In the proof of [52], the previous claim is lifted to the \(\mathsf{LOCAL}\) model using an indistinguishability argument. This argument only works if nodes cannot see the whole graph, requiring to cap the lower bound at \(\Omega(\log_{\Delta}n)\), which is the diameter of an \(n\)-node \(\Delta\)-regular tree. In their work, this does not appear in their theorem as the cap is always larger than the bound \(\log_{\Delta}( \log( 1/p)) - \log_{\Delta} \log f(\Delta))\) imposed when used with a hardcoded \(p=1/n\). Thus, for our theorem, the lower bound cannot exceed \(\log_{\Delta}n\), to which we adjust by adding it as a third argument in the min function.

  Modified A.6: Let \(\Pi_0 \rightarrow \Pi_1 \rightarrow \cdots \rightarrow \Pi_t\) be a sequence of problems satisfying the conditions of1. Any randomised algorithm running in the \(\mathsf{LOCAL}\) model, in \(\Delta\)-regular balanced trees of \(n\) nodes, that fails with probability at most \(p\), requires \(\Omega\left(\min\left\{t,\log_{\Delta}(\log( 1/p)) -\log_{\Delta}\log f(\Delta), \log_{\Delta} n \right\}\right)\) rounds.

Note that this is exactly our desired statement 1. ◻

Proof. Throughout the proof, we work with the binomial model of hyperbolic random graphs, in which the number of vertices is fixed to be \(n\). At the end of the proof, the result is transferred to the Poisson model with \(\mathbb{E}[N]=n\), incurring only a minor additional error probability (see also [43] for a detailed discussion).

Let \(b = \lceil c\cdot \log n \rceil\) as given by our hypothesis and let \(\mathcal{E}\) be the event that there exists a pair of vertices \(u,v \in [n]\) where \(\varphi_b(u) = \varphi_b(v)\). Since the angular coordinates are sampled independently and uniformly from \([0,2\pi)\), the first \(b\) bits of every angular coordinate form an independent uniformly distributed bit string in \(\{0,1\}^b\). Hence, for every fixed pair of distinct vertices \(u,v \in [n]\) we have \(\mathbf{P}\left(\varphi_b(u)=\varphi_b(v)\right) = 2^{-b}\). Subsequently, it holds for our "collision" event \(\mathcal{E}\) by a union bound \[\mathbf{P}\left(\mathcal{E}\right) \leq {n\choose 2}\cdot 2^{-b}\in\mathcal{O}(n^{-c+2}),\] where in the last step we plugged in \(b = \lceil c\cdot \log n \rceil\). We then obtain the desired probability bound by the transfer from the binomial model to Poisson [43] which yields \(\mathbf{P}\left(\mathcal{E}\right)\cdot\mathcal{O}(n^{1/2}) \in \mathcal{O}(n^{-c+5/2})\). ◻