Random recursive triangulations of the disk via fragmentation theory (Q653302)

This paper treats an infinite random triangulation of the unit disk that arises as the limit of recursive models. This triangulation is generated by throwing chords randomly in the unit disk and keeping only those chords that do not intersect with previous ones. Throwing infinitely many chords and taking the closure of the resulting set leads to a random compact set whose complement is a countable union of triangles, it is shown that this limiting set has Hausdorff dimension \(\beta^* +1\) \(=\) \((\sqrt{17} -1)/2\) and also a description as the geodesic lamination coded by a random continuous function. Lastly recursive constructions of triangulations of the \(n\)-gon that give rise to the same limit are discussed as well. More precisely, one of the peculiar features in this work consists in the use of fragmentation theory (cf. [\textit{J. Bertoin}, Random fragmentation and coagulation processes. Cambridge: Cambridge Univ. Press (2006; Zbl 1107.60002)]) to study an infinite random triangulation of the unit disk \({\mathbb D}\) that arises as the limit of several recursive models. To make the story short, let us consider a special case for explanation. Take a sequence \(U_1, V_1, U_2, V_2, \dots\) of independent random variables, which are uniformly distributed over the unit circle \({\mathbb S}_1\). \(L_1\) just consists of the chord with endpoints \(U_1\) and \(V_1\), denoted by \([U_1 V_1]\). Then at step \(n+1\), two cases are possible: either the chord \([U_{n+1} V_{n+1}]\) intersects \(L_n\), and set \(L_{n+1}\) \(=\) \(L_n\); or \([ U_{n+1} V_{n+1}]\) does not intersect \(L_n\), and set \(L_{n+1}\) \(=\) \(L_n\) \(\cup\) \([U_{n+1} V_{n+1}]\). Thus, for every integer \(n \geq 1\), \(L_n\) is a disjoint union of random chords. Let \[ L_{\infty}= \overline{ \bigcup_{n=1}^{\infty} L_n } \] be the closure of the increasing union of the sets \(L_n\). The closed set \(L_{\infty}\) is a geodesic lamination (cf. [\textit{F. Bonahon}, Contemp. Math. 269, 1--37 (2001; Zbl 0996.53029)]) of the unit disk. \(L_{\infty}\) can be viewed as an infinite triangulation of the unit disk in the same sense as in [\textit{D. Aldous}, Am. Math. Mon. 101, 223--233 (1994; Zbl 0804.52011)]. \(N(L_n)\) denotes the number of chords in \(L_n\). For every \(x,y \in {\mathbb S}_1\), let \(H_n(x,y)\) be the number of chords in \(L_n\) that intersect the chord \([xy]\). Theorem 1. (i) We have \[ n^{-1/2} N(L_n) \overset \text{a.s.}\longrightarrow \sqrt{\pi} \qquad ( {n} \infty). \] (ii) There exists a random process \(( {\mathcal M}_{\infty}(x), x \in {\mathbb S}_1)\), which is Hölder continuous with exponent \(\beta^* - \varepsilon\), for every \(\varepsilon >0\), such that, for every \(x \in {\mathbb S}_1\), \[ n^{- \beta^* /2} H_n(1, x)\longrightarrow {\mathcal M}_{\infty}(x) \qquad ( n \to \infty) \] in probability. In this paper, the authors prove more general versions of the under (i) and (ii) above-mentioned convergences by using fragmentation theory. Their second theorem shows that the random geodesic lamination \(L_{\infty}\) is coded by the process \({\mathcal M}_{\infty}\). Theorem 2. The random set \(L_{\infty}\) is the union of the chords \([xy]\) for all \(x, y\) \(\in\) \({\mathbb S}_1\) such that \[ {\mathcal M}_{\infty}(x) = {\mathcal M}_{\infty}(y) = \min_{ z \in \text{Arc}(x,y) } {\mathcal M}_{\infty}(z), \quad \text{a.s.} \tag{1} \] Moreover, \(L_{\infty}\) is maximal for the inclusion relation among geodesic laminations. Recall the work done by D. Aldous [loc. cit.], where the case when the coding function is the normalized Brownian excursion was considered. In that case, the Hausdorff dimension of the corresponding lamination is 3/2. This may be compared to the following statement, where \(\dim(A)\) stands for the Hausdorff dimension of a subset \(A\) of the plane. Theorem 3. We have almost surely \[ \dim(L_{\infty}) = \beta^* + 1 = \frac{ \sqrt{17} -1}{2}. \] The next topic is about another derivation of the random set \(L_{\infty}\). As a matter of fact, \(L_{\infty}\) also occurs as the limit in distribution of certain random recursive triangulations of the \(n\)-gon. For every \(n \geq 3\), consider the \(n\)-gon whose vertices are the \(n\)-th roots of unity \(x_k^n=\exp ( 2 i \pi k/n )\), \(k=1,2, \dots, n\). A chord of \({\mathbb S}_1\) is called a diagonal of the \(n\)-gon if its vertices belong to the set \(\{ x_k^n : 1 \leqslant k \leqslant n \}\) and if it is not an edge of the \(n\)-gon. Denote by \({\mathcal D}_n\) the set of all diagonals of the \(n\)-gon. Let \(c_1\) be chosen uniformly at random in \({\mathcal D}_n\). Then, conditionally given \(c_1\), let \(c_2\) be a chord chosen uniformly at random in the set of all chords in \({\mathcal D}_n\) that do not cross \(c_1\). Then, continue by induction and construct a finite sequence of chords \(c_1, c_2,\dots, c_{n-3}\). Actually, for every \(1 < k \leqslant n-3\), \(c_k\) is chosen uniformly at random in the set of all chords in \({\mathcal D}_n\) that do not cross \(c_1, c_2, \dots, c_{k-1}\). Finally, let \(\Lambda_n\) be the union of the chords \(c_1, c_2, \dots, c_{n-3}\). Next, the authors introduce a slightly different model. Let \(\sigma\) be a uniformly distributed random permutation of \(\{ 1,2, \dots, n \}\). A collection of diagonals of the \(n\)-gon is associated with \(\sigma\). Indeed, for every integer \(0 \leqslant k \leqslant n\), define a set \(M_k\) of disjoint diagonals of the \(n\)-gon, and a set \(F_k\) of free vertices. Let them be initially \(M_0=F_0=\emptyset\). Then, at step \(k \in\) \(\{ 1,2, \dots, n \}\), when there is a unique free vertex \(x \in F_{k-1}\) such that \([ x x_{\sigma(k)}^n ]\) is a diagonal of the \(n\)-gon that does not intersect the chords in \(M_{k-1}\), and set \[ M_k = M_{k-1} \cup \{ [ x x_{ \sigma(k)}^n ] \} \qquad \text{and} \qquad F_k = F_{k-1} \setminus \{ x \}. \] Otherwise, i.e., when there is no such vertex, simply define \[ M_k = M_{k-1} \qquad \text{and} \qquad F_k = F_{k-1} \cup \{ x_{ \sigma(k)}^n \}. \] Finally, let \(\tilde{\Lambda}_n\) be the union of the chords in \(M_n\). \textbf{Theorem 4.} We have \[ \Lambda_n \overset {(d)}\longrightarrow L_{\infty} \quad (\text{as} \quad {n} \infty) \qquad \text{and} \qquad \tilde{\Lambda}_n \overset {(d)}\longrightarrow L_{\infty} \quad (\text{as} \quad {n} \infty). \] In both cases, the convergence holds in distribution in the sense of the Hausdorff distance between compact subsets of the closed unit disk \(\bar{\mathbb D}\). \textit{D. D. Sleator, R. E. Tarjan} and \textit{W. P. Thurston} [J. Am. Math. Soc. 1, No. 3, 647--681 (1988; Zbl 0653.51017)] gave a result on triangulations of convex polygons, which is very interesting from the geometric and combinatorial point of view. For the coding of geodesic laminations by continuous functions, see, e.g., [\textit{J.-F. Le Gall} and \textit{F. Paulin}, Geom. Funct. Anal. 18, No. 3, 893--918, (2008; Zbl 1166.60006)].