School of Technology and Computer Science Seminars
Topology of a Randomly Evolving Erdos Renyi Graph
by Mr. Gugan Thoppe (School of Technology and Computer Science, TIFR)
Friday, July 11, 2014
from
to
(Asia/Kolkata)
at Colaba Campus ( D-405 (D-Block Seminar Room) )
at Colaba Campus ( D-405 (D-Block Seminar Room) )
Description |
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. |