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

Publication date 1 November 2019

Random graphs (graph-theoretic aspects) (05C80) Homology and cohomology theories in algebraic topology (55N99) Applied homological algebra and category theory in algebraic topology (55U99)

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 i n V

, denoted by

G_{u; r}

, is the induced subgraph of

G

over vertex set

D e l t a_{u}^{r} := l e f t v i n V : d_{G} (u, v) = r i g h t

, 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 ErdH{o}s--R'enyi random graphs

G (n, p)

satisfies a central limit theorem.

This page was built for publication: A limit theorem for the $1$st Betti number of layer-$1$ subgraphs in random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6328382)