Homological percolation and the Euler characteristic

In this paper we study the connection between the zeros of the expected Euler characteristic curve and the phenomenon which we refer to as homological percolation—the formation of “giant” cycles in persistent homology, which is intimately related to classical notions of percolation. We perform an experimental study that covers four different models: site percolation on the cubical and permutahedral lattices, the Poisson-Boolean model, and Gaussian random fields. All the models are generated on the flat torus ${\mathbb{T}}^d$ for $d=2,3,4$. The simulation results strongly indicate that the zeros of the expected Euler characteristic curve approximate the critical values for homological percolation. Our results also provide some insight about the approximation error. Further study of this connection could have powerful implications both in the study of percolation theory and in the field of topological data analysis.

Figure 1

Persistent homology for a point sample on the two-dimensional flat torus (a unit box with periodic boundary conditions). (a) A set of 50 points $\mathcal{X}$ sampled from the flat torus. The filtration $X_t$ taken here is the union of balls of radius $t$ around the points. We increase $t$ from 0 to $\infty$ and calculate ${PH}_1$. (b) The barcode for ${PH}_1$. Each 1-cycle is represented by a bar, where the endpoints are the radii in which the cycle was formed and filled in (birth, death). The two red bars (bottom two with arrows) correspond to the two cycles in the torus (“the giant cycles”) while the blue ones are considered as “noise”. (c) The persistence diagram for ${PH}_1$. Here the $(birth,death)$ pairs are plotted as points in the plane. Two points are far away from the diagonal (shown by the vertical red dashed line), representing the true nontrivial or giant cycles of the torus. This figure was generated using the GUDHI package [10].

Figure 2

Example of simple topological spaces with their Betti numbers. From left to right: a disk, a circle, a two-dimensional sphere, and a two-dimensional torus. For the torus, we marked the two 1-cycles in dashed lines.

Figure 3

The emergence of the giant 1-cycles in two dimensions for (a) the cubical site model $Q(n,p)$ with ($n=2500, p=0.43$), (b) the permutahedral site model $P(n,p)$ with $(n=1024,p=\frac{1}{2})$, (c) Poisson-Boolean model $B(n,\lambda )$ with ($n=500$), and (d) the GRF model $G\left(\alpha \right)$ (computed on a $512\times 512$ grid). The red and green lines mark the two giant 1-cycles (recall the period boundary gluing). Note in $P(n,p)$ that only one giant cycle has appeared and that it is the sum of the two “obvious” giant cycles. [(d)–(g)] ${PH}_1$ for the corresponding models with the red vertical lines mark the birth times of the giant 1-cycles. [(h)–(l)] The persistence diagrams for the corresponding models for $d=4$. In this case we have homology in degrees $k=1,2,3$ (which alternatively dominate from left to right in increasing order of dimension). The vertical lines mark the birth times of the giant $k$-cycles. The relevant scale parameter is $n=65536$ for $Q(n,p), P(n,p)$, as well as the grid size for the GRF model. For $B(n,\lambda ), n=5000$.

Figure 4

The expected EC curve and the giant cycles. In each plot we draw the expected EC curve (solid line), along with the birth time of the first giant $k$-cycle for $k=1,...,d-1$ (dots). We simulated all the models on the $d$-dimensional torus, for $d=2,3,4$ (from left to right). [(a)–(c)] The random cubical complex. [(d)–(f)] The random permutahedral complex. [(g)–(i)] The Boolean model. [(j)–(l)] The Gaussian random field.

Figure 5

Statistics for the birth time of the giant $k$-cycles. For each model we repeated the simulations in order to estimate the mean and variance of the birth time of the first giant $k$-cycle. In each figure the $x$ axis is $lnn$, and the $y$ axis represent the parameter value ($p,\lambda ,$ or $\alpha$). The dots represent the mean value estimate, and the bars around them follows the standard deviation. The horizontal lines mark the corresponding zeros of the EC curve. [(a)–(c)] The random cubical complex. [(d)–(f)] The random permutahedral complex. [(g)–(i)] The Boolean model. [(j)–(l)] The Gaussian random field.

Figure 6

Appearance of giant cycles vs. zeros of the expected EC curve. The $x$ coordinate of each point is the corresponding zero of the expected EC curve, and the $y$ coordinate is the value when a giant $k$-cycle appears. (a) Cubical site model; (b) permutahedral site model; (c) Gaussian random field; (d) Poisson-Boolean.

Figure 7

The empirical (average) Betti curves and the giant cycles. In each plot, we draw the Betti curves (solid line), along with the birth time of the first giant $k$-cycle for $k=1,...,d-1$. We simulated all the models on the $d$-dimensional torus, for $d=2,3,4$ (from left to right). [(a)–(c)] The random cubical complex. [(d)–(f)] The random permutahedral complex. [(g)–(i)] The Boolean model. [(j)–(l)] The Gaussian random field.

Figure 8

Appearance of giant cycles vs. emerging of the Betti numbers. The $x$ coordinate of each point corresponds to the appearance time of the $k\mathrm{th}$ giant cycle, while the $y$ axis is the time at which the equality ${\beta }_i={\beta }_{i-1}$ occurs. The plots provide strong experimental evidence that the appearance of higher-dimensional cycles occurs in the vicinity of this equality. (a) Cubical site model; (b) permutahedral site model; (c) Gaussian random field; (d) Poisson-Boolean.

Figure 9

An example of a failure of symmetry for the cubical complex. The dark squares indicate open sites. The complement of the open sites is different (bottom right) than the union closed sites. In particular, the latter is connected (via the point in the middle), while the former is not.