Proofs. We give the proof of the upper bound on \(R_\alpha(\widehat{\sigma}_2)\) in Corollary 3; the other bounds follow analogously. The risk defined in 1 can be rewritten as follows: \[\begin{align} \notag R_\alpha(\widehat{\sigma}_2)=\sum_{u=1}^nu^{-\alpha}\mathbb{E}\big[|\widehat{\sigma}_2(u)-u|\big]&= \sum_{u=1}^n u^{-\alpha}\int_0^n\mathbb{P}\left(|\widehat{\sigma}_2(u)-u|\ge x\right)\;\mathrm{d}x\\ & \label{eq:coro5461insert} = \sum_{u=1}^n u^{1-\alpha}\int_0^{n/u}\mathbb{P}\left(|\widehat{\sigma}_2(u)-u|\ge u y\right)\;\mathrm{d}y. \end{align}\tag{14}\] When \(y > 1\), \(|\widehat{\sigma}_2(u)-u| \geq u y\) implies that \(\widehat{\sigma}_2(u) \geq uy\), since \(\widehat{\sigma}_2(u) \geq 0\). Thus, we get that \[\begin{align} \int_0^{n/u}\mathbb{P}\left(|\widehat{\sigma}_2(u)-u|\ge u y\right)\;\mathrm{d}y \leq 1 + \int_1^{\infty}\mathbb{P}\left(\widehat{\sigma}_2(u)\ge u y\right)\;\mathrm{d}y \overset{\eqref{jordan2:overest95combined}}{\leq } 1 + \int_1^{\infty} C \frac{1+\log(y)}{y^2} \mathrm{d}y \eqqcolon C^\star, \end{align}\] where \(C^\star>0\) is a constant not depending on \(u\). Inserting this bound into 14 finishes the proof of the upper bound. The other bounds in Corollaries 2 and 3 can be obtained analogously. ◻

Proof. By the definition of \(\phi_n(v)\) and \(v^{\scriptscriptstyle{({1}})}\) in 5 and 4 , we have \[\label{eq:phi-recap} \phi_n(v)=\min_{u\sim v}\big|(T_n, u)_{v\downarrow}\big|, \qquad v^{\scriptscriptstyle{({1}})}=\mathop{\mathrm{arg\,min}}_{u\sim v}\big|(T_n, u)_{v\downarrow}\big|, \qquad \phi_n(v^{\scriptscriptstyle{({1}})})=\min_{u\sim v^{\scriptscriptstyle{({1}})}}\big|(T_n, u)_{v^{\scriptscriptstyle{({1}})}\downarrow}\big|,\tag{24}\] where \((T_n,u)_{v\downarrow}\) denotes the subtree of \(v\) in the tree \(T_n\) when rooted at \(u\).

For the lower bound on \(\phi_n(v)\), we distinguish two cases, see also Figure 4.

If \(\mathrm{pa}(v)\) attains the minimum in the first equation in 24 , then \(\phi_n(v)=\big|(T_n, \mathrm{pa}(v) )_{v\downarrow}\big|=\mathrm{Fr}_n(v)=\mathrm{Fr}^{>v}_n(v)\). Assume next that the minimum is instead attained at a child \(c\) of \(v\), so \(\phi_n(v)=|(T_n, c)_{v\downarrow}|\). We claim that the tree \((T_n, c)_{v\downarrow}\) contains the fringe tree of vertex \(1\) witnessed after time \(v\). Indeed, if we pick a vertex \(w\) in this witnessed fringe tree, then the unique path from \(w\) to \(c\) has to contain the edge \(\{v, \mathrm{pa}(v)\}\) which arrived before time \(v+1\), and thus \(w \in (T_n, c)_{v\downarrow}\). Thus, we get that \(\phi_n(v) = |(T_n, c)_{v\downarrow}| \ge \mathrm{Fr}_n^{>v}(1)\) in this case.

As a result, we see that in either case we have \(\phi_n(v)\ge \min(\mathrm{Fr}_n^{>v}(v), \mathrm{Fr}_n^{>v}(1))\) when \(v\ge 2\), proving the first inequality of Lemma 2.

We proceed to the proof of inequality 22 . Recall from 6 that \[\phi_n^{\scriptscriptstyle{({2}})}(v) = (\phi_n(v))^2\vee\left(\phi_n(v)\cdot \phi_n(v^{\scriptscriptstyle{({1}})})\right).\] For the lower bound on \(\phi_n^{{\scriptscriptstyle{({2}})}}\), we distinguish three cases; see Figure 5.

Case 1: \(v^{\scriptscriptstyle{({1}})}=\mathrm{pa}(v)\ge 2\). The parent of \(v\) attains the minimum in the first equation in 24 , so \(\phi_n(v)=\mathrm{Fr}_n(v)=\mathrm{Fr}^{>v}_n(v)\). If \(v^{\scriptscriptstyle{({1}})}\ge 2\), it follows by the lower bound on \(\phi_n\) that \[\nonumber \phi_n^{\scriptscriptstyle{({2}})}(v)\ge \phi_n(v)\cdot\phi_n(v^{\scriptscriptstyle{({1}})}) = \mathrm{Fr}_n^{>v}(v) \cdot\phi_n(\mathrm{pa}(v)) \ge \mathrm{Fr}_n^{>v}(v) \cdot \min\left(\mathrm{Fr}^{>v}_n(\mathrm{pa}(v)), \mathrm{Fr}^{>v}_n(1)\right).\] Case 2: \(v^{\scriptscriptstyle{({1}})}=\mathrm{pa}(v)=1\). Similar to case 1, \(\phi_n(v)=\mathrm{Fr}_n(v)=\mathrm{Fr}^{>v}_n(v)\). Since \(1\) has no parent, the minimum in 24 is attained at one of its children, say \(c\).

If \(c\ge 3\), the tree \((T_n, c)_{1\downarrow}\) must contain the entire fringe tree of \(2\): indeed, since \(c\geq 3\) and \(2\) are both children of \(1\), the trees \((T_n,1)_{2 \downarrow}\) and \((T_n,1)_{c \downarrow}\) are disjoint and thus \((T_n,1)_{2 \downarrow} \subseteq T_n \setminus (T_n,1)_{c\downarrow} = (T_n,c)_{1\downarrow}\).

If \(c=2\), \((T_n, 2)_{1\downarrow}\) contains the entire fringe tree of \(1\) witnessed after time \(v\ge 2\): the unique path in \(T_n\) from a vertex in \((T_n,1)_{2\downarrow}\) to a vertex in the fringe tree of \(1\) witnessed after time \(v\) must traverse the edge \(\{1,2\}\) which is not in the fringe tree of \(1\) witnessed after time \(v\ge 2\). Thus, \(\phi_n(1) = |(T_n,2)_{1\downarrow}| \ge \mathrm{Fr}_n^{>v}(1)\) if \(c = 2\). Combining these subcases, if \(v^{\scriptscriptstyle{({1}})}=\mathrm{pa}(v)=1\), then \[\phi_n^{\scriptscriptstyle{({2}})}(v)\ge \phi_n(v)\phi_n(1)\ge \mathrm{Fr}_n^{>v}(v)\cdot\min\left(\mathrm{Fr}_n^{>v}(1), \mathrm{Fr}_n^{>v}(2)\right).\]

Case 3: \(v^{\scriptscriptstyle{({1}})}\neq \mathrm{pa}(v)\). We use the bound \(\phi_n^{\scriptscriptstyle{({2}})}(v)\ge (\phi_n(v))^2\). The minimum in the first equation in 24 is attained at a child \(c\) of \(v\). Since \(c>v\ge 2\), the subtree \((T_n, c)_{v\downarrow}\) contains vertices \(1\) and \(2\). Therefore, the subtree \((T_n, c)_{v\downarrow}\) also contains the fringe trees of \(1\) and \(2\) witnessed after time \(v\). Thus, \[\phi_n^{\scriptscriptstyle{({2}})}(v)\ge (\phi_n(v))^2\ge \max \left(\mathrm{Fr}_n^{>v}(1) , \mathrm{Fr}_n^{>v}(2)\right)^2 \ge \mathrm{Fr}_n^{>v}(1)\mathrm{Fr}_n^{>v}(2).\] Since exactly one of the three cases we discussed needs to occur, the second inequality of Lemma 2 follows.

We are left to show inequality 23 for \(v=2\). We distinguish 4 cases.

Case 1: \(2^{\scriptscriptstyle{({1}})}=1, 3 \sim 2\). The fringe trees of \(2\) and \(3\) witnessed after time \(3\) and are contained in the fringe tree of \(2\). Further, since \(2^{\scriptscriptstyle{({1}})}=1\), one has \(\phi_n(2) = \mathrm{Fr}_n(2)\), implying that \[\phi_n^{\scriptscriptstyle{({2}})}(2) \geq \phi_n(2)^2 = \mathrm{Fr}_n(2)^2 \geq \left(\mathrm{Fr}_n^{>3}(2) + \mathrm{Fr}_n^{>3}(3)\right)^2 \geq \mathrm{Fr}_n^{>3}(2) \mathrm{Fr}_n^{>3}(3) .\]

Case 2: \(2^{\scriptscriptstyle{({1}})} = c \geq 3, 3 \sim 2\). If \(c=3\), then the fringe tree of \(2\) witnessed after time \(3\) is contained in the tree \((T_n, c)_{2 \downarrow}\). If \(c>3\), then the fringe tree of \(3\) witnessed after time \(3\) is contained in the tree \((T_n, c)_{2 \downarrow}\). This implies that \(\phi_n(2) = |(T_n, c)_{2\downarrow}| \geq \min(\mathrm{Fr}_n^{>3}(2), \mathrm{Fr}_n^{>3}(2))\). Further, in either case, the fringe tree of \(1\) witnessed after time \(3\) is contained in the tree \((T_n,c)_{2\downarrow}\). Thus we see that \[\phi_n^{\scriptscriptstyle{({2}})}(2) \geq \phi_n(2)^2 \geq \mathrm{Fr}_n^{>3}(1)\cdot \min(\mathrm{Fr}_n^{>3}(2), \mathrm{Fr}_n^{>3}(3)) = \min(\mathrm{Fr}_n^{>3}(1) \mathrm{Fr}_n^{>3}(2), \mathrm{Fr}_n^{>3}(1) \mathrm{Fr}_n^{>3}(3)) .\]

Case 3: \(2^{\scriptscriptstyle{({1}})} = 1, 3 \sim 1\). If \(a \mathrel{\vcenter{:}}= 1^{{\scriptscriptstyle{({1}})}} \in \{2,3\}\), then the fringe tree of \(1\) witnessed after time \(3\) is contained in the tree \((T_n,a)_{1\downarrow}\). If \(a = 1^{{\scriptscriptstyle{({1}})}} > 3\), then the fringe tree of \(3\) witnessed after time \(3\) is contained in the tree \((T_n,a)_{1\downarrow}\). This implies that \(\phi_n(1) = |(T_n,a)_{1\downarrow}| \geq \min(\mathrm{Fr}_n^{>3}(1), \mathrm{Fr}_n^{>3}(3))\). Further, since \(2^{\scriptscriptstyle{({1}})} = 1 = \mathrm{pa}(v)\), we always have that \(\phi_n(2) = \mathrm{Fr}_n(2) \geq \mathrm{Fr}_n^{>3}(2)\). Combining these inequalities gives \[\phi_n^{{\scriptscriptstyle{({2}})}}(2) \geq \phi_n(2) \phi_n(1) \geq \mathrm{Fr}_n^{>3}(2) \cdot \min(\mathrm{Fr}_n^{>3}(1), \mathrm{Fr}_n^{>3}(3)) = \min(\mathrm{Fr}_n^{>3}(2) \mathrm{Fr}_n^{>3}(1) , \mathrm{Fr}_n^{>3}(2) \mathrm{Fr}_n^{>3}(3)) .\]

Case 4: \(2^{\scriptscriptstyle{({1}})} \geq 3, 3 \sim 1\). Since \(3 \nsim 2\), we have \(a \mathrel{\vcenter{:}}= 2^{{\scriptscriptstyle{({1}})}} \geq 4\), and thus the tree \((T_n,a)_{2 \downarrow}\) contains both the fringe tree of \(1\) witnessed after time \(3\) as well as the fringe tree of \(2\) witnessed after time \(3\), implying that \[\phi_n^{\scriptscriptstyle{({2}})}(2) \geq \phi_n(2)^2 =|(T_n,a)_{2\downarrow}| \geq \left(\mathrm{Fr}_n^{>3}(1) + \mathrm{Fr}_n^{>3}(3)\right)^2 \geq \mathrm{Fr}_n^{>3}(1) \mathrm{Fr}_n^{>3}(3) .\] Since exactly one of the four preceding cases needs to occur, this shows inequality 23 . ◻

Proof. We bound \(\mathbb{P}(XY\le s) \le \mathbb{P}(X\le s)+\mathbb{P}(Y\le s) + \mathbb{P}\left(XY\le s, X> s, Y> s\right).\)
The first two terms are each at most \(Cs\). For the third term we use a dyadic decomposition for \(X\): for \(j\ge0\), define \(I_j \mathrel{\vcenter{:}}= (s2^j, s2^{j+1}]\). If \(X\in I_j\) and \(XY\le s\), then \(Y\le 2^{-j}\). Hence, \[\begin{align} \mathbb{P}\left(XY\le s,\;X> s,\;Y> s\right) & \le \sum_{j=0}^{\lfloor\log_2(1/s)\rfloor} \mathbb{P}\left( X \in I_j, Y \leq 2^{-j} \right) \\ &\le \sum_{j=0}^{\lfloor\log_2(1/s)\rfloor} \mathbb{P}\left(X\le s2^{j+1}, Y\le 2^{-j}\right). \end{align}\] By negative association, \[\mathbb{P}\left(X\le s2^{j+1}, Y\le 2^{-j}\right) \le \mathbb{P}(X\le s2^{j+1})\cdot \mathbb{P}(Y\le 2^{-j}) \le Cs2^{j+1}\cdot C2^{-j} = 2C^2 s.\] Summing over \(j=0,\dots,\lfloor\log_2(1/s)\rfloor\) yields the claimed bound. ◻

Proof of Lemma 1. Since \(\phi_n^{\scriptscriptstyle{({2}})}(1)\) and \(\phi_n^{\scriptscriptstyle{({2}})}(2)\) have the same distribution, we assume without loss of generality that \(v\ge 2\), at the cost of changing the constants \(C,c\). We start by proving the upper bound. Let \(\mathcal{G}_v\) be the \(\sigma\)-algebra generated by the evolution of the tree up to time \(v\), i.e., \(\mathcal{G}_v=\sigma\left( \{u, \mathrm{pa}(u) \} ; 2 \leq u \leq v \right)\). Note that the random variables \(\left(\mathrm{Fr}_n^{>v}(j) : 1\leq j \leq n \right)\) are independent of \(\mathcal{G}_v\), whereas \(\mathrm{pa}(v)\) is measurable with respect to \(\mathcal{G}_v\). By Lemma 2 and a union bound, \[\begin{align} \mathbb{P}\left( \phi_n^{{\scriptscriptstyle{({2}})}}(v) \leq \left( \frac{n}{t v} \right)^2 \right) & \le \mathbb{E}\left[ \mathbb{P}\left( \min_{(x,y) \in \left\{ (v,\mathrm{pa}(v)), (v,1), (v,2), (1,2) \right\}} \mathrm{Fr}_n^{>v}(x) \mathrm{Fr}_n^{>v}(y) \leq \left( \frac{n}{t v} \right)^2 \,\Big|\, \mathcal{G}_v \right) \right] \\ & \leq \mathbb{E}\left[ \sum_{(x,y) \in \left\{ (v,\mathrm{pa}(v)), (v,1), (v,2), (1,2) \right\}} \mathbb{P}\left( \mathrm{Fr}_n^{>v}(x) \mathrm{Fr}_n^{>v}(y) \leq \left( \frac{n}{t v} \right)^2 \,\Big|\, \mathcal{G}_v \right) \right]. \end{align}\] The pairs of witnessed fringe-trees in the sum are identically distributed by the exchangeability in Lemma [lem:beta-bin-fringe](1), and they are independent of \(\mathcal{G}_v\). Further, for \(v \geq 3\), all pairs in \(\{(v,\mathrm{pa}(v))\), \((v,1)\), \((v,2)\), \((1,2)\}\) consist of two different vertices. Thus, \[\mathbb{P}\left( \phi_n^{{\scriptscriptstyle{({2}})}}(v) \leq \left( \frac{n}{t v} \right)^2 \right)\le 4\mathbb{P}\left( \frac{v}{n}\mathrm{Fr}_n^{>v}(v) \cdot \frac{v}{n}\mathrm{Fr}_n^{>v}(1) \leq \frac{1}{t^2} \right).\] The upper bound on the lower tail in Lemma [lem:beta-bin-fringe](3) implies that for all \(M\ge 1\), \[\mathbb{P}\left(\frac{v}{n}\mathrm{Fr}_n^{>v}(1)\le \frac{1}{M}\right) = \mathbb{P}\left(\frac{v}{n}\mathrm{Fr}_n^{>v}(v)\le \frac{1}{M}\right) = \mathbb{P}\left(\mathrm{Fr}_n(v)\le \frac{n}{Mv}\right) \le \frac{2}{M}.\] Since \(\tfrac{v}{n}\mathrm{Fr}_n^{>v}(1)\) and \(\tfrac{v}{n}\mathrm{Fr}_n^{>v}(v)\) are negatively associated by Lemma [lem:beta-bin-fringe](2), Claim 5 with \(s=1/t^2\) implies that \[\mathbb{P}\left( \phi_{n}^{{\scriptscriptstyle{({2}})}}(v) \leq \left( \frac{n}{t v} \right)^2 \right) \leq 4\mathbb{P}\left( \frac{v}{n}\mathrm{Fr}_n^{>v}(v) \cdot \frac{v}{n}\mathrm{Fr}_n^{>v}(1) \leq \frac{1}{t^2} \right) \le 4\cdot 2\cdot 2^2\cdot \frac{1+\log_2 t^2}{t^2} +\frac{4\cdot2\cdot 2}{t^2},\] finishing the upper bound for \(v \geq 3\). For \(v=2\), we have, using similar arguments and 23 , that \[\begin{gather} \mathbb{P}\left( \phi_n^{{\scriptscriptstyle{({2}})}}(v) \leq \left( \frac{n}{t v} \right)^2 \right) \le \sum_{(x,y) \in \left\{ (1,2), (2,3), (1,3) \right\}} \mathbb{P}\left( \mathrm{Fr}_n^{>3}(x) \mathrm{Fr}_n^{>3}(y) \leq \left( \frac{n}{t v} \right)^2 \right) \\ = 3 \mathbb{P}\left( \frac{3}{n} \mathrm{Fr}_n^{>3}(1) \frac{3}{n} \mathrm{Fr}_n^{>3}(2) \leq \frac{9}{4 t^2} \right) \leq C \frac{1 + \log t}{t^2}, \end{gather}\] for some constant \(C< \infty\) and all \(t\geq 1\).

