Random Simplicial Complexes:
Models and Phenomena

The edge existence probability in the random Erdős-Rényi graph $G(n,p)$ does definitely not have to be the same $p$ for all edges. Each edge $i,j$ can have a different existence probability $p_{ij}$, $i,j=1,2,\ldots,n$. Such random graphs are known as inhomogeneous or generalized random graphs [38, 39, 40, 41]. We denote them by $G(n,\hat{p})$, where $\hat{p}$ is the matrix of edge existence probabilities, $\hat{p}=\{p_{ij}\}$.

A straightforward generalization of $G(n,\hat{p})$ to higher dimensions was introduced in [21]. It is also a generalization of $X(n,{\bf{p}})$, and it is defined as follows. Let $\hat{{\bf{p}}}=(\hat{p}_{1},\hat{p}_{2},\ldots,\hat{p}_{n-1})$ be a vector of simplex existence probabilities for all possible simplexes of all possible dimensions $k=1,2,\ldots,n-1$: $\hat{p}_{1}=\{p_{ij}\}$, $\hat{p}_{2}=\{p_{ijl}\}$, and $\hat{p}_{k}=\{p_{\sigma_{k}}\}$ collects the $n\choose k+1$ existence probabilities for all possible $n\choose k+1$ simplexes $\sigma_{k}$ of dimension $k$. Given such a vector of tensors $\hat{{\bf{p}}}$, the random complex $X(n,\hat{{\bf{p}}})$ is then generated similarly to $X(n,{\bf{p}})$: starting with an inhomogeneous random graph $G(n,\hat{p}_{1})$, go over all the $3$-cliques ($2$-shells) in this graph, and fill them with $2$-simplexes $\sigma_{2}$ independently with probability $p_{\sigma_{2}}$. Proceed to higher dimensions $k=3,4,\ldots,n-1$ in a similar fashion, filling $k$-shells with $k$-simplexes independently with probabilities $p_{\sigma_{k}}$. The complex $X(n,{\bf{p}})$ is a special case of $X(n,\hat{{\bf{p}}})$—the one with $\hat{p}_{k}\equiv p_{k}$.

The inhomogeneous random graphs $G(n,\hat{p})$ are quite general, subsuming many other important models of random graphs. In particular, they encompass the soft configuration model $\mathrm{SCM}(n,\mathbf{k})$ [38, 39, 40, 41, 42, 43, 44], which is the canonical model of random graphs with a given sequence of expected degrees $\mathbf{k}=(k_{1},k_{2},\ldots,k_{n})$, $k_{i}\geq 0$, $i=1,2,\ldots,n$. The $\mathrm{SCM}(n,\mathbf{k})$ model is the $G(n,\hat{p})$ with $\hat{p}$ given by

$$p_{ij}=\frac{1}{e^{\lambda_{i}+\lambda_{j}}+1},$$

(2.1)

where the parameters $\lambda_{i}$’s (known as Lagrange multipliers) solve the system of $n$ equations given by

$$\sum_{j}p_{ij}=k_{i}.$$

(2.2)

This equation guarantees the expected degree of node $i$ to be $k_{i}$.

The sufficient statistics in $\mathrm{SCM}(n,\mathbf{k})$ are the degrees of all nodes in a graph. Therefore, $\mathrm{SCM}(n,\mathbf{k})$’s microcanonical counterpart, the configuration model $\mathrm{CM}(n,\mathbf{k})$ [45, 46], is the uniform distribution over all the graphs with the degree sequence $\mathbf{k}$. Note that $\mathbf{k}$ can be any sequence of nonnegative real numbers in $\mathrm{SCM}(n,\mathbf{k})$, but in $\mathrm{CM}(n,\mathbf{k})$, $\mathbf{k}$ is a graphical sequence of nonnegative integers. A sequence $\mathbf{k}$ is called graphical, if there exists a graph whose degree sequence is $\mathbf{k}$. The necessary and sufficient conditions for $\mathbf{k}$ to be graphical are the Erdős-Gallai conditions [47].

An important special case of $\mathrm{CM}(n,\mathbf{k})$ is the random $k$-regular graph $G(n,k)=\mathrm{CM}(n,(k,k,\ldots,k))$.

