The Shadow Knows: Empirical Distributions of Minimum Spanning Acycles and Persistence Diagrams of Random Complexes

We now provide a summary of our main result along with its visual illustration. The necessary background is given in parallel.

A simplicial complex $\mathcal{K}$ on a vertex set $V$ is a collection of subsets of $V$ that is closed under the subset operation. Trivially, every graph is a simplicial complex. However, the closure is what distinguishes a simplicial complex from a hypergraph, the other standard model for studying higher-order relations. In particular, all simplicial complexes are hypergraphs, but the reverse is not true. We refer to an element of $\mathcal{K}$ with cardinality $k+1$ as a $k$-dimensional face or simply a $k$-face. Similarly, the $k$-skeleton of $\mathcal{K},$ denoted $\mathcal{K}^{k},$ refers to the subset of faces with dimension less than or equal to $k.$

Let $d\geq 1$ and $(\mathcal{K}_{n},w_{u})$ be the weighted simplicial complex, where i.) $\mathcal{K}_{n}$ is the complete $d$-skeleton on $n$ vertices, i.e., $\mathcal{K}_{n}$ is the set of all subsets that have cardinality less than or equal to $d+1;$ and ii.) $w_{u}$ is a weight function such that $w_{u}(\sigma)$ is an independent uniform $[0,1]$ random variable if $\sigma$ is a $d$-face, and zero otherwise. Let $M_{n}$ be a $d$-dimensional MSA¹¹1We provide the formal definition of an MSA in Section 2, but the reader unfamiliar with this term can set $d=1$ and replace MSA with a MST to read ahead. (or $d$-MSA in short) in $(\mathcal{K}_{n},w_{u}).$ Then our main result can be informally stated as follows (see Section 2 for the details).

Intuitively, our result says that the normalized count of the $M_{n}$ face weights—after being scaled by $n$—that lie in any subset of the real line asymptotically converges to that subset’s measure under $\mu.$ The next couple of paragraphs briefly explain what this measure $\mu$ is.

Recall that the Erdős-Rényi graph, denoted by $G(n,p),$ is a random graph on $n$ vertices where each edge is present with probability $p$ independently. The $d$-dimensional Linial-Meshulam complex $Y_{d}(n,p)$ or simply $Y(n,p)$ is an analog of this model in higher dimensions. This random complex has $n$ vertices and the complete $(d-1)$-skeleton; further, the $d$-faces are included with probability $p$ independently. It is easy to see that $Y_{1}(n,p)$ and $G(n,p)$ are equivalent.

The shadow of a graph $G$ is the set of all the missing transitive edges. That is, it includes a vertex pair $\{u,v\},$ if $G$’s edge set excludes such a pair, but contains an alternative path from $u$ to $v$ via other edges. Clearly, each vertex pair in $G$’s shadow has endpoints in any one component of $G.$ A simplicial complex’s shadow is a related topological generalization; see Definition 3 for details.

The shadow of the random complex $Y(n,c/n)$ was investigated in [10], and its cardinality, after a suitable normalization, was shown to converge to a deterministic constant $s(c).$ Now, $\mu$ is that measure whose density is, loosely, one minus the function made up of these constants for different $c$ values.

Figure 1 illustrates our main result pictorially. The two scenarios shown there correspond to two different values of the pair $(n,d).$ The yellow plots show the normalized histogram of the set $\{nw_{u}(\sigma):\sigma\in M_{n}\},$ while the red curves show the density of the shadow based limiting measure $\mu.$ Observe that the red curves and the top of the yellow plots more or less resemble each other. Our main result loosely states that the difference between them decays to zero, as $n\to\infty.$

The weighted simplicial complex $(\mathcal{K}_{n},w_{u})$ can also be viewed as the evolving simplicial complex $(\mathcal{L}_{n}(s))_{s\in[0,1]},$ where $\mathcal{L}_{n}(s):=\{\sigma\in\mathcal{K}_{n}:w_{u}(\sigma)\leq s\}.$ In this evolution, $\mathcal{L}_{n}(s)$ monotically grows from a simplicial complex with an (almost surely) empty $d$-skeleton (when $s=0$) to one that has all the $d$-faces (when $s=1$). There is a natural persistence diagram associated with this process, which records the birth and death times of the different topological holes that appear and disappear as the process evolves. In [12, Theorem 3], it was shown that the set of death times in the $(d-1)$-th dimension of this diagram exactly equals the set of weights in the $d$-MSA of $(\mathcal{K}_{n},w_{u}).$ Consequently, the above result can also be stated in terms of the death times in the persistence diagram related to $(\mathcal{K}_{n},w_{u}).$

Our work lies at the intersection of two broad strands of research: one concerning component sizes, shadow densities, and homologies of random graphs and random complexes, and the other dealing with the statistics of weights in random MSTs and MSAs. In this section, we look at a few of the historical milestones in these two strands.