We turn to the lower bound, starting with \(v\ge 3\). The lower bound follows from inequality 25 of Lemma [lem:appendix95fringe95size], since \[\begin{align} \mathbb{P}\left( \phi_n^{{\scriptscriptstyle{({2}})}}(v) \leq \left( \frac{n}{tv} \right)^2 \right) \geq \mathbb{P}\left( \mathrm{Fr}_n(v) \mathrm{Fr}_n(\mathrm{pa}(v)) \leq t^{-2} \left( \frac{n}{v} \right)^2 \right) \geq c t^{-2} \log(t^2) = 2c \frac{\log t}{t^2}, \end{align}\] for some constant \(c>0\) (depending on \(\varepsilon>0\)) and all \(t > 0\) with \(3(v/n)^2 \vee (v/n)^{2-\varepsilon} \leq t^{-2} \leq 1/2\), which is equivalent to \(\sqrt{2} \leq t \leq \tfrac{1}{\sqrt{3}} (n/v) \wedge (n/v)^{1-\varepsilon/2}\). Since \((n/v)^{1-\varepsilon/2} \geq (n/v)^{1-\varepsilon}\), 18 follows. The proof of 19 follows analogously, with 25 replaced by 26 .

For \(v=2\), observe that conditioned on the event \(\mathrm{pa}(3)=1\), the tree \(T_3\) consists of a line of length \(3\) with vertices \(2\) and \(3\) at the ends. In particular, conditioned on \(\mathrm{pa}(3)=1\), \(\phi_n^{{\scriptscriptstyle{({2}})}}(2)\) has the same distribution as \(\phi_n^{{\scriptscriptstyle{({2}})}}(3)\). Furthermore, \(\phi_n^{{\scriptscriptstyle{({2}})}}(3)\) is independent of \(\mathrm{pa}(3)\), since the tree \(T_3\) always consists of a line of length \(3\), with \(3\) at one of its endpoints, implying that \[\begin{align} \mathbb{P}\big( \phi_n^{{\scriptscriptstyle{({2}})}}(2) \leq s \big) &\geq \mathbb{P}(\mathrm{pa}(3)=1)\mathbb{P}\big( \phi_n^{{\scriptscriptstyle{({2}})}}(2) \leq s \mid \mathrm{pa}(3)=1 \big) \\&= \frac{1}{2}\mathbb{P}\big( \phi_n^{{\scriptscriptstyle{({2}})}}(3) \leq s \mid \mathrm{pa}(3)=1 \big) = \frac{1}{2}\mathbb{P}\left( \phi_n^{{\scriptscriptstyle{({2}})}}(3) \leq s\right) \end{align}\] for all \(s > 0\). The proofs of 18 and 19 for \(v=2\) follow by decreasing the constant \(c\). ◻

Proof of Lemma 3. The statement of the lemma is clear for \(S > \frac{v}{16}\) or for \(v=1\), by taking the constant \(C\) large enough. Thus, we can assume that \(S \leq \frac{v}{16}\) for the rest of the proof. Fix some \(n\geq1\) and \(S\geq 1\). We first relate the Jordan-2 centrality to the product of the fringe-tree size of \(v\) and its parent, that is,

\[\begin{align} \mathbb{P}\left(\phi_n^{\scriptscriptstyle{({2}})}(v) \ge S\left(\frac{n}{v}\right)^2\right) \geq \mathbb{P}\left(\left\{\phi_n^{\scriptscriptstyle{({2}})}(v) \ge S\left(\frac{n}{v}\right)^2\right\}\cap \left\{ \mathrm{Fr}_n(\mathrm{pa}(v))\leq \frac{n}{2} \right\} \right). \end{align}\] If \(\mathrm{Fr}_n(\mathrm{pa}(v))\leq n/2\), then \(\mathrm{Fr}_n(v)\leq n/2\) and hence \(\phi^{\scriptscriptstyle{({2}})}_n(v)=\mathrm{Fr}_n(\mathrm{pa}(v))\mathrm{Fr}_n(v)\). Therefore,

\[\nonumber \begin{align} \mathbb{P}\left(\phi_n^{\scriptscriptstyle{({2}})}(v) \ge S \left(\frac{n}{v}\right)^2\right) &\geq \mathbb{P}\Big(\mathrm{Fr}_n (\mathrm{pa}(v))\mathrm{Fr}_n(v) \ge S\left(\frac{n}{v}\right)^2 \Big)-\mathbb{P}\Big( \mathrm{Fr}_n(\mathrm{pa}(v)) > \frac{n}{2} \Big). \end{align}\] By 31 , there exists a constant \(C>0\) such that for all \(v\ge 2\), and \(n\ge 3\), the probability of the event \(\{\mathrm{Fr}_n(\mathrm{pa}(v)) > n/2\}\) is at most \(C/v\). So, \[\label{eq:Jordan295lower95tail95LB95decompo} \begin{align} \mathbb{P}\left(\phi_n^{\scriptscriptstyle{({2}})}(v) \ge S\left(\frac{n}{v}\right)^2\right) &\geq \mathbb{P}\Big(\mathrm{Fr}_n (\mathrm{pa}(v))\mathrm{Fr}_n(v) \ge S\left(\frac{n}{v}\right)^2 \Big)-C/v. \end{align}\tag{32}\] In the remainder, we establish a lower bound on the probability on the right-hand side of this inequality. We intersect with the likely events that both \(v\) and its parent have a fringe-tree size of the right order. That is, \[\begin{align} &\mathbb{P}\left( \mathrm{Fr}_n(\mathrm{pa}(v))\mathrm{Fr}_n(v) \ge S\left(\frac{n}{v}\right)^2 \right) \\ &\geq \mathbb{P}\left( \left\{\mathrm{Fr}_n(\mathrm{pa}(v))\mathrm{Fr}_n(v) \ge S\left(\frac{n}{v}\right)^2\right\} \cap \left\{\mathrm{Fr}_n(v) \geq \frac{n}{4v}\right\} \cap \left\{\mathrm{Fr}_n(\mathrm{pa}(v)) \geq \frac{n}{4\mathrm{pa}(v)}\right\}\right)\\ &\geq \mathbb{P}\left( \left\{\frac{n^2}{16v\mathrm{pa}(v)} \ge S \left( \frac{n}{v}\right)^2 \right\} \cap \left\{\mathrm{Fr}_n(v) \geq \frac{n}{4v}\right\} \cap \left\{\mathrm{Fr}_n(\mathrm{pa}(v)) \geq \frac{n}{4\mathrm{pa}(v)}\right\}\right). \end{align}\] The event \(\left\{\tfrac{n^2}{16v\mathrm{pa}(v)} \ge S \left( n/v\right)^2 \right\}\) is satisfied for \(\mathrm{pa}(v) \leq v/(16S)\). Using that \(\mathrm{pa}(v)\) is uniformly distributed on \([v-1]\) and is independent from \(\mathrm{Fr}_n(v)\), the law of total probability yields

\[\begin{align} \mathbb{P}\Big(\mathrm{Fr}_n(\mathrm{pa}(v)) &\mathrm{Fr}_n(v) \ge S \left(\frac{n}{v}\right)^2 \Big) \\ &\geq \frac{1}{v-1}\sum_{u\leq v/(16S)} \mathbb{P}\left( \left\{\mathrm{Fr}_n(v) \geq \frac{n}{4v}\right\} \cap \left\{\mathrm{Fr}_n(u) \geq \frac{n}{4u}\right\}\;\Big| \;\mathrm{pa}(v)=u \right)\\ &= \frac{\mathbb{P}\left(\mathrm{Fr}_n(v) \geq \tfrac{n}{4v}\right)}{v-1}\sum_{u\leq v/(16S)} \mathbb{P}\left( \left\{\mathrm{Fr}_n(u) \geq \frac{n}{4u}\right\} \Big| \left\{\mathrm{Fr}_n(v) \geq \frac{n}{4v}\right\} \cap \left\{\mathrm{pa}(v)=u\right\} \right), \end{align}\] where the last inequality holds since \(\mathrm{Fr}_n(v)\) and \(\mathrm{pa}(v)\) are independent. Furthermore, the random variable \(\mathrm{Fr}_n(u) \mid \left\{\mathrm{Fr}_n(v) \geq \tfrac{n}{4v}\right\} \cap \left\{\mathrm{pa}(v)=u\right\}\) stochastically dominates \(\mathrm{Fr}_n(u)\), so that \[\begin{align} \mathbb{P}\left(\mathrm{Fr}_n(\mathrm{pa}(v)) \mathrm{Fr}_n(v) \ge S\left(\frac{n}{v}\right)^2 \right) &\geq \frac{\mathbb{P}\left(\mathrm{Fr}_n(v) \geq \tfrac{n}{4v}\right)}{v-1}\sum_{u\leq v/(16S)} \mathbb{P}\left( \mathrm{Fr}_n(u) \geq \frac{n}{4u} \right). \end{align}\] Using Lemma [lem:beta-bin-fringe](3), we get that \(\mathbb{P}\left(\mathrm{Fr}_n(v) \geq \frac{n}{4v}\right)\geq \tfrac{1}{2}\) and \(\mathbb{P}\left( \mathrm{Fr}_n(u) \geq \tfrac{n}{4u} \right)\geq \tfrac{1}{2}\), so

\[\mathbb{P}\left(\mathrm{Fr}_n(v) \mathrm{Fr}_n(\mathrm{pa}(v))\ge S\left(\tfrac{n}{v}\right)^2\right) \geq \frac{\tfrac{1}{2}}{v-1} \lfloor v/(16S) \rfloor \frac{1}{2} \geq \frac{1}{128S},\] where we used the assumption \(S \leq \frac{v}{16}\) for the last inequality. Inserting this into 32 concludes the proof of the lemma. ◻

Proof. We first split the event inside the probability by considering dyadic intervals for the potential fringe-tree size of \(u\): \[\begin{align} \big\{(u,i)\in A_n^\prime: \mathrm{Fr}_n(u)&\mathrm{Fr}_n\left((u,i)\right) > (n/t)^2\big\}\\ &\subseteq \bigcup_{j=0}^{\lfloor\log_2t\rfloor}\big\{(u,i)\in A_n^\prime: \mathrm{Fr}_n(u)\in\big(2^j\tfrac{n}{t}, 2^{j+1}\tfrac{n}{t}\big], \mathrm{Fr}_n((u,i))\ge 2^{-(j+1)}\tfrac{n}{t}\big\}. \end{align}\] Assuming that for each \(j\in\{0,\ldots, \lfloor\log_2t\rfloor\}\), \[\big|\big\{(u,i)\in A_n^\prime: \mathrm{Fr}_n(u)\in\big(2^j\tfrac{n}{t}, 2^{j+1}\tfrac{n}{t}\big], \mathrm{Fr}_n\left((u,i)\right)\ge 2^{-(j+1)}\tfrac{n}{t}\big\}\big| \le (C/5)\cdot t\cdot 0.8^j,\] we have \[\big|\big\{(u,i)\in A_n^\prime: \mathrm{Fr}_n(u)\mathrm{Fr}_n\left((u,i)\right) > (n/t)^2\big\}\big| \le \sum_{j=0}^{\lfloor\log_2t\rfloor }(C/5)\cdot t\cdot 0.8^j \le Ct.\] By a union bound, and using that \(2^{-(j+1)}\tfrac{n}{t}\ge 2^{-2(j+1)}\mathrm{Fr}_n(u)\) if \(\mathrm{Fr}_n(u)\in (2^j \tfrac{n}{t}, 2^{j+1}\tfrac{n}{t}]\), \[\begin{align} &\mathbb{P}\left(\big|\big\{(u,i)\in A_n^\prime: \mathrm{Fr}_n(u)\mathrm{Fr}_n\left((u,i)\right) > (n/t)^2\big\}\big|>Ct\right)\\ &\le \sum_{j=0}^{\lfloor \log_2 t\rfloor}\mathbb{P}\left(\big|\big\{(u,i)\in A_n^\prime: \mathrm{Fr}_n(u)\in\left(2^j\tfrac{n}{t}, 2^{j+1}\tfrac{n}{t}\right], \mathrm{Fr}_n\left((u,i)\right)\ge 2^{-(j+1)}\tfrac{n}{t}\big\}\big| > (C/5) 0.8^jt\right) \\ &\le \sum_{j=0}^{\lfloor \log_2 t\rfloor}\mathbb{P}\left(\big|\big\{(u,i)\in A_n^\prime: \mathrm{Fr}_n(u)\in\left(2^j\tfrac{n}{t}, 2^{j+1}\tfrac{n}{t}\right], \mathrm{Fr}_n\left((u,i)\right)\ge 2^{-2(j+1)}\mathrm{Fr}_n(u)\big\}\big| > (C/5) 0.8^jt\right) .\end{align}\] We bound the summands individually using Lemmas 4 and 5 and the fringe-tree splitting construction. Define \[\label{eq:rj} J_j=N_n^\mathrm{Fr}\big(2^j\tfrac{n}{t}, 2^{j+1}\tfrac{n}t\big], \qquad r_j:=\lceil\sqrt{C}0.6^jt\rceil.\tag{35}\]