Recall that the degree $k_{i}$ of a vertex ($0$-simplex) $i$ is the number of edges ($1$-simplexes) that contain $i$. In a similar vein, the degree $k_{\sigma}$ of $d$-simplex $\sigma$ is defined to be the number of $(d+1)$-simplices that contain $\sigma$.

The $d$-dimensional soft configuration model $\mathrm{SCM}_{d}(n,\mathbf{k})$ is a generalization of $\mathrm{SCM}(n,\mathbf{k})$, where now $\mathbf{k}=\{k_{\tau}\}$ is a sequence of $n\choose d$ expected degrees $k_{\tau}\geq 0$ of all $(d-1)$-simplexes $\tau$. To construct $\mathrm{SCM}_{d}(n,\mathbf{k})$ we take the complete $(d-1)$-skeleton on $n$ vertices, and add all possible $d$-simplexes $\sigma$ independently with probability

$$p_{\sigma}=\frac{1}{e^{\sum_{\tau}\lambda_{\tau}\boldsymbol{\mathbbm{1}}\left\{\tau<\sigma\right\}}+1},$$

(2.3)

where the summation is over all $(d-1)$-faces $\tau$ of $\sigma$ (as implied by the standard $\tau<\sigma$ notation), and the parameters $\lambda_{\tau}$ solve the system of $n\choose d$ equations

$$\sum_{\sigma}p_{\sigma}\boldsymbol{\mathbbm{1}}\left\{\tau<\sigma\right\}=k_{\tau}.$$

(2.4)

Note that $\mathrm{SCM}_{d}(n,\mathbf{k})$ is a special case of $X(n,\hat{{\bf{p}}})$:

$$\mathrm{SCM}_{d}(n,\mathbf{k})=X(n,(\underbrace{1,1,\ldots,1}_{d-1},\hat{p}_{d},\underbrace{0,0,\ldots,0}_{n-d-1})),$$

where $\hat{p}_{d}=\{p_{\sigma}\}$ is given by (2.3). If $d=1$, then Eqs. (2.3,2.4) reduce to Eqs. (2.1,2.2), respectively, and we have $\mathrm{SCM}_{1}(n,\mathbf{k})\equiv\mathrm{SCM}(n,\mathbf{k})$.

The $\mathrm{SCM}_{d}(n,\mathbf{k})$ is the canonical model of random complexes whose sufficient statistics are the degrees of all the $(d-1)$-simplexes in a complex. Therefore, $\mathrm{SCM}_{d}(n,\mathbf{k})$’s microcanonical counterpart, the configuration model $\mathrm{CM}_{d}(n,\mathbf{k})$, is the uniform distribution over complexes with the complete $(d-1)$-skeleton and the degree sequence of $(d-1)$-simplexes equal to $\mathbf{k}$. In $\mathrm{CM}_{d}(n,\mathbf{k})$, $\mathbf{k}$ is a realizable sequence of $n\choose d$ nonnegative integers, versus any sequence of $n\choose d$ nonnegative real numbers in $\mathrm{SCM}_{d}(n,\mathbf{k})$. The conditions for $\mathbf{k}$ to be realizable, analogous to the Erdős-Gallai graphicality conditions in the $d=1$ case, are at present unknown.

An important special case of the configuration model is the random $k$-regular complex $X_{d}(n,k)=\mathrm{CM}_{d}(n,(k,k,\ldots,k))$ in which all $(d-1)$-simplexes have degree $k$ [48]. For $k=1$, such a complex is also known as an $(n,d)$-Steiner system, whose randomized construction is due to [49].

With the exception of $X_{d}(n,k)$, the $d$-dimensional configuration models $\mathrm{CM}_{d}(n,\mathbf{k})$ and $\mathrm{SCM}_{d}(n,\mathbf{k})$ have not been considered in the past. The configuration models defined and studied in [50, 51] are very different and unrelated to any other model considered above. We review them in Section 2.5.2.

