A limit theorem for the $1$st Betti number of layer-$1$ subgraphs in random graphs

Abstract

We initiate the study of local topology of random graphs. The high level goal is to characterize local "motifs" in graphs. In this paper, we consider what we call the layer-$r$ subgraphs for an input graph $G=(V,E)$: Specifically, the layer-$r$ subgraph at vertex $u\in V$, denoted by $G_{u;r}$, is the induced subgraph of $G$ over vertex set ${\Delta }_u^r:=\left\{v\in V:d_G(u,v)=r\right\}$, where $d_G$ is shortest-path distance in $G$. Viewing a graph as a 1-dimensional simplicial complex, we then aim to study the $1$st Betti number of such subgraphs. Our main result is that the $1$st Betti number of layer-$1$ subgraphs in Erdős--Rényi random graphs $G(n,p)$ satisfies a central limit theorem.

Comments are welcome!