Maximally persistent cycles in random geometric complexes Joint work with Omer Bobrowski and Primoz Skraba Motivation The probabilistic method provides existence proofs. The probabilistic method provides existence proofs. 1. Ramsey theory 2. Expander graphs 3. Metric geometry 4. Geometric group theory The probabilistic method provides existence proofs. 1. Ramsey theory 2. Expander graphs 3. Metric geometry 4. Geometric group theory The probabilistic method provides existence proofs. 1. Ramsey theory 2. Expander graphs 3. Metric geometry 4. Geometric group theory The probabilistic method provides existence proofs. 1. Ramsey theory 2. Expander graphs 3. Metric geometry 4. Geometric group theory Randomness models natural phenomena. Randomness models natural phenomena. 1. Physics—black holes, quantum gravity, material science. 2. Mathematics—what does a typical object look like? 3. Statistics—often the null hypothesis is that the data is random. Randomness models natural phenomena. 1. Physics—black holes, quantum gravity, material science. 2. Mathematics—what does a typical object look like? 3. Statistics—often the null hypothesis is that the data is random. Randomness models natural phenomena. 1. Physics—black holes, quantum gravity, material science. 2. Mathematics—what does a typical object look like? 3. Statistics—often the null hypothesis is that the data is random. Random geometric graphs Definition. The random geometric graph G(n, r) has as its vertices n points chosen i.i.d. in Rd , according to some probability distribution. Two vertices are adjacent if they are within distance r. Usually r = r(n) and n ! 1. Proposition. Consider n points chosen i.i.d. uniformly in the unit square [0, 1]2 . If r ⌧ n 3/4 then with high probability G(n; r) contains no triangles. If r 3/4 then with high probability G(n; r) contains many triangles. n Sketch of proof. E [# triangles] ✓ ◆ n = P [{x, y, z} form a triangle] 3 ✓ ◆ n = P [x ⇠ y and y ⇠ z and z ⇠ x] 3 ✓ ◆ n = P [x ⇠ y] P [y ⇠ z] P [z ⇠ x | x ⇠ y and y ⇠ z] 3 ⇣ n3 r 4 Proposition. (Gilbert, Penrose, etc.) Let G1 be the number of vertices in the largest connected component of G(n; r). There exists a constant c⇤ with the following property. If r pc n and c < c⇤ , then w.h.p. G1 = O(log n) If r pc n and c > c⇤ , then w.h.p. G1 = ⌦(n) Random geometric complexes Random geometric graphs can be extended to random geometric complexes, via either ˇ the Vietoris–Rips or Cech constructions. Proposition. Consider n points chosen i.i.d. uniformly in the unit square [0, 1]2 . If r ⌧ n If r If n 3/4 then w.h.p. H1 (C(n, r)) = 0. log n/n then w.h.p. H1 (C(n, r)) = 0. 3/4 ⌧ r ⌧ log n/n then w.h.p. H1 (C(n, r)) 6= 0. Proposition. Consider n points chosen i.i.d. uniformly in the unit square [0, 1]2 . If r ⌧ n If r If n 3/4 then w.h.p. H1 (C(n, r)) = 0. log n/n then w.h.p. H1 (C(n, r)) = 0. 3/4 ⌧ r ⌧ log n/n then w.h.p. H1 (C(n, r)) 6= 0. References. M. Kahle. Random geometric complexes. Discrete Comput. Geom., 45 (2011), no. 3, 553–573. O. Bobrowski and M. Kahle. Topology of random geometric complexes: a survey. (to appear in AMS Proceedings of Symposia in Applied Mathematics, arXiv:1409.4734.) Persistent homology of a random geometric complex. −3 1.5 x 10 1 0.5 0 0 0.5 1 1.5 −3 x 10 Definition. For a cycle in persistent homology, let b( ) denote the birth radius of , Definition. For a cycle in persistent homology, let b( ) denote the birth radius of , d( ) denote the death radius of , Definition. For a cycle in persistent homology, let b( ) denote the birth radius of , d( ) denote the death radius of , and p( ) = d( )/b( ) denote the persistence of . Advantages of the multiplicative definition. 1. In the random setting, many cycles d( ) satisfy b( ) ⇡ d( ). 2. This makes the persistence a scale-free, dimensionless parameter. ˇ 3. The relationship between Cech and Rips is a multiplicative one. That is, for every finite point set P, we have that C(P, r) ,! R(P, r) ,! C(P, 2r). Advantages of the multiplicative definition. 1. In the random setting, many cycles d( ) satisfy b( ) ⇡ d( ). 2. This makes the persistence a scale-free, dimensionless parameter. ˇ 3. The relationship between Cech and Rips is a multiplicative one. That is, for every finite point set P, we have that C(P, r) ,! R(P, r) ,! C(P, 2r). Advantages of the multiplicative definition. 1. In the random setting, many cycles d( ) satisfy b( ) ⇡ d( ). 2. This makes the persistence a scale-free, dimensionless parameter. ˇ 3. The relationship between Cech and Rips is a multiplicative one. That is, for every finite point set P, we have that C(P, r) ,! R(P, r) ,! C(P, 2r). Main result Theorem. (Two-dimensional case.) Consider n points chosen i.i.d. uniformly in the unit square [0, 1]2 . Then w.h.p. the maximal persistence in degree one homology is of order log n max p( ) ⇣ . log log n That is, there exist constants C1 and C2 such that ✓ ◆ ✓ ◆ log n log n . C1 max p( ) C2 log log n log log n Maximum H1 in 2D 2.6 death birth 2.4 3 max max death birth 4 2.2 2 1.8 2 1.6 3 3.5 4 log n log log n 4.5 5 Sketch of upper bound. (Attempt 1.) p Set r = c/ n for some sufficiently small c > 0. ⇤ Sketch of upper bound. (Attempt 1.) p Set r = c/ n for some sufficiently small c > 0. ⇤ Call cycles with b( ) < r⇤ early-born cycles, and cycles with b( ) r⇤ late-born cycles. Sketch of upper bound. (Attempt 1.) p Set r = c/ n for some sufficiently small c > 0. ⇤ ⇤ Call cycles with b( ) < r early-born, and cycles with b( ) r⇤ late-born. With high probability, all late-born cycles have p p( ) = O log ⇣pn , since⌘all cycles have died before r = O log n/n . Sketch of upper bound. (Attempt 1.) So our main concern is early-born cycles. Sketch of upper bound. (Attempt 1.) So our main concern is early-born cycles. 1. Probability to vertices. Sketch of upper bound. (Attempt 1.) So our main concern is early-born cycles. 1. Probability to vertices. 2. Vertices to length. Sketch of upper bound. (Attempt 1.) So our main concern is early-born cycles. 1. Probability to vertices. 2. Vertices to length. 3. Length to filling radius. Sketch of upper bound. (Attempt 1.) So our main concern is early-born cycles. 1. Probability to vertices. Sketch of upper bound. (Attempt 1.) So our main concern is early-born cycles. 1. Probability to vertices. 2. Vertices to length. Sketch of upper bound. (Attempt 1.) So our main concern is early-born cycles. 1. Probability to vertices. 2. Vertices to length. 3. Length to filling radius. Sketch of upper bound. (Attempt 1.) So our main concern is early-born cycles. 1. Probability to vertices. 2. Vertices to length. 3. Length to filling radius. 4. Filling radius to persistence. Sketch of upper bound. (Attempt 1.) So our main concern is early-born cycles. 1. Probability to vertices. 2. Vertices to length. 3. Length to filling radius. 4. Filling radius to persistence. This allows us to show that early-born cycles p( ) O(log n). have Sketch of upper bound. (Attempt 1.) So our main concern is early-born cycles. 1. Probability to vertices. 2. Vertices to length. 3. Length to filling radius. 4. Filling radius to persistence. This allows us to show that early-born cycles p( ) O(log n). So then all cycles p( ) have p( ) O(log n). have Sketch of upper bound. (Attempt 1.) p Set r = c/ n for some sufficiently small c > 0. ⇤ Sketch of upper bound. (Attempt 2.) ⇤ Set r = (log n) ↵ p / n for some small ↵ > 0. Sketch of upper bound. (Attempt 2.) ⇤ Set r = (log n) ↵ p / n for some small ↵ > 0. ⇤ Call cycles with b( ) < r early-born, and cycles with b( ) r⇤ late-born. ... We conclude that p( ) = O ✓ log n log log n for all cycles , with high probability. ◆ , Theorem. (General case.) Consider n points chosen i.i.d. uniformly in the unit cube [0, 1]d . Then the maximally persistent cycle in degree i homology is of order max p( ) ⇣ ✓ log n log log n ◆1/i . (The implied constants depend on i, d, and on whether ˇ we are considering the random Cech or Rips filtration.) (a) 1.8 1.4 1.6 1.3 max death birth max death birth Maximum H2 in 3D 1.4 1.1 1.2 1 1.2 1 1.7 1.8 1.9 q (c) 2 2.1 log n log log n 2.2 2.3 (b) Maximum H2 in 4D D max death birth 1.4 1.3 1.2 1.1 1 2.2 2.3 1.7 1.8 q log n log log n (d) 1.9 2 Sketch of upper bound. 1. Probability to vertices. 2. Vertices to volume. 3. Volume to filling radius (isoperimetry). 4. Filling radius to persistence. Main tool: isoperimetric inequality. Theorem. (Federer–Fleming, 1960.) If is a k-cycle in Rd of k-dimensional volume V , then the filling radius R satisfies R = O V 1/k . Main tool: isoperimetric inequality. Theorem. (Federer–Fleming, 1960.) If is a k-cycle in Rd of k-dimensional volume V , then the filling radius R satisfies R = O V 1/k . References. H. Federer and W.H. Fleming. Normal and integral currents. Annals of Math. Vol. 72, No. 3 (1960), pp. 458-520. L. Guth. Notes on Gromov’s systolic estimate. Geom. Dedicata. Vol. 123 (2006), pp. 113-129. Future directions 1. Law of large numbers. Is it true that max p( ) lim exists? 1/i n!1 (log n/ log log n) 1. Law of large numbers. Is it true that max p( ) lim exists? 1/i n!1 (log n/ log log n) 2. Other distributions. What about a standard multivariate normal distribution? 1. Law of large numbers. Is it true that max p( ) lim exists? 1/i n!1 (log n/ log log n) 2. Other distributions. What about a standard multivariate normal distribution? 3. Homology in the critical regime. Find a formula for E[ i ] when r = cn 1/i . Thanks for your time and attention! Acknowledgements DARPA Young Faculty Award Alfred P. Sloan Research Fellowship NSF-CAREER Award

1/--страниц