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

The Shadow Knows: Empirical Distributions of Minimal Spanning Acycles and Persistence Diagrams of Random Complexes, Discrete Analysis 2023:2, 18 pp.

This paper deals with the following natural and important question. Suppose that the edges of the complete graph are given random weights, with each weight chosen uniformly from $[0,1]$ and all weights independent. A famous result of Frieze is that the expected total weight of the minimum spanning tree converges to $\sum_{n=1}^\infty n^{-3}=\zeta(3)$. The authors explore this result further with a view to determining the limiting empirical distribution of the weights of the edges in the minimal spanning tree. They also consider a higher-dimensional analogue of the problem in which spanning trees are replaced by Q-acyclic complexes, or minimum spanning acycles, which are complexes $C$ such that the Betti number $\beta_p(C)$ is 1 when $p=0$ (this says that the complex is connected) and 0 for $p>0$ (this says that the complex has no higher-dimensional “holes” of any kind).

In two dimensions we can think of the set-up as follows. Begin by taking the complete graph on $n$ vertices, thought of as a 1-dimensional simplicial complex. This has many cycles, and thus a great deal of 1-dimensional homology, but we can get rid of this homology if we add faces, in the form of 2-simplices, just as for graphs if we start with $n$ isolated vertices, we can reduce the number of components to the minimum by adding edges. If each 2-simplex is given an independent weight chosen uniformly from $[0,1]$, then the minimum spanning acycle is the minimum total weight of a set of 2-simplices such that the resulting simplicial complex has trivial 1-dimensional homology. More generally, we start with all $(d-1)$-simplices, give weights to the $d$-simplices, and take the minimum total weight of a set of $d$-simplices such that the $(d-1)$-dimensional homology group is trivial. Minimal spanning acycles have been studied in recent years in both combinatorial and probabilistic contexts.

Since a spanning tree needs $n-1$ edges, one might intuitively expect that a typical weight in a minimal spanning tree would have order of magnitude $n^{-1}$. And this indeed turns out to be the case both for minimal spanning trees and minimal spanning acycles. Thus, if $M_n$ is a minimal spanning acycle, one of the empirical measures examined in this paper is $\mathbb E_{\sigma\in M_n}\delta_{nw(\sigma)}$, where $\delta_u$ denotes the point measure at $u$ and $w(\sigma)$ is the weight of the $d$-simplex $\sigma$. In their main theorem, the authors give an explicit description of the limiting distribution of this measure and establish a suitable convergence result. (Specifically, they show convergence in the Kolmogorov metric in $L^q$, which is quite a strong form of convergence.)
.
This result uses a well-known connection between the minimum spanning tree/acycle and the evolution of random graphs/complexes. To build the minimum spanning tree one uses Kruskal’s algorithm, which repeatedly picks the minimal-weight edge that joins two components (or equivalently, does not create a cycle) until a tree is obtained. This algorithm generalizes easily to higher dimensions as well. The probability that a simplex is added relates to the structure of the homology of the complex built so far.

This connection has been used in several papers. However, it is a non-trivial task to make use of it for the results of this paper, which provide an interesting contribution to our understanding of the typical behaviour of minimum spanning trees and acycles.