Topology of random geometric complexes: a survey <s> Connectivity <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> Connectivity <s> In this paper, we study the size of the giant component CG in the random geometric graph G = G(n, rn, f) of n nodes independently distributed each according to a certain density f(.) in [0, 1]2 satisfying infx∈[0,1]2 f(x) > 0. If c1 n ≤ r 2 n ≤ c2 logn n for some positive constants c1, c2 and nr 2 n −→ ∞, we show that the giant component of G contains at least n − o(n) nodes with probability at least 1 − o(1) as n → ∞. We also obtain estimates on the diameter and number of the non-giant components of G. <s> BIB002
The zeroth homology H 0 is generated by the connected components, and its rank β 0 is the number of components. Note the connectivity properties of any simplicial complex depend only on its one-dimensional skeleton, namely the underlying graph. In theČech and Vietoris-Rips complexes C(n, r) and R(n, r) the underlying graph is the random geometric graph G(n, r) described above, and therefore the results related to connectivity are the same for both complexes. The connectivity properties of random geometric graphs were extensively studied in the past, see BIB001 for a comprehensive review. The main purpose of this survey is to review recent results related to higher degrees of homology. For completeness, however, we wish to include a brief review of the key properties related to the connected components. As mentioned above, the limiting behavior splits into three main regimes, depending on the limit of the term nr d . We will correspondingly split the discussion on the limiting results. 3.1. The subcritical regime. The subcritical regime (also known as the 'sparse' or 'dust' regime) is when nr d → 0. In this regime, the graph G(n, r) is very sparse, and mostly disconnected. Therefore, the study of connectivity did not draw much attention in the past. See  for a proof of the following. This statement can be sharpened to a central limit theorem, and a law of large numbers can be proved for deviation from the mean. In fact, as we see in the next section, a central limit theorem and law of large numbers continue, even into the critical regime. 3.2. The critical regime. The critical regime (also known as the 'thermodynamic limit') is when nr d → λ ∈ (0, ∞). In this regime β 0 (n, r) ≈ Cn for some constant C < 1 (depending on λ), so the number of components is still Θ(n), but is significantly lower than in the subcritical regime. The following law of large numbers is proved in section 13.7 of BIB001 . (1) , and The infinite sum in (1) comes from the fact that we need to count the number of components consisting of any possible number of vertices. The limiting expression provided by the theorem is highly intricate, and at this point impossible to evaluate analytically. Nonetheless, as we will discuss later, this theorem provides the only formula available to date for the limit of the Betti numbers in the critical regime. In addition to a law of large numbers, there is also a central limit theorem available. A more geometric view of connectivity is studied in percolation theory. Penrose considered the case where f is a uniform probability density on a d-dimensional unit cube, and nr d → λ. A remarkable fact is that there exists a constant c > 0 depending only on the underlying density function, such that if λ < c then a.a.s. every connected component is of order O(log n), and if λ > c then a.a.s. there is a unique "giant" component on Θ(n) vertices. This sudden change in behavior over a very small shift of parameter is sometimes called a phase transition. In chapters 9 and 10 of BIB001 , Penrose relates percolation on random geometric graphs to more classical continuum percolation theory. In continuum percolation, also called the Gilbert disk model  , one considers a random geometric graph on a unit-intensity uniform Poisson process on R d , and then there is a threshold radius r c > 0 such that for r > r c the random geometric graph has an infinite connected component, and for r < r c every component is finite size. For a deeper study of continuum percolation, see Meester and Roy's book  . Or an introduction and overview of the subject, see Chapter 8 of Bollobas-Riordan [13] or Section 12.10 of Grimmett  . 3.3. The supercritical regime. The supercritical regime is when nr d → ∞. As we will see soon, if the radius is large enough (yet still satisfying r → 0) it can be shown that the graph G(n, r) becomes connected (caveat, this statement depends on the underlying distribution). This phase is sometimes referred to as the 'connected regime'. Arriving from the critical regime where β 0 (n, r) = Θ(n) and ending at the connected regime where β 0 (n, r) = Θ(1), the number of components in G(n, r) should exhibit some kind of a decay within the supercritical regime. To this date only partial information is available about this decay process, and we will present it later. We start by describing the connected regime. In the case of a uniform distribution on the unit Penrose gives a sharp result for the connectivity threshold. See BIB001 , Chapter 13. Theorem 3.4 (Penrose, BIB001 ). Let c ∈ R be fixed, and set In other words, the threshold radius for connectivity is r = It is interesting to contrast Theorem 3.4 with the analogous statement for a standard multivariate normal distribution N (0, I d×d ) in R d , a case which Penrose also studies. Here r must be significantly larger, roughly 1/ √ log n, in order to ensure connectivity. Theorem 3.5 (Penrose, BIB001 ). Let X i ∼ N (0, I d×d ) and c ∈ R be fixed. If as n → ∞. In both cases, letting c → ±∞ gives the correct width of the critical window. Why does the threshold distance r = r(n) have to be so much larger in the Gaussian case? The support of the Gaussian distribution is unbounded, and there are outlier points at distance roughly √ 2 log n. The radius must be large enough just to connect these points to the rest of the graph. The contrast of Theorems 3.4 and 3.5 suggests that whatever we hope to prove about the topology of random geometric complexes will necessarily depend on the underlying distribution. On the other hand, certain theorems in geometric probability are fairly general, and do not depend on the underlying distribution so drastically. For example, if we ask what is the threshold for G(n, r) to contain subgraphs, or what is the expected number of occurrences of a given subgraph in the sparse regime, in some sense the answer does not depend too much on the underlying density function. The following is proved in Chapter 3 of BIB001 . Theorem 3.6 (Penrose, BIB001 ). Let Γ be a finite connected graph on k vertices, and let N Γ count the number of subgraphs isomorphic to Γ in G(n, r), then Note that Theorem 3.6 applies equally well to uniform distribution on [0, 1] d and to Gaussian distributions; there is no assumption that the underlying measure has compact support. It is only the implied constant in the limit that depends on the measure. This constant may be written out explicitly as an integral - where As a rule of thumb, one might expect that global properties such as connectivity depend very delicately on the underlying probability measure. Local properties, such as subgraph counts or behavior in the subcritical regime, do not depend so much on the underlying measure. To conclude this section, we mention a recent result about the supercritical regime preceding connectivity. As mentioned above, there is a huge gap remaining between the critical regime where β 0 (n, r) = Θ(n) and the connectivity point where β 0 (n, r) = Θ(1). Recent work by Ganesan studies the decay in the number of components within the super critical regime, in the case d = 2. The assumption is that the underlying probabilty measure on [0, 1] 2 is supported on a measurable density function f , and that f is bounded above and below. The following is Theorem 1 in BIB002 . Theorem 3.7 (Ganesan, BIB002 ). There exists C > 0, such that if A ≤ nr 2 ≤ B log n, then a.a.s. where the constants A and B depend only on the density function f . We will see an analogue of this theorem for higher Betti numbers of a random Vietoris-Rips complex in the following section.