Topology of a Randomly Evolving Erdos Renyi Graph



Friday, 11 July 2014, 14:30 to 16:00


  • D-405 (D-Block Seminar Room)

Abstract: 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 evolves as the time $t$ varies. 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, it asymptotically behaves like a stationary Gaussian Markov process with an exponentially decaying covariance function. 


This talk will NOT assume any prerequisites.