Report

BETTI NUMBERS OF RANDOM SIMPLICIAL COMPLEXES MATTHEW KAHLE & ELIZABETH MECKE Presented by Ariel Szapiro INTRODUCTION : BETTI NUMBERS Informally, the kth Betti number refers to the number of unconnected k-dimensional surfaces. The first few Betti numbers have the following intuitive definitions: β0 is the number of connected components β1 is the number of two-dimensional holes or “handles” β2 is the number of three-dimensional holes or “voids” etc … INTRODUCTION : BETTI NUMBERS Similarity to bar codes method, Betti numbers can also tell you a lot about the topology of an examined space or object. Suppose we sample random points from a given object. Its corresponding Betti numbers are a vector of random variables βk. Understanding how βk is distributed can shed a lot of light about the original space or object. Shown here are some interesting bounds and relation of βk for three well known random objects. ERDOS-R’ENYI RANDOM CLIQUE COMPLEXE Erdos-R’enyi random graph Definition : The Erdos-R’enyi random graph G(n, p) is the probability space of all graphs on vertex set [n] = {1, 2, . . . , n} with each edge included independently with probability p. clique complex The clique complex X(H) of a graph H is the simplicial complex with vertex set V(H) and a face for each set of vertices spanning a complete subgraph of H i.e. clique. Erdos-R’enyi random clique complex is simply X(G(n, p)) ERDOS-R’ENYI RANDOM CLIQUE COMPLEXE EXAMPLE Let say we are in an instance of Erdos-R’enyi random graph with n=5 and p=0.5 What are the Betti numbers ? 4 1 5 3 2 Simplexes complex with dimension:0 are all the dots 1 are all the lines 2 are all the triangels RANDOM CECH & RIPS COMPLEX The random Cech complex The random Cech complex C X n ; r is a simplicial complex with vertex set X n , and a face of C X n ; r if xi B xi , r The random Rips complex The random Rips complex R X n ; r is a simplicial complex with vertex set X n , and a face of R X n ; r if B xi , r B x j , r for every pair xi , x j RANDOM CECH & RIPS COMPLEX Random geometric graph Definition: Let f : Rd → R be a probability density function, let x1, x2, . . ., xn be a sequence of independent and identically distributed d-dimensional random variables with common density f, and let Xn = {x1, x2, . . ., xn }. The geometric random graph G(Xn; r) is the geometric graph with vertices Xn, and edges between every pair of vertices u, v with d(u, v) ≤ r. RANDOM CECH & RIPS COMPLEX EXAMPLE AND DIFFERENCES Let say we are in an instance of random geometric graph with n=5 and r = 1 4 1 3 2 5 InInCech Rips configuration the Simplexes are: ERDOS-R’ENYI RANDOM CLIQUE COMPLEXE MAIN RESULTS Theorem on Expectation If p n 1/ k and p o n 1/ k 1 then lim E k n nk p k 1 2 1 k 1! In particular it is shown that if p O n1/ k or p n1/ 2 k 1 for some constant 0, then a.a.s. k 0. Central limit theorem If p n 1/ k and p o n 1/ k 1 then k E k Var k N 0,1 ERDOS-R’ENYI RANDOM CLIQUE COMPLEXE MAIN RESULTS Lower bound Lower bound Lower bound 1/ k p n1/ k p 0.01 0.215 n 1/pk n0.1 Upper bound Upper bound Upper bound p n 1/2 k 1 0.215 p n 1/2 k p1 0.398 n 1/2 k 1 0.517 RANDOM CECH MAIN RESULTS & RIPS COMPLEX There are four main ranges i.e. regimes, with qualitatively different behavior in each, for different values of r, the ranges are : SUBCRITICAL - r o n 1/ d 1/ d CRITICAL - r n 1/ d 1/ d SUPERCRITICAL - r n o r n CONNECTED – r log n / n 1/ d Note – since the results for Cech and Rips complexes are very similar we will ignore the former. RANDOM CECH MAIN RESULTS & RIPS COMPLEX - SUBCRITICAL In the Subcritical regime the simplicial complexes that is constructed from the random geometric graph G(Xn; r) intuitively, has many disconnected pieces. In this regime the writes shows: Theorem on Expectation and Variance (for Rips Complexes) For any d 2, k 1, 0, and r O n 1/ d E k 2 k 2 d 2 k 1 Ck Var k 2 k 2 d 2 k 1 Ck n r n r as n where Ck is a constant that depends only on k and the underlying density function f . RANDOM CECH MAIN RESULTS & RIPS COMPLEX - SUBCRITICAL Central limit Theorem For d 2, k 1, 0, and r O n 1/ d this limit holds k E k Var k N 0,1 as n . A very interesting outcome from the previous Theorem is that you can know a.a.s in this regime that: 1 1 If k 1 then k 0 2 d 1 1 And if k 1 then k 0 2 d RANDOM CECH MAIN RESULTS & RIPS COMPLEX - CRITICAL In the Critical regime the expectation of all the Betti numbers grow linearly, we will see that this is the maximal rate of growth for every Betti number from r = 0 to infinty. In this regime the writes shows: Theorem on Expectation (for Rips Complexes) For any density on d and k 0 fixed, E k n RANDOM CECH MAIN RESULTS & RIPS COMPLEX - SUPERCRITICAL In the Supercritical regime the writes shows an upper bound on the expectation of Betti numbers. This illustrate that it grows sub-linearly, thus the linear growth of the Betti numbers in the critical regime is maximal In this regime the writes shows: Theorem on Expectation (for Rips Complexes) Let n points taken i.i.d. uniformly from a smoothly bounded convex body C. Let r n , where as n , and k 0 is fixed. 1/ d then E k O k e c n for same c 0 RANDOM CECH MAIN RESULTS & RIPS COMPLEX - CONNECTED In the Connected regime the graph becomes fully connected w.h.p for the uniform distribution on a convex body In this regime the writes shows: Theorem on connectivity For a smoothly bounded convex body C in d , endowed with 1d a uniform distribution, and fixed k 0, if r log n n then the random Rips complex R( X n ; r ) is a.a.s. k-connected. METHODS OF WORK The main techniques/mode of work to obtain the nice theorems presented here are: • First move the problem topology into a combinatorial one -this is done mainly with the help of Morse theory • Second use expectation and probably properties to obtain the requested theorem Lets take for Example the Theorem on Expectation for Erdos-R’enyi random clique complexes : If p n 1/ k and p o n 1/ k 1 then lim E k n nk p k 1 2 1 k 1! METHODS OF WORK – FIRST STAGE The writers uses the following inequality (proven by Allen Hatcher. In Algebraic topology) : fk 1 fk fk 1 k fk Where fi donates the number of i-dimensional simplexes. In the Erdos-R’enyi case this is simply the number of (k + 1)-cliques in the original graph. Thus we obtain: n E fk p k 1 k 1 2 k 1 2 n k 1 p n k 1 ! METHODS OF WORK – SECOND STAGE Now we only need to finish the proof, we know by now that : k 1 k 1 2 n p E f k n k 1! E f k 1 o 1 k 1 k p n k E f k 1 np k 2 n p E f k 1 n k! Thus we only need to squeeze the k-Betti number and obtain the desire result. SUMMERY Three types of random generated complexes were presented Theories on expectation and on statistic behavior of their Betti numbers was given, for each one of the four regimes (in Rips case) And the basic working technique the writers used was presented