Erdős and Rényi were the ones who initiated the first strand with their work in [2]. There they showed that $p=\log n/n$ is a sharp asymptotic threshold for connectivity in $G(n,p).$ Also that, if $p=(\log n+c)/n$ for $c\in\mathbb{R}$ and $n\to\infty,$ then i.) almost all the vertices in $G(n,p)$ lie in one single component, and ii.) the vertices outside this are all isolated and their number has a Poisson distribution with mean $e^{-c}.$ This result was subsequently refined in [3] and the new statement included the following additional facts: i.) the asymptotic order of the largest component jumps from logarithmic to linear around $p=1/n,$ and ii.) for $c>1,$ the largest component in $G(n,c/n),$ denoted $L_{n}(c),$ satisfies $|L_{n}(c)|/n\to 1-t(c),$ where $|S|$ denotes the cardinality of a set $S,$ and $t(c)$ is the unique root in $(0,1)$ of the equation

A graph is a one-dimensional simplicial complex, so one can ask if phenomena like the ones above also occur in random complexes. Since connectivity is related to the vanishing of the zeroth homology, it is natural to look at the higher order Betti numbers to answer this question. Such a study was done in [8, 11], and it was found that the $(d-1)$-th Betti number of $Y(n,p)$ indeed shows a non-vanishing to vanishing phase transition at $p=d\log n/n.$ A separate study [6] also showed that this Betti number converges to a Poisson random variable with mean $e^{-c},$ when $p=(d\log n-\log(d!)+c)/n$ for $c\in\mathbb{R}.$

The result on component sizes, in contrast, was not so easy to generalize. The challenge was in coming up with a higher dimensional analog of a component in a simplicial complex. The breakthrough came in [9] with the introduction of the shadow. The underlying motivation was that, in a sparse graph, a giant component exists if and only if the shadow includes a positive fraction of all the possible edges. With this in mind, the behavior of $\textnormal{Sh}(Y(n,c/n)),$ the $d$-dimensional shadow (or $d$-shadow) of $Y(n,p),$ was investigated in [10], and these were the key findings there. One, $|\textnormal{Sh}(Y(n,p))|$ changes from $o(n^{d+1})$ to $\Theta(n^{d+1})$ at $p=c_{*}/n,$ where $c_{*}$ equals $1$ when $d=1,$ but is strictly greater than $1$ for $d\geq 2.$ Two, for $c>c_{*},$ $|\textnormal{Sh}(Y(n,c/n))|/\binom{n}{d+1}\to(1-t(c))^{d},$ where $t(c)$ is the smallest root in $(0,1)$ of the equation

Note that (2) matches (1) when $d=1.$ Also, for $c>1,$ $|\textnormal{Sh}(Y_{1}(n,c/n))|=\Theta(n^{2}),$ while $|L_{n}(c)|=\Theta(n).$

The pioneering work in the second strand was done by Frieze [4]. He showed that, given a complete graph on $n$ vertices with uniform $[0,1]$ weights on each edge, the expected sum of weights in the MST converges to the constant $\zeta(3)\approx 1.2,$ as $n\to\infty.$ Note that this graph is the $d=1$ case of our $(\mathcal{K}_{n},w_{u})$ model. Recently, [5] showed that a similar result exists even for the $d$-MSA of $(\mathcal{K}_{n},w_{u})$ for $d\geq 2.$

Separately, [12] studied the extremal weights in the $d$-MSA of $(\mathcal{K}_{n},w_{u}).$ An illustration of a main result there is given in Figure 2. It shows two distinct $(n,d)$ scenarios. In both, a plot of the values in $\{nw_{u}(\sigma)-d\log(n)+\log(d!):\sigma\in M_{n}\}$ is given. This choice of scaling gives more prominence to the extremal weights, which in the two plots are the values on the extreme right. The result in [12] states that these extremal values converge to a Poisson point process, while the rest go to $-\infty.$

We now briefly describe how we combine the different facts stated above for proving our main result. Let $\sigma$ be an arbitrary $d$-face in $(\mathcal{K}_{n},w_{u})$ and suppose $w_{u}(\sigma)=s>0.$ Let $\mathcal{L}_{n}(s^{-}):=\{\sigma\in\mathcal{K}_{n}:w(\sigma)<s\}.$ Clearly, the distributions of $\mathcal{L}_{n}(s^{-})$ and $Y(n,s$), and hence of their shadows, are identical. Now, [12, Lemma 32] states that $\sigma$ belongs to the $d$-MSA of $(\mathcal{K}_{n},w_{u})$ if and only if it does not lie in the shadow²²2The word ‘shadow’ is not used in [12], but the result can be interpreted in terms of the shadow in a straightforward fashion. of $\mathcal{L}_{n}(s^{-}).$ Given that $\sigma$ could potentially have been any of the $d$-faces outside of $\mathcal{L}_{n}(s^{-}),$ the probability that it belongs to the $d$-MSA must then equal one minus the shadow density of $\mathcal{L}_{n}(s^{-}).$ By shadow density, we mean the shadow’s size divided by the total number of potential $d$-faces. Based on this and the shadow density results from [10], the desired result is then easy to see.