Similarly to the proof of Lemma 4, for \(0 \leq i \leq n\), let \(\{ u^i_1,\ldots,u^i_{n^i}\}= [n]^i\) in lexicographic ordering and let \(\{v_1,\ldots,v_{K}\} = \bigcup_{i=1}^n [n]^i\) with \(K=\sum_{i=0}^{n} n^i\) be so that the level of \(v_j\), i.e., the unique value \(i\in [n]\) s.t. \(v_j \in [n]^i\), is non-decreasing in \(j\), and so that each block \([n]^i\) is in the lexicographic ordering. For \(1 \leq \ell \leq K\), define the sets \(F_1(\ell)\) and \(F_2(\ell)\) by \[\begin{align} F_1(\ell)& := \left\{ u \in \{v_1,\ldots,v_\ell\} : \mathrm{Fr}_n \left(u\right)\in \left( 2^j \frac{n}{t}, 2^{j+1} \frac{n}{t} \right] \right\}, \\ F_2(\ell)& := \left\{(u,i)\in \mathcal{U} : u \in \{v_1,\ldots,v_\ell\} , \mathrm{Fr}_n \left(u\right)\in \left( 2^j \frac{n}{t}, 2^{j+1} \frac{n}{t} \right], \mathrm{Fr}_n\left((u,i)\right) \geq 2^{-2(j+1)} \mathrm{Fr}_n(u) \right\}. \end{align}\] Let \(\mathcal{F}_\ell\) be the \(\sigma\)-algebra \(\mathcal{F}_\ell=\sigma\left( \mathrm{Fr}_n((u,i)) : u \in \{\emptyset,v_1,\ldots,v_\ell\}, i\in \mathbb{N}\right)\). Let \(u = v_{\ell} \in \mathcal{U}\) with fringe-tree size \(\mathrm{Fr}_n(u)\in\big(2^j\tfrac{n}{t}+1, 2^{j+1}\tfrac{n}{t}\big]\). Conditional on \(\mathcal{F}_{\ell-1}\), the sizes of the fringe trees \(\left(\mathrm{Fr}_n((u,i))\right)_{i\geq 1}\) have the same distribution as the sizes of these fringe trees, when conditioned on \(\mathrm{Fr}_n(u)\). (Note that \(\mathrm{Fr}_n(u)\) is measurable with respect to \(\mathcal{F}_{\ell-1}\)). Lemma 5 with \(\alpha=2^{-2(j+1)}\) implies that its number of children with fringe-tree size at least \(2^{-2(j+1)}\mathrm{Fr}_n(u)\) has an exponentially decaying tail: for every \(m\ge 0\), \[\begin{gather} \mathbb{P}\left(\big|\{i: \mathrm{Fr}_n\left((u,i)\right) \ge 2^{-2(j+1)}\mathrm{Fr}_n(u)\}\big|>6(j+1)+m \;\big|\;\mathcal{F}_{\ell-1} \right) \\ = \mathbb{P}\left(\big|\{i: \mathrm{Fr}_n\left((u,i)\right) \ge 2^{-2(j+1)}\mathrm{Fr}_n(u)\}\big|>6(j+1)+m \;\big|\;\mathrm{Fr}_n(u) \right) \leq 0.95^{6(j+1)+m} \le 0.95^m \end{gather}\] Hence, conditional on \(\mathcal{F}_{\ell-1}\), the number of children of \(u\) with \(\mathrm{Fr}_n\left((u,i)\right) \ge 2^{-2(j+1)}\mathrm{Fr}_n(u)\) is stochastically dominated by a shifted geometric random variable \(6(j+1)+Y\), where \(Y\sim\mathrm{Geo}(0.05)\). Using this inductively, we see that there exist i.i.d. random variables \(Y_1, Y_2,\ldots\) with \(Y_i \sim \mathrm{Geo}(0.05)\) so that \[|F_2(\ell)| \leq \sum_{k=1}^{|F_1(\ell)|} \left( 6(j+1) + Y_k \right).\] for all \(1 \leq \ell \leq K\). Thus, we obtain that \[\begin{align} &\mathbb{P}\left(\big|\big\{(u,i)\in A_n^\prime: \mathrm{Fr}_n(u)\mathrm{Fr}_n\left((u,i)\right) > (n/t)^2\big\}\big|>Ct\right)\nonumber\\ &\qquad\le \sum_{j=0}^{\lfloor \log_2 t\rfloor}\mathbb{P}\bigg(\sum_{k=1}^{J_j} \left(Y_{k}+6(j+1)\right)>(C/5) 0.8^j t\bigg)\nonumber \\ &\qquad\le \sum_{j=0}^{\lfloor \log_2 t\rfloor}\Bigg(\mathbb{P}\left(J_j>r_j\right)+ \mathbb{P}\bigg(\sum_{k=1}^{r_j} \left(Y_{k}+6(j+1)\right)>(C/5) 0.8^j t\bigg)\Bigg) .\label{eq:lem-mixed-pr1} \end{align}\tag{36}\] To bound the first summands, we use Lemma 4 for \(\ell=2^j\tfrac{n}{t}\) and \(r=r_j\). This requires that \[r_j = \lceil\sqrt{C}t0.6^j\rceil\ge 20\cdot 2^{-j}t,\] which is satisfied for all \(j\) provided that \(C\) is a sufficiently large constant. As \(\log(0.6)/\log(2)=-0.73...>-0.75\), we obtain for \(C\) large enough \[\begin{align} \sum_{j=0}^{\lfloor \log_2 t\rfloor}\mathbb{P}\left(J_j>r_j\right)&\le 27\sum_{j=0}^{\lfloor \log_2 t\rfloor}\exp\left(-0.04 \sqrt{C}0.6^jt\right)\nonumber\\&\le 27(1+\lfloor\log_2t\rfloor) \exp\left(-0.04\sqrt{C}t^{1+\log(0.6)/\log(2)}\right)\le \tfrac{1}{2}\exp\left(-t^{1/4}\right).\label{eq:lem-mixed-pr2} \end{align}\tag{37}\] We proceed to the second term within the sum in 36 . As \(Y_{k}+6(j+1)\le 7(j+1)Y_{k}\), \(r_j \leq 2 \sqrt{C}0.6^j t\), and \(\mathbb{E}\left[ \exp(0.04 Y_k) \right]<\infty\), we get that \[\begin{gather} \mathbb{P}\bigg(\sum_{k=1}^{r_j} \left(Y_{k}+6(j+1)\right)>(C/5) 0.8^j t\bigg) \le \mathbb{P}\bigg(\sum_{k=1}^{r_j} Y_{k}>r_j\frac{C0.8^j}{35r_j(j+1)} t\bigg). \\ \leq \left(\mathbb{E}\big[\exp\left(0.04Y_{k}\right)\big]\exp\left(-\frac{0.04 C 0.8^j }{35 \cdot 2 \sqrt{C} 0.6^j (j+1) t } t \right)\right)^{r_j} \leq \left( \exp\left(- 1 \right) \right)^{r_j} \leq \exp\left(- \sqrt{C} t 0.6^j \right) . \end{gather}\] Combining this bound with 36 and 37 , we obtain for \(t\ge1\) and \(C\) sufficiently large, \[\begin{gather} \mathbb{P}\left( \left|\left\{(u,i)\in A_n^\prime: \mathrm{Fr}_n(u)\mathrm{Fr}_n\left((u,i)\right) > (n/t)^2\right\}\right|>Ct \right)\\ \le \tfrac{1}{2}\exp\left(-t^{1/4}\right)+ \sum_{j=0}^{\lfloor\log_2t\rfloor} \exp\left(- \sqrt{C} t 0.6^j \right) \le \exp\left(-t^{1/4}\right). \qedhere \end{gather}\] ◻

Proof. We follow the reasoning from the outline at the beginning of Section 2. If \(\widehat{\sigma}_2(v)\ge Sv\), there are at least \(Sv\) vertices with Jordan-2 centrality at least as large as \(\phi_n^{\scriptscriptstyle{({2}})}(v)\). So, \[\begin{align} \mathbb{P}\left(\widehat{\sigma}_2(v)\ge Sv\right) \leq \mathbb{P}\left(\big|\big\{u\in [n]: \phi_n^{\scriptscriptstyle{({2}})}(u)\ge \phi_n^{{\scriptscriptstyle{({2}})}}(v)\big\}\big|\ge Sv\right). \end{align}\] We consider two cases: either \(\phi_n^{\scriptscriptstyle{({2}})}(v)\) is unlikely small, or there are many vertices with large Jordan-2 centrality. Let \(C_1\) be the constant \(C\) from Lemma [lem:mixed32large]. We bound \[\begin{align} \mathbb{P}\left(\widehat{\sigma}_2(v)\ge Sv\right)&\le \mathbb{P}\left(\phi_n^{\scriptscriptstyle{({2}})}(v)\le \left(\frac{2C_1n}{Sv}\right)^2\right) + \mathbb{P}\left(\Big|\Big\{u\in[n]: \phi_n^{\scriptscriptstyle{({2}})}(u)> \left(\frac{2C_1n}{Sv}\right)^2\Big\}\Big| > Sv\right) . \end{align}\] We use that \(\phi_n^{\scriptscriptstyle{({2}})}(v)\le \mathrm{Fr}_n(v)\mathrm{Fr}_n(\mathrm{pa}(v))\) by 9 for \(v\ge2\). Hence, \[\begin{align} & \mathbb{P}\left(\widehat{\sigma}_2(v)\ge Sv\right) \\ &\le \mathbb{P}\left(\phi_n^{\scriptscriptstyle{({2}})}(v)\le \left(\frac{2C_1n}{Sv}\right)^2\right) + \mathbb{P}\left(\Big|\Big\{u\in[n]\setminus\{1\}: \mathrm{Fr}_n(u)\mathrm{Fr}_n(\mathrm{pa}(u))> \left(\frac{2C_1n}{Sv}\right)^2\Big\}\Big| > Sv-1\right) \\ &\le \mathbb{P}\left(\phi_n^{\scriptscriptstyle{({2}})}(v)\le \left(\frac{2C_1n}{Sv}\right)^2\right) + \mathbb{P}\left(\Big|\Big\{u\in[n]\setminus\{1\}: \mathrm{Fr}_n(u)\mathrm{Fr}_n(\mathrm{pa}(u))> \left(\frac{2C_1n}{Sv}\right)^2\Big\}\Big| > C_1 \frac{Sv}{2C_1}\right) \end{align}\] where the last inequality holds for \(S\geq 2\). Applying inequality 17 from Lemma 1 with \(t=S/(2C_1)\) to the first term and Lemma [lem:mixed32large] with \(t=Sv/(2C_1)\) to the second term, we get that for \(S\geq 2C_1 \vee 2\), \[\mathbb{P}\left(\widehat{\sigma}_2(v)\ge Sv\right) \le C_2\cdot 4C_1^2\frac{1+\log\left( S/(2C_1)\right)}{S^2} + \exp\left(-(2C_1)^{-1/4}S^{1/4}\right),\] where \(C_2\) is the constant \(C\) from Lemma 1. As a result, there exists a constant \(C>0\) such that for all \(S\geq 2C_1 \vee 2\), \[\mathbb{P}\left(\widehat{\sigma}_2(v)\ge Sv\right)\le C\frac{1+\log S}{S^2}.\] Increasing the constant \(C\) also implies that the same inequality holds for all \(S\geq 1\). ◻

Proof. As \(\phi_n^{\scriptscriptstyle{({2}})}(u)\ge \phi_n(u)^2\) by 6 , the first inequality in 40 follows. We turn to the inequality on the second line in 40 .

It suffices to consider the case when \(t \in \mathbb{N}\), which we will assume for the rest of the proof. Since \(t\le n/16\), we have \(\left\{ 8t , \ldots, 16t \right\} \subset [n]\). For a vertex \(u \in \left\{ 8t , \ldots, 16t \right\}\) with \(\mathrm{Fr}_n(u) \leq \frac{n}{2}\) we have \(\mathrm{Fr}_n^{>16t}(u) \leq \mathrm{Fr}_n(u) = \phi_n(u)\). Hence, \[\begin{align} \notag\mathbb{P}&\left(\Big|\left\{u \in [n] : \phi_n(u) > \frac{n}{64t} \right\}\Big|\le t\right)\\ &\notag\leq \mathbb{P}\left(\Big|\left\{u \in \left\{ 8t , \ldots, 16t \right\} : \phi_n(u) > \frac{n}{64t}\right\}\Big|\le t\right) \\ & \notag \le \mathbb{P}\left(\exists u\in \left\{ 8t , \ldots, 16t \right\} : \mathrm{Fr}_n(u)\geq \frac{n}{2}\right) \\ & \notag+ \mathbb{P}\left(\Big|\left\{u\in \left\{ 8t , \ldots, 16t \right\} : \mathrm{Fr}_n(u) > \frac{n}{64t}\right\}\Big|\le t\right) \\ & \tag{41} \le \mathbb{P}\left(\exists u\in \left\{ 8t , \ldots, 16t \right\} : \mathrm{Fr}_n(u)\geq \frac{n}{2}\right) \\ & \tag{42}+ \mathbb{P}\left(\Big|\left\{u\in \left\{ 8t, \ldots, 16t \right\} : \mathrm{Fr}_n^{>16t}(u) > \frac{n}{64t}\right\}\Big|\le t\right), \end{align}\] where \(\mathrm{Fr}_n^{>16t}(u)\) denotes the fringe tree witnessed after time \(16t\), see Definition 2. The first summand in 41 can be bounded by a union bound and Lemma [lem:proba95large95fringe]: \[\begin{gather} \mathbb{P}\left(\exists u\in \left\{ 8t , \ldots, 16t \right\} : \mathrm{Fr}_n(u)\geq \frac{n}{2}\right) \leq \sum_{u = 8t }^{16t} \mathbb{P}\left( \mathrm{Fr}_n(u)\geq \frac{n}{2} \right) \\ \label{large32fringe} = \sum_{u = 8t }^{16t} \mathbb{P}\left( \mathrm{Fr}_n(u)\geq \frac{u}{2} \frac{n}{u} \right) \overset{\eqref{eq:proba95fringe-large}}{\leq} \sum_{u = 8t }^{16t} 2 e^2 \exp\left( - \frac{u}{2} \right) \leq \frac{2 \exp \left( \frac{5}{2} - 4t \right) }{\sqrt{e}-1} \leq 38 \exp \left( -4t \right). \end{gather}\tag{43}\] For the second summand, 42 , observe that for each \(u \in \left\{ 8t , \ldots , 16t \right\}\), we have \[\begin{align} \mathbb{P}\left( \mathrm{Fr}_n^{>16t}(u) >\frac{n}{64 t} \right) = 1 - \mathbb{P}\left( \mathrm{Fr}_n \left( 16t \right) \leq \frac{n}{4 \cdot 16t} \right) \overset{\eqref{eq:fringe-ub}}{\geq} 1 - \frac{2}{4} = \frac{1}{2}. \end{align}\] Linearity of expectation implies that \[\begin{align} \mathbb{E}\left[ \Big| \left\{ u \in \left\{ 8t , \ldots , 16t \right\} : \mathrm{Fr}_n^{>16t}(u) > \frac{n}{64 t} \right\}\Big| \right] \geq 8t \frac{1}{2} = 4t. \end{align}\] Since the terms \(\mathrm{Fr}_n^{>16t}(u), u \in \left\{ 8t, \ldots , 16t \right\}\), are negatively associated by Lemma [lem:beta-bin-fringe](2), we can apply the Chernoff bound for negatively associated Bernoulli random variables (see [22] and [23]) and get that \[\mathbb{P}\left(\Big|\left\{u\in \left\{ 8t , \ldots, 16t \right\} : \mathrm{Fr}_n^{>16t}(u) > \frac{n}{64t} \right\}\Big|\le t\right) \leq \exp \left( - t/8 \right).\qedhere\] ◻

Proof of Lemma 7. Let \(\varepsilon>0\). By 18 there exists a constant \(c^\star=c^\star(\varepsilon)\) such that \[\begin{align} \mathbb{P}\left( \phi_n^{{\scriptscriptstyle{({2}})}}(v) \leq \left( \frac{n}{t v} \right)^2 \right) \geq c^\star \frac{\log t}{t^2} \end{align}\] for all \(t \in \big( \sqrt{2}, \tfrac{n}{v \sqrt{3}} \wedge (n/v)^{1-\varepsilon}\big)\). Let \(n\ge3\), \(v\in[n/4]\) and \(S\in\big[1, \tfrac{1}{1024\sqrt{3}} (n/v)^{1-\varepsilon} \big]\). We start by noting that to have \(\widehat{\sigma}_2(v)\ge Sv\), it suffices that at least \(Sv\) vertices have Jordan-\(2\) centrality larger than \(\phi_n^{(2)}(v)\). So, \[\begin{align} \mathbb{P}\left(\widehat{\sigma}_2(v) \ge Sv\right) &\notag \geq \mathbb{P}\left(\big|\big\{u\in [n]: \phi_n^{\scriptscriptstyle{({2}})}(u) >\phi^{\scriptscriptstyle{({2}})}_n(v)\big\}\big|\ge Sv\right) \\ &\notag \geq \mathbb{P}\left(\left\{\phi_n^{\scriptscriptstyle{({2}})}(v)\leq \left(\tfrac{1}{64S}\tfrac{n}{v}\right)^2\right\} \cap \left\{\big|\big\{u\in [n]: \phi_n^{\scriptscriptstyle{({2}})}(u) >\left(\tfrac{1}{64S}\tfrac{n}{v}\right)^2\big\}\big|\ge Sv\right\}\right)\\ & \label{eq:Jordan295upper95tail95LB95decompo} \geq \mathbb{P}\left(\phi_n^{\scriptscriptstyle{({2}})}(v)\leq \left(\tfrac{1}{64S}\tfrac{n}{v}\right)^2\right) - \mathbb{P}\left(\big|\big\{u\in [n]: \phi_n^{\scriptscriptstyle{({2}})}(u) > \left(\tfrac{1}{64S}\tfrac{n}{v}\right)^2 \big\}\big|< Sv\right). \end{align}\tag{44}\] The first term of 44 is lower bounded using inequality 18 from Lemma 1 evaluated at \(t=64S\). The second term is bounded from above by Lemma 8 \(t=Sv\) (our assumed upper bound on \(S\) implies that \(t=Sv\le n/16\)). As a result, there exist constants \(C,c>0\) such that \[\nonumber \begin{align} \mathbb{P}\left(\widehat{\sigma}_2(v) \ge Sv\right) & \geq c^\star \frac{1+\log S}{S^2} - C\exp\big(-vS/8\big) \geq c \frac{1+\log S}{S^2}, \end{align}\] where the last inequality holds for some constant \(c>0\) small enough and all \(S\geq M\), where \(M\) is a large enough constant. Let \(\delta = \tfrac{1}{M 1024 \sqrt{3}}\). This shows inequality 38 for \(M \leq S \leq \tfrac{1}{1024 \sqrt{3}} (n/v)^{1-\varepsilon}\). When \(1 \leq S \leq M\), then there is nothing to show when \(\delta (n/v)^{1-\varepsilon} < 1\). But when \(1\leq \delta (n/v)^{1-\varepsilon}\), we have that \[\begin{align} \mathbb{P}\left(\widehat{\sigma}_2(v) \ge Sv\right) \geq \mathbb{P}\left(\widehat{\sigma}_2(v) \ge M v \right) \geq c \frac{1+\log M}{M^2} > 0, \end{align}\] since \(M \leq \tfrac{1}{1024 \sqrt{3}} (n/v)^{1-\varepsilon}\). This shows 38 , by changing the constant \(c\).

The proof of 39 follows analogously, since \[\begin{align} \mathbb{P}\left(\widehat{\sigma}_2(v) \ge Sv\right) &\notag \geq \mathbb{P}\left(\big|\big\{u\in [n]: \phi_n^{\scriptscriptstyle{({2}})}(u) >\phi^{\scriptscriptstyle{({2}})}_n(v)\big\}\big|\ge Sv\right) \\ &\notag \geq \mathbb{P}\left(\phi_n^{\scriptscriptstyle{({2}})}(v)\leq \left(\tfrac{1}{64S}\tfrac{n}{v}\right)^2\right) - \mathbb{P}\left(\big|\big\{u\in [n]: \phi_n^{\scriptscriptstyle{({2}})}(u) > \left(\tfrac{1}{64S}\tfrac{n}{v}\right)^2 \big\}\big|< Sv\right) \\ & \overset{\eqref{eq:lem246132lower32bound32version2}}{\geq} c \frac{1}{(64S)^2} - C \exp \left( -vS/8 \right) \geq c^\prime \frac{1}{S^2}, \end{align}\] where \(c\) is the constant from inequality 19 . The second-to-last inequality holds for \(1 \leq 64 S \leq \tfrac{1}{\sqrt{3}}(n/v)\), and the last inequality holds for all \(S\geq S_0\), where \(S_0\) is a large enough constant. ◻