Note that the edge probabilities $p_{ij}$ in inhomogeneous random graphs $G(n,\hat{p})$ can themselves be random [52, 53, 40, 41]. In that case, we replace $\hat{p}$ with $\hat{r}=\{r_{ij}\}$ which is a random matrix with entries in $[0,1]$, and the corresponding inhomogeneous random graph is denoted $G(n,\hat{r})$. This class of random graphs is extremely general and subsumes a great variety of many important random graph models, for example $G(n,\hat{p})$.

Of a particular interest is the case where

$$r_{ij}=p(X_{i},X_{j}),$$

where $\{X_{1},\ldots,X_{n}\}$ is a set of random variables in some measure space $S$, and $p:S\times S\to[0,1]$ is a fixed function called the connection probability function. This class of models is quite general and subsumes, for instance, the stochastic block models [54], hidden variable models [52, 53], latent space models [55, 56, 57], random geometric graphs [58, 59], and many other popular models. If the $X_{i}$’s are independent random variables uniformly distributed in $[0,1]$, and $p$ is a symmetric integrable function, then $p$ is also known as a graphon in the theory of graph limits [60, 61].

The most general class of models considered in this chapter is a version of the multi-parameter complex $X(n,\hat{{\bf{p}}})$ with random simplex existence probabilities $\hat{{\bf{p}}}$. To emphasize their randomness, we denote this complex by $X(n,\hat{\mathbf{r}})$, where $\hat{\mathbf{r}}$ is random $\hat{{\bf{p}}}$. For maximum generality, the probabilities of existence of different simplexes, including simplexes of different dimensions, do not have to be independent random variables, so that the space of $X(n,\hat{\mathbf{r}})$ is parameterized by joint probability distributions over the vector of tensors $\hat{\mathbf{r}}$, equivalent to all nonempty subsets of $\left\{1,\ldots,n\right\}$. As evident from Fig. 1, all other models of random complexes and graphs are special cases of $X(n,\hat{\mathbf{r}})$. In particular, $X(n,\hat{{\bf{p}}})$ is a special degenerate case of $X(n,\hat{\mathbf{r}})$. At this level of generality, the complex $X(n,\hat{\mathbf{r}})$ has not been considered or defined before, yet it is simply a higher-dimensional version of the well-studied $G(n,\hat{r})$.

The hypersoft configuration model is the hypercanonical model of random graphs with a given expected degree distribution $\rho$ [52, 53, 40, 41, 44, 62]. It is defined as the $\mathrm{SCM}(n,\mathbf{k})$ in which the expected degree sequence $\mathbf{k}$ is not fixed but random: the expected degree $k_{i}$ of every vertex $i$ is an independent random variable with distribution $\rho$, $k_{i}\sim\rho$. In other words, to generate an $\mathrm{HSCM}(n,\rho)$ graph, one first samples $k_{i}$s independently from the distribution $\rho$, then solves the system of equations (2.2) to find all $\lambda_{i}$s, and finally creates edges with probabilities $p_{ij}$ (2.1). The $\mathrm{HSCM}(n,\rho)$ is thus a probabilistic mixture of $\mathrm{SCM}(n,\mathbf{k})$’s with random $\mathbf{k}\sim\rho^{n}$. The degree distribution in $\mathrm{HSCM}(n,\rho)$ is the mixed Poisson distribution with mixing $\rho$ [40, 41].

An equivalent definition of $\mathrm{HSCM}(n,\rho)$ is based on the observation that the distribution $\rho$ defines the joint distribution $\Psi$ of $\Lambda=\{\lambda_{i}\}$ via (2.2). This means that an equivalent procedure to generate an $\mathrm{HSCM}(n,\rho)$ graph is to sample $\Lambda$ directly from $\Psi$ first, and then create edges with probabilities $p_{ij}$ (2.1). This definition makes it explicit that the $\mathrm{HSCM}(n,\rho)$ is a special case of $G(n,\hat{r})$.

For a given $\rho$, it may difficult to find the explicit form of the distribution $\Psi$. However, in many cases with important applications—including the Pareto $\rho$ with a finite mean, for instance—it has been shown that the canonical connection probability (2.1) and its classical limit approximation

$$p_{ij}^{\mathrm{CL}}=\min\left(1,e^{-\lambda_{i}}e^{-\lambda_{i}}\right)=\min\left(1,\frac{k_{i}k_{j}}{\bar{k}n}\right),$$

