Topology of a Randomly Evolving Erdos Renyi Graph

by Mr Gugan Thoppe (School of Technology and Computer Science, TIFR)

Friday 11 Jul 2014, 14:30 → 16:00 Asia/Kolkata

D-405 (D-Block Seminar Room) (Colaba Campus)

Mathew Kahle and Elizabeth Meckes recently established interesting results concerning the topology of the clique complex $X(n,p)$ on an Erdos Renyi graph $G(n,p).$ Specifically, they showed that, if $p = n^{\alpha}$ with $\alpha \in (-1/k, -1/(k + 1))$ for some positive integer $k,$ then asymptotically, i.e., as $n \rightarrow \infty,$ every Betti number $\beta_j$ of $X(n,p),$ except for the $k-$th one, vanishes. Further, for the choice of $p$ as above, $\beta_k$ of $X(n,p)$ follows a central limit theorem, i.e., $(\beta_k - \mathbb{E}[\beta_k])/\sqrt{Var(\beta_k)}$ is asymptotically Gaussian. In this talk, we will consider a randomly evolving Erdos Renyi graph $G(n, p, t)$ and study how its topology varies with time $t.$ Specifically, we will prove that if p is chosen as above, then the process $(\beta_k(t) - \mathbb{E}[\beta_k(t)])/\sqrt{Var[\beta_k(t)]}$ is asymptotically an Ornstein-Uhlenbeck process. That is, the k-th Betti number asymptotically behaves like a stationary Gaussian Markov process with an exponentially decaying covariance function. I will NOT assume any prerequisites for this talk.