Proof. We give two (slightly) different proofs, depending whether \(S < v^{3/4}\) or \(S \geq v^{3/4}\). We start the proof for the case where \(S < v^{3/4}\). Without loss of generality, let \(S\) be such that \(\frac{v}{S} \in \mathbb{N}\), and assume that \(S\ge 32\); inequality 45 clearly holds for \(S\leq 32\) and \(C\) large enough. If \(\widehat{\sigma}_2(v)\leq \tfrac{1}{S} v\), there are no more than \(\tfrac{1}{S}v\) vertices with Jordan-2 centrality strictly larger than \(\phi_n^{\scriptscriptstyle{({2}})}(v)\). So,

\[\begin{align} \mathbb{P}\Big(\widehat{\sigma}_2(v)\le \tfrac{1}{S}v \Big) & \leq \mathbb{P}\Big(\big|\big\{u\in[n]: \phi_n^{\scriptscriptstyle{({2}})}(u) > \phi_n^{\scriptscriptstyle{({2}})}(v)\big\}\big|\le \tfrac{1}{S}v\Big) \\ & \leq \mathbb{P}\Big(\big|\big\{u\in[n]: \phi_n^{{\scriptscriptstyle{({2}})}}(u) > \left( S\tfrac{n}{64v} \right)^2 \big\}\big|\le \tfrac{1}{S}v\Big) + \mathbb{P}\Big(\phi_n^{\scriptscriptstyle{({2}})}(v)\ge \big(S\tfrac{n}{64v}\big)^2\Big). \end{align}\] The first probability on the right-hand side is bounded from above by Lemma 8 for \(t=v/S\), which is at most \(n/32\), by the assumption \(S\ge 32\). The second probability is bounded from above using Lemma [lem:Fringe95fringe95parent95large] with \(S_{\ref{lem:Fringe95fringe95parent95large}}=(S/64)^2\). Combined, we obtain that there exist constants \(C^\prime, C\) so that \[\mathbb{P}\Big(\widehat{\sigma}_2(v)\le \tfrac{1}{S}v \Big) \leq C^\prime \exp\Big(-\frac{v}{8S}\Big) + \frac{64^2C^\prime}{S^2} \leq C^\prime \exp \Big(-\frac{S^{1/3}}{8}\Big) + \frac{64^2C^\prime}{S^2} \leq \frac{C}{S^2},\] where we used the assumption \(S < v^{3/4}\) for the second inequality.