(2.5)

where $\bar{k}$ is the mean of $\rho$, lead to asymptotically equivalent random graphs [28]. In such cases, the random Lagrange multipliers $\lambda_{i}$’s are asymptotically independent, $\Psi=\psi^{n}$, $\lambda_{i}\sim\psi$, with the distribution $\psi$ defined by the distribution $\rho$ via the change of variables $\lambda_{i}=\ln\left(\sqrt{\bar{k}n}/k_{i}\right)$ where $k_{i}\sim\rho$. Generating such a graph is extremely simple: first sample either the $k_{i}$’s or $\lambda_{i}$’s independently from the distribution $\rho$ or $\psi$, respectively, and then generate edges with probabilities $p_{ij}^{\mathrm{CL}}$ (2.5).

A straightforward generalization of $\mathrm{HSCM}(n,\rho)$ to dimension $d$ is achieved by defining the $\mathrm{HSCM}_{d}(n,\rho)$ as the probabilistic mixture of $\mathrm{SCM}_{d}(n,\mathbf{k})$ with random $\mathbf{k}\sim\rho^{n\choose d}$: the expected degree $k_{\tau}$ of every $(d-1)$-simplex $\tau$ is an independent random variable with distribution $\rho$. In other words, to generate a random $\mathrm{HSCM}_{d}(n,\rho)$ complex, one first prepares the complete $(d-1)$-complex of size $n$, then samples the $n\choose d$ expected degrees $k_{\tau}$ of all the $(d-1)$-simplexes $\tau$ independently from the distribution $\rho$, then solves the system of equations (2.4) to find all the $\lambda_{\tau}$’s, and finally creates the $d$-simplexes $\sigma$ independently with probability $p_{\sigma}$ (2.3). For the same reasons as in the $d=1$ case, the $\mathrm{HSCM}_{d}(n,\rho)$ model is a special case of $X(n,\hat{\mathbf{r}})$ for any $d\geq 1$. The model has not been previously considered, except the $d=1$ case.

is simply a set of $n$ random points $\mathcal{X}_{n}=\left\{X_{1},\ldots,X_{n}\right\}\subset S$ sampled independently from $P$. In the simplest case $S=\mathbb{T}^{1}$, we simply sample $X_{i}$’s from the uniform distribution, $X_{i}\sim\mathcal{U}(0,1)$, viewed as a circle. The distribution of the number of points in any measurable subset $A\subseteq S$ is binomial with mean $nP(A)$, giving the process its name.

is the binomial process with a random number of points $N$ sampled from the Poisson distribution with mean $n$, i.e. $\mathcal{P}_{n}=\mathcal{X}_{N}$, where $N\sim\mathrm{Pois}\left({n}\right)$. The distribution of the number of points in any measurable $A\subseteq S$ is Poisson with mean $nP(A)$, where $n$ is the rate of the process. Another key property of the Poisson process is spatial independence: the numbers of points in any pair of disjoint subsets of $S$ are independent random variables. This property, absent in the binomial process, makes the Poisson process favorable in probabilistic analysis.

In the $n\to\infty$ limit, the two process are asymptotically identical—the binomial process converges to the Poisson process in a proper sense [63]. For this reason, and given that the Poisson process is easier to deal with, we will restrict ourselves in this chapter to the Poisson process $\mathcal{P}_{n}$ on the torus $\mathbb{T}^{d}$. These setting turn out to provide the most elegant results, while not losing much in terms of generality.

We start with $G(\mathcal{X}_{n},r)$, which is a special case of $G(n,\hat{r})$, in which

$$r_{ij}=p(X_{i},X_{j})=\boldsymbol{\mathbbm{1}}\left\{d(X_{i},X_{j})\leq r\right\},$$

where $d(X_{i},X_{j})$ is the distance between $X_{i},X_{j}\in\mathcal{X}_{n}$ in $\mathbb{T}^{d}$, and $r>0$ is the connectivity radius parameter [58, 59]. In other words, the vertices of this random graph are a realization of the binomial process, and two vertices are connected if the distance between them in $\mathbb{T}^{d}$ is at most $r$. To generate the random geometric graph $G(\mathcal{P}_{n},r)$ we first sample $N\sim\mathrm{Pois}\left({n}\right)$, and then generate $G(\mathcal{X}_{N},r)$ as described above.

