Topology of random geometric complexes: a survey <s> The Euler characteristic. The Euler characteristic of a simplicial complex <s> 1. Introduction 2. Probabilistic ingredients 3. Subgraph and component counts 4. Typical vertex degrees 5. Geometrical ingredients 6. Maximum degree, cliques and colourings 7. Minimum degree: laws of large numbers 8. Minimum degree: convergence in distribution 9. Percolative ingredients 10. Percolation and the largest component 11. The largest component for a binomial process 12. Ordering and partitioning problems 13. Connectivity and the number of components References Index <s> BIB001 </s> Topology of random geometric complexes: a survey <s> The Euler characteristic. The Euler characteristic of a simplicial complex <s> Recently there has been a lot of interest in geometrically motivated approaches to data analysis in high-dimensional spaces. We consider the case where data are drawn from sampling a probability distribution that has support on or near a submanifold of Euclidean space. We show how to “learn” the homology of the submanifold with high confidence. We discuss an algorithm to do this and provide learning-theoretic complexity bounds. Our bounds are obtained in terms of a condition number that limits the curvature and nearness to self-intersection of the submanifold. We are also able to treat the situation where the data are “noisy” and lie near rather than on the submanifold in question. <s> BIB002 </s> Topology of random geometric complexes: a survey <s> The Euler characteristic. The Euler characteristic of a simplicial complex <s> In this paper, we take a topological view of unsupervised learning. From this point of view, clustering may be interpreted as trying to find the number of connected components of any underlying geometrically structured probability distribution in a certain sense that we will make precise. We construct a geometrically structured probability distribution that seems appropriate for modeling data in very high dimensions. A special case of our construction is the mixture of Gaussians where there is Gaussian noise concentrated around a finite set of points (the means). More generally we consider Gaussian noise concentrated around a low dimensional manifold and discuss how to recover the homology of this underlying geometric core from data that do not lie on it. We show that if the variance of the Gaussian noise is small in a certain sense, then the homology can be learned with high confidence by an algorithm that has a weak (linear) dependence on the ambient dimension. Our algorithm has a natural interpretation as a spectral learning algorithm using a combinatorial Laplacian of a suitable data-derived simplicial complex. <s> BIB003
S has a number of equivalent definitions, and a number of important applications. One of the definitions, via Betti numbers, is Thus, one can think of the Euler characteristic as an integer "summary" of the set of Betti numbers of the complex. In the case of the randomČech complex C(n, r) we have However, using Morse theory for the distance function (see section 5), χ(n, r) can also be computed in the following way The limiting behavior of the critical points presented in Section 5.2, thus leads us to the following conclusion. Corollary 5.2 (Bobrowski-Adler,  ). Let χ(n, r) be the Euler characteristic of C(n, r), and let where γ i (λ) are increasing functions of λ and are defined in  . Note that (4) cannot be proven using only the existing results on Betti numbers, since the values of the limiting mean in the critical regime are not available. This demonstrates one of the advantages of studying the homology of theČech complex via the distance function. An alternative way to compute the Euler characteristic is where ∆ k (r) is the number of k-simplexes in C(n, r). In  the Euler characteristic was studied this way for a uniform distribution on a d-dimensional torus. Computing the mean value (and also the variance) of ∆ k (r) is possible, however there are going to be infinitely summands in this formula, which will make the it highly complicated. Thus, counting critical points is still advantageous. Figure 4 presents the limiting expected Euler characteristic (divided by n) as a function of λ for a uniform distribution on the unit cube in R 3 . In this case the functions γ k (k = 1, 2, 3) were computed explicitly in  ) and are given by - Note that the curve starts at positive values, turns negative and then becomes positive once and for all. In R 3 the formula (3) implies that X = β 0 − β 1 + β 2 . The shapes of the Betti number curves in Figure 2 suggests the conjecture that each of the different Betti numbers becomes dominant in a slightly different regime. A similar phenomenon is known to occur in for certain random abstract simplicial complexes [31], but it is still not known whether this holds for random geometric complexes. The exact setup studied was as follows. Let M ⊂ R d be a m-dimensional smooth closed manifold (compact and without a boundary). Let f : M → R d be a probability density function supported on M. Let X n = {X 1 , . . . , X n } be a set of i.i.d. points generated by f , and let C(n, r) be theČech complex generated by these points (using d-dimensional balls). The results in this case turn out to be very similar to the ones we described earlier, even though the proofs require different analysis tools. In the following we briefly review the results in  and highlight the main difference from the results in R d . In the subcritical regime, the results for both the Betti numbers β i (n, r) and the number of critical points N i (n, r) are almost identical to those presented in Sections 4.1 and 5.2. The main difference is that the ambient dimension d is replaced by the intrinsic dimension m, and the limiting constants are a bit different. For example, we have that These differences stem from the fact that in the subcritical regime the Betti numbers computation is very 'local', and locally, a m-dimensional manifold looks very similar to R m . In the critical regime we also have very similar statements to the Euclidean setup. The main difference in studying manifolds shows up when we study the vanishing of the homology. When studying compact and convex bodies, Theorem 4.12 states that homology completely vanishes when r ∼ log n n . Sampling from a manifold, upon coverage we expect the homology of the complex C(n, r) not to vanish but rather to be equal to the homology of M. This result is stated in the following theorem. Theorem 6.1 (Bobrowski-Mukherjee,  ). Let > 0 be fixed. If Note that if f is a uniform density on a unit volume manifold, then f min = 1, and comparing to Theorem 3.4 we have that the vanishing of H i , i ≥ 1, occurs at a radius which is twice the threshold for connectivity (this comparison is not rigorous since Theorem 3.4 deals with a cube rather than a closed manifolds, but it could be shown that the same holds for manifolds). This phenomenon has a non formal, yet convincing, explanation. In BIB001 (Theorem 13.17) it is shown that at the edge of connectivity the graph G(n, r) consists roughly of a giant component and some isolated vertices. For a vertex to be isolated, a ball of radius r around it has to be vacant (i.e. with no other points in X n inside it). To get all the higher homology groups correctly, we need to guarantee that the balls of radius r/2 (the ones used to construct theČech complex) cover the support. Now, the support is covered if and only if there is no vacant ball of radius r/2. Thus, it seems harder to reach coverage than connectivity, and the vacancy radii involved have the same ratio as the thresholds we presented. The statement in Theorem 6.1 has an important consequence to problems in manifold learning, since it shows that by studyingČech complexes we can recover the homology of an unknown manifold M from a finite (yet probably large) number of random samples. The analysis of this type of "topological manifold learning" was established by the seminal work in BIB002 and BIB003 , and theorem 6.1 can be viewed as an asymptotic and extended version of the main results there. Considering asymptotic behavior has the advantage of covering a more general class of distributions, using fewer assumptions, and requiring fewer samples. to vanish at slightly different radii. The work in  is still in progress, and aims at discovering these exact thresholds. This is an example where studying the critical points for the distance function becomes very useful. We will briefly describe the main ideas here, with the caveat that this is work in progress. First, we denote byN i (n, r) the number of critical points of index i for the distance function d Xn , with a critical value greater than r. Finding the radius at which the critical points vanish (N i (n, r) = 0) would give us an idea of when homology vanishes, since by Morse theory there could not be further changes in homology if there are no critical points for the distance function. In  the distribution studied is uniform on the d-torus, and the following result will be proven. where n = o(log log n), then: (1) If n → −∞ then N i (n, r) = 0 a.a.s. (2) If n → ∞ then N i (n, r) = 0 a.a.s. , the last proposition tells us that ρ i is the vanishing radius for the critical points of index i. Using Morse theory, we can draw some important conclusions from that onβ i (n, r): (1) For radii larger than ρ i no more i-cycles are created, and thereforeβ i (n, r) is decreasing in r. (2) For radii larger than ρ i+1 , we must have thatβ i (n, r) = 0, since there are no more critical points of index i + 1, and those are the ones responsible for terminating the noisy i-cycles. While these conclusions do not provide us with the exact vanishing radius for , we conjecture that it should be somewhere in the range [ρ i , ρ i+1 ].