Next, we consider the case where \(v \geq S\geq v^{3/4}\). For the proof of 45 , it suffices to consider large values of \(v\), say \(v^{3/4} \geq 32\). Indeed, when \(v^{3/4} \leq 32\), then 45 is trivially satisfied for \(C\geq 32^{8/3}\), since the left-hand side of 45 equals \(0\) for \(S > 32^{4/3} \geq v\). Using the elementary inequality \[\phi_n^{{\scriptscriptstyle{({2}})}}(v) \leq n \phi_n(v) \leq n \mathrm{Fr}_n(v),\] we see that \[\begin{align} \left\{ \widehat{\sigma}_2(v) \leq \frac{v}{S} \right\} & \subseteq \left\{ \phi_n^{{\scriptscriptstyle{({2}})}}(v) \geq \Big(\frac{n}{64v^{1/4}}\Big)^2 \right\} \cup \left\{ \Big| \Big\{ u \in [n] : \phi_n^{{\scriptscriptstyle{({2}})}}(u) \geq \Big(\frac{n}{64v^{1/4}}\Big)^2 \Big\} \Big| \leq \frac{v}{S} \right\} \\ & \subseteq \left\{ \mathrm{Fr}_n(v) \geq \frac{n}{2^{12}\sqrt{v}} \right\} \cup \left\{ \Big| \Big\{ u \in [n] : \phi_n^{{\scriptscriptstyle{({2}})}}(u) \geq \Big(\frac{n}{64v^{1/4}}\Big)^2 \Big\} \Big| \leq v^{1/4} \right\} . \end{align}\] To bound the probability of the first event on the right-hand side, we apply inequality 28 from Lemma [lem:proba95large95fringe]. For the second event, we use Lemma 8 for \(t=v^{1/4}\), which applies for \(v^{1/4}\le n/16\), which holds since \(v^{3/4}\ge 32\). We obtain \[\begin{align} \mathbb{P}\left( \widehat{\sigma}_2(v) \leq \frac{v}{S} \right) & \leq \mathbb{P}\left( \mathrm{Fr}_n(v) \geq \frac{\sqrt{v}}{2^{12}} \frac{n}{v} \right) + \mathbb{P}\left( \Big| \Big\{ u \in [n] : \phi_n^{{\scriptscriptstyle{({2}})}}(u) \geq \Big(\frac{n}{64v^{1/4}}\Big)^2 \Big\} \Big| \leq v^{1/4} \right) \\ & \leq 2 e^2 \exp\left( - \frac{\sqrt{v}}{2^{12}} \right) + C \exp \left( - \frac{v}{8 v^{3/4}} \right) \leq \frac{C^\prime}{v^{2}} \leq \frac{C^\prime}{S^2}, \end{align}\] for some constant \(C'\), where we used the assumption \(S \leq v\) for the last inequality.

Lastly, inequality 45 is clear for \(S>v\), since the left-hand side of inequality 45 equals \(0\) for \(S>v\). ◻

Proof. Let us fix some \(n\geq1\), \(v\in [n]\) and \(S\geq 1\). We start by noting that to have \(\widehat{\sigma}_2(v)\le \tfrac{1}{S}v\), it suffices that no more than \(v/S\) vertices have Jordan-\(2\) centrality at least \(\phi_n^{(2)}(v)\). So,

\[\mathbb{P}\left(\widehat{\sigma}_2(v)\le \frac{1}{S}v\right) \geq \mathbb{P}\left(\big|\big\{u \in [n]: \phi_n^{\scriptscriptstyle{({2}})}(u) \ge\phi^{\scriptscriptstyle{({2}})}_n(v)\big\}\big|\le v/S\right).\] Moreover, for any constant positive constant \(C^\star\) \[\label{eq:Jordan95295LT95LB95decompo} \begin{align} \mathbb{P}\left(\widehat{\sigma}_2(v)\le \frac{1}{S}v\right) &\ge \mathbb{P}\left(\left\{\phi_n^{\scriptscriptstyle{({2}})}(v) \ge \left(2C^\star S\tfrac{n}{v}\right)^2\right\} \cap \Big\{ \big|\big\{u \in [n] : \phi^{\scriptscriptstyle{({2}})}_n(u) \ge\phi^{\scriptscriptstyle{({2}})}_n(v)\big\}\big|\le v/S \Big\}\right)\\ &\ge \mathbb{P}\left(\phi_n^{\scriptscriptstyle{({2}})}(v) \ge \left(2C^\star S\tfrac{n}{v}\right)^2\right) - \mathbb{P}\left(\big|\big\{u\in [n]: \phi^{\scriptscriptstyle{({2}})}_n(u) \ge \left(2C^\star S\tfrac{n}{v}\right)^2\big\}\big|> \frac{1}{S}v\right). \end{align}\tag{46}\] Choose \(C^\star \in (0,\infty)\) large enough, as in Lemma [lem:mixed32large], so that \[\label{eq:lem2461032ref} \mathbb{P}\left(\big|\big\{u\in [n] \setminus {1}: \mathrm{Fr}_n(u)\mathrm{Fr}_n(\mathrm{pa}(u)) \ge \left(\tfrac{n}{t}\right)^2\big\}\big|> C^\star t \right) \leq \exp \left( - t^{1/4} \right)\tag{47}\] for all \(t\geq 1\). Let \(\delta \leq \frac{1}{2 C^\star}\), so that \(v/S \geq 2\) and \(\tfrac{v}{2 C^\star S} \geq 1\). Applying the previous inequality for \(t=\tfrac{v}{2 C^\star S}\), we get that for \(S \leq \delta v\), \[\begin{align} & \mathbb{P}\left(\big|\big\{u\in [n]: \phi^{\scriptscriptstyle{({2}})}_n(u) \ge \left(2 C^\star S\tfrac{n}{v}\right)^2\big\}\big|> \frac{1}{S}v\right) \\ &\leq \mathbb{P}\left(\big|\big\{u\in [n] \setminus {1}: \mathrm{Fr}_n(u)\mathrm{Fr}_n(\mathrm{pa}(u)) \ge \left(2 C^\star S \tfrac{n}{v}\right)^2\big\}\big|> \frac{1}{S}v - 1\right) \\ & \leq \mathbb{P}\left(\big|\big\{u\in [n] \setminus {1}: \mathrm{Fr}_n(u)\mathrm{Fr}_n(\mathrm{pa}(u)) \ge \left(2 C^\star S\tfrac{n}{v}\right)^2\big\}\big|> C^\star \frac{v}{2C^\star S} \right)\\ &\leq \exp \left( - \left( \tfrac{v}{2 C^\star S} \right)^{1/4} \right) , \end{align}\] where the first inequality holds since \(\phi_n^{\scriptscriptstyle{({2}})}(u)\leq \mathrm{Fr}_n(u)\mathrm{Fr}_n(\mathrm{pa}(u))\). Plugging the above into 46 and using Lemma 3 at \((2C^\star S)^2\), \[\begin{align} \mathbb{P}\left(\widehat{\sigma}_2(v)\le \frac{1}{S}v\right) &\geq \frac{1}{128\cdot (2C^\star S)^2} - \frac{C}{v} - \exp \left( - \left( \tfrac{v}{2C^\star S} \right)^{1/4} \right)\geq \frac{c'}{S^2} \end{align}\] for some constants \(C>0\) and \(c^\prime >0\) and all \(S \in \left[1, \delta \sqrt{v} \right]\), for a sufficiently small constant \(\delta>0\). ◻

Proof. The proof of the theorem follows immediately from combining Lemmas 6, 7, 9, and 10. ◻

Proof. We start by noting that it suffices to prove the result for \(n \geq n_0\) and \(S\geq S_0\) large enough. Let \(v\in\{2,\ldots,n\}\) and \(S \in[1, \frac{n}{64v}]\). Define the two events \[\begin{align} \mathcal{A}& = \left\{ \mathrm{Fr}_{n}(v) \leq \frac{n}{64 Sv} \right\}, \\ \mathcal{B}& = \left\{ \left| \left\{ u \in [n] : \phi_n(u) > \frac{n}{64Sv} \right\} \right| > Sv \right\} . \end{align}\] On the event \(\mathcal{A}\), the fringe-tree size of \(v\) is smaller than \(n/2\), so \(\phi_n(v) = \mathrm{Fr}_n(v) \leq \frac{n}{64Sv}\). Moreover, on the event \(\mathcal{B}\), there are at least \(Sv\) vertices \(u\) with \(\phi_n(u)> \frac{n}{64Sv}\). Thus, on the event \(\mathcal{A}\cap \mathcal{B}\) one has that \[\left| \left\{ u\in [n] : \phi_{n}(u) > \phi_{n}(v) \right\} \right|\, > \, Sv,\] which implies that \[\mathbb{P}\left( \widehat{\sigma}_J(v)\ge Sv \right) \;\geq\;\mathbb{P}\left( \mathcal{A}\cap \mathcal{B}\right) \;\ge\;\mathbb{P}\left( \mathcal{A}\right) - \mathbb{P}\left( \mathcal{B}^c \right).\] To bound \(\mathbb{P}(\mathcal{A})\), we apply the lower bound on the lower tail of the fringe-tree size in 21 in Lemma [lem:beta-bin-fringe](3), which requires \(S \le n/(64v)\), which holds by our assumptions on \(S\). We obtain

\[\mathbb{P}\left( \mathcal{A}\right) = \mathbb{P}\left(\mathrm{Fr}_n(v)\le \frac{n}{64 Sv}\right) \geq \frac{1}{8\cdot 64S}=\frac{1}{512 S}.\] In order to bound \(\mathbb{P}(\mathcal{B}^c)\) from above, we use Lemma 8 and get that for \(S\leq \frac{n}{16 v}\), \[\begin{align} \mathbb{P}\left( \mathcal{B}^c \right) = \mathbb{P}\left(\left|\left\{ u \in [n] : \phi_n(u) > \frac{n}{64Sv} \right\}\right| \leq Sv\right) \leq C \exp(-Sv/8) \leq C \exp(-S/8) , \end{align}\] where \(C\) is the constant from inequality 40 . Thus, we see that \[\begin{align} \mathbb{P}\left( \widehat{\sigma}_{J}(v) \geq S v \right) \geq \mathbb{P}\left( \mathcal{A}\right) - \mathbb{P}\left( \mathcal{B}^c \right) \geq \frac{1}{512S} - C e^{-S/8} \geq \frac{c_\star}{S} , \end{align}\] for some constant \(c_\star>0\), and all \(S\) large enough, say \(S\geq S_0 > 1\). It remains to prove the result for \(1\leq S\leq S_0\). Let \(\delta = \tfrac{1}{(S_0 +1) 64}\). For \(v > \delta n\), there is nothing to show since \(\delta \tfrac{n}{v} < 1\) and we only consider \(1\leq S\leq \delta \tfrac{n}{v}\). If \(\delta \tfrac{n}{v} \geq 1\) (and thus \(S_0 \leq \tfrac{n}{64v})\), then for \(v\in \{2,\ldots, \lfloor \delta n \rfloor \}\), and \(1 \leq S \leq S_0\), we have \[\mathbb{P}\left( \widehat{\sigma}_J(v) \geq Sv \right) \geq \mathbb{P}\left( \widehat{\sigma}_J(v) \geq S_0 v \right) \geq \frac{c_\star}{S_0} \geq \frac{c_\star / S_0}{S},\] showing inequality 48 with \(c=c_\star / S_0\) and \(\delta= \tfrac{1}{(S_0+1) 64}\), for all \(v \in \{2,\ldots,\lfloor \delta n \rfloor \}\). For \(v=1\), observe that the vertices \(1\) and \(2\) are indistinguishable for any label-invariant estimator, so that for \(1\leq S \leq \delta \frac{n}{v}\) we get that \[\begin{align} \mathbb{P}\left( \widehat{\sigma}_J(1) \geq S \cdot 1 \right) = \mathbb{P}\left( \widehat{\sigma}_J(2) \geq S/2 \cdot 2 \right) \geq \frac{c}{S/2} \geq \frac{c}{S}, \end{align}\] where we applied inequality 48 , which was previously established for \(v=2\). ◻

Proof. Fix some \(n\in\mathbb{N}\), \(v\in[n]\) and \(S\ge 1\). Since \(\widehat{\sigma}_J\) is a permutation of \([n]\), if \(S>n/v\) then the probability in 49 equals 0. Further, it suffices to consider \(S\) large enough and \(v \leq \frac{n}{2}\), by taking the constant \(C\) in 49 large enough.

We first assume \(v\ge 2\). Note that if \(\widehat{\sigma}_J(v)\ge Sv\) then at least \(Sv\) vertices have Jordan centrality at least \(\phi_n(v)\). Thus, for some \(M=M(S,v)>0\), we decompose \[\begin{align} \{\widehat{\sigma}_J(v)\ge Sv\} &\subseteq \Big\{ \big|\big\{u \in [n] : \phi_{n}(u) \geq \phi_{n}(v)\big\} \big| \geq Sv \Big\} \\ &\subseteq \left\{\phi_n(v) \le \frac{n}{Mv}\right\}\cup \left\{ \left|\left\{u \in [n] : \phi_{n}(u) \geq \frac{n}{Mv}\right\} \right| \geq Sv \right\}. \end{align}\] By Lemma 2, \(\phi_n(v)\ge \min(\mathrm{Fr}_n^{>v}(v), \mathrm{Fr}_n^{>v}(1))\), which we use for the first event in the union. Further, by the exchangeability in Lemma [lem:beta-bin-fringe](1), \(\mathrm{Fr}_n^{>v}(v)\) and \(\mathrm{Fr}_n^{>v}(1)\) have the same distribution as \(\mathrm{Fr}_n(v)\). For the second event we use the upper bound \(\phi_n(u)\le \mathrm{Fr}_n(u)\), see 8 . Therefore, \[\begin{align} \mathbb{P}\left(\widehat{\sigma}_J(v)\ge Sv\right)\;& \leq \mathbb{P}\Big(\phi_n(v) \le \frac{n}{Mv}\Big) + \mathbb{P}\left( \left|\left\{u \in [n] : \phi_{n}(u) \geq \frac{n}{Mv}\right\} \right| \geq Sv \right)\\ & \le\; 2\mathbb{P}\left(\mathrm{Fr}_n(v) \le \frac{n}{Mv}\right)+ \mathbb{P}\left( \left|\left\{u \in [n] : \mathrm{Fr}_n(u) \geq \frac{n}{Mv}\right\} \right| \geq Sv \right). \end{align}\] Inequality 20 from Lemma [lem:beta-bin-fringe](3) (which actually holds for all \(M>0\)) provides an upper bound for the first term, implying that \[\mathbb{P}\left(\widehat{\sigma}_J(v)\ge Sv\right) \le \frac{4}{M}+ \mathbb{P}\left( \left|\left\{u \in [n] : \mathrm{Fr}_n(u) \geq \frac{n}{Mv}\right\} \right| \geq Sv \right).\] We bound the remaining term using Corollary 4. Let \(C\) be the constant from Corollary 4, let \(\widetilde{C}>C\), and let \(M\mathrel{\vcenter{:}}= \frac{S}{C}\). Then Corollary 4 implies that \[\begin{gather} \mathbb{P}\left(\widehat{\sigma}_J(v)\ge Sv\right) \le \frac{4}{S/\widetilde{C}} + \mathbb{P}\bigg( \Big|\Big\{u \in [n] : \mathrm{Fr}_{n}(u) \geq \frac{n}{Sv/\widetilde{C}}\Big\} \Big| \geq \widetilde{C} \frac{Sv}{\widetilde{C}} \bigg) \\ \le \frac{4 \widetilde{C}}{S} + \exp\left(-\widetilde{C}^{-1/4}\left(Sv\right)^{1/4}\right) \leq \frac{8 \widetilde{C}}{S}, \end{gather}\] where the last inequality holds for \(S\) large enough. To prove 49 for \(v=1\), note that vertices \(1\) and \(2\) are indistinguishable for any label-invariant estimator. Thus for \(S\) large enough, \[\mathbb{P}\left(\widehat{\sigma}_J(1)\ge S\cdot 1\right) = \mathbb{P}\left(\widehat{\sigma}_J(2)\ge (S/2)\cdot 2\right)\le \frac{8\widetilde{C}}{S/2}=\frac{16\widetilde{C}}{S},\] so that the result 49 follows by taking the constant \(C\) in 49 large enough. ◻

Proof. The statement is clear for \(4v \leq S\), since the relevant probability equals \(0\). Further, it suffices to consider the case when \(v/S \in \mathbb{N}\), which we will assume for the rest of the proof. Lastly, the statement is clear for \(S\in[1,32]\) by taking \(C\) large enough. So let \(n\in \mathbb{N}\), \(v\in \{1,\ldots,n\}\) and \(4v >S\ge 32\). First, note that if \(\widehat{\sigma}_J(v)\le v/S\) then no more than \(v/S\) vertices have Jordan centrality exceeding \(\phi_n(v)\). Hence

\[\begin{align} \mathbb{P}\left(\widehat{\sigma}_J(v)\le \frac{1}{S}v\right) &\leq \mathbb{P}\left(\big|\big\{u\in [n]: \phi_n(u) >\phi_n(v)\big\}\big|\le \frac{v}{S}\right) \\ &\le \mathbb{P}\left(\left|\left\{u : \phi_n(u) > S \frac{n}{64v} \right\}\right|\le \frac{v}{S}\right) + \mathbb{P}\left( \phi_n(v) \geq S \frac{n}{64 v} \right) . \end{align}\] The first summand can be bounded using Lemma 8 for \(t=v/S\), which applies as \(v/S\le n/16\) because \(S\ge 32\). For the second summand we use that \(\phi_n(v)\le \mathrm{Fr}_n(v)\), so that \[\nonumber \mathbb{P}\left(\phi_n(v) \ge S \frac{n}{64v}\right) \leq \mathbb{P}\left(\mathrm{Fr}_n(v)\ge \frac{S}{64} \frac{n}{v}\right) \le C^\prime \exp\left(-\frac{S}{64} \right)\] with \(C^\prime = 2 e^2\), by inequality 28 . Thus, we get that \[\mathbb{P}\Big(\widehat{\sigma}_J(v)\le \frac{1}{S}v\Big) \le C \exp \Big( - \frac{v}{8S} \Big)+ C^\prime \exp\Big(-\frac{S}{64} \Big). \qedhere\] ◻

Proof. It suffices to consider the case where \(v/S \in \mathbb{N}\), which we will assume for the rest of the proof. Moreover, we assume that \(v\ge3\), as the range for \(S\) can be made empty for \(v\in\{1,2\}\) by choosing \(c'\) small. We start with the case where \(S \leq \sqrt[10]{v}\). Let \(M\ge 1\) be a constant such that for all \(t>0\), \[\label{corocoro} \mathbb{P}\left( \big| \big\{ v\in [n] : \mathrm{Fr}_{n}(v) > n/t \big\} \big| > Mt \right) \leq \exp \left( 1-t^{1/4} \right).\tag{51}\] Such a constant exists by Corollary 4. The most likely way to underestimate the arrival time of \(v\) is when its fringe tree is large. Similar to the proof of Lemma 10, we bound

\[\begin{align} \notag \mathbb{P}\left(\widehat{\sigma}_J(v)\leq \frac{v}{S}\right) &\geq \mathbb{P}\left(\big|\big\{u\in [n]: \phi_n(u) \ge\phi_n(v)\big\}\big|\le \frac{v}{S} \right) \\ \notag&\ge \mathbb{P}\left( \Big\{\mathrm{Fr}_n(v)\in \left[MS\frac{n}{v}, \frac{n}{2}\right]\Big\} \cap \Big\{\big|\big\{u\in [n]: \phi_n(u) \ge MS\frac{n}{v}\big\}\big|\le v/S\Big\} \right) \\ &\ge \mathbb{P}\left(\mathrm{Fr}_n(v)\ge MS\frac{n}{v}\right) - \mathbb{P}\left(\mathrm{Fr}_n(v)\ge n/2\right) \tag{52}\\&- \mathbb{P}\left(\big|\big\{u\in [n]: \phi_n(u) \ge MS\frac{n}{v}\big\}\big|> v/S\right).\tag{53} \end{align}\] To bound the probabilities in 52 , we employ 29 and 28 from Lemma [lem:proba95large95fringe], which imply that \[\begin{align} \mathbb{P}\left(\mathrm{Fr}_n(v)\ge MS\frac{n}{v}\right) \geq \frac{1}{2} \exp \left(-8MS \right), \qquad \text{ and } \qquad \mathbb{P}\left(\mathrm{Fr}_n(v)\ge n/2\right) \leq 2 e^2 \exp \left( - \frac{v}{2} \right) . \end{align}\] Further, the remaining probability on 53 is bounded from above by 51 (see also Corollary 4), using additionally that \(\phi_n(v)\le \mathrm{Fr}_n(v)\): \[\begin{gather} \mathbb{P}\left(\left|\left\{u\in [n]: \phi_n(u) \ge MS\frac{n}{v}\right\}\right|> \frac{v}{S}\right) \\ \leq \mathbb{P}\left(\left|\left\{u\in [n]: \mathrm{Fr}_n(u) \ge \frac{n}{v/(MS)}\right\}\right|> M \frac{v}{MS}\right) \leq \exp\left(1 - \left( \frac{v}{MS} \right)^{1/4} \right) . \end{gather}\] Combining the above inequalities, we get that \[\begin{align} \mathbb{P}\left(\widehat{\sigma}_J(v)\leq \frac{v}{S}\right) &\ge\frac{1}{2} \exp \left( -8MS \right) - 2 e^2 \exp\left( - \frac{v}{2} \right)- \exp\left(1 - \left( \frac{v}{MS} \right)^{1/4} \right). \end{align}\] Since we assumed that \(S\leq \sqrt[10]{v}\), we see that there exist positive constants \(c^\prime, c, C\) so that \[\mathbb{P}\left(\widehat{\sigma}_J(v)\leq \frac{v}{S}\right) \geq c e^{-CS}.\] for any \(1 \leq S \leq c^\prime v \wedge \sqrt[10]{v}\).

Next, we consider the case where \(\tfrac{v}{2} \geq S> \sqrt[10]{v}\). We intersect with the event that \(\mathrm{pa}(v)=1\) and also condition on the size of the fringe tree of \(v\). We first prove for each \(k\in [2 RSn/v, n/2]\), where \(R\) is a large constant, the inclusion \[\label{eq:inclusion} \Big\{\widehat{\sigma}_J(v)\le \frac{v}{S}\Big\}\, \supseteq\,\left\{ \mathrm{pa}(v) = 1, \mathrm{Fr}_n(v) = k \right\} \cap \left\{ \left| \left\{u \notin (T_n,1)_{v \downarrow}: \mathrm{Fr}_n(u) \geq k \right\} \right| \leq \frac{Rn}{k} \right\}.\tag{54}\] We start from the right-hand side. If the fringe tree of \(v\) has size equal to \(k\), then all its children have fringe tree size strictly smaller than \(k\), allowing to change the counted set in the last event to include all \(u\in[n]\) without changing the event. Since for \(k\le n/2\) we have \(k=\mathrm{Fr}_n(v)=\phi_n(v)\), we have \[\begin{align} &\left\{ \mathrm{Fr}_n(v)=k, \left| \left\{u \notin (T_n,1)_{v \downarrow}: \mathrm{Fr}_n(u) \geq k \right\} \right| \leq \frac{Rn}{k} \right\} \\ &\subseteq \left\{ \phi_n(v)=k, \left| \left\{u \in[n], \mathrm{Fr}_n(u) \geq \phi_n(v) \right\} \right| \leq \frac{Rn}{k} +1 \right\}\\ &\subseteq \left\{ \phi_n(v)=k, \left| \left\{u \in[n]: \phi_n(u) \geq \phi_n(v) \right\} \right| \leq \frac{Rn}{k} +1 \right\}, \end{align}\] where we used that \(\phi_n(u)\le \mathrm{Fr}_n(u)\) for the last inclusion. The inclusion 54 follows since \(Rn/k +1 \le v/S\) for \(k\in [2RSn/v, n/2]\) and \(S \leq \tfrac{v}{2}\). Since the events on the right-hand side in 54 are disjoint in \(k\), we obtain that \[\begin{align} \notag \mathbb{P}\big(\widehat{\sigma}_J(v)\le v/S\big) \ge \sum_{k= \lceil 2RSn/v\rceil}^{n/2}\bigg( &\mathbb{P}\Big( \left| \left\{u \notin (T_n,1)_{v \downarrow}: \mathrm{Fr}_n(u) \geq k \right\} \right| \leq \frac{Rn}{k}\, \Big|\, \mathrm{pa}(v) = 1, \mathrm{Fr}_n(v) = k \Big) \\ & \label{align:three32terms} \cdot \mathbb{P}\big( \mathrm{pa}(v) = 1\big)\cdot\mathbb{P}\big( \mathrm{Fr}_n(v) = k \big)\bigg), \end{align}\tag{55}\] using that the size of the fringe tree of \(v\) and the parent of \(v\) are independent. Conditioned on the event \(\left\{ \mathrm{pa}(v) = 1, \mathrm{Fr}_n(v) = k \right\}\), the tree \(T_n \setminus (T_n,1)_{v \downarrow}\) is distributed like a uniform attachment tree of size \(n-k\). By Markov’s inequality, \[\begin{align} \mathbb{P}\Big( \Big| \Big\{u \notin (T_n,1)_{v \downarrow}&: \mathrm{Fr}_n(u) \geq k \Big\} \Big| \leq \frac{Rn}{k}\, \Big|\, \mathrm{pa}(v) = 1, \mathrm{Fr}_n(v) = k \Big) \\ &= 1-\mathbb{P}\Big( \left| \left\{u\in[n-k]: \mathrm{Fr}_{n-k}(u) \ge k \right\} \right| > \frac{Rn}{k}\Big) \\ & \geq 1 - \frac{k}{Rn} \mathbb{E}\left[ \left| \left\{u\in[n-k]: \mathrm{Fr}_{n-k}(u) \ge k \right\} \right| \right] \\ &= 1- \frac{k}{Rn}\sum_{u\in[n-k]}\mathbb{P}\Big(\mathrm{Fr}_{n-k}(u)\ge k\Big) \\ &\ge 1- \frac{k}{Rn}\sum_{u\in[n]}\mathbb{P}\Big(\mathrm{Fr}_{n}(u)\ge k\Big). \end{align}\] By 28 in Lemma [lem:proba95large95fringe] there exists an absolute constant \(C>0\) such that the last sum in the above display is at most \(Cn/k\). Fixing \(R=2C\) implies that the probability is at least \(1/2\). Using that \(\mathbb{P}(\mathrm{pa}(v)=1)=1/(v-1)\), and inserting the previous inequalities into 55 , we see that \[\mathbb{P}\big(\widehat{\sigma}_J(v)\le v/S\big) \ge \sum_{k= \lceil 2RSn/v\rceil}^{n/2} \frac{1}{2} \frac{1}{v-1} \mathbb{P}\left( \mathrm{Fr}_n(v)=k \right) = \frac{1}{2(v-1)}\mathbb{P}\Big(\mathrm{Fr}_n(v)\in \big[2RSn/v, n/2\big] \Big).\] Using 29 and 28 in Lemma [lem:proba95large95fringe], it follows that there exist constants \(c, c'>0\) such that for all \(S\in[\sqrt[10]{v}, c'v]\), \[\mathbb{P}\big(\widehat{\sigma}_J(v)\le v/S\big) \ge \frac{1}{2(v-1)}\left( \frac{1}{2} \exp\left( -16 RS \right) -2 e^2 \exp \left( - \frac{v}{2} \right) \right) \geq c e^{-CS}. \qedhere\] ◻

Proof. Lemmas 11 and 12 establish the upper tail 12 . Lemma 14 shows the first inequality in 13 . Lemma 13 shows the second inequality in 13 , since \(v/S\ge S\) for \(S \leq \sqrt{v}\). Thus, \[\mathbb{P}\Big(\widehat{\sigma}_J(v)\le \frac{1}{S}v\Big)\leq C \left( e^{- c v/S} + e^{-S/64} \right) \leq C \left( e^{- c S} + e^{-S/64} \right) .\qedhere\] ◻

Proof. Let \(\mathrm{t}\) be a recursive tree of size \(n\ge v\). The proof of the lemma is trivial if \(I_v(\mathrm{t})\) has only one element. Suppose \(|I_v(\mathrm{t})|\ge2\) and let \(i,j\) be two distinct vertices in \(I_v(\mathrm{t})\). Since every permutation on \(I_v(\mathrm{t})\) can be written as a product of transpositions on \(I_v(\mathrm{t})\), it suffices to prove the claim for transpositions. Let \(\tau=(i,j)\). Every simple path from the root to a leaf that does not pass through \(i\) or \(j\) remains increasing in \(\mathrm{t}^\tau\). Consider the two simple paths \(\pi^{\scriptscriptstyle{({i}})}\) and \(\pi^{\scriptscriptstyle{({j}})}\) from vertex \(1\) passing through \(i\) and \(j\), respectively, and ending at a leaf of \(\mathrm{t}\). We have to show that the labels along these paths remain increasing if we swap \(i\) and \(j\) and that \(i\) and \(j\) belong to \(I_v(\mathrm{t}^{\tau})\).

Because \(\mathrm{t}\) is recursive, these paths are of the form \(\pi^{\scriptscriptstyle{({i}})}=(1,i_1,\dots ,i_k,i,i_{k+1},\dots,i_K)\) and \(\pi^{\scriptscriptstyle{({j}})}=(1,j_1,\dots ,j_\ell,j,j_{\ell+1},\dots,j_L)\) with increasing labels along both paths. By definition of \(I_v(\mathrm{t})\), we have that \(i_k < v/2 \leq i\leq v < i_{k+1}\) and \(j_\ell< v/2 \leq j \leq v < j_{\ell+1}\). As a consequence, the two simple paths in \(\mathrm{t}^{\tau}\) starting at \(1\), going through \(i\) and \(j\), respectively, and finishing at the same leaves become \((1,i_1,\dots ,i_k,j,i_{k+1},\dots,i_K)\) and \((1,j_1,\dots ,j_\ell,i,j_{\ell+1},\dots,j_L)\). Hence these paths remain increasing and both \(i\) and \(j\) belong to \(I_v(\mathrm{t}^{\tau})\). Thus \(\mathrm{t}^{\tau}\) is recursive and \(I_v(\mathrm{t})=I_v(\mathrm{t}^{\tau})\). ◻

Proof. Let \(\widehat{\sigma}\) be a label-invariant estimator. From [15] we know that in the RRT model, for every recursive tree \(\mathrm{t}\) on \(n\) vertices and every permutation \(\gamma\) such that \(\mathrm{t}^{\gamma}\) is also recursive, one has \(\mathbb{P}(T_n=t)=\mathbb{P}(T_n=t^{\gamma})\). So, for a fixed recursive tree \(\mathrm{t}\) of size at least \(v\) and a permutation \(\tau\) preserving recursivity on this tree

\[\mathbb{P}\left( T_n=\mathrm{t}\right)=\mathbb{P}\left( T_n=\mathrm{t}^{\tau^{-1}} \right)=\mathbb{P}\left( T_n^{\tau}=\mathrm{t}\right).\] Hence, for every fixed set \(\mathcal{I}\subseteq[v]\) and any permutation \(\tau\) of \(\mathcal{I}\), \[\label{eq:tree95distrib95equality2} T_n\mid I(T_v)=\mathcal{I} \;\overset{\mathcal{L}}{=} \;T_n^\tau\mid I(T_v)=\mathcal{I},\tag{57}\] where we condition on \(I(T_v)\) on both sides because \(I(T_v)=I(T_v^{\tau})\). For a fixed tree \(\mathrm{t}\) and a permutation \(\tau\) of \(\mathcal{I}\), because \(\widehat{\sigma}\) is label-invariant (see 3 ), \[\widehat{\sigma}\left(i,\mathrm{t}\right)\quad \overset{\mathcal{L}}{=} \quad \widehat{\sigma}\left(\tau(i),\mathrm{t}^{\tau}\right),\] where the equality would be deterministic if the label-invariant estimator \(\widehat{\sigma}\) were deterministic given a tree. Fix some non-empty subset \(\mathcal{I}\subseteq [v]\) consistent with \(I(\mathrm{t})=\mathcal{I}\) for some tree \(\mathrm{t}\), and \(\tau\) a permutation of \(\mathcal{I}\). Plugging the random tree \(T_n\) into the above equality, we get for \(n\ge v\),

\[\widehat{\sigma}\left(i,T_n\right)\mid I(T_v)=\mathcal{I} \quad \overset{\mathcal{L}}{=} \quad \widehat{\sigma}\left(\tau(i),T^{\tau}_n\right)\mid I(T_v) =\mathcal{I}.\] Since we assumed that \(v,i\in\mathcal{I}\), the transposition \((i,v)\) is a permutation of \(\mathcal{I}\). Choosing \(\tau=(i,v)\) yields for \(n\ge v\),

\[\widehat{\sigma}\left(i,T_n\right)\mid I(T_v)=\mathcal{I} \quad \overset{\mathcal{L}}{=} \quad \widehat{\sigma}\left(v,T_n^\tau\right)\mid I(T_v)=\mathcal{I}\quad \overset{\mathcal{L}}{=} \quad \widehat{\sigma}\left(v,T_n\right)\mid I(T_v)=\mathcal{I},\] where the second equality follows from 57 . For all \(n\ge v\), we have \(I(T_ n)=I(T_v)\) which concludes the proof of the lemma. ◻

Proof of Proposition 1. Let \(\widehat{\sigma}\) be a label-invariant estimator of the arrival times in the random recursive tree \(T_n\) of size \(n\ge v\). Let \(\delta = \tfrac{1}{56}\). We start by proving that for \(v\in[3,n]\) and \(v\geq 1/(2\delta) = 28\) \[\mathbb{P}\left(|\widehat{\sigma}(v, T_n)-v|\ge \delta v\right) \ge \frac{1}{112}-\frac{\delta}{4},\] which implies Proposition [prop:lower95bound] for \(v \geq 28.\) We condition on the set of indistinguishable vertices \(I_v(T_n)\). That is, \[\label{eq:condition-1} \mathbb{P}\left(|\widehat{\sigma}(v, T_n)-v|\ge \delta v\right) \ge\!\! \sum_{\substack{\mathcal{I} \subseteq [n]: \\ |\mathcal{I}|\ge 4\delta v ,\\ v \in \mathcal{I}}} \!\! \mathbb{P}\left(|\widehat{\sigma}(v,T_n)-v|\ge \frac{|I_v(T_n)|}{4}\;\Big|\;I_v(T_n) = \mathcal{I}\right) \mathbb{P}\big( I_v(T_n) = \mathcal{I}\big) .\tag{58}\] We first argue that the conditional probability is bounded from below by \(1/4\). By the definition of \(I_v\) in 56 and Lemma 15, \(I_v\) satisfies the hypothesis of Lemma 16. So the estimated arrival times \(\widehat{\sigma}(u, T_n)\) are identically distributed for \(u\in I_v(T_n)\). Therefore, for any set \(\mathcal{I}\) with \(|\mathcal{I}|\geq 4 \delta v\), \[\begin{align} &\mathbb{P}\left(|\widehat{\sigma}(v,T_n)-v|\ge \frac{|I_v(T_n)|}{4}\;\big|\;I_v(T_n) = \mathcal{I}\right) \\ &= \frac{1}{|\mathcal{I}|}\sum_{u\in \mathcal{I} } \mathbb{P}\left(|\widehat{\sigma}(u,T_n)-v|\ge \frac{|I_v(T_n)|}{4} \;\big|\;I_v(T_n) = \mathcal{I}\right) \\ &= \frac{1}{|\mathcal{I}|}\mathbb{E}\Bigg[\sum_{u\in I_v(T_n)} \mathbb{1}_{\left\{|\widehat{\sigma}(u,T_n)-v|\ge \frac{|I_v(T_n)|}{4} \right\}} \;\Big|\;\;I_v(T_n) = \mathcal{I} \Bigg] . \end{align}\]

Since \(\widehat{\sigma}(\, \cdot\, , T_n)\) is a bijection from \([n]\) to \([n]\), at least \(|I_v(T_n)|/4\) of the elements in \(I_v(T_n)\) must satisfy \(|\widehat{\sigma}(u,T_n)-v| \geq |I_v(T_n)|/4\) when \(|I_v(T_n)| \geq 2\). Since \(|I_v(T_n)| \geq 4\delta v \geq 2\), the sum within the conditional expectation is bounded from below by \(|I_v(T_n)|/4 = |\mathcal{I}|/4\), and the entire expression is bounded from below by \(1/4\). Substituting this bound into 58 we get that \[\label{eq:proba95lower95bound95order} \mathbb{P}\left(|\widehat{\sigma}(v,T_n)-v|\ge \delta v\right) \;\ge \!\! \sum_{\substack{\mathcal{I} \subset [n]: \\ |\mathcal{I}|\ge 4\delta v ,\\ v \in \mathcal{I}}} \!\! \tfrac{1}{4} \mathbb{P}\big( I_v(T_n) = \mathcal{I}\big)\; =\; \tfrac{1}{4}\mathbb{P}\big(|I_v(T_n)|\ge 4\delta v, v \in I_v(T_n)\big).\tag{59}\]

To conclude, we bound the probability on the right-hand side using a first-moment method. We define the set \(I_v^\prime (T_{v-1})\) by

\[I_v^\prime(T_{v-1}):=\big\{ i\in [v/2,v-1]\;: \;i\text{ is a leaf in }T_{v-1}, \;\mathrm{pa}(i) < v/2\big\}.\]

We compute the expected size of this set to be \[\begin{align} \mathbb{E}\big[ |I_v^\prime(T_{v-1})| \big] &= \sum_{k=\lceil \tfrac{v}{2}\rceil}^{v-1} \mathbb{P}\left( k\text{ is a leaf in }T_{v-1}, \;\mathrm{pa}(k)< v/2 \right)\\ &= \sum_{k=\lceil \tfrac{v}{2}\rceil}^{v-1} \frac{\lceil \tfrac{v}{2}\rceil -1}{k-1}\prod_{j=k+1}^{v-1} \frac{j-2}{j-1} = \big( v-\lceil \tfrac{v}{2}\rceil \big) \frac{\lceil \tfrac{v}{2}\rceil-1}{v-2} \\ & \geq \left( \frac{v}{2} - \frac{1}{2} \right) \frac{ \tfrac{v}{2}-1}{v-2} = \frac{v}{4}- \frac{1}{4} \geq \frac{v}{7} , \end{align}\] where the last inequality holds since \(v \geq 3\).

By truncating the first moment, and using the deterministic bound \(|I_v^\prime(T_{v-1})|\le v\), we see that \[\begin{align} \frac{v}{7}\le \mathbb{E}\left[ |I_v^\prime(T_{v-1})| \right] &= \mathbb{E}\big[|I_v^\prime(T_{v-1})|\mathbb{1}{\{|I_v^\prime(T_{v-1})|< 4\delta v\}}\big]+\mathbb{E}\big[|I_v^\prime(T_{v-1})|\mathbb{1}{\{|I_v^\prime(T_{v-1})|\ge 4\delta v\}}\big]\\ &\leq 4\delta v + v\cdot \mathbb{P}\left( |I_v^\prime(T_{v-1})|\geq 4\delta v \right). \end{align}\] Rearranging gives that for \(v\ge 3\), \[\mathbb{P}\left( |I_v^\prime(T_{v-1})|\geq 4 \delta v \right)\, \geq \,\frac{1}{7}-4\delta .\] The set \(I_v^\prime (T_{v-1})\) and \(\mathrm{pa}(v)\) are independent. Further, if \(\mathrm{pa}(v) < v/2\), then \(I_v(T_n) = I_v(T_v) = I_v^\prime(T_{v-1}) \cup \{v\}\), implying that \[\begin{align} &\mathbb{P}\left( |I_v(T_n)| \geq 4 \delta v, v \in I_v(T_n) \right) = \mathbb{P}\left( |I_v(T_n)| \geq 4 \delta v, \mathrm{pa}(v) < \frac{v}{2} \right) \\ &\geq \mathbb{P}\left( |I_v^\prime(T_{v-1})| \geq 4 \delta v, \mathrm{pa}(v) < \frac{v}{2} \right) \\ &= \mathbb{P}\left( |I_v^\prime(T_{v-1})| \geq 4 \delta v\right) \mathbb{P}\left( \mathrm{pa}(v) < \frac{v}{2} \right) \geq \left( \frac{1}{7} - 4\delta \right) \frac{\tfrac{v}{2} -1}{v-1} \geq \frac{1}{28} - \delta . \end{align}\] Plugging this result into 59 , yields \[\mathbb{P}\big(|\widehat{\sigma}(v,T_n)-v|\ge \delta v\big) \ge\frac{1}{112}-\frac{\delta}{4} .\] Since \(\delta =1/56\), this concludes the proof of the proposition for \(v\geq 28\), as we required \(v\ge 1/(2\delta)\) at the beginning of the proof.

For any \(v\in[3,28]\) and any recursive tree \(\mathrm{t}\) of size at least \(v\), we define the set

\[\tilde{I}_v(\mathrm{t}_n):=\begin{cases} \{v-1,v\} & \text{ if }v-1 \text{ and }v \text{ are leaves in } \mathrm{t}_v, \\ \emptyset & \text{ otherwise.} \end{cases}\] It is direct to check that \(\tilde{I}_v\) satisfies the hypothesis of Lemma 16. Hence

\[\widehat{\sigma}(v,T_n) \;\big| \; \tilde{I}_v(T_n)\neq \emptyset \quad \overset{\mathcal{L}}{=} \quad \widehat{\sigma}(v-1,T_n) \;\big| \; \tilde{I}_v(T_n)\neq \emptyset,\] and in particular \(\mathbb{P}\big( \widehat{\sigma}(v)=v \;\big| \;\tilde{I}_v(T_n)\neq \emptyset\big)\leq 1/2\). So

\[\mathbb{P}\big(|\widehat{\sigma}(v,T_n)-v|\ge 1 \big) \geq \mathbb{P}\big(\tilde{I}_v(T_n)\neq \emptyset\big) \mathbb{P}\left(|\widehat{\sigma}(v,T_n)-v|\ge 1 \;\big|\;\tilde{I}_v(T_n)\neq \emptyset\right) \geq \frac{1}{2}\mathbb{P}\big(\tilde{I}_v(T_n)\neq \emptyset\big).\] Checking that \(\mathbb{P}\big(\tilde{I}_v(T_n)\neq \emptyset\big)=\tfrac{v-2}{v-1}\geq \tfrac{1}{3}\) and that \(1\geq v/28\) yields

\[\mathbb{P}\big(|\widehat{\sigma}(v,T_n)-v|\ge v/28 \big) \geq \frac{1}{6},\] concluding the proof of the proposition for \(v\in [3,28]\).

For \(v\in\{1,2\}\), we use that vertices \(1\) and \(2\) are indistinguishable, hence \(\widehat{\sigma}(1,T_n)\overset{\mathcal{L}}{=}\widehat{\sigma}(2,T_n)\) and so \(\mathbb{P}\big(|\widehat{\sigma}(v,T_n)-v|\ge 1\big)\geq 1/2\), proving the proposition for \(v=1,2\). ◻

Proof. For the first item, we observe that the fringe trees witnessed after time \(m\) are all disjoint. Their evolution after time \(m\) is modeled by a Pólya urn [24] with \(m\) colors, starting at time \(m\) with one ball of each color. At each time \(n > m\), a ball is picked uniformly at random from the urn, and the picked ball is replaced by two balls of the same color as the picked ball. The number of balls of color \(i\in[m]\) at time \(n\) describes the witnessed fringe tree size of a vertex: indeed, each arriving vertex joins a fringe tree with probability proportional to the size of the tree.

The number of balls of each color at time \(n\ge m\) is an exchangeable family of random variables, yielding point 1. The family follows a Dirichlet-multinomial distribution, implying that the witnessed fringe-tree sizes are negatively associated, proving the second item.

For the third item of Lemma [lem:beta-bin-fringe], we use the exchangeability, and observe that \(\mathrm{Fr}_n^{>m}(m)=\mathrm{Fr}_n(m)\). The size of a single fringe tree evolves according to a beta-binomial random variable plus one. That is, \[\label{eq:pmf-fringe-tree} \mathbb{P}\left(\mathrm{Fr}_n(m)=k\right) = (m-1)\frac{(n-m)!}{(n-1)!}\frac{(n-k-1)!}{(n-m-k+1)!}, \quad k \in \{1,\ldots,n-m\}.\tag{60}\] We start with the upper bound on the lower tail, i.e., inequality 20 . When \(m=1\), \(\mathrm{Fr}_n(1)=n\) and the bound is trivial. So we can assume that \(n\ge m\ge2\) for the rest of the proof of 20 . Observe that for \(k \in \{1,\ldots,n-m+1\}\), \[\frac{\mathbb{P}\left(\mathrm{Fr}_n(m)=k+1\right)}{\mathbb{P}\left(\mathrm{Fr}_n(m)=k\right)} = \frac{(n-k-2)!}{(n-m-k)!} \frac{(n-m-k+1)!}{(n-k-1)!} = \frac{n-m-k+1}{n-k-1}=1 - \frac{m-2}{n-k-1} \leq 1.\] So the function \(k\mapsto \mathbb{P}(\mathrm{Fr}_n(v)=k)\) is non-increasing for \(m\ge 2\). Hence, \[\mathbb{P}\left(\mathrm{Fr}_n(m)\le \frac{n}{M m}\right) \le \frac{n}{M m}\mathbb{P}\left(\mathrm{Fr}_n( m)=1\right)=\frac{n}{M m}(m-1)\frac{(n-m)!}{(n-1)!}\frac{(n-2)!}{(n-m)!}=\frac{n}{Mm}\frac{m-1}{n-1}.\] The right-hand side is at most \(2/M\), since \(n\geq 2\). We proceed to the lower bound on the lower tail, inequality 21 , assuming \(n\ge m\ge 2\), \(m\le n/M\), and \(M\ge 4\). Set \[\label{eq:lower-tail-useful} k=\left\lfloor\frac{n}{Mm}\right\rfloor,\qquad\text{and observe}\qquad m-2\leq \frac{n}{4} \le \frac{n}{2}\left(1-\frac{1}{Mm}\right)\le \frac{n-k}{2}.\tag{61}\] Since the function \(j \mapsto \mathbb{P}(\mathrm{Fr}_n(m)=j)\) is non-increasing for \(m\geq 2\), we have \[\begin{align} \mathbb{P}\big(\mathrm{Fr}_n(m)\le k\big) \;\ge \;k \cdot \mathbb{P}\big(\mathrm{Fr}_n(m)=k\big) \;& = \;k \cdot \mathbb{P}\big(\mathrm{Fr}_n(m)=1\big) \prod_{j=1}^{k-1} \frac{\mathbb{P}\left(\mathrm{Fr}_n(m)=j+1\right)}{\mathbb{P}\left(\mathrm{Fr}_n(m)=j\right)} \\ & = \left\lfloor\frac{n}{Mm}\right\rfloor\frac{m-1}{n-1}\prod_{j=1}^{k-1}\left(1-\frac{m-2}{n-j-1}\right)\\&\ge \frac{1}{4M}\prod_{j=1}^{k-1}\left(1-\frac{m-2}{n-j-1}\right),\end{align}\] where we used the formula for \(\tfrac{\mathbb{P}\left(\mathrm{Fr}_n(m)=j+1\right)}{\mathbb{P}\left(\mathrm{Fr}_n(m)=j\right)}\) proven above. By 61 , each term \(\tfrac{m-2}{n-j-1}\) in the above product product is at most \(1/2\). We use that \(1-x\ge \exp(-2x)\) for all \(x\in[0, 1/2]\). This yields \[\mathbb{P}\left(\mathrm{Fr}_n(v)\le k\right)\ge \frac{1}{4M}\exp\bigg(-2(m-2)\sum_{j=1}^{k-1}\frac{1}{n-j-1}\bigg) = \frac{1}{4M}\exp\bigg(-2(m-2)\sum_{j=2}^k\frac{1}{n-j}\bigg).\] Recall \(k=\lfloor n/(Mm)\rfloor\). We bound the sum in the exponential from above by \(k/(n-k)\), which is at most \(1/(Mm-1)\). We obtain for \(M\ge 4\) and \(m\ge 2\), \[\mathbb{P}\left(\mathrm{Fr}_n(m)\le \frac{n}{Mm}\right) \ge \frac{1}{4M}\exp\bigg(-2(m-2)\frac{1}{Mm-1}\bigg) \geq \frac{1}{4M}\exp\bigg(-\frac{2(m-2)}{4m-1}\bigg) \ge \frac{1}{4\sqrt{e} M}\ge \frac{1}{8M}.\] This finishes the proof. ◻

Proof. We work on the event \(\mathcal{E}=\{\mathrm{pa}(v)\text{ is a leaf in }T_{v-1}, \mathrm{pa}(v) \geq 2\}\), which has probability \(1/2\) for \(v\geq 3\). Indeed, using that \(\mathrm{pa}(v)\) is uniformly distributed on \([1,v-1]\) and independent from \(T_{v-1}\), we see that

\[\begin{align} \mathbb{P}\left( \mathcal{E}\right) = &\; \frac{1}{v-1}\sum_{i=2}^{v-1}\mathbb{P}\left( i \text{ is a leaf in }T_{v-1} \right) = \frac{1}{v-1}\left[1+\sum_{i=2}^{v-2}\prod_{j=i+1}^{v-1}\frac{j-2}{j-1} \right]\\ =& \; \frac{1}{v-1}\left[1+\sum_{i=2}^{v-2}\frac{i-1}{v-2} \right] = \frac{1}{v-1}\sum_{i=2}^{v-1}\frac{i-1}{v-2} = \frac{1}{(v-1)(v-2)} \sum_{i=1}^{v-2} i =\frac{1}{2}. \end{align}\] Since, on the event \(\mathcal{E}\), \(\mathrm{Fr}_n^{>v}(\mathrm{pa}(v)) + \mathrm{Fr}_n^{>v}(v)\) behaves like the number of red balls in a Pólya urn, started with \(2\) red balls and \(v-2\) many blue balls at time \(v\), we get that \[\begin{align} &\mathrm{Fr}_n^{>v}(\mathrm{pa}(v)) + \mathrm{Fr}_n^{>v}(v) - 2 \sim \mathrm{BetaBin}\left( n - v , 2, v-2 \right) , \text{ and } \\ & \mathrm{Fr}_n^{>v}(v) \sim \mathrm{Unif} \left\{ 1 , \ldots , \mathrm{Fr}_n^{>v}(\mathrm{pa}(v)) + \mathrm{Fr}_n^{>v}(v) - 1 \right\}. \end{align}\] We record a useful claim about the Beta-Binomial distribution, which we will prove below.

On the event \(\mathcal{E}\) one has \[\mathrm{Fr}_n(\mathrm{pa}(v)) = \mathrm{Fr}_n^{>v}(\mathrm{pa}(v)) + \mathrm{Fr}_n^{>v}(v).\] Using the law of total probability, we can thus calculate \[\begin{align} \label{eq:log32dep} \notag \mathbb{P}\left( \mathrm{Fr}_n(v) \mathrm{Fr}_n(\mathrm{pa}(v)) \leq s \left(\frac{n}{v}\right)^2 \right) &\geq \mathbb{P}\left( \mathrm{Fr}_n(v) \mathrm{Fr}_n(\mathrm{pa}(v)) \leq s \left(\frac{n}{v}\right)^2 \;\Big|\; \mathcal{E}\right) \mathbb{P}\left(\mathcal{E}\right) \\ & \notag = \mathbb{P}\left( \mathrm{Fr}_n^{>v}(v) \left(\mathrm{Fr}_n^{>v}(\mathrm{pa}(v)) + \mathrm{Fr}_n^{>v}(v)\right) \leq s \left(\frac{n}{v}\right)^2\;\Big|\;\mathcal{E}\right) \frac{1}{2} \\ & \notag \geq \sum_{k=2}^{n-v} \mathbb{P}\left( \mathrm{Fr}_n^{>v}(v) k \leq s \left(\frac{n}{v}\right)^2\;\Big|\;\mathcal{E}, \mathrm{Fr}_n^{>v}(\mathrm{pa}(v)) + \mathrm{Fr}_n^{>v}(v) = k \right) \\ &\cdot \mathbb{P}\left( \mathrm{Fr}_n^{>v}(\mathrm{pa}(v)) + \mathrm{Fr}_n^{>v}(v) = k\;\big|\;\mathcal{E}\right) \frac{1}{2}. \end{align}\tag{62}\] The events \(\left\{\mathrm{Fr}_n^{>v}(\mathrm{pa}(v)) + \mathrm{Fr}_n^{>v}(v) = k \right\}\) and \(\mathcal{E}\) are independent, so that Claim 7 implies that for all \(2 \leq k \leq \frac{n}{v}\), \[\begin{align} \mathbb{P}\left( \mathrm{Fr}_n^{>v}(\mathrm{pa}(v)) + \mathrm{Fr}_n^{>v}(v) = k \;\big|\; \mathcal{E}\right) & = \mathbb{P}\left( \mathrm{Fr}_n^{>v}(\mathrm{pa}(v)) + \mathrm{Fr}_n^{>v}(v) = k \right) \\ & = \mathbb{P}\left( \mathrm{BetaBin}(n-v,2,v-2) = k - 2 \right) \geq c_{\mathrm{B}} (k-2) \frac{v^2}{n^2} , \end{align}\] where we used ?? for the last inequality. Further, conditioned on \(\left\{\mathrm{Fr}_n^{>v}(\mathrm{pa}(v)) + \mathrm{Fr}_n^{>v}(v) = k , \mathcal{E}\right\}\), \(\mathrm{Fr}_n^{>v}(v)\) is still uniformly distributed on \(\{1,\ldots,k-1\}\). Thus, for all \(k=1,\ldots,\lfloor s \left(\frac{n}{v}\right)^2 \rfloor\), \[\begin{align} & \mathbb{P}\left( \mathrm{Fr}_n^{>v}(v) k \leq s \left(\frac{n}{v}\right)^2 \;\Big|\; \mathcal{E}, \mathrm{Fr}_n^{>v}(\mathrm{pa}(v)) + \mathrm{Fr}_n^{>v}(v) = k \right) \\ &= \mathbb{P}\left( \mathrm{Fr}_n^{>v}(v) \leq \frac{s}{k} \left(\frac{n}{v}\right)^2 \;\Big|\; \mathcal{E}, \mathrm{Fr}_n^{>v}(\mathrm{pa}(v)) + \mathrm{Fr}_n^{>v}(v) = k \right) \\ &= \frac{\lfloor \frac{s}{k} \left(\frac{n}{v}\right)^2 \rfloor}{k-1} \geq \frac{1}{2} \frac{s}{k^2} \left(\frac{n}{v}\right)^2 . \end{align}\] Inserting the two previous inequalities into 62 , we get that \[\begin{align} \mathbb{P}\left( \mathrm{Fr}_n(v) \mathrm{Fr}_n(\mathrm{pa}(v)) \leq s \left(\frac{n}{v}\right)^2 \right) &\geq \frac{1}{2} \sum_{k=3}^{ \lfloor s \left(\frac{n}{v}\right)^2 \wedge \frac{n}{v} \rfloor} c_{\mathrm{B}} (k-2) \frac{v^2}{n^2} \frac{1}{2} \frac{s}{k^2} \left(\frac{n}{v}\right)^2 \notag \\ &= \frac{s c_{\mathrm{B}} }{4} \sum_{k=3}^{ \lfloor s \left(\frac{n}{v}\right)^2 \wedge \frac{n}{v} \rfloor} \frac{k-2}{k^2} \geq c^\star s \log \left( s \left(\frac{n}{v}\right)^2 \wedge \frac{n}{v} \right),\label{eq:almost32there} \end{align}\tag{63}\] where \(c^\star > 0\) is a positive constant. Using that \(s \geq \left(\frac{v}{n}\right)^{2-\varepsilon}\), we see that \[\begin{align} \log \left( s \left(\frac{n}{v}\right)^2 \wedge \frac{n}{v} \right) & = \mathbb{1}_{\left(\frac{v}{n}\right)^{2-\varepsilon} \leq s \leq \frac{v}{n}} \log \left( s \left(\frac{n}{v}\right)^2 \right) + \mathbb{1}_{s > \frac{v}{n}} \log \left( \frac{n}{v} \right) \\ & \geq \mathbb{1}_{\left(\frac{v}{n}\right)^{2-\varepsilon} \leq s \leq \frac{v}{n}} \log \left( \left(\frac{n}{v}\right)^\varepsilon\right) + \mathbb{1}_{s > \frac{v}{n}} \log \left( \frac{1}{s} \right) \\ & \geq \mathbb{1}_{\left(\frac{v}{n}\right)^{2-\varepsilon} \leq s \leq \frac{v}{n}} \frac{\varepsilon}{2-\varepsilon} \log \left( \frac{1}{s} \right) + \mathbb{1}_{s > \frac{v}{n}} \log \left( \frac{1}{s} \right) \geq \frac{\varepsilon}{2} \log \left( \frac{1}{s} \right), \end{align}\] and inserting this into 63 finishes the proof of 25 .

To prove 26 , it suffices to consider \(s\) with \(3 (v/n)^2 \leq s \leq v/n\). From 63 , we see that \[\mathbb{P}\left( \mathrm{Fr}_n(v) \mathrm{Fr}_n(\mathrm{pa}(v)) \leq s \left(\frac{n}{v}\right)^2 \right) \geq \frac{s c_{\mathrm{B}} }{4} \sum_{k=3}^{ \lfloor s \left(\frac{n}{v}\right)^2 \wedge \frac{n}{v} \rfloor} \frac{k-2}{k^2} \geq \frac{s c_{\mathrm{B}} }{12} \sum_{k=3}^{ \lfloor s \left(\frac{n}{v}\right)^2 \rfloor} \frac{1}{k} \geq \frac{c_{\mathrm{B}} }{36} s .\qedhere\] ◻

Proof of Claim 7. Writing \(B(x,y)=\frac{(x-1)!(y-1)!}{(x+y-1)!}\) for the Beta function, we get that \[\nonumber \begin{align} \mathbb{P}\left( \mathrm{BetaBin}(n-v,2,v-2) = k \right) & = \binom{n-v}{k}\frac{B(k+2, n-(k+2))}{B(2, v-2)} \\ &= \frac{(n-v)!}{k!(n-v-k)!} \frac{(k+1)!(n-k-3)!}{(n-1)!} \frac{(v-1)!}{(v-3)!1!} \\ & = \frac{(k+1)(v-1)(v-2)}{(n-1)(n-2)} \frac{(n-v)!}{(n-v-k)!} \frac{(n-3-k)!}{(n-3)!}. \end{align}\] For the first term in the above product, we have, since \(v\geq 3\), that \[\frac{(k+1)(v-1)(v-2)}{(n-1)(n-2)} \geq \frac{k(v-1)(v-2)}{n^2} \geq \frac{k v^2}{6 n^2}.\] To bound the remaining terms, assume first that \(v \geq k\). Using that \(\frac{2v}{n}\leq \frac{1}{2}\) and the elementary inequality \(1-x\geq \exp(-2x)\) for \(x \in \left[ 0, \frac{1}{2} \right]\), we get that \[\begin{gather} \frac{(n-v)!}{(n-v-k)!} \frac{(n-3-k)!}{(n-3)!} = \prod_{j=0}^{k-1} \frac{n-v-j}{n-3-j} \geq \prod_{j=0}^{k-1} \frac{n-v-k}{n} \geq \left( \frac{n-2v}{n} \right)^k \\ = \left( 1 - \frac{2v}{n} \right)^k \geq \exp \left( - \frac{4kv}{n} \right) \geq \exp\left( -4 \right), \end{gather}\] where we used that \(k \leq \frac{n}{v}\) for the last inequality. Similarly, for \(v < k\) we get that \[\begin{gather} \frac{(n-v)!}{(n-v-k)!} \frac{(n-3-k)!}{(n-3)!} = \frac{(n-v)!}{(n-3)!} \frac{(n-3-k)!}{(n-v-k)!} = \prod_{j=0}^{v-4} \frac{n-3-k-j}{n-3-j} \\ \geq \prod_{j=0}^{v-4} \frac{n-v-k}{n} \geq \left( \frac{n-2k}{n} \right)^v = \left( 1 - \frac{2k}{n} \right)^v \geq \exp \left( - \frac{4kv}{n} \right) \geq \exp\left( -4 \right). \end{gather}\] Combining the three previous inequalities, we get that \[\mathbb{P}\left( \mathrm{BetaBin}(n-v,2,v-2) = k \right) \geq \frac{e^{-4}}{6} k \frac{v^2}{n^2} ,\] proving the claim. ◻

Proof. Fix some \(n\geq3\), \(v\geq 2\) and \(1\leq k \leq n-v+1\). Then, we use that, for \(v\geq 2\), \[\mathbb{P}\left(\mathrm{Fr}_n(v)=k\right) = (v-1) \frac{(n-v)!}{(n-1)!}\frac{(n-k-1)!}{(n-v-k+1)!} = \frac{v-1}{n-1}\prod_{j=0}^{k-2}\frac{n-v-j}{n-2-j}\leq \frac{v-1}{n-1}\left( \frac{n-v}{n-2}\right)^{k-1},\] as the factors are decreasing in \(j\). Using that \(\tfrac{v-1}{n-1}\leq 2v/n\), that \((\tfrac{n}{n-2})^{k-1}\leq (\tfrac{n}{n-2})^{n-2} \leq e^2\), that \(\log(1-v/n)\leq -v/n\), and that \(\exp(-(k-1)v/n)\leq \exp(1-kv/n)\), we get \[\begin{align} &\notag \frac{v-1}{n-1}\le 2v/n, \qquad \text{ and } \\ &\label{eq:k} \left( \frac{n-v}{n-2}\right)^{k-1}=\left( 1-\frac{v-2}{n-2}\right)^{k-1} \leq \exp\left(-(k-1)\frac{v-2}{n-2}\right) \leq \exp\bigg(2-k\frac{v}{n}\bigg), \end{align}\tag{64}\] where the last inequality holds since \(1 \leq k \leq n-v+1\) and \(v \geq 2\): indeed, since the two functions \(k \mapsto \tfrac{-(k-1)(v-1)}{n-1}\) and \(k \mapsto 2-\tfrac{kv}{n}\) are linear in \(k\), it suffices to prove the inequality for \(k=1\) and for \(k=n-v+1\). The statement for \(k=1\) is clear, since \(v\leq n\). For \(k=n-v+1\), the statement is equivalent to \[\label{eq:h} (n-v+1) \frac{v}{n}- (n-v)\frac{v-2}{n-2}-2 = \frac{-3nv+2v^{2}-2v+4n}{n\left(n-2\right)} \leq 0.\tag{65}\] The function \(h(v) \mathrel{\vcenter{:}}= -3nv+2v^{2}-2v+4n\) is convex, so that the maximum in the domain \([2,n]\) is attained at one of the boundary values. One readily checks that \(h(2),h(n) \leq 0\), so that \(h(v)\leq 0\) for all \(v\in [2,n]\), implying 65 and thus also 64 . Because 27 is also trivially true for \(k>n-v+1\), these bounds yield 27 .

For the proof of 28 , it suffices to consider \(t > 2\), and thus also for \(v\geq 3\), since the probability of the event on the left-hand side of 28 equals zero for \(v=2, t>2\). Further, the statement is clear when \(t\tfrac{n}{v} > n-v+1\). Using the previously established bound on \(\mathbb{P}(\mathrm{Fr}_n(v)=k)\), we obtain for \(v\ge 3\), \[\begin{gather} \mathbb{P}\left(\mathrm{Fr}_n(v)\geq t\frac{n}{v} \right) \leq \frac{v-1}{n-1}\sum_{k\geq t\tfrac{n}{v} }\bigg(\frac{n-v}{n-2}\bigg)^{k-1} \le \frac{v-1}{n-1}\frac{n-2}{v-2}\bigg(\frac{n-v}{n-2}\bigg)^{t(n/v)-1} \\ \le \frac{v-1}{v-2} \bigg(\frac{n-v}{n-2}\bigg)^{t(n/v)-1} \le 2 \bigg(\frac{n-v}{n-2}\bigg)^{t(n/v)-1} \le 2e^2\exp\left(-t\right). \end{gather}\] In the last inequality, we used that \((\tfrac{n-v}{n-2})^{t(n/v)-1} \leq \exp(2-t\tfrac{n}{v}\tfrac{v}{n})\) for \(t\tfrac{n}{v} \leq n-v+1\), as proven in inequality 64 . This proves 28 for \(v\ge 3\).

We next prove 29 . We use the de-Finetti representation of the Beta-Binomial distribution and see that \[\begin{align} \mathbb{P}\left( \mathrm{Fr}_n(v) > t \frac{n}{v} \right) & \notag = \int_{0}^{1} \mathbb{P}\left( \mathrm{Bin}(n-v,p) + 1 > t \frac{n}{v} \right)(v-1)(1-p)^{v-2} \mathrm{d}p \\ & \label{eq:definetti} \geq \int_{\frac{4t}{v}}^{1} \mathbb{P}\left( \mathrm{Bin}\left( \Big\lceil\frac{n}{2}\Big\rceil ,p\right) \geq t \frac{n}{v} \right)(v-1)(1-p)^{v-2} \mathrm{d}p . \end{align}\tag{66}\] First, observe that for a Binomial random variable \(X_p\) with parameters \(\lceil \frac{n}{2} \rceil\) and \(p \geq \frac{4t}{v}\), one has \[\begin{align} \mathrm{Var}(X_p) \leq \mathbb{E}\left[ X_p \right] \quad \text{ and } \quad \mathbb{E}\left[ X_p \right] = \Big\lceil \frac{n}{2} \Big\rceil p \geq \frac{n}{2} \frac{4 t}{v} = 2t \frac{n}{v} \geq 4, \end{align}\] where the last inequality holds since \(v \leq \tfrac{n}{2}, t \geq 1\). Combining these facts with Cantelli’s inequality, we get that \[\begin{gather} \mathbb{P}\left( \mathrm{Bin}\left( \Big\lceil\frac{n}{2}\Big\rceil ,p\right) \geq t \frac{n}{v} \right) \geq \mathbb{P}\left( X_p \geq \frac{\mathbb{E}\left[X_p\right]}{2} \right) \geq 1 - \frac{\mathrm{Var}(X_p)}{\mathrm{Var}(X_p) + \mathbb{E}\left[X_p\right]^2/4 } \\ = \frac{\mathbb{E}\left[ X_p \right]^2/4}{\mathrm{Var}(X_p) + \mathbb{E}\left[ X_p \right]^2/4} \geq \frac{\mathbb{E}\left[ X_p \right]^2/4}{\mathbb{E}\left[ X_p \right] + \mathbb{E}\left[ X_p \right]^2/4} = \frac{\mathbb{E}\left[ X_p \right]/4}{1+\mathbb{E}\left[ X_p \right]/4} \geq \frac{1}{2} . \end{gather}\] Inserting this bound into 66 yields that \[\begin{align} \mathbb{P}\left( \mathrm{Fr}_n(v) > t \frac{n}{v} \right) &\geq \int_{\frac{4t}{v}}^{1} \mathbb{P}\left( \mathrm{Bin}\left( \Big\lceil\frac{n}{2}\Big\rceil ,p\right) \geq t \frac{n}{v} \right)(v-1)(1-p)^{v-2} \mathrm{d}p \\ &\geq \frac{1}{2} \int_{\frac{4t}{v}}^{1}(v-1)(1-p)^{v-2} \mathrm{d}p \\ &= \frac{1}{2} \left( 1- \frac{4t}{v} \right)^{v-1} \geq \frac{1}{2} \exp\left( - \frac{8t}{v} \right)^{v-1} \geq \frac{1}{2} \exp\left( - 8t \right), \end{align}\] where we used the elementary inequality \(1-x \geq e^{-2x}\) for all \(x \in \left[0,\frac{1}{2} \right]\) in the last line. This finishes the proof of 29 .

For the proof of inequality 30 , we start by decomposing on the event \(\{\mathrm{Fr}_n(v)\geq t n/(2v)\}\) and its complement, i.e., \[\begin{align} \mathbb{P}\left( \mathrm{Fr}_n(\mathrm{pa}(v))\geq t \frac{n}{v} \right) \leq \mathbb{P}\left( \mathrm{Fr}_n(v)\geq \frac{t}{2} \frac{n}{v} \right) + \mathbb{P}\left( \mathrm{Fr}_n(\mathrm{pa}(v))\geq t \frac{n}{v}, \;\mathrm{Fr}_n(v)\leq t \frac{n}{2v} \right). \end{align}\] For the first summand in the above sum, we use inequality 28 with \(t/2\). Using further that \(\mathrm{pa}(v)\) is uniformly distributed on \([v-1]\) on the second summand, we obtain \[\label{eq:split32law32of32total32prob}\mathbb{P}\left( \mathrm{Fr}_n(\mathrm{pa}(v))\geq t \frac{n}{v} \right) \leq 2e^{-t/2 + 2} + \frac{1}{v-1}\sum_{i=1}^{v-1} \mathbb{P}\left( \mathrm{Fr}_n(i)\geq t \frac{n}{v}, \; \mathrm{Fr}_n(v)\leq t \frac{n}{2v} \;\Big| \;\mathrm{pa}(v)=i \right).\tag{67}\] If \(\mathrm{pa}(v)=i\) and \(\mathrm{Fr}_n(v)\leq t \frac{n}{2v}\), then the subtree \((T,1)_{i\downarrow}\setminus(T,1)_{v\downarrow}\) must have at least \(t \frac{n}{2v}\) elements for \(\mathrm{Fr}_n(i)\) to exceed \(t \frac{n}{v}\). So,

\[\begin{align} \mathbb{P}\left( \mathrm{Fr}_n(i)\geq t \frac{n}{v} , \mathrm{Fr}_n(v)\leq t \frac{n}{2v} \;\Big| \;\mathrm{pa}(v)=i \right) & \leq \mathbb{P}\left( \big|(T,1)_{i\downarrow}\setminus (T,1)_{v\downarrow}|\geq t \frac{n}{2v} \;\Big| \;\mathrm{pa}(v)=i\right). \end{align}\] One can couple a RRT and a RRT conditioned on \(\{\mathrm{pa}(v)=i\}\) by grafting \(v\) and its subtree at \(i\). Doing so, it is direct that \(|(T,1)_{i\downarrow}\setminus (T,1)_{v\downarrow}|\) conditioned on \(\mathrm{pa}(v)=i\) is stochastically dominated by \(\mathrm{Fr}_n(i)\). So,

\[\begin{gather} \mathbb{P}\left( \mathrm{Fr}_n(i)\geq t \frac{n}{v}, \mathrm{Fr}_n(v)\leq t \frac{n}{2v} \;\Big| \; \mathrm{pa}(v)=i \right) \\ \leq \mathbb{P}\left( |(T,1)_{i\downarrow}\setminus (T,1)_{v\downarrow}| \geq t \frac{n}{2v} \;\Big| \;\mathrm{pa}(v)=i \right) \leq \mathbb{P}\left( \mathrm{Fr}_n(i)\geq t \frac{n}{2v} \right). \end{gather}\] Inserting this inequality into 67 and using 28 , we get \[\begin{align} \mathbb{P}\left( \mathrm{Fr}_n(\mathrm{pa}(v))\geq t \frac{n}{v} \right) & \leq 2e^{-t/2 + 2} + \frac{1}{v-1}\sum_{i=1}^{v-1} \mathbb{P}\left( \mathrm{Fr}_n(i)\geq t \frac{n}{2v} \right) \\ & = 2e^{-t/2 + 2} + \frac{1}{v-1}\sum_{i=1}^{v-1} \mathbb{P}\left( \mathrm{Fr}_n(i)\geq i \frac{t}{2v} \frac{n}{i} \right) \\ & \leq 2e^{-t/2+2} + \frac{1}{v-1} \sum_{i=1}^{v-1} 2\exp\left(-i \frac{t}{2v}+2\right) \\ & \leq 2e^{-t/2+2} + \frac{2 e^2}{v-1} \sum_{i=1}^{\infty} \exp\left(-i \frac{t}{2v}\right) \\ & = 2e^{-t/2+2} + \frac{2 e^2}{v-1} \frac{1}{\exp(t/(2v))-1} \leq 2e^{-t/2+2} + \frac{2 e^2}{v-1} \frac{2v}{t}, \end{align}\] where we used the elementary inequality \(\exp(t/(2v))-1 \geq t/(2v)\) for the last inequality. The bound 30 follows. Inequality 31 follows from an application of 30 with \(t=\frac{v}{2}\). ◻

Proof. We start by treating the cases \(v=1,2\). Using that \(\phi_n^{\scriptscriptstyle{({2}})}(v)\le \mathrm{Fr}_n(\mathrm{pa}(v))\mathrm{Fr}_n(v)\) at \(v=2\) yields

\[\mathbb{P}\Big(\phi_n^{\scriptscriptstyle{({2}})}(v) \ge S\left(\frac{n}{v}\right)^2 \Big) \le \mathbb{P}\Big( \mathrm{Fr}_n(1)\mathrm{Fr}_n(2) \geq S\frac{n^2}{4}\Big) \overset{ \eqref{eq:proba95fringe-large}}{\leq} 2e^2 e^{-S/2} \leq \frac{C}{S}\] for some positive constant \(C\). For \(v=1\) it suffices to use that \(\phi_n^{\scriptscriptstyle{({2}})}(1)\) and \(\phi_n^{\scriptscriptstyle{({2}})}(2)\) are identically distributed, leading to

\[\mathbb{P}\Big(\phi_n^{\scriptscriptstyle{({2}})}(1) \ge S\left(\frac{n}{1}\right)^2 \Big) = \mathbb{P}\Big(\phi_n^{\scriptscriptstyle{({2}})}(2) \ge 4S\left(\frac{n}{2}\right)^2 \Big) \leq \frac{C}{4S},\] concluding the proof of the lemma for \(v=1,2\). For \(v\in [3,n]\), we write for any \(u\in [v-1]\) \[\mathrm{Fr}_n^{\neq v}(u) \mathrel{\vcenter{:}}= \mathrm{Fr}_n(u) - \mathrm{Fr}_n(v) \mathbb{1}_{v \in (T_n,1)_{u\downarrow}}\] for the number of vertices in the fringe tree of \(u\) that are not contained in the fringe tree of \(v\). In particular, for \(\mathrm{pa}(v)\) one has that \[\mathrm{Fr}_n(\mathrm{pa}(v)) = \mathrm{Fr}_n^{\neq v}(\mathrm{pa}(v)) + \mathrm{Fr}_n(v).\] This directly implies that \[\phi_n^{\scriptscriptstyle{({2}})}(v)\le \mathrm{Fr}_n(\mathrm{pa}(v))\mathrm{Fr}_n(v) = \mathrm{Fr}_n^{\neq v}(\mathrm{pa}(v)) \mathrm{Fr}_n(v) + \mathrm{Fr}_n(v)^2 .\] Thus we get that \[\begin{align} \label{eq:Two32terms32S472} \mathbb{P}\left( \phi_n^{{\scriptscriptstyle{({2}})}}(v) \geq S \left( \frac{n}{v} \right)^2 \right) \leq \mathbb{P}\left( \mathrm{Fr}_n^{\neq v}(\mathrm{pa}(v)) \mathrm{Fr}_n(v) \geq \frac{S}{2} \left( \frac{n}{v} \right)^2 \right) + \mathbb{P}\left( \mathrm{Fr}_n(v)^2 \geq \frac{S}{2} \left( \frac{n}{v} \right)^2 \right). \end{align}\tag{68}\] By 28 , there exists a constant \(C^\prime < \infty\) so that \(\mathbb{E}\left[ \mathrm{Fr}_n(v)^2 \right] \leq C^\prime (n/v)^2\) for all \(n\in \mathbb{N}, v \in [n]\). Markov’s inequality thus implies that \[\label{eq:Two32terms32S47232term321} \mathbb{P}\left( \mathrm{Fr}_n(v)^2 \geq \frac{S}{2} \left( \frac{n}{v} \right)^2 \right) \leq \frac{\mathbb{E}\left[ \mathrm{Fr}_n(v)^2 \right]}{\frac{S}{2} \left( \frac{n}{v} \right)^2} \leq \frac{2 C^\prime}{S} .\tag{69}\] For the first term in 68 , we use the law of total probability to get that. \[\begin{align} \label{parent32switch} & \mathbb{P}\left( \mathrm{Fr}_n^{\neq v}(\mathrm{pa}(v)) \mathrm{Fr}_n(v) \geq \frac{S}{2} \left( \frac{n}{v} \right)^2 \right) = \frac{1}{v-1} \sum_{u=1}^{v-1} \mathbb{P}\left( \mathrm{Fr}_n^{\neq v}(u) \mathrm{Fr}_n(v) \geq \frac{S}{2} \left( \frac{n}{v} \right)^2\;\Big|\;\mathrm{pa}(v)=u \right). \end{align}\tag{70}\] For fixed \(u\in [v-1]\), the random variable \(\mathrm{Fr}_n^{\neq v}(u) \mathrm{Fr}_n(v)\) is independent of \(\mathrm{pa}(v)\). Indeed, both \(\mathrm{Fr}_n(v)\) and \(\mathrm{Fr}_n^{\neq v}(u)\) are determined by \(\left( \mathrm{pa}(w) ; w \in [n] \setminus \{v\} \right)\). Further, the random variables \(\mathrm{Fr}_n^{\neq v}(u)\) and \(\mathrm{Fr}_n(v)\) are negatively associated. Indeed, conditioned on \(\mathrm{Fr}_n(v)=k\), the tree \(T_n \setminus (T_n,1)_{v \downarrow}\) is just distributed like a uniform attachment tree of size \(n-k\). Thus, we see that \[\begin{align} & \mathbb{P}\left( \mathrm{Fr}_n^{\neq v}(u) \mathrm{Fr}_n(v) \geq \frac{S}{2} \left( \frac{n}{v} \right)^2\;\Big|\;\mathrm{pa}(v)=u \right) \\ & = \mathbb{P}\left( \mathrm{Fr}_n^{\neq v}(u) \mathrm{Fr}_n(v) \geq \frac{S}{2} \left( \frac{n}{v} \right)^2 \right) \\ & \leq \mathbb{P}\left( \mathrm{Fr}_n^{\neq v}(u) \geq \frac{S}{2} \frac{n}{v} \right) + \sum_{\ell=0}^{\infty} \mathbb{P}\left( \mathrm{Fr}_n(v) \geq 2^{\ell} \frac{n}{v}, \mathrm{Fr}_n^{\neq v}(u) \geq \frac{S}{4} 2^{-\ell} \frac{n}{v} \right) \\ & \leq \mathbb{P}\left( \mathrm{Fr}_n^{\neq v}(u) \geq \frac{S}{2} \frac{n}{v} \right) + \sum_{\ell=0}^{\infty} \mathbb{P}\left( \mathrm{Fr}_n(v) \geq 2^{\ell} \frac{n}{v}\right) \mathbb{P}\left( \mathrm{Fr}_n^{\neq v}(u) \geq \frac{S}{4} 2^{-\ell} \frac{n}{v} \right) \\ & \overset{ \eqref{eq:proba95fringe-large}}{\leq} \mathbb{P}\left( \mathrm{Fr}_n^{\neq v}(u) \geq \frac{S}{2} \frac{n}{v} \right) + \sum_{\ell=0}^{\infty} 2 e^2 \exp\left(-2^\ell\right) \mathbb{P}\left( \mathrm{Fr}_n^{\neq v}(u) \geq \frac{S}{4} 2^{-\ell} \frac{n}{v} \right). \end{align}\] Inserting this into 70 and using again that \(\mathrm{Fr}_n^{\neq v}(u)\) and \(\mathrm{pa}(v)\) are independent, we get that \[\begin{align} & \mathbb{P}\left( \mathrm{Fr}_n^{\neq v}(\mathrm{pa}(v)) \mathrm{Fr}_n(v) \geq \frac{S}{2} \left( \frac{n}{v} \right)^2 \right) \\ & \leq \frac{1}{v-1} \sum_{u=1}^{v-1} \left( \mathbb{P}\left( \mathrm{Fr}_n^{\neq v}(u) \geq \frac{S}{2} \frac{n}{v} \right) + \sum_{\ell=0}^{\infty} 2 e^2 \exp\left(-2^\ell\right) \mathbb{P}\left( \mathrm{Fr}_n^{\neq v}(u) \geq \frac{S}{4} 2^{-\ell} \frac{n}{v} \right) \right) \\ & = \frac{1}{v-1} \sum_{u=1}^{v-1} \mathbb{P}\left( \mathrm{Fr}_n^{\neq v}(u) \geq \frac{S}{2} \frac{n}{v} \;\Big|\; \mathrm{pa}(v)=u \right) \\ &+ \sum_{\ell=0}^{\infty} 2 e^2 \exp\left(-2^\ell\right) \frac{1}{v-1} \sum_{u=1}^{v-1} \mathbb{P}\left( \mathrm{Fr}_n^{\neq v}(u) \geq \frac{S}{4} 2^{-\ell} \frac{n}{v} \;\Big|\; \mathrm{pa}(v)=u \right) \\ & = \mathbb{P}\left( \mathrm{Fr}_n^{\neq v}(\mathrm{pa}(v)) \geq \frac{S}{2} \frac{n}{v} \right) + \sum_{\ell=0}^{\infty} 2 e^2 \exp\left(-2^\ell\right) \mathbb{P}\left( \mathrm{Fr}_n^{\neq v}(\mathrm{pa}(v)) \geq \frac{S}{4} 2^{-\ell} \frac{n}{v} \right) \\ & \leq \mathbb{P}\left( \mathrm{Fr}_n(\mathrm{pa}(v)) \geq \frac{S}{2} \frac{n}{v} \right) + \sum_{\ell=0}^{\infty} 2 e^2 \exp\left(-2^\ell\right) \mathbb{P}\left( \mathrm{Fr}_n(\mathrm{pa}(v)) \geq \frac{S}{4} 2^{-\ell} \frac{n}{v} \right) . \end{align}\] By Lemma [lem:proba95large95fringe], there exists a constant \(C<\infty\) so that \(\mathbb{P}\left( \mathrm{Fr}_n(\mathrm{pa}(v)) \geq tn/v \right) \leq C/t\) for all \(t>0\). Further, let \(C^\star>0\) be a constant so that \(\exp \left(-x\right) \leq C^\star x^{-2}\) for all \(x\geq 1\). Then we get that \[\begin{align} \mathbb{P}\left( \mathrm{Fr}_n^{\neq v}(\mathrm{pa}(v)) \mathrm{Fr}_n(v) \geq \frac{S}{2} \left( \frac{n}{v} \right)^2 \right) &\leq \frac{C}{S/2} + \sum_{\ell=0}^{\infty} 2 e^2 \exp\left(-2^\ell\right) \frac{C}{\frac{S}{4} 2^{-\ell}} \\ &\leq \frac{2C}{S} + \sum_{\ell=0}^{\infty} 2 e^2 C^\star 2^{-2\ell} \frac{4C}{S 2^{-\ell}} \\ &= \frac{2C}{S} + \frac{8 e^2 C^\star C}{S} \sum_{\ell=0}^{\infty} 2^{-\ell} = \frac{2C}{S} + \frac{16 e^2 C^\star C}{S}. \end{align}\] Inserting this inequality and inequality 69 into 68 shows that \[\mathbb{P}\left( \phi_n^{{\scriptscriptstyle{({2}})}}(v) \geq S \left( \frac{n}{v} \right)^2 \right) \leq \frac{2C^\prime}{S} + \frac{2C}{S} + \frac{16 e^2 C^\star C}{S},\] finishing the proof. ◻