This is the flag complex over the random geometric graph $G(\mathcal{P}_{n},r)$. It is thus a straightforward higher-dimensional generalization of $G(\mathcal{P}_{n},r)$. Note that we can consider $R(\mathcal{X}_{n},r)$ for the binomial process as well, which is a special case of $X(n,\hat{\mathbf{r}})$. Then $R(\mathcal{P}_{n},r)=R(\mathcal{X}_{N},r)$ with $N\sim\mathrm{Pois}\left({n}\right)$.

This is a different higher-dimensional generalization of $G(\mathcal{P}_{n},r)$. The $C(\mathcal{P}_{n},r)$ rule is: draw balls $B_{r/2}(X_{i})$ of radius $r/2$ around each of the points $X_{i}\in\mathcal{P}_{n}$, then look for all the intersections of these balls, and for every $(k+1)$-fold intersection of the balls, add the corresponding $k$-simplex to the complex. Note that the binomial version $C(\mathcal{X}_{n},r)$ can still be considered as a special case of $X(n,\hat{\mathbf{r}})$ with a different rule for the creation of higher-dimensional simplexes, compared to $R(\mathcal{X}_{n},r)$.

While the $1$-skeleton of both $R(\mathcal{P}_{n},r)$ and $C(\mathcal{P}_{n},r)$ is the same random geometric graph $G(\mathcal{P}_{n},r)$, higher-dimensional simplexes in these complexes are in general different, as illustrated in Fig. 2. The following useful relation was proved in [64] for any $\alpha\leq\sqrt{\frac{d+1}{2d}}$:

$$R(\mathcal{P}_{n},\alpha r)\subset C(\mathcal{P}_{n},r)\subset R(\mathcal{P}_{n},r).$$

A powerful property of the Čech complex is due to the Nerve Lemma [65] stating that under mild conditions we have the following isomorphism between the homology groups $H_{k}$:

$$H_{k}(C(\mathcal{P}_{n},r))\cong H_{k}(B(\mathcal{P}_{n},r)),$$

where $B(\mathcal{P}_{n},r)=\bigcup_{X_{i}\in\mathcal{P}_{n}}B_{r/2}(X_{i})$. This property, absent in the Rips complex, is very useful in the probabilistic analysis of the Čech complex, allowing one to switch back-and-forth between combinatorics and stochastic geometry.

This is a straightforward generalization of the inhomogeneous random graph $G(n,\hat{p})$ to hypergraphs: every possible hyperedge $\sigma$ (which is a nonempty subset of $\left\{1,\ldots,n\right\}$) in $H\sim H(n,\hat{{\bf{p}}})$ exists independently with probability $p_{\sigma}\in\hat{{\bf{p}}}$. Note that $H$ is not a simplicial complex with high probability, unless $\hat{{\bf{p}}}$ is specially designed for $H$ to be a complex.

Introduced in [68, 66], these are both based on the $H(n,\hat{{\bf{p}}})$. The lower complex $\underline{Z}\sim\underline{Z}(n,\hat{{\bf{p}}})$ is the largest simplicial complex that the random $H\sim H(n,\hat{{\bf{p}}})$ contains, while the upper complex $\overline{Z}\sim\overline{Z}(n,\hat{{\bf{p}}})$ is the smallest simplicial complex that contains the random $H\sim H(n,\hat{{\bf{p}}})$, so that $\underline{Z}\leq H\leq\overline{Z}$. In other words, a simplex $\sigma$ is included in the lower complex $\underline{Z}$ if and only if $\sigma\in H$ and also all its faces are hyperedges of $H$. The other way around, every hyperedge $\sigma\in H$ is included in the upper complex $\overline{Z}$ as a simplex together with all its faces, even if some of these faces do not happen to be in $H$.

Compared to the graph-based models reviewed in the previous sections, the hypergraph-based models are much more difficult to analyze, primarily because the distributions of the skeletons are highly nontrivial and carry intricate dependency structure. However, an exciting fact about these two models is that they are dual in some strict topological sense (Alexander duality), and therefore statements about one of the models can be translated with ease to corresponding statements about the other [66, 67].

At this point, it may be tempting to proceed similarity to the previous $X$-sections, and let the hyperedge existence probabilities $\hat{{\bf{p}}}$ be random $\hat{\mathbf{r}}$, leading to $H(n,\hat{\mathbf{r}})$, $\underline{Z}(n,\hat{\mathbf{r}})$, and $\overline{Z}(n,\hat{\mathbf{r}})$. However, nothing new is gained by doing so, since the $X(n,\hat{\mathbf{r}})$ model is already general enough as it includes any possible joint distribution of simplex existence probabilities, including the distributions describing $\underline{Z}(n,\hat{{\bf{p}}})$ and $\overline{Z}(n,\hat{{\bf{p}}})$. That is, the lower and upper models $\underline{Z}(n,\hat{{\bf{p}}})$ and $\overline{Z}(n,\hat{{\bf{p}}})$ with nonrandom $\hat{{\bf{p}}}$ are special cases of the more general $X(n,\hat{\mathbf{r}})$ model with the joint distribution of $\hat{\mathbf{r}}$ set equal to the joint distribution of simplex existence probabilities in $\underline{Z}(n,\hat{{\bf{p}}})$ and $\overline{Z}(n,\hat{{\bf{p}}})$, while the lower and upper models $\underline{Z}(n,\hat{\mathbf{r}})$ and $\overline{Z}(n,\hat{\mathbf{r}})$ with random $\hat{\mathbf{r}}$ are equivalent to $X(n,\hat{\mathbf{r}}_{*})$ with matching joint distributions of $\hat{\mathbf{r}}_{*}$.

The $d$-degree $k_{\sigma}(d)$ of a $d^{\prime}$-simplex $\sigma$ is defined to be the number of simplexes of dimension $d>d^{\prime}$ that contain $\sigma$ [2], and the $Z$-configuration models are defined by a vector $\mathbf{k}=\{k_{i}(d)\}$ of a given sequence of (expected) $d$-degrees of vertices $i=1,2,\ldots,n$, as opposed to the vector of (expected) $d$-degrees of $(d-1)$-simplexes in the $\mathrm{(S)CM}_{d}(n,\mathbf{k})$ in Section 2.3.2. No low-dimensional skeleton is formed in the Z-$\mathrm{SCM}_{d}(n,\mathbf{k})$, while the probability of $d$-simplex $\sigma$ is

$$p_{\sigma}=\frac{1}{e^{\sum_{i}\lambda_{i}\boldsymbol{\mathbbm{1}}\left\{i<\sigma\right\}}+1},$$

(2.6)

where the $n$ parameters $\lambda_{i}$ of vertices $i$ solve the system of $n$ equations

$$\sum_{\sigma}p_{\sigma}\boldsymbol{\mathbbm{1}}\left\{i<\sigma\right\}=k_{i}(d).$$

(2.7)

If simplex $\sigma$ is added to the complex, then so are all its lower-dimensional faces. The Z-$\mathrm{SCM}_{d}(n,\mathbf{k})$ is a special case of the $\bar{Z}(n,\hat{{\bf{p}}})$ with $\hat{{\bf{p}}}=(0,\ldots,0,\hat{p}_{d},0,\ldots,0)$ and $\hat{p}_{d}=\{p_{\sigma}\}$ given by (2.6).

The model is canonical with the $d$-degree of all vertices being its sufficient statistics, so that the corresponding microcanonical model Z-$\mathrm{CM}_{d}(n,\mathbf{k})$ is the uniform distribution over all the $d$-complexes with the $d$-degree sequence of the vertices equal to $\mathbf{k}$. Note that these complexes satisfy the additional constraint: they do not contain any simplex of dimension $d^{\prime}<d$ that is not a face of a $d$-simplex. The hypercanonical model Z-$\mathrm{HSCM}_{d}(n,\rho)$ is the Z-$\mathrm{SCM}_{d}(n,\mathbf{k})$ with random $k_{i}(d)\sim\rho$.