1 Introduction

1.1 Background

Many problems in physics, economics, biology, and mechanics involve the modeling of extremely large and intricate systems. With such high levels of complexity, understanding these systems from their microscopic structure is often intractable. In such cases it may make more sense to view them as random topological spaces with certain probability parameters. This framework enables us to make a variety of powerful conclusions about how these systems will generally behave. Indeed, as mentioned in [15], the study of random geometric and topological spaces has on several occasions lent intuition to the extraordinary prevalence of certain properties amongst mathematical objects.

The purpose of this work is to understand the homological behavior of a generalized model for random simplicial complexes, mentioned in [15] and recently explored in [5]. We define \(X(n, p_1, p_2, \ldots )\) to be the probability distribution over simplicial complexes on vertex set \([n] = \{1, \ldots , n\}\) whose distribution on 1-skeletons agrees with \(G(n, p_1)\). The distribution on higher dimensional skeletons is constructed inductively: for an integer \(k > 1\), any k-simplex whose boundary is contained in our complex is added with probability \(p_k\). This provides a measure on all simplicial complexes on n vertices. Two well-studied structures, random k-complexes (Linial–Meshulam complexes for \(k=2\) and Meshulam–Wallach complexes for higher d) and clique complexes, are realized as \(X(n, 1, \ldots , 1, p_k, 0, \ldots )\) and \(X(n, p, 1, \ldots )\).

The study of random topological spaces began with random graphs, the seminal example of which is G(n, p), the Erdős–Rényi model. Given a probability parameter \(p \in (0,1)\), typically a function of n, we consider a graph on n vertices where every edge between two vertices of G is added independently with probability p. This defines a probability measure on the set of all simple graphs on n vertices and we say G(n, p) to indicate a random graph with law G(n, p).

Most random topology results pertain to the asymptotic behavior of a model, i.e., what happens as the number of vertices tends to infinity. Given some property \({\mathcal {A}}\) of simplicial complexes, we say that \(X \in {\mathcal {A}}\)with high probability, or w.h.p., if

$$\begin{aligned} \lim _{n\rightarrow \infty } {\mathbb {P}}\left[ X \in {\mathcal {A}} \right] = 1. \end{aligned}$$

These results frequently involve asymptotic notation worth briefly covering. Given two functions f(n) and g(n), we say f if little-o of g, or \(f(n) = o \left( g(n) \right) \), if \(\lim _{n \rightarrow \infty } \frac{f(n)}{g(n)} = 0\). We say f is big-O of g, or \(f(n) = O \left( g(n) \right) \), if \(\limsup _{n \rightarrow \infty } \frac{|f(n) |}{g(n)} < \infty \) Finally, we say f is little-\(\omega \) of g, or \(f(n) = \omega \left( g(n) \right) \), if \(\lim _{n \rightarrow \infty } \bigl |\frac{f(n)}{g(n)}\bigr | = \infty \). Observe that all asymptotic terms in these results are relative to the number of vertices, n. A formative result of random graph theory, proven by Erdős and Rényi, was the sharp threshold for connectivity in G(n, p).

Erdős–Rényi Theorem [8, Thm.] If \(p \ge (\log n +\omega (1)) / n\) then G(n, p) is w.h.p. connected, and if \(p \le (\log n- \omega (1)) / n\) then G(n, p) is w.h.p. disconnected.

Significant work has been done on the behavior of random graphs since [8]. Providing a higher dimensional analog, recent study has been focused on several models for random simplicial complexes. One of the most natural questions to ask, results in this field often depict the homological or cohomological behavior of a complex. Even the connectivity threshold for G(n, p) is a statement about the 0-homology of graphs: \(H_0(G, {\mathbb {Z}}) = {\mathbb {Z}}^m\) where m is the number of connected components of G.

In this context there are two different types of phase transitions that occur in these models. For any given dimension, there can be a threshold at which homology or cohomology changes from trivial to nontrivial. Conversely, there can be a threshold at which it goes from nontrivial to trivial, or vanishes. Extensive work has been done to establish lower bounds on the thresholds at which homology appears and upper bounds on the thresholds at which homology vanishes for various models.

A high-dimensional analog to G(n, p) is \(Y_k(n, p)\), the model for random k-dimensional simplicial complexes. We begin with a complex on n vertices and full \((k-1)\)-skeleton, then add every possible k-face independently with probability p. Linial and Meshulam initially considered when \(k=2\) in [19], establishing a sharp threshold for when \({\mathbb {Z}}_2\)-homology disappears in the first dimension. Babson, Hoffman, and Kahle later looked at the fundamental group of this model in [3], proving a threshold where \(\pi _1\left( Y_2(n,p)\right) \) transitions w.h.p. from hyperbolic to trivial.

Meshulam and Wallach [21] extended the result in [19] to \(H_{k-1} \left( Y_k(n,p), {\mathbb {Z}}_q \right) \) for any dimension k. Their work was followed by [12], where Hoffman, Kahle, and Paquette demonstrated an upper bound for the vanishing of integer homology in this model. It is also natural to ask how \(H_k(Y_k(n,p) , {\mathbb {Z}})\) behaves in these complexes. Kozlov proved a threshold for the appearance of k-homology in [18]. Aronshtam and Linial [1], joined by Łuczak and Meshulam [2], extended this work to bounds on when the top dimension of this complex is in fact collapsible. Peled and Linial impressively established a tight bound for the top homology for every k in [20].

Another model of interest is the random clique complex model, X(n, p). Just as in our own model, the distribution of the 1-skeleton is identical to G(n, p), but in this case the edges dictate the entire complex. Given some \(X \overset{\mathrm{dist}}{=}X(n,p)\), X contains the k-simplex spanned by a set of \(k+1\) vertices only if the vertices form a complete subgraph in X, called a \((k+1)\)-clique. For any dimension k, Kahle established in [13] and [14] sharp thresholds for p for which there will be nontrivial kth cohomology. This shows that, outside the critical windows of these thresholds, cohomology will w.h.p. be nontrivial in just one dimension, the middle dimension of the complex. Kahle has proved numerous results concerning the behavior of X(n, p), such as establishing a central limit theorem for the distribution of Betti numbers \(\beta _k = \text {dim}\left( H^k(X,{\mathbb {Q}})\right) \) with Meckes [17].

As we noted before, all these complexes are special cases of \(X(n, p_1, p_2, \ldots )\). The random graph model G(n, p) is identical to \(X(n, p, 0, \ldots )\), \(Y_k(n,p)\) corresponds to \(X(n, 1, \ldots , 1, p_k=p, 0, \ldots )\), and clique complexes are the case \(X(n, p_1, 1, \ldots )\). In fact, many of our results are achieved through a reworking of frameworks laid down in [13, 14]. This appears to be the natural bridge between these models, and we show that often the results for specific models may be extended to this broader construction. Through this process we exhibit cohomological behavior unique to this model.

Significant work has been done on this model concurrently by Costa and Farber, where they introduce the additional parameter \(p_0\) for adding vertices of [n]. In [5] they address the containment problem: given an r-dimensional subcomplex S, they define a convex set \( \overline{{\mathcal {M}}} (S) \subset {\mathbb {R}}^{r+1}\) such that if \((\alpha _0, \ldots , \alpha _k) \in \overline{{\mathcal {M}}}(S)\), then X w.h.p. contains a subcomplex isomorphic to S. In [6, 7], they look at the fundamental group of these complexes, establishing regimes in which it w.h.p. trivial, nontrivial, and specifically has property (T). They also show cohomology is concentrated in a critical dimension, showing bounds on the Betti numbers in this and nearby dimensions, as well as bounding the size of possible cycles in higher dimensions.

1.2 Statement of Results

Notation. We write \(X \overset{\mathrm{dist}}{=}X(n, p_1, p_2, \ldots )\) to indicate that X is chosen from the distribution \(X(n, p_1, p_2, \ldots )\).

Our theorems deal with the \((k-1)\)th homology or cohomology of \(X(n, p_1, p_2, \ldots )\). As mentioned above there are two types of phase transitions, and we work to develop bounds on the thresholds for both. Since the \((k-1)\)th (co)homology of a simplicial complex depends only on its k-skeleton, these theorems only depend on probabilities \(p_1\) through \(p_k\). The primary open problem from this work concerns the \((k-1)\)th homology of our complexes when \(p_k = 1\), which we discuss following our statement of results.

As with clique complexes, the \((k-1)\)-cohomology of \(X(n, p_1, p_2, \ldots )\) has two phase transitions. We can think of this as corresponding to two disjoint hypersurfaces in \(\alpha \)-space. Cohomology will be trivial for sufficiently small or sufficiently large probabilities \(p_i\), corresponding to large and small \(\alpha _i\), respectively. The range of values between these two hypersurfaces is where nontrivial cohomology is exhibited.

The following result establishes when the probabilities are sufficiently large that we will have trivial cohomology.

Theorem 1.1

Let \(X \overset{\mathrm{dist}}{=}X(n, p_1, p_2, \ldots )\) with \(p_i = n^{-\alpha _i}\) and \(\alpha _i \ge 0\) for all i. If

$$\begin{aligned} \sum _{i=1}^{k} \alpha _i \left( {\begin{array}{c}k\\ i\end{array}}\right) < 1 \end{aligned}$$
(1)

then w.h.p. \(H^{k-1} ( X, {\mathbb {Q}}) = 0\).

We prove this threshold is essentially the best possible by establishing nontrivial cohomology on the other side of (1). Moreover, the second regime for which cohomology exists is establishes the potential for \(H^k(X,{\mathbb {Q}}) \ne 0\) simultaneously for several k.

Theorem 1.2

Let \(X \overset{\mathrm{dist}}{=}X(n, p_1, p_2, \ldots )\) with \(p_i = n^{-\alpha _i}\), \(\alpha _i \ge 0\) for all i, and

$$\begin{aligned} 1 \le \sum _{i=1}^{k} \alpha _i \left( {\begin{array}{c}k\\ i\end{array}}\right) . \end{aligned}$$
(2)

If

$$\begin{aligned} \sum _{i=1}^{k-1} \alpha _i \left( {\begin{array}{c}k-1\\ i\end{array}}\right) < 1, \end{aligned}$$
(3)

then w.h.p. \(H^{k-1} ( X, {\mathbb {Q}} ) \ne 0\). Furthermore, when \(\alpha _k >0 \) we can relax the condition in (3) to

$$\begin{aligned} \sum _{i=1}^{k-1} \alpha _i \left( {\begin{array}{c}k+1\\ i+1\end{array}}\right) < k+1. \end{aligned}$$
(4)

A common question to ask concerning phase transitions is what happens at the boundary between phases. Given a complex X, we let \(\beta _k\) denote the kth Betti number ofX, given by \(\beta _k : = \text {dim} \left( H^k (X, {\mathbb {Q}}) \right) \). Allowing the \(p_i\) to be more varied functions of n, we identify this critical region and establish a limit theorem for the Betti number. Combined with Theorems 1.1 and 1.2, this proves a threshold for vanishing cohomology for all possible \(p_i\).

Theorem 1.3

Let \(X \overset{\mathrm{dist}}{=}X(n,p_1, p_2, \ldots )\) with

$$\begin{aligned} p_i = \left( \rho _1 \log n + \rho _2 \log \log n + c \right) ^{\nu _i}n^{-\alpha _i} \end{aligned}$$

such that

$$\begin{aligned} \rho _1 = k - \sum _{i=1}^{k-1} \alpha _i \left( {\begin{array}{c}k\\ i+1\end{array}}\right) \text {, }\; \rho _2 = \sum _{i=1}^{k-1} \nu _i \left( {\begin{array}{c}k\\ i+1\end{array}}\right) \; \text { and }\;\sum _{i=1}^k \alpha _i \left( {\begin{array}{c}k\\ i\end{array}}\right) = \sum _{i=1}^k \nu _i \left( {\begin{array}{c}k\\ i\end{array}}\right) = 1. \end{aligned}$$

Then \(\beta _{k-1}\) approaches a Poisson distribution

$$\begin{aligned} \beta _{k-1} \rightarrow {{\,\mathrm{Poi}\,}}(\mu ) \end{aligned}$$

with mean

$$\begin{aligned} \mu = \frac{\rho _1 ^{\rho _2} e^{-c}}{k!}. \end{aligned}$$

We also provide a lower bound on the threshold where homology first appears in our complex. This bound, combined with the second part of Theorem 1.2, is essentially the best possible when \(\alpha _k > 0\).

Theorem 1.4

Let \(X \overset{\mathrm{dist}}{=}X(n, p_1, p_2, \ldots )\) with \(p_i = n^{-\alpha _i}\) and \(\alpha _i \ge 0\) for all i. If

$$\begin{aligned} k+1 < \sum _{i=1}^{k-1} \alpha _i \left( {\begin{array}{c}k+1\\ i+1\end{array}}\right) \end{aligned}$$
(5)

then w.h.p. \(H_{k-1} (X, {\mathbb {Z}}) = 0\).

Repeated application of our theorems for each dimension will often fully describe the cohomology of our random complex. Specifically when the set of \(p_i = n^{-\alpha _i}\) parameters fall within the specified regimes of Theorems 1.1, 1.2, and 1.4.

Example 1.5

Consider \(X \overset{\mathrm{dist}}{=}X(n, p_1, p_2, \ldots )\) with \(p_i = n^{-\alpha _i}\) and

$$\begin{aligned} (\alpha _1, \alpha _2, \alpha _3, \ldots ) = \left( \frac{1}{5}, \frac{1}{5} , \frac{2}{5}, 0 , 0, \ldots \right) . \end{aligned}$$

Then

$$\begin{aligned} \sum _{i=1}^2 \alpha _i \left( {\begin{array}{c}2\\ i\end{array}}\right) = \frac{3}{5} < 1 \end{aligned}$$

so w.h.p. \(H^1 (X, {\mathbb {Q}}) = 0\) by Theorem 1.1.

$$\begin{aligned} \sum _{i=1}^3 \alpha _i \left( {\begin{array}{c}3\\ i\end{array}}\right) = \frac{7}{5} > 1\; \text { and }\; \sum _{i=1}^{3-1} \alpha _i \left( {\begin{array}{c}3-1\\ i\end{array}}\right) = \frac{3}{5} < 1, \end{aligned}$$

so by Theorem 1.2 w.h.p. \(H^2 (X, {\mathbb {Q}}) \ne 0\). Finally,

$$\begin{aligned} \sum _{i=1}^{4-1} \alpha _i \left( {\begin{array}{c}4+1\\ i+1\end{array}}\right) = 6 > 4+1, \end{aligned}$$

so by Theorem 1.4, \(H_3 (X, {\mathbb {Z}}) = 0\) w.h.p. Moreover, a simple bound using the last equation allows us to use the theorem to deduce \(H_k(X, {\mathbb {Z}}) = 0\) w.h.p. for all \(k \ge 3\).

The proof of Theorem 1.1 is handled in Sects. 3 and 4. The inequality (1) precisely ensures every \((k-1)\)-simplex of X is w.h.p. contained in a k-simplex, so no single face generates a nontrivial cocyle in \(H^{k-1}(X)\). With this condition satisfied we prove the result by applying [4, Theorem 2.1], a result connecting spectral gap theory and the homology of simplicial complexes and presented in Sect. 2. Most of the work lies in showing the various hypotheses of the theorem are met by our complexes, for which we use [11, Theorem 1.1], a tool for bounding the spectral gap of Erdős–Rényi random graphs.

Theorem 1.2 is proven in Sects. 5 and 6. The statement for the range defined by (2) and (3) is shown by exhibiting that our complex will have far more \((k-1)\)-dimensional faces than those in adjacent dimensions, so the kernel of the coboundary map is very large. In fact, the second moment argument used in the proof yields the stronger result that within this range of values our Betti number \(\beta _{k-1}\) will grow polynomially in n. We write \(X \sim Y\) with high probability if for all \(\epsilon > 0\), we have

$$\begin{aligned} \lim _{n \rightarrow \infty } {\mathbb {P}}\left[ (1-\epsilon ) \le Y/X \le (1+ \epsilon )\right] \rightarrow 1. \end{aligned}$$

Using this notation, we have a strong handle on the size of cohomology within this window.

Theorem 1.6

Let \(X \overset{\mathrm{dist}}{=}X(n,p_1, p_2, \ldots )\) with \(p_i = n^{-\alpha _i}\) and \(\alpha _i \ge 0\) for all i and \(\beta _{k-1}\) be the \((k-1)\)th Betti number. If

$$\begin{aligned} \sum _{i=1}^{k-1} \alpha _i \left( {\begin{array}{c}k-1\\ i\end{array}}\right)< 1 < \sum _{i=1}^{k} \alpha _i \left( {\begin{array}{c}k\\ i\end{array}}\right) , \end{aligned}$$

then w.h.p. \(\beta _{k-1}\) is growing polynomially according to

$$\begin{aligned} \beta _{k-1} \sim \left( {\begin{array}{c}n\\ k\end{array}}\right) n^{-\sum _{i=1}^{k-1} \alpha _i \left( {\begin{array}{c}k\\ i+1\end{array}}\right) }. \end{aligned}$$

The result when (2) and (4) hold extends the argument presented in the example at the end of this section: showing our complex will w.h.p. contain certain subcomplexes that generate nontrivial homological cycles.

In Sect. 7 we prove Theorem 1.3. The strict requirements on our \(p_i\) define a range where we have a nonzero but finite expected number of maximal \((k-1)\)-faces. A factorial moment argument shows this number approaches a limiting distribution, a slight adaptation of the work in Sect. 4 then proves these faces generate the only nontrivial cocycles of dimension \(k-1\).

Finally, the proof of Theorem 1.4 is found in Sect. 8. The subset (5) defines when our complex will w.h.p. not contain the boundary of a k-simplex. We show this is the most likely subcomplex to appear in X that generates a \((k-1)\)-cycle. Thus, when X w.h.p. does not contain the boundary of a k-simplex it will have no \((k-1)\)-cycles.

1.3 Discussion

Primarily our results concern when \(p_i = n^{- \alpha _i}\) with \(\alpha _i \ge 0\) or \(p_i = 0\) (here we say \(\alpha _i = \infty \)). This was done to make the theorem statements as concise as possible. Our threshold results extend easily to when \(p_i\) are more varied functions of n. If \(p_i = \omega _i n^{-\alpha _i}\) with \(\omega _i(n) \rightarrow \infty \) and \(\omega _i(n) = o(n^{\epsilon })\) for all \(\epsilon >0\), then Theorems 1.1, 1.2, and 1.4 still hold provided the \(\alpha _i\) do not lie on the boundary between two thresholds.

Our work on this multi-parameter model confirms it as the natural bridge between X(n, p) and \(Y_k(n,p)\). Our theorems imply the analogous results for the rational cohomology of these complexes. However, it is important to note for both these models there are results concerning the vanishing of homology over arbitrary field coefficients. The boundary between Theorems 1.1 and 1.2 is sharp when \(p_i = n^{-\alpha _i}\), and combined with Theorem 1.3 establishes a sharp upper bound for vanishing cohomology that encompasses the analogous results for clique complexes [14, Thm. 1.1] and Linial–Meshulam complexes [21, Thm. 1.1].

While our bounds on the threshold where homology vanishes are seen to be close to optimal, we have not fully characterized the threshold for appearing homology. Our bounds for when \(H_{k-1}\) first becomes nontrivial are good so long as \(\alpha _k >0\), and Kahle proved the correct bound for clique complex case in [13], but we have been unable to generalize his arguments or find another method. For now we leave this as an open problem.

Open Problem 1 What is the correct threshold for the appearance of \(H_{k-1} \left( X, {\mathbb {Z}}\right) \) when \(\alpha _k = 0\)? I.e., what hyperplane for \(\alpha _1, \ldots , \alpha _{k-1}\) determines whether homology is trivial or nontrivial?

Note that \(\alpha _k = 0\), or \(p_k = 1\), implies X cannot contain the unfilled boundary of a k-simplex, the question likely reduces to understanding the smallest homological cycle that can appear in X. We suspect the answer is determined, perhaps uniquely, by the largest \(l < k\), such that \(p_l \ne 1\). Meanwhile, the Linial–Meshulam and Meshulam–Wallach models begin with nontrivial \((k-1)\)-homology, and \(p_{k+1}= 0\) so our bounds for \(H_k(Y_k(n,p))\) are roughly in line with the main results, though we only consider probability parameters that are powers of n.

Another open problem concerns when integer homology vanishes in a specific dimension.

Open Problem 2 Does (1) in Theorem 1.1 imply that w.h.p. \(H_{k-1}(X, {\mathbb {Z}}) = 0\)?

We understand the phase transition for \(H^{k-1}(X, {\mathbb {Q}})\) and have reason to believe our results should hold for integer homology, but our present arguments are insufficient. We note this question is also currently unsolved for X(n, p). Morevoer, in [16] Kahle, Lutz, Newman, and Parsons mention that experimentally, through many trials X(n, p) never exhibited torsion in homology.

Although X(n, p) and \(Y_k(n,p)\) seem like quite different instances of \(X(n, p_1, p_2, \ldots )\), they do not fully characterize our model. We often observe asymptotic behavior dramatically different from either one. In fact, for any fixed integer l we can find some k such that the range of values for \(p_i\) defined by applications of Theorem 1.2 in dimensions k through \(k+l\) is nontrivial. This yields a result exemplifying the differences in this model.

Corollary 1.7

Let \(X \overset{\mathrm{dist}}{=}X(n, p_1, p_2, \ldots )\) with \(p_i = n^{-\alpha _i}\), for any integer l there exists an integer k and an open set of \(\alpha _i\) for which X w.h.p. has nontrivial cohomology in dimensions k through \(k+l\).

Proof

The result follows directly from Theorem 1.2. Considering (2), if

$$\begin{aligned} 1 \le \sum _{i=1}^k \alpha _i \left( {\begin{array}{c}k\\ i\end{array}}\right) \end{aligned}$$

for some k, then

$$\begin{aligned} 1 \le \sum _{i=1}^j \alpha _i \left( {\begin{array}{c}j\\ i\end{array}}\right) \end{aligned}$$

for all \(j > k\). Similarly, considering (4), if

$$\begin{aligned} \sum _{i=1}^{k-1} \alpha _i \left( {\begin{array}{c}k+1\\ i+1\end{array}}\right) < k+1, \end{aligned}$$

then

$$\begin{aligned} \sum _{i=1}^{j-1} \alpha _i \left( {\begin{array}{c}j+1\\ i+1\end{array}}\right) < j+1 \end{aligned}$$

for all \(j<k\).

We will construct a simple, far from optimized open set. We fix our l and let k be sufficiently large such that \(k > l+2\). If

$$\begin{aligned} \frac{1}{k+1} < \alpha _1, \end{aligned}$$

then

$$\begin{aligned} 1 < \sum _{i=1}^{k+} \alpha _i \left( {\begin{array}{c}k+1\\ i\end{array}}\right) . \end{aligned}$$

Moreover, if

$$\begin{aligned} \alpha _1 < \frac{1}{k}, \end{aligned}$$

then

$$\begin{aligned} \alpha _1 \left( {\begin{array}{c}k+l + 2\\ 2\end{array}}\right) < k + l +2. \end{aligned}$$

Thus, so long as \(p_i \ne 1\) for \(k +1 \le i \le k+l + 1\) and

$$\begin{aligned} \sum _{i=2}^{k+l} \alpha _i \left( {\begin{array}{c}k+l+2\\ i+1\end{array}}\right) < 1, \end{aligned}$$

our result follows from Theorem 1.2. \(\square \)

1.4 Low-Dimensional Example

We present a low-dimensional example to give some intuition for where the inequalities in our theorems come from, as well as illustrate the potential for nontrivial cohomology in multiple dimensions simultaneously.

Example 1.8

Let \(X \overset{\mathrm{dist}}{=}X(n,p_1, p_2, \ldots )\), if

$$\begin{aligned} \alpha _2,\alpha _3 >0,\; 6\alpha _1 + 4 \alpha _2 < 4,\; \text { and } \;1 \le 2\alpha _1 + \alpha _2 \end{aligned}$$

then w.h.p. \(H^1(X, {\mathbb {Q}}) \ne 0\) and \(H^2(X, {\mathbb {Q}}) \ne 0\).

Proof

Within this proof, and later in Sect. 5, we consider the appearance of certain subcomplexes in X. First, we establish the presence of triangles with an unfilled 2-face whose first edge, determined lexicographically, is not part of any 2-face in X. Our complex is defined on the vertex set [n], and for any \(j \in \left( {\begin{array}{c}[n]\\ 3\end{array}}\right) \) we let \(A_j\) denote the event that the vertex set corresponding to j forms such a subcomplex. Using independence, this has probability

$$\begin{aligned} {\mathbb {P}}\left[ A_j \right] = p_1^3 (1-p_2 ) (1-p_1^2p_2)^{n-3}. \end{aligned}$$

The first two terms require the three edges are in X while the 2-simplex itself is not present. The last term ensures our first edge is maximal, i.e. does not form a 2-simplex with any of the \(n-2\) remaining vertices.

Letting \(M_1\) denote the number of such subcomplexes in X, by linearity of expectation

$$\begin{aligned} {\mathbb {E}}\left[ M_1\right] = \sum _{j \in \left( {\begin{array}{c}[n]\\ 3\end{array}}\right) } {\mathbb {P}}\left[ A_j\right] = \left( {\begin{array}{c}n\\ 3\end{array}}\right) p_1^3(1-p_2 ) (1-p_1^2p_2)^{n-3}. \end{aligned}$$

Using standard first moment techniques we see, for large enough n,

$$\begin{aligned} {\mathbb {E}}\left[ M_1\right]&\approx \frac{n^3}{6}\, n^{-3\alpha _1} ( 1 - p_2 )\left( 1 - n^{-(2\alpha _1 + \alpha _2)}\right) ^{n} \\&\approx \frac{1}{6}\,\, n^{3-3\alpha _1} \left( 1 - p_2 \right) e^{-n^{1 - (2\alpha _1 + \alpha _2)}}. \end{aligned}$$

Since \(\alpha _2 > 0\), we have that \(1- p_2 > 0\). The last two terms are therefore \(\Theta (1)\) when \(1 \le 2\alpha _1 + \alpha _2\), then \(\alpha _1 < 1\) implies \({\mathbb {E}}[M_1] \rightarrow \infty \). Second moment arguments, detailed in Appendix A, then show that w.h.p. \(M_1 > 0\).

We now show the existence of empty tetrahedrons, the first 2-face of which is maximal. For each \(l \in \left( {\begin{array}{c}[n]\\ 3\end{array}}\right) \), let \(B_l\) be the event that the vertices l form such a subcomplex in X. Similar considerations show

$$\begin{aligned} {\mathbb {P}}\left[ B_l \right] = p_1^6 p_2^4 (1-p_3 ) \left( 1-p_1^3 p_2^3 p_3 \right) ^{n-4}. \end{aligned}$$

Letting \(M_2\) denote the total number of such subcomplexes in X, linearity of expectation shows

$$\begin{aligned} {\mathbb {E}}\left[ M_2 \right] = \sum _{l \in \left( {\begin{array}{c}[n]\\ 4\end{array}}\right) } {\mathbb {P}}[B_l] = \left( {\begin{array}{c}n\\ 4\end{array}}\right) p_1^6 p_2^4 (1-p_3) \left( 1-p_1^3 p_2^3 p_3 \right) ^{n-4}. \end{aligned}$$

It follows that if \(\alpha _3 > 0\), \(6 \alpha _1 + 4 \alpha _2 < 4\), and \(1 \le 3\alpha _1 + 2 \alpha _2 +\alpha _3\), then \({\mathbb {E}}\left[ M_2\right] \rightarrow \infty \). Second moment calculations establish that w.h.p. \(M_2 > 0\).

Combining the two sets of requirements on \(p_i\) yields that whenever \(p_2, p_3 \ne 1\), \(1\le 2\alpha _1 +\alpha _2\), and \(6 \alpha _1 + 4 \alpha _2 < 4\) w.h.p. \(M_1, M_2>0\). Each such subcomplex can be seen to generate a nontrivial \({\mathbb {Z}}\)-summand in the 1- and 2-homology, respectively. Thus w.h.p. \(H_1(X, {\mathbb {Z}}) \ne 0\) and \(H_2(X,{\mathbb {Z}}) \ne 0\), and our result follows by the Universal Coefficients Theorem, covered in the next section. \(\square \)

2 Topological Preliminaries

2.1 Basic Definitions

Before proceeding, we lay out the definitions and theorems critical to our work. For further reference, specifically regarding the homology and cohomology of simplicial complexes, we direct the reader to [10].

A crucial definition for our work is the link of a subcomplex. Given a simplicial complex X and a k-dimensional simplex \(\sigma \) in X, we define the link of\(\sigma \)inX, denoted \(\text {lk}_X(\sigma )\), to be a new simplicial complex with the vertex set corresponding to the vertices of X that form a \((k+1)\)-face with \(\sigma \). We then construct the new simplicial complex by adding the \((l-1)\)-face corresponding to a set of vertices \(v_1, \ldots , v_l\) precisely when the vertices \(\sigma \cup \{v_1 , \ldots , v_l \}\) comprise a \((k+l)\)-face in X.

A simplicial complex X is purek-dimensional if every face of X is contained in a k-dimensional face.

Finally, let G be some graph of ordered vertices with minimum degree at least 1. Define D and A to be the associated degree and adjacency matrices of G, respectively. We define the normalized Laplacian ofG, denoted \({\mathcal {L}}\), by

$$\begin{aligned} {\mathcal {L}} = I - D^{-1/2} A D^{-1/2}. \end{aligned}$$

For our work we look at the spectral gap of G (denoted \(\lambda _2 [G]\)), which is the absolute value of the smallest nonzero eigenvalue of the normalized Laplacian of G.

2.2 Useful Theorems

There are several established theorems we use in our work.

While not explicitly used in this work, the Universal Coefficient Theorem provides the link between the homology and cohomology over \({\mathbb {Z}}\) and various finite fields. Any statement about rational homology can be extended to cohomology, and vice versa. Moreover, a \({\mathbb {Z}}\)-summand of \(H_k \left( X, {\mathbb {Z}}\right) \) necessarily corresponds to a \({\mathbb {Q}}\)-summand of \(H_k(X, {\mathbb {Q}})\), and any torsion will correspond to nontrivial homology of the finite field with the same number of elements. Within our work, the language of a theorem statement primarily corresponds to whichever group we worked with in the proof. Finally, we note that the vanishing of integer homology is a much stronger statement than the vanishing of rational homology.

With the definitions established we introduce the first of the two theorems instrumental in our proof of Theorem 1.1. We use a special case of Theorem 2.1 in a paper by Ballmann and Świątkowski [4].

Cohomology Vanishing Theorem. To prove vanishing cohomology we employ a result of Garland [9]. Paraphrasing [4, Thm. 2.1], let X be a pure D-dimensional finite simplicial complex such that for every \((D-2)\)-dimensional face \(\sigma \), the link \(\text {lk}_X (\sigma )\) is connected and has spectral gap

$$\begin{aligned} \lambda _2 [\text {lk}_X (\sigma ) ] > 1- \frac{1}{D}. \end{aligned}$$

Then \(H^{D-1} (X , {\mathbb {Q}}) = 0\).

We note that since X is stipulated to be pure D-dimensional, the link of any \((D-2)\)-face will be of dimension 1. The spectral gaps of these link complexes are therefore well defined.

To produce the necessary estimates on these gaps we then need the help of the main result in [11], established by Hoffman, Kahle, and Paquette. We present it here as a concise statement sufficient for our needs, noting the actual result yields more general and precise results.

Spectral Gap Theorem [11, Thm. 1.1] Fix a \(\delta > 0\) and let \(G \overset{\mathrm{dist}}{=}G(n, p)\) with \(p \ge \frac{(1+\delta ) \log n}{n}\). Then G is connected and

$$\begin{aligned} \lambda _2 (G) > 1 -o(1) \end{aligned}$$

with probability \(1 - o(n^{-\delta })\).

3 Calculating Maximal Faces

We call a \((k-1)\)-face in a simplicial complex maximal if it is not contained in any k-simplex. These subcomplexes naturally play an important role in homology, their characteristic functions generate \((k-1)\)-cocycles. We let \(N_{k-1}\) denote the number of maximal \((k-1)\)-faces in X. Recall our complex has vertex set [n], we use \(j \in \left( {\begin{array}{c}[n]\\ k\end{array}}\right) \) to denote a set of k vertices of [n]. Letting \(C_j\) be the event that the vertices of j span a maximal \((k-1)\)-simplex, it follows that

$$\begin{aligned} N_{k-1} = \sum _{j \in \left( {\begin{array}{c}[n]\\ k\end{array}}\right) } 1_{C_j}. \end{aligned}$$

Lemma 3.1

For any \(j \in \left( {\begin{array}{c}[n]\\ k\end{array}}\right) \),

$$\begin{aligned} {\mathbb {P}}\left[ C_j \right] = \left( \prod _{i=1}^{k-1} p_i^{\left( {\begin{array}{c}k\\ i+1\end{array}}\right) } \right) \left( 1 - \prod _{i=1}^{k} p_i^{\left( {\begin{array}{c}k\\ i\end{array}}\right) } \right) ^{n-k}. \end{aligned}$$
(6)

Proof

The left parenthetical calculates the probability that j is in our complex. For any \(1 \le i \le k-1\) we need the \(\left( {\begin{array}{c}k\\ i+1\end{array}}\right) \) possible i-faces on the vertices of j to be contained in X. Proceeding inductively, the \((i-1)\)-skeleton of each face is already contained in X and each i-face is added independently with probability \(p_i\). The right parenthetical calculates the probability these vertices do not form a k-face with one of the other \(n-k\) vertices. For a fixed vertex v, this happens when every face of dimension \(1, \ldots , k\) involving v and vertices of j is contained in our complex. This event that we wish to avoid occurs independently for each vertex with probability \( \prod _{i=1}^{k} p_i^{\left( {\begin{array}{c}k\\ i\end{array}}\right) }\), and our result follows. \(\square \)

We now establish the threshold where these subcomplexes do not appear in our complex.

Lemma 3.2

Let \(X \overset{\mathrm{dist}}{=}X(n, p_1, p_2, \ldots )\) with \(p_i = n^{-\alpha _i}\), if

$$\begin{aligned} \sum _{i=1}^k \left( {\begin{array}{c}k\\ i\end{array}}\right) \alpha _i < 1 \end{aligned}$$

then X w.h.p. contains no maximal \((k-1)\)-faces.

Proof

Recall \(N_{k-1}\) counts the maximal faces in X, by (6) and linearity of expectation we have

$$\begin{aligned} {\mathbb {E}} \left[ N_{k-1}\right]&= \sum _{j \in \left( {\begin{array}{c}[n]\\ k\end{array}}\right) } {\mathbb {E}}\left[ 1_{C_j}\right] = \sum _{j \in \left( {\begin{array}{c}[n]\\ k\end{array}}\right) } {\mathbb {P}}\left[ C_j\right] \\&= \sum _{j \in \left( {\begin{array}{c}[n]\\ k\end{array}}\right) } \left( \prod _{i=1}^{k-1} p_i^{\left( {\begin{array}{c}k\\ i+1\end{array}}\right) } \right) \left( 1 - \prod _{i=1}^{k} p_i^{\left( {\begin{array}{c}k\\ i\end{array}}\right) } \right) ^{n-k}\\&= \left( {\begin{array}{c}n\\ k\end{array}}\right) \left( \prod _{i=1}^{k-1} p_i^{\left( {\begin{array}{c}k\\ i+1\end{array}}\right) } \right) \left( 1 - \prod _{i=1}^{k} p_i^{\left( {\begin{array}{c}k\\ i\end{array}}\right) } \right) ^{n-k} \\&\le \frac{n^k}{k!} \left( \prod _{i=1}^{k-1} n^{-\alpha _i \left( {\begin{array}{c}k\\ i+1\end{array}}\right) } \right) \left( e^{-(n-k) \left( \prod _{i=1}^{k} n^{- \alpha _i \left( {\begin{array}{c}k\\ i\end{array}}\right) } \right) } \right) . \end{aligned}$$

Then for some \(D>0\),

$$\begin{aligned} {\mathbb {E}}\left[ N_{k-1}\right]&\le D \frac{n^k}{k!} \left( n^{-\sum _{i=1}^{k-1} \alpha _i \left( {\begin{array}{c}k\\ i+1\end{array}}\right) } \right) \left( e^{-n \left( n^{-\sum _{i=1}^{k} \alpha _i \left( {\begin{array}{c}k\\ i\end{array}}\right) } \right) } \right) \\&= \frac{D}{k!} \left( n^{k - \sum _{i=1}^{k-1} \alpha _i \left( {\begin{array}{c}k\\ i+1\end{array}}\right) } \right) \left( e^{-n^{1 - \sum _{i=1}^k \alpha _i \left( {\begin{array}{c}k\\ i\end{array}}\right) }} \right) . \end{aligned}$$

By hypothesis

$$\begin{aligned} \sum _{i=1}^{k-1} \alpha _i \left( {\begin{array}{c}k\\ i\end{array}}\right) < 1, \end{aligned}$$

so the right parenthetical of our last term is \(e^{-n^\epsilon }\) for some \(\epsilon > 0\). This term asymptotically dominates the rest of the expression and \({\mathbb {E}}\left[ N_{k-1} \right] \rightarrow 0\) exponentially. Markov’s inequality tells us

$$\begin{aligned} {\mathbb {P}}\left[ N_{k-1} \ge 1 \right] \le {\mathbb {E}}\left[ N_{k-1} \right] = o(1), \end{aligned}$$

completing our proof. \(\square \)

So in this regime w.h.p. every \((k-1)\)-face of our complex is contained in a k-face, a fact necessary to utilize [4, Theorem 2.1] and prove that \(H^{k-1} (X, {\mathbb {Q}}) = 0\) in this range.

4 Trivial Cohomology

In this section we prove Theorem 1.1, the upper threshold for vanishing cohomology, with [4, Thm. 2.1] and [11, Thm. 1.1] crucial to our argument.

To understand the \((k-1)\)th cohomology of a complex we need only consider its k-skeleton, i.e., the subcomplex of X induced by its faces of dimension k and lower. We use \(X_k\) to denote the k-skeleton of X, observing \(H^{k-1}(X_k) = H^{k-1}(X)\). The following lemma provides the first step to invoking the [4, Thm. 2.1].

Lemma 4.1

Let \(X \overset{\mathrm{dist}}{=}X(n, p_1, p_2, \ldots )\) such that

$$\begin{aligned} \sum _{i=1}^k \alpha _i \left( {\begin{array}{c}k\\ i\end{array}}\right) < 1 \end{aligned}$$

and \(X_k\) be its k-skeleton. Then \(X_k\) is w.h.p. pure k-dimensional.

Proof

This implies \(\alpha _1< 1/ k < 1\), so w.h.p. every vertex has degree greater than 0. Fixing a \(1 \le j \le k-1\) we have

$$\begin{aligned} \sum _{i=1}^{j+1} \alpha _i \left( {\begin{array}{c}j+1\\ i\end{array}}\right) \le \sum _{i=1}^k \alpha _i \left( {\begin{array}{c}k\\ i\end{array}}\right) < 1, \end{aligned}$$

so by Lemma 3.2 w.h.p. every j-face of \(X_k\) is contained in a \((j+1)\)-face. Our claim follows immediately. \(\square \)

Thus \(X_k\) satisfies the first hypothesis of [4, Theorem 2.1]. To establish trivial cohomology we must bound the spectral gaps of the links of \(X_k\).

4.1 Using the Spectral Gap Theorem

We wish to understand the structure of the links of the \((k-2)\)-faces in our complex. Given a \((k-2)\)-face \(\sigma \in X_k\), we let \(L_\sigma \) denote the number of vertices in \(\text {lk}_{X_k}(\sigma )\). We also define

$$\begin{aligned} {\bar{p}} = \prod _{i=1}^{k-1} p_i^{\left( {\begin{array}{c}k-1\\ i\end{array}}\right) } \end{aligned}$$

and

$$\begin{aligned} p' = \prod _{i=1}^k p_i^{\left( {\begin{array}{c}k-1\\ i-1\end{array}}\right) }. \end{aligned}$$

Lemma 4.2

For any \((k-2)\)-face \(\sigma \in X\), \(L_\sigma \) has the same distribution as Bin \((n- k+1, {{\bar{p}}})\). Moreover, conditioning on the value of \(L_\sigma \), \(\mathrm{lk}_{X_k}(\sigma )\) has the same distribution as \(G(L_\sigma , p')\).

Proof

Fixing a \((k-2)\)-face \(\sigma \), a vertex v will be in  \(\mathrm{lk}_{X_k} (\sigma )\) if \(X_k\) contains every possible face spanned by v and some subset of the vertices of \(\sigma \). In dimension \(1 \le i \le k-1\) there are \(\left( {\begin{array}{c}k-1\\ i\end{array}}\right) \) such faces, each present with probability \(p_i\). Distinct vertices appearing in the link are statements about disjoint sets of faces, so these events are independent with probability \({\bar{p}}\) and our statement about \(L_\sigma \) follows.

Similarly, after conditioning upon the number of vertices in the link, the edge between two vertices of \(\text {lk}_{X_k}(\sigma )\) is included when \(X_k\) contains every face of dimension \(1, \ldots , k\) involving those two vertices and vertices of \(\sigma \). This occurs with probability \(p'\), and the inclusion of distinct edges are again independent events. Thus \(\text {lk}_{X_k}(\sigma )\) has the same distribution as \(G(L_\sigma , p')\) as desired. \(\square \)

So the link of a \((k-2)\)-face behaves like an Erdős–Rényi random graph, but before applying the Spectral Gap Theorem we must bound \(L_\sigma \).

Lemma 4.3

Let \(X \overset{\mathrm{dist}}{=}X(n, p_1, p_2 \ldots )\) with

$$\begin{aligned} \sum _{i=1}^k \alpha _i \left( {\begin{array}{c}k\\ i\end{array}}\right) < 1, \end{aligned}$$

then w.h.p. \(n{\bar{p}}/2 \le L_\sigma \) for every \((k-2)\)-face \(\sigma \in X\).

Proof

For any specific \((k-2)\)-face \(\sigma \) and n large enough that

$$\begin{aligned} n{\bar{p}}/2 <4 (n-k+1) {\bar{p}}/7, \end{aligned}$$

if \(\mu \) denotes the mean of \(L_\sigma \), then Chernoff bounds on binomial random variables give us that

$$\begin{aligned} {\mathbb {P}}\left( L_\sigma< n {\bar{p}}/2 \right)&\le {\mathbb {P}}\left( L_\sigma< 4 (n-k+1) {\bar{p}}/7 \right) \nonumber \\&= {\mathbb {P}}\left( L_\sigma < \left( 1- \frac{3}{7}\right) \mu \right) \nonumber \\&\le e^{-\left( \frac{3}{7} \right) ^2 \frac{\mu }{2}} \nonumber \\&= e^{-\frac{9\mu }{98}}. \end{aligned}$$
(7)

However, these probabilities are not independent for each \((k-2)\)-face. Defining \(J_\sigma \) to be the indicator random variable for \(\{L_\sigma < n{\bar{p}}/2\}\) for a \((k-2)\)-face \(\sigma \), Markov’s Inequality tells us

$$\begin{aligned} {\mathbb {P}}\Big [ \sum _{\sigma \in \left( {\begin{array}{c}[n]\\ k-1\end{array}}\right) } J_\sigma \ge 1 \Big ] \le {\mathbb {E}}\Big [ \sum _{\sigma \in \left( {\begin{array}{c}[n]\\ k-1\end{array}}\right) } J_\sigma \Big ] = \sum _{\sigma \in \left( {\begin{array}{c}[n]\\ k-1\end{array}}\right) } {\mathbb {E}}\left[ J_\sigma \right] . \end{aligned}$$

There are at most \(\left( {\begin{array}{c}n\\ k-1\end{array}}\right) \) faces of dimension \(k-2\) in X and by construction \({\mathbb {E}}\left[ J_\sigma \right] = {\mathbb {P}}( L_\sigma < n{\bar{p}}/2)\), so

$$\begin{aligned} {\mathbb {P}}\Big [ \sum _{\sigma \in \left( {\begin{array}{c}[n]\\ k-1\end{array}}\right) } J_\sigma \ge 1 \Big ]&\le \left( {\begin{array}{c}n\\ k-1\end{array}}\right) {\mathbb {P}}\left( L_\sigma < n{\bar{p}}/2\right) \text { (for some fixed }\sigma ) \\&\le \left( {\begin{array}{c}n\\ k-1\end{array}}\right) e^{-\frac{9\mu }{98}} \text { (by } (7))\\&= \left( {\begin{array}{c}n\\ k-1\end{array}}\right) e^{-\frac{9(n-k+1){\bar{p}}}{98}} \\&= \left( {\begin{array}{c}n\\ k-1\end{array}}\right) e^{-\frac{9n{\bar{p}}}{98}} e^{\frac{(k-1){\bar{p}}}{98}}. \end{aligned}$$

Since \(\alpha _i \ge 0\) for all i, we know

$$\begin{aligned} \sum _{i=1}^{k-1} \alpha _i \left( {\begin{array}{c}k-1\\ i\end{array}}\right)< \sum _{i=1}^{k} \alpha _i \left( {\begin{array}{c}k\\ i\end{array}}\right) < 1 \end{aligned}$$

and so for some \(\epsilon >0\)

$$\begin{aligned} {\bar{p}} = \prod _{i=1}^{k-1} p_i^{\left( {\begin{array}{c}k-1\\ i\end{array}}\right) } = n^{-\sum _{i=1}^{k-1} \alpha _i \left( {\begin{array}{c}k-1\\ i\end{array}}\right) } = n^{\epsilon -1} . \end{aligned}$$

Since \(\frac{(k-1){\bar{p}}}{98} \rightarrow 0\) so long as \(p_i < 1\) for some \(1 \le i \le k-1\), we may bound \(e^{\frac{(k-1){\bar{p}}}{98}}\) above by a constant \(C>0\). It follows that

$$\begin{aligned} {\mathbb {P}}\Big [ \Big ( \sum _{\sigma \in \left( {\begin{array}{c}[n]\\ k-1\end{array}}\right) } J_\sigma \Big ) \ge 1\Big ] \le C \left( {\begin{array}{c}n\\ k-1\end{array}}\right) e^{-\frac{9}{98} n^\epsilon } = o(1). \end{aligned}$$

Thus w.h.p. \(L_\sigma = 0\) for every \((k-2)\)-face \(\sigma \), completing our proof. \(\square \)

We require one last lemma before proving our main result.

Lemma 4.4

Let \(X \overset{\mathrm{dist}}{=}X(n, p_1, p_2, \ldots )\) and fix \(\delta >0\). If

$$\begin{aligned} \sum _{i=1}^{k} \alpha _i \left( {\begin{array}{c}k\\ i\end{array}}\right) < 1 \end{aligned}$$

then w.h.p.

$$\begin{aligned} \frac{(1+\delta ) \log L_\sigma }{L_\sigma } \le p' \end{aligned}$$
(8)

for all \((k-2)\)-faces \(\sigma \) in X.

Proof

We let \(L = n {\bar{p}} / 2\). Straightforward calculus shows \(f(x) = \frac{(1+\delta ) \log (x)}{x}\) is monotonically decreasing on \([e, \infty )\). For large n we have \(e < L\), so if \(f(L) < p'\) then by Lemma 4.3, \(f(L_\sigma ) < p'\) for all \(\sigma \) w.h.p. We let \(\epsilon = 1 - \sum _{i=1}^k \alpha _i \left( {\begin{array}{c}k\\ i\end{array}}\right) \), noting \(\epsilon >0\) by hypothesis. Then

$$\begin{aligned} \frac{f(L)}{p'}&= (1+ \delta )\, \frac{\log L}{Lp'} \\&\le (2+ 2\delta )\, \frac{\log n}{n {\bar{p}} p'} \\&= (2+ 2\delta )\, \frac{\log n}{n^{1 - \sum _{i=1}^{k-1} \alpha _i \left( {\begin{array}{c}k-1\\ i\end{array}}\right) - \sum _1^{k} \alpha _i \left( {\begin{array}{c}k-1\\ i-1\end{array}}\right) } } \\&= (2+ 2\delta )\, \frac{\log n}{n^{1 - \sum _{i=1}^{k} \alpha _i \left( {\begin{array}{c}k\\ i\end{array}}\right) } } \\&= (2+ 2\delta )\, \frac{\log n}{n^{\epsilon }} \\&= o(1). \end{aligned}$$

Thus w.h.p. \(f(L_\sigma )< f(L) < p'\) for all \((k-2)\)-faces \(\sigma \). \(\square \)

4.2 The Main Result

We now have the machinery to prove a main theorem.

Proof of Theorem 1.1

We begin by fixing the \(\delta > 0\) we will use in the Spectral Gap Theorem in Sect. 2:

$$\begin{aligned} \delta = \frac{k - \sum _{i=1}^{k-2} \alpha _i \left( {\begin{array}{c}k-1\\ i+1\end{array}}\right) }{1-\sum _{i=1}^{k-1} \alpha _i \left( {\begin{array}{c}k-1\\ i\end{array}}\right) }. \end{aligned}$$
(9)

A standard second moment technique, detailed in Sect. 6, tells us that if \(f_{k-2}\) denotes the number of \((k-2)\)-faces in X, or \(X_k\), then w.h.p.

$$\begin{aligned} f_{k-2} \le (1+o(1))\, {\mathbb {E}}\left[ f_{k-2} \right] = (1 + o(1)) \left( {\begin{array}{c}n\\ k-1\end{array}}\right) \prod _{i=1}^{k-2} p_i ^{\left( {\begin{array}{c}k-1\\ i+1\end{array}}\right) } . \end{aligned}$$
(10)

By Lemma 4.2 each of these faces has link with distribution \(G ( L_\sigma , p' )\), and by Lemma 4.4 w.h.p.

$$\begin{aligned} \frac{(1+\delta ) \log L_\sigma }{L_\sigma } < p' \end{aligned}$$

for all \((k-2)\)-faces \(\sigma \) of X. Thus by the Spectral Gap Theorem the probability \(P_\sigma \) that

$$\begin{aligned} \lambda _2 [ \text {lk}_{X_k} (\sigma ) ] < 1 - 1/k \end{aligned}$$

is \(o\left( L_\sigma ^{-\delta } \right) \). Let \(P_X\) denote the probability there exists any \((k-2)\)-face whose link in \(X_k\) has spectral gap less than \(1-1/k\). We apply a union bound over all \((k-2)\)-faces to see

$$\begin{aligned} P_X&\le \sum _{\sigma \in \left( {\begin{array}{c}[n]\\ k-1\end{array}}\right) } P_\sigma \\&= \sum _{\sigma \in \left( {\begin{array}{c}[n]\\ k-1\end{array}}\right) } o\left( L_\sigma ^{-\delta } \right) \\&\le \sum _{\sigma \in \left( {\begin{array}{c}[n]\\ k-1\end{array}}\right) } o\left( \left( \frac{n {\bar{p}}}{2} \right) ^{-\delta } \right) . \end{aligned}$$

The last line holds since w.h.p. \( n{\bar{p}}/2 <L_\sigma \), so \(L_\sigma ^{-\delta } < \left( n {\bar{p}}/2 \right) ^{-\delta }\). By (10),

$$\begin{aligned} P_X&\le \left( 1 + o(1) \right) \left( {\begin{array}{c}n\\ k-1\end{array}}\right) \left( \prod _{i=1}^{k-2} p_i ^{\left( {\begin{array}{c}k-1\\ i+1\end{array}}\right) } \right) o \left( 2^{\delta } (n{\bar{p}})^{-\delta } \right) \\&\le \left( 1+ o(1) \right) \frac{n^{k-1}}{(k-1)!} \left( \prod _{i=1}^{k-2} p_i ^{\left( {\begin{array}{c}k-1\\ i+1\end{array}}\right) } \right) o \left( 2^\delta (n{\bar{p}})^{-\delta } \right) \\&= O \left( 2^\delta n^{k-1} n^{- \sum _{i=1}^{k-2} \alpha _i \left( {\begin{array}{c}k-1\\ i+1\end{array}}\right) } \left( n \cdot n^{-\sum _{i=1}^{k-1} \alpha _i \left( {\begin{array}{c}k-1\\ i\end{array}}\right) } \right) ^{-\delta } \right) \\&= O \left( 2^\delta n^{k-1- \sum _{i=1}^{k-2} \alpha _i \left( {\begin{array}{c}k-1\\ i+1\end{array}}\right) } n^{-\delta \left( 1 - \sum _{i=1}^{k-1} \alpha _i \left( {\begin{array}{c}k-1\\ i\end{array}}\right) \right) } \right) . \end{aligned}$$

By our choice of \(\delta \) in (9),

$$\begin{aligned} P_X&= O \left( n^{k-1- \sum _{i=1}^{k-2} \alpha _i \left( {\begin{array}{c}k-1\\ i+1\end{array}}\right) } n^{- ( k- \sum _{i=1}^{k-2} \alpha _i \left( {\begin{array}{c}k-1\\ i+1\end{array}}\right) )} \right) \\&= O\Big (n^{-1} \Big ) \\&= o(1). \end{aligned}$$

Thus w.h.p.

$$\begin{aligned} \lambda _2 [\text {lk}_{X_k}(\sigma )] > 1 - \frac{1}{k} \end{aligned}$$

for every \((k-2)\)-face \(\sigma \) of X. Combining this with Lemma 3.2, we may apply the Cohomology Vanishing Theorem in Sect. 2 on \(X_k\) to conclude that w.h.p. \(H^{k-1}(X_k, {\mathbb {Q}}) = 0\). Noting that \(H^{k-1}(X_k , {\mathbb {Q}}) \cong H^{k-1}(X, {\mathbb {Q}} )\) completes our proof. \(\square \)

5 Nontrivial Homology: Boundaries of Simplices

In this section we consider the case

$$\begin{aligned} 1 \le \sum _{i=1}^k \alpha _i \left( {\begin{array}{c}k\\ i\end{array}}\right) ,\;\; \sum _{i=1}^{k-1} \alpha _i \left( {\begin{array}{c}k+1\\ i+1\end{array}}\right) < k+1,\; \text { and } \; \alpha _k > 0, \text { so }\; p_k \ne 1 \end{aligned}$$

to prove the second half of Theorem 1.2.

In [2], the threshold for the appearance of nontrivial k-homology in \(Y_k(n,p)\) was studied with a stochastic k-face adding process. It was shown that under this process of adding faces uniform randomly, the first type of homological k-cycle to appear was either an empty k-simplex, the \((k-1)\)-skeleton of a k-simplex, or a cycle supported on a positive fraction of the total number of k-faces. In this section we consider the first case to \(X(n, p_1, p_2,\ldots )\), when \(p_k \ne 1\) and the presence of an empty k-simplex is possible. If X contains an empty k-simplex with at least one maximal \((k-1)\)-face, then it generates a \({\mathbb {Z}}\)-summand in \(H_{k-1}(X,{\mathbb {Z}})\). For a set of \(k+1\) vertices \(j \in \left( {\begin{array}{c}[n]\\ k+1\end{array}}\right) \), we define \(A_j\) as the event j corresponds to an empty k-simplex with first \((k-1)\)-face, determined by lexicographic order, maximal in X. Letting \(M_{k-1}\) denote the total number of such subcomplexes in X, it follows that

$$\begin{aligned} M_{k-1} = \sum _{j \in \left( {\begin{array}{c}[n]\\ k+1\end{array}}\right) } 1_{A_j}. \end{aligned}$$

We then calculate the probability of \(A_j\).

Lemma 5.1

For any \(j\in \left( {\begin{array}{c}[n]\\ k+1\end{array}}\right) \),

$$\begin{aligned} {\mathbb {E}}\left[ 1_{A_j}\right] = {\mathbb {P}}\left[ A_j\right] = \left( \prod _{i=1}^{k-1} p_i^{\left( {\begin{array}{c}k+1\\ i+1\end{array}}\right) } \right) (1-p_k) \left( 1 - \prod _{i=1}^{k} p_i^{\left( {\begin{array}{c}k\\ i\end{array}}\right) } \right) ^{n-k-1}. \end{aligned}$$
(11)

Proof

The first term calculates the probability that X contains the necessary i-faces for \(i< k\): we need every subset of \(i+1\) vertices of j to form an i-simplex. The second term is the requirement that the associated k-simplex is empty. The last term is ensuring our first \((k-1)\)-face is maximal, or does not form a k-simplex with any of the remaining \(n-k-1\) vertices. This occurs independently with probability \(\prod _{i=1}^k p_i^{\left( {\begin{array}{c}k\\ i\end{array}}\right) }\) for each vertex. \(\square \)

We note that narrowing our consideration to when the first \((k-1)\)-face is maximal simplifies the calculations without altering the relevant probability thresholds. Recall that we say \(X \sim Y\) with high probability if for all \(\epsilon > 0\), we have

$$\begin{aligned} \lim _{n \rightarrow \infty } {\mathbb {P}}\left[ (1-\epsilon ) \le Y/X \le (1+ \epsilon )\right] \rightarrow 1. \end{aligned}$$

Lemma 5.2

Let \(X \overset{\mathrm{dist}}{=}X(n, p_1,p_2, \ldots )\) with \(p_i = n^{-\alpha _i}\) and \(M_{k-1}\) count the number of empty k-simplices in X with maximal first \((k-1)\)-face. If

$$\begin{aligned} 1 \le \sum _{i=1}^k \alpha _i \left( {\begin{array}{c}k\\ i\end{array}}\right) ,\;\; \sum _{i=1}^{k-1} \alpha _i \left( {\begin{array}{c}k+1\\ i+1\end{array}}\right) < k+1 , \;\text { and }\; p_k \ne 1 \end{aligned}$$

then w.h.p. \(M_{k-1} > 0\) and \(M_{k-1} \sim {\mathbb {E}}\left[ M_{k-1}\right] \).

Proof

By linearity of expectation we have

$$\begin{aligned} {\mathbb {E}} \,[ M_{k-1} ]&= \left( {\begin{array}{c}n\\ k+1\end{array}}\right) \left( \prod _{i=1}^{k-1} p_i^{\left( {\begin{array}{c}k+1\\ i+1\end{array}}\right) } \right) (1-p_k) \left( 1 - \prod _{i=1}^{k} p_i^{\left( {\begin{array}{c}k\\ i\end{array}}\right) } \right) ^{n-k-1} \\&\approx \frac{1-p_k}{(k+1)!} \left( n^{k+1 - \sum _{i=1}^{k-1} \alpha _i \left( {\begin{array}{c}k+1\\ i+1\end{array}}\right) } \right) \left( e^{-n^{1 - \sum _{i=1}^k \alpha _i \left( {\begin{array}{c}k\\ i\end{array}}\right) }} \right) . \end{aligned}$$

By the first inequality in our hypothesis,

$$\begin{aligned} 1- \sum _{i=1}^k \alpha _i \left( {\begin{array}{c}k\\ i\end{array}}\right) \le 0, \end{aligned}$$

which implies that

$$\begin{aligned} e^{-n^{1 - \sum _{i=1}^k \alpha _i \left( {\begin{array}{c}k\\ i\end{array}}\right) }} = \Theta (1). \end{aligned}$$

We therefore have

$$\begin{aligned} {\mathbb {E}} \left[ M_{k-1} \right] = \Theta \left( n^{k+1 - \sum _{i=1}^{k-1} \alpha _l \left( {\begin{array}{c}k+1\\ i+1\end{array}}\right) } \right) , \end{aligned}$$
(12)

hence \({\mathbb {E}}[M_{k-1}] \rightarrow \infty \).

This, along with a straightforward second moment argument (see e.g. [14]) which is detailed in Appendix A, allow us to use Chebyshev’s inequality to conclude that w.h.p. \(M_{k-1} \sim {\mathbb {E}}\left[ M_{k-1}\right] \). \(\square \)

Proof of the second part of Theorem 1.2

It follows from Lemma 5.2 that w.h.p. \(M_{k-1} > 0\). Consider such a subcomplex \(\sigma \). As the boundary of a k-simplex, a signed sum of its \((k-1)\)-faces is in the kernel of the \((k-1)\)-boundary map. Since one of these faces, \(\tau \), is maximal, it is not contained in a k-face of X. Thus no \((k-1)\)-chain with a non-zero coefficient of \(\tau \) can be a \((k-1)\)-boundary of X. Thus we have a nontrivial cycle no multiple of which is a boundary, contributing a \({\mathbb {Z}}\)-summand to \(H_{k-1} (X , {\mathbb {Z}})\) and a \({\mathbb {Q}}\)-cycle to \(H_{k-1}(X,{\mathbb {Q}})\). By vector space duality we conclude \(H^{k-1} (X, {\mathbb {Q}}) \cong H_{k-1} (X, {\mathbb {Q}}) \ne 0\). \(\square \)

6 Nontrivial Cohomology: Betti Numbers Argument

We now consider when

$$\begin{aligned} 1< \sum _{i=1}^k \alpha _i \left( {\begin{array}{c}k\\ i\end{array}}\right) \;\text { and }\; \sum _{i=1}^{k-1} \alpha _i \left( {\begin{array}{c}k-1\\ i\end{array}}\right) < 1, \end{aligned}$$

proving the other half of Theorem 1.2.

Proof of the first part of Theorem 1.2

For \(X \overset{\mathrm{dist}}{=}X(n, p_1, p_2, \ldots )\), with the aforementioned conditions on \(p_i\), we let \(f_i\) denote the number of i-simplices in X and \(\beta _i = \mathrm{dim}\, H^i(X, {\mathbb {Q}})\). Linear algebra considerations tell us

$$\begin{aligned} f_{k-1} \ge \beta _{k-1} \ge f_{k-1} - f_k - f_{k-2}. \end{aligned}$$
(13)

Thus showing that w.h.p. \( f_{k-1} > f_k + f_{k-2}\) implies \(\beta _{k-1} > 0\). We begin by calculating the expected number of faces in these dimensions:

$$\begin{aligned} {\mathbb {E}}\left[ f_{k-2} \right]&= \left( {\begin{array}{c}n\\ k-1\end{array}}\right) \prod _{i=1}^{k-2} p_i^{\left( {\begin{array}{c}k-1\\ i+1\end{array}}\right) }, \\ {\mathbb {E}}\left[ f_{k-1} \right]&= \left( {\begin{array}{c}n\\ k\end{array}}\right) \prod _{i=1}^{k-1} p_i^{\left( {\begin{array}{c}k\\ i+1\end{array}}\right) }, \\ {\mathbb {E}}\left[ f_{k} \right]&= \left( {\begin{array}{c}n\\ k+1\end{array}}\right) \prod _{i=1}^{k} p_i^{\left( {\begin{array}{c}k+1\\ i+1\end{array}}\right) }. \end{aligned}$$

By linearity of expectation

$$\begin{aligned} {\mathbb {E}}\left[ f_{k-1} \right] \ge {\mathbb {E}}\left[ \beta _{k-1} \right] \ge {\mathbb {E}}\left[ f_{k-1} \right] -{\mathbb {E}}\left[ f_{k-2} \right] -{\mathbb {E}}\left[ f_{k} \right] . \end{aligned}$$

Comparing the expectations in different dimensions we see

$$\begin{aligned} \frac{{\mathbb {E}}\left[ f_{k}\right] }{{\mathbb {E}}\left[ f_{k-1}\right] } = \frac{n-k}{k+1} \prod _{i=1}^k p_i^{\left( {\begin{array}{c}k+1\\ i+1\end{array}}\right) - \left( {\begin{array}{c}k\\ i+1\end{array}}\right) } = \frac{n-k}{k+1} \prod _{i=1}^k p_i^{\left( {\begin{array}{c}k\\ i\end{array}}\right) } \le n \prod _{i=1}^k p_i^{\left( {\begin{array}{c}k\\ i\end{array}}\right) } = o(1) , \end{aligned}$$
(14)

because

$$\begin{aligned} \prod _{i=1}^k p_i^{\left( {\begin{array}{c}k\\ i\end{array}}\right) } < n^{-1} \end{aligned}$$

by hypothesis. Similarly, since

$$\begin{aligned} \prod _{i=1}^{k-1} p_i^{\left( {\begin{array}{c}k-1\\ i\end{array}}\right) } = n^{c-1} \end{aligned}$$

for some \(c>0\), we have

$$\begin{aligned} \frac{{\mathbb {E}}\left[ f_{k-2}\right] }{{\mathbb {E}}\left[ f_{k-1}\right] }&= \frac{k}{n-k+1} \prod _{i=1}^{k-1} p_i^{\left( {\begin{array}{c}k-1\\ i+1\end{array}}\right) - \left( {\begin{array}{c}k\\ i+1\end{array}}\right) }\nonumber \\&= \frac{k}{n-k+1} \prod _{i=1}^{k-1} p_i^{-\left( {\begin{array}{c}k-1\\ i\end{array}}\right) } = \frac{k n^{1-c}}{n-k+1} = o(1). \end{aligned}$$
(15)

Thus \({\mathbb {E}}\left[ f_{k-1} \right] \) asymptotically dominates the other two terms. Letting

$$\begin{aligned} {\tilde{f}}_{k-1} := f_{k-1} - f_k - f_{k-2}, \end{aligned}$$

it follows from (14) and (15) that

$$\begin{aligned} {\mathbb {E}}\,[{\tilde{f}}_{k-1} ] \sim {\mathbb {E}}\left[ \beta _{k-1}\right] \sim {\mathbb {E}}\left[ f_{k-1}\right] . \end{aligned}$$
(16)

To prove stronger statements about \(\beta _{k-1}\) we again make use of Chebyshev’s Inequality. That is, if Z is a random variable with \({\mathbb {E}}\left[ Z\right] \rightarrow \infty \) and \(\text {Var}\left[ Z\right] = o \left( {\mathbb {E}}[Z]^2 \right) \), then w.h.p. \(Z \sim {\mathbb {E}}\left[ Z \right] \).

Now

$$\begin{aligned} \text {Var} \Big [f_{k-1} \Big ]&= {\mathbb {E}}\left[ f_{k-1}^2 \right] - {\mathbb {E}}\left[ f_{k-1} \right] ^2 \\&= {\mathbb {E}}\Big [f_{k-1}^2 \Big ] - \left( {\begin{array}{c}n\\ k\end{array}}\right) ^2 \left( \prod _{i=1}^{k-1} p_i^{2\left( {\begin{array}{c}k\\ i+1\end{array}}\right) } \right) . \end{aligned}$$

It remains to calculate \( {\mathbb {E}}\,[f_{k-1}^2]\). For any \(j \in \left( {\begin{array}{c}[n]\\ k\end{array}}\right) \) let \(E_j\) be the event that the vertices of j span a \((k-1)\)-face in X. Then

$$\begin{aligned} {\mathbb {E}}\,[ f_{k-1}^2 ]&= \sum _{j,l \in \left( {\begin{array}{c}[n]\\ k\end{array}}\right) } {\mathbb {P}}\,[E_j \cap E_l] = \left( {\begin{array}{c}n\\ k\end{array}}\right) \sum _{l \in \left( {\begin{array}{c}[n]\\ k\end{array}}\right) } {\mathbb {P}}\,[E_j \cap E_l]. \end{aligned}$$

The second equality follows by symmetry and fixing some set of vertices j, say \(\{ 1, \ldots , k \}\). We proceed by grouping the l according to \(|j \cap l |\). Through this approach we see

$$\begin{aligned} {\mathbb {E}}\,[f_{k-1}^2]&= \left( {\begin{array}{c}n\\ k\end{array}}\right) \sum _{l \in \left( {\begin{array}{c}[n]\\ k\end{array}}\right) } {\mathbb {P}}\,[A_j \cap A_l] \\&= \left( {\begin{array}{c}n\\ k\end{array}}\right) \sum _{m=0}^k \left( {\begin{array}{c}k\\ m\end{array}}\right) \left( {\begin{array}{c}n-k\\ k-m\end{array}}\right) \left( \prod _{i=1}^{k-1} p_i^{2\left( {\begin{array}{c}k\\ i+1\end{array}}\right) - \left( {\begin{array}{c}m\\ i+1\end{array}}\right) } \right) \\&= \left( {\begin{array}{c}n\\ k\end{array}}\right) \prod _{i=1}^{k-1} p_i^{2\left( {\begin{array}{c}k\\ i+1\end{array}}\right) } \left( \sum _{m=0}^k \left( {\begin{array}{c}k\\ m\end{array}}\right) \left( {\begin{array}{c}n-k\\ k-m\end{array}}\right) \prod _{i=1}^{m-1}p_i^{- \left( {\begin{array}{c}m\\ i+1\end{array}}\right) } \right) . \end{aligned}$$

We pull the \(m=0\) term out of the summation and use \(\left( {\begin{array}{c}n-k\\ k\end{array}}\right) < \left( {\begin{array}{c}n\\ k\end{array}}\right) \) to see

$$\begin{aligned} {\mathbb {E}}\,[f_{k-1}^2] \le {\mathbb {E}}\,[f_{k-1}]^2 + \left( {\begin{array}{c}n\\ k\end{array}}\right) \prod _{i=1}^{k-1} p_i^{2\left( {\begin{array}{c}k\\ i+1\end{array}}\right) } \left( \sum _{m=1}^k \left( {\begin{array}{c}k\\ m\end{array}}\right) \left( {\begin{array}{c}n-k\\ k-m\end{array}}\right) \prod _{i=1}^{m-1}p_i^{- \left( {\begin{array}{c}m\\ i+1\end{array}}\right) } \right) . \end{aligned}$$

We observe

$$\begin{aligned} \frac{\text {Var} \,[f_{k-1}]}{{\mathbb {E}}\,[f_{k-1}]^2}&\le \frac{\left( {\begin{array}{c}n\\ k\end{array}}\right) \prod _{i=1}^{k-1} p_i^{2\left( {\begin{array}{c}k\\ i+1\end{array}}\right) } \left( \sum _{m=1}^k \left( {\begin{array}{c}k\\ m\end{array}}\right) \left( {\begin{array}{c}n-k\\ k-m\end{array}}\right) \prod _{i=1}^{m-1}p_i^{- \left( {\begin{array}{c}m\\ i+1\end{array}}\right) } \right) }{\left( {\begin{array}{c}n\\ k\end{array}}\right) ^2 \left( \prod _{i=1}^{k-1} p_i^{2\left( {\begin{array}{c}k\\ i+1\end{array}}\right) } \right) } \\&= \frac{ \sum _{m=1}^k \left( {\begin{array}{c}k\\ m\end{array}}\right) \left( {\begin{array}{c}n-k\\ k-m\end{array}}\right) \prod _{i=1}^{m-1}p_i^{- \left( {\begin{array}{c}m\\ i+1\end{array}}\right) } }{\left( {\begin{array}{c}n\\ k\end{array}}\right) } \\&= \sum _{m=1}^k O \left( n^{-m} \prod _{i=1}^{m-1}p_i^{- \left( {\begin{array}{c}m\\ i+1\end{array}}\right) } \right) \\&= o(1). \end{aligned}$$

The final line holds from our hypotheses since

$$\begin{aligned} \sum _{i=1}^{m-1} \alpha _i \left( {\begin{array}{c}m\\ i+1\end{array}}\right) \le \frac{m}{k} \left( \sum _{i=1}^{k-1} \alpha _i \left( {\begin{array}{c}k\\ i+1\end{array}}\right) \right) \le \frac{m}{k}\left( k \cdot \sum _{i=1}^{k-1} \alpha _i \left( {\begin{array}{c}k-1\\ i\end{array}}\right) \right) < m, \end{aligned}$$

so for \(m=1, \ldots , k\),

$$\begin{aligned} \prod _{i=1}^{m-1}p_i^{- \left( {\begin{array}{c}m\\ i+1\end{array}}\right) } = n^{\sum _{i=1}^{m-1} \alpha _i \left( {\begin{array}{c}m\\ i+1\end{array}}\right) } = o \left( n^m \right) . \end{aligned}$$

We conclude \(f_{k-1} \sim {\mathbb {E}}\,[f_{k-1}]\).

We note that nothing in the above argument is unique to \(f_{k-1}\), so w.h.p. \(-f_{k-2} \sim {\mathbb {E}}\left[ -f_{k-2} \right] \) and \(-f_k \sim {\mathbb {E}}\left[ -f_k \right] \). By linearity of expectation \({\tilde{f}}_{k-1} \sim {\mathbb {E}}\,[{\tilde{f}}_{k-1}]\), then from (13) and (16) we conclude that w.h.p. \(\beta _{k-1} \sim {\mathbb {E}}\, [\beta _{k-1}] \sim f_{k-1}\). Thus \(\beta _{k-1} = \text {dim} \left( H^{k-1} (X , {\mathbb {Q}} ) \right) \ne 0\) w.h.p., which completes our proof. \(\square \)

Under these conditions we have proven a stronger result than nontrivial homology.

Proof of Theorem 1.6

From the above,

$$\begin{aligned} \beta _{k-1} \sim f_{k-1} \sim {\mathbb {E}}\, [ f_{k-1}] = g_{k-1}(n, \alpha _1, \ldots \alpha _k). \end{aligned}$$

The result follows. \(\square \)

Our proof also shows that allowing

$$\begin{aligned} \sum _{i=1}^{k} \alpha _i \left( {\begin{array}{c}k\\ i\end{array}}\right) = 1 \end{aligned}$$

still ensures nontrivial cohomology.

Lemma 6.1

If

$$\begin{aligned} \sum _{i=1}^{k} \alpha _i \left( {\begin{array}{c}k\\ i\end{array}}\right) = 1, \end{aligned}$$

then w.h.p. \(H^{k-1} (X , {\mathbb {Q}}) \ne 0\) and

$$\begin{aligned} \beta _{k-1} \ge \left( \frac{k}{k+1} \right) f_{k-1}. \end{aligned}$$

Proof

We first calculate

$$\begin{aligned} \frac{{\mathbb {E}}\,[f_k]}{{\mathbb {E}}\,[f_{k-1}]}&= \frac{n-k}{k+1} \prod _{i=1}^k p_i^{\left( {\begin{array}{c}k\\ i\end{array}}\right) } \\&= \frac{n-k}{n(k+1)} \\&\approx \frac{1}{k+1}. \end{aligned}$$

The machinery established in the previous section then does the work for us. Since \(\beta _{k-1}\) is bounded between \(f_{k-1}\) and \(f_{k-1} - f_k - f_{k-2}\), with \(f_{k-1} \sim {\mathbb {E}}\,[f_{k-1}]\) and \((f_{k-1} - f_k - f_{k-2}) \sim {\mathbb {E}}\,[(f_{k-1} - f_k - f_{k-2})] \sim \bigl (\frac{k}{k+1} \bigr )\, {\mathbb {E}}\,[f_{k-1}]\), our result follows immediately. \(\square \)

7 Behavior at the Boundary

In this section we explore the behavior of the \((k-1)\)th cohomology of \(X(n, p_1, p_2, \ldots )\) at the upper threshold line. Specifically, we refine the parameters of our \(p_i\) to elicit some interesting behavior and prove Theorem 1.3.

7.1 Maximal Faces

To get the threshold for maximal faces, and thus trivial cohomology, we must slightly refine our model. Unfortunately there is no concise way to categorize these \(p_i\). We consider when

$$\begin{aligned} p_i = \left( \rho _1 \log n + \rho _2 \log \log n + c\right) ^{\nu _i} n^{-\alpha _i} \end{aligned}$$

for some constants \(\nu _i, \rho _1, \rho _2\), and c, with

$$\begin{aligned} \sum _{i=1}^k \alpha _i \left( {\begin{array}{c}k\\ i\end{array}}\right) = 1. \end{aligned}$$

It follows that

$$\begin{aligned} {\mathbb {E}} \,[ N_{k-1} ]&\approx \frac{n^k}{k!} \left( \prod _{i=1}^{k-1} p_i^{ \left( {\begin{array}{c}k\\ i+1\end{array}}\right) } \right) \left( e^{-n \left( \prod _{i=1}^{k} p_i^{\left( {\begin{array}{c}k\\ i\end{array}}\right) } \right) } \right) \\&= \frac{n^{k-\sum _{i=1}^{k-1} \alpha _i \left( {\begin{array}{c}k\\ i+1\end{array}}\right) }}{k!} \left[ \prod _{i=1}^{k-1} \left( \left( \rho _1 + o(1)\right) \log n \right) ^{\nu _i \left( {\begin{array}{c}k\\ i+1\end{array}}\right) } \right] \\ {}&\quad \quad \quad \quad \quad \quad \times e^{- \prod _{i=1}^k \left( \rho _1 \log n + \rho _2 \log \log n + c\right) ^{\nu _i \left( {\begin{array}{c}k\\ i\end{array}}\right) }} \\&= \frac{n^{k-\sum _{i=1}^{k-1} \alpha _i \left( {\begin{array}{c}k\\ i+1\end{array}}\right) }}{k!} \left( \left( \rho _1 + o(1)\right) \log n \right) ^{\sum _{i=1}^{k-1} \nu _i \left( {\begin{array}{c}k\\ i+1\end{array}}\right) }\\ {}&\quad \quad \quad \quad \quad \quad \times e^{- \left( \rho _1 \log n + \rho _2 \log \log n + c\right) ^{\sum _{i=1}^k \nu _i \left( {\begin{array}{c}k\\ i\end{array}}\right) } }. \end{aligned}$$

Letting

$$\begin{aligned} \sum _{i=1}^k \nu _i \left( {\begin{array}{c}k\\ i\end{array}}\right) = 1, \end{aligned}$$

we have

$$\begin{aligned} {\mathbb {E}}\, [ N_{k-1}]&\approx \frac{n^{k-\sum _{i=1}^{k-1} \alpha _i \left( {\begin{array}{c}k\\ i+1\end{array}}\right) }}{k!} \left( \left( \rho _1 + o(1)\right) \log n \right) ^{\sum _{i=1}^{k-1} \nu _i \left( {\begin{array}{c}k\\ i+1\end{array}}\right) }\\ {}&\quad \quad \quad \quad \quad \quad \times e^{-(\rho _1 \log n + \rho _2 \log \log n + c )} \\&= \frac{n^{k-\sum _{i=1}^{k-1} \alpha _i \left( {\begin{array}{c}k\\ i+1\end{array}}\right) }}{k!} \left( \left( \rho _1 + o(1)\right) \log n \right) ^{\sum _{i=1}^{k-1} \nu _i \left( {\begin{array}{c}k\\ i+1\end{array}}\right) } n^{-\rho _1} (\log n)^{-\rho _2} e^{-c}. \end{aligned}$$

If we set

$$\begin{aligned} \rho _1 = k - \sum _{i=1}^{k-1} \alpha _i \left( {\begin{array}{c}k\\ i+1\end{array}}\right) \end{aligned}$$

and

$$\begin{aligned} \rho _2 = \sum _{i=1}^{k-1} \nu _i \left( {\begin{array}{c}k\\ i+1\end{array}}\right) , \end{aligned}$$

then

$$\begin{aligned} {\mathbb {E}}\, [ N_{k-1} ] \rightarrow \frac{\rho _1^{\rho _2} e^{-c}}{k!} \end{aligned}$$
(17)

as \(n \rightarrow \infty \). We then establish the following result.

Lemma 7.1

Let \(X \overset{\mathrm{dist}}{=}X(n,p_1, p_2, \ldots )\) with

$$\begin{aligned} p_i = \left( \rho _1 \log n + \rho _2 \log \log n + c \right) ^{\nu _i}n^{-\alpha _i} \end{aligned}$$

such that

$$\begin{aligned} \rho _1 = k - \sum _{i=1}^{k-1} \alpha _i \left( {\begin{array}{c}k\\ i+1\end{array}}\right) \end{aligned}$$

and

$$\begin{aligned} \rho _2 = \sum _{i=1}^{k-1} \nu _i \left( {\begin{array}{c}k\\ i+1\end{array}}\right) . \end{aligned}$$

If

$$\begin{aligned} \sum _{i=1}^k \alpha _i \left( {\begin{array}{c}k\\ i\end{array}}\right) = 1 = \sum _{i=1}^k \nu _i \left( {\begin{array}{c}k\\ i\end{array}}\right) , \end{aligned}$$

then \(N_{k-1}\), the number of maximal \((k-1)\)-faces in X, approaches a Poisson distribution

$$\begin{aligned} N_{k-1} \rightarrow {{\,\mathrm{Poi}\,}}(\mu ) \end{aligned}$$

with mean

$$\begin{aligned} \mu = \frac{\rho _1^{\rho _2} e^{-c}}{k!}. \end{aligned}$$

Proof

We prove this with through a standard factorial moment argument, found in Appendix B. \(\square \)

7.2 Betti Numbers

At criticality, if we condition on the event \(N_{k-1} =0\) then slightly modifying our arguments in Sect. 4 will show \(H^{k-1}(X, {\mathbb {Q}}) = 0\) w.h.p. This enables us to use the limiting distribution of \(N_{k-1}\) to prove an identical result for \(\beta _{k-1}\).

Proof of Theorem 1.3

From Lemma 7.1 we know that given these hypotheses, \(N_{k-1} \rightarrow {{\,\mathrm{Poi}\,}}(\mu )\). We suppose \(N_{k-1} = m\) for some \(m \in {\mathbb {Z}}\). The characteristic functions of these m maximal faces are \((k-1)\)-cocycles. We show these cocycles are not coboundaries, and in fact constitute the only cohomological cocycles of dimension \(k-1\) in X.

We label these faces \(\sigma _1, \ldots , \sigma _m\) and their respective characteristic functions \(\phi _1, \ldots , \phi _m\). Letting \(R_{k-2}\) count the number of \((k-2)\)-faces of X contained in m or fewer \((k-1)\)-faces, we have

$$\begin{aligned} {\mathbb {E}}\,[R_{k-2}]&= \left( {\begin{array}{c}n\\ k-1\end{array}}\right) \prod _{i=1}^{k-2} p_i^{\left( {\begin{array}{c}k-1\\ i+1\end{array}}\right) } \left( \sum _{j=0}^m \left( {\begin{array}{c}n-k+1\\ j\end{array}}\right) \left( \prod _{i=1}^{k-1} p_i^{\left( {\begin{array}{c}k-1\\ i\end{array}}\right) }\right) ^j \right. \\ {}&\quad \times \left. \left( 1- \prod _{i=1}^{k-1} p_i^{\left( {\begin{array}{c}k-1\\ i\end{array}}\right) } \right) ^{n-k+1-j} \right) \\&= o(e^{-n^{-\epsilon }})\;\; \text { for some }\epsilon >0. \end{aligned}$$

This holds since by our hypotheses

$$\begin{aligned} n \left( \prod _{i=1}^{k-1} p_i^{\left( {\begin{array}{c}n-1\\ i\end{array}}\right) } \right) \rightarrow \infty , \end{aligned}$$

so the right-most term is exponentially decaying and dominates the expression.

Therefore w.h.p. X contains no \((k-2)\)-face contained solely in some combination of our \(\sigma _i\). We now suppose there exists some \((k-2)\)-cochain \(\lambda \) such that \(\delta ^{k-2}(\lambda ) = \sum _{i=1}^m a_i \phi _i\) with \(a_i \ne 0\) for some i. It follows that \(\lambda \) is not a \((k-2)\)-coboundary. We now consider the subcomplex \(X' = X- \{\sigma _1, \ldots , \sigma _m\}\), and observe \(R_{k-2} = 0\) implies that \(X'\) has no maximal \((k-2)\)-faces. Since \(\sum _{i=1}^{k-1} \alpha _i \left( {\begin{array}{c}k-1\\ i\end{array}}\right) < 1\), it follows from Theorem 1.1 that w.h.p. \(H^{k-2} (X', {\mathbb {Q}}) = 0\). But \(\delta ^{k-2} ( \lambda ) = 0\) in \(X'\) and \(\lambda \) is not a coboundary in X or \(X'\), yielding a contradiction. Therefore no such \(\lambda \) exists and we conclude each \(\phi _i\) generates a unique nontrivial cocycle in \(H^{k-1} \left( X, {\mathbb {Q}} \right) \).

To show these cochains are the only contributors to cohomology we again consider \(X'\). By construction \(X'\) has no maximal \((k-1)\)-faces, and a reworking of our proof of Theorem 1.1 (primarily refining our estimate in Lemma 4.3 to show Lemma 4.4 still holds) tells us \(H^{k-1}(X', {\mathbb {Q}}) = 0\) w.h.p. It follows that \(H^{k-1} \left( X, {\mathbb {Q}} \right) \cong {\mathbb {Q}}^m\). \(\square \)

Implicit in our proof is the result that when

$$\begin{aligned} \sum _{i=1}^k \alpha _i \left( {\begin{array}{c}k\\ i\end{array}}\right) =1, \end{aligned}$$

the presence of maximal \((k-1)\)-faces is a necessary and sufficient condition for \(H^{k-1} (X, {\mathbb {Q}}) \ne 0\).

8 The Phase Transition for Homology Appearing

In this section we prove Theorem 1.4. The requirement

$$\begin{aligned} k+1 < \sum _{i=1}^{k-1} \alpha _i \left( {\begin{array}{c}k+1\\ i+1\end{array}}\right) \end{aligned}$$

is exactly the condition that our complex will w.h.p. not contain the boundary of a k-simplex. Logic dictates that, as the first \((k-1)\)-cycle to appear, the threshold for the presence of these subcomplexes should provide a lower bound for trivial homology. We proceed by verifying this intuition, using the fact that minimal homological cycles have bounded vertex support. After establishing these points we may apply a union bound to conclude our result.

8.1 Cycles of Small Vertex Support

We begin with a few definitions identical to those in Section 5 of [13]. For a \((k-1)\)-chain C the support of C is the union of \((k-1)\)-faces with nonzero coefficients in C, while the vertex support is the underlying vertex set of the support. A pure \((k-1)\)-dimensional subcomplex K is strongly connected if every pair of \((k-1)\)-faces \(\sigma , \tau \in K^{k-1}\) can be connected by a sequence of faces \(\sigma = \sigma _0 , \sigma _1, \ldots , \sigma _j = \tau \) such that \(\text {dim}(\sigma _i \cap \sigma _{i+1}) = k-2\) for \(0 \le i \le j-1\). Every \((k-1)\)-cycle is a linear combination of \((k-1)\)-cycles with strongly connected support.

Lemma 8.1

Let

$$\begin{aligned} 1 < \sum _{i=1}^{k-1} \alpha _i \left( {\begin{array}{c}k-1\\ i\end{array}}\right) \end{aligned}$$

and fix D such that

$$\begin{aligned} \frac{k- \sum _{i=1}^{k-1} \alpha _i \left( {\begin{array}{c}k\\ i+1\end{array}}\right) }{ \sum _{i=1}^{k-1} \alpha _i \left( {\begin{array}{c}k-1\\ i\end{array}}\right) - 1} < D. \end{aligned}$$

Then w.h.p. all strongly connected pure \((k-1)\)-dimensional subcomplexes of X have fewer than \(D+k\) vertices in their support.

Proof

Let K be such a subcomplex, since it is strongly connected we may order its faces \(f_1, f_2, \ldots f_m\) where each face \(f_j\), for \(j>1\), has \((k-2)\)-dimensional intersection with at least one \(f_l\) with \(l < j\). This induces an ordering on the supporting vertices \(v_1, \ldots , v_s\) by looking at the vertex supports of \(f_1, f_1 \cup f_2, f_1 \cup f_2 \cup f_3, \ldots \) Thus each vertex after \(v_k\) corresponds to the addition of a \((k-1)\)-face \(f_j\), along with the \(\left( {\begin{array}{c}k-1\\ i\end{array}}\right) \)i-dimensional faces of \(f_j\) that include this vertex (and hence were not contained in \(f_1 \cup \cdots \cup f_{j-1}\) ).

If K has \(D+k\) vertices, it follows that there are at least

$$\begin{aligned} \left( {\begin{array}{c}k\\ i+1\end{array}}\right) + D \left( {\begin{array}{c}k-1\\ i\end{array}}\right) \end{aligned}$$

i-dimensional faces for each \(1 \le i \le k-1\). Now either X w.h.p. contains no \((k-1)\)-simplices, in which case the result is trivial, or

$$\begin{aligned} \prod _{i=1}^{k-1} p_i^{\left( {\begin{array}{c}k\\ i+1\end{array}}\right) } = \prod _{i=1}^{k-1} n^{-\alpha _i \left( {\begin{array}{c}k\\ i+1\end{array}}\right) } = n^{-k + \beta } \end{aligned}$$

for some \(\beta >0\). By hypothesis

$$\begin{aligned} \prod _{i=1}^{k-1} p_i^{\left( {\begin{array}{c}k-1\\ i\end{array}}\right) } = \prod _{i=1}^{k-1} n^{-\alpha _i \left( {\begin{array}{c}k-1\\ i\end{array}}\right) } = n^{-1 - \epsilon } \end{aligned}$$

for some \(\epsilon >0\). We choose D such that \(\beta < D \epsilon \) and let \(A_K\) denote the event that X contains a subcomplex isomorphic to K. We apply a union bound on the probability of \(A_K\) as follows:

$$\begin{aligned} {\mathbb {P}}(A_K)&\le (D+k)! \left( {\begin{array}{c}n\\ D+k\end{array}}\right) \prod _{i=1}^{k-1} p_i^{\left( {\begin{array}{c}k\\ i+1\end{array}}\right) + D \left( {\begin{array}{c}k-1\\ i\end{array}}\right) } \\&= (D+k)! \left( {\begin{array}{c}n\\ D+k\end{array}}\right) \, n^{(-k+\beta ) - D (1 + \epsilon )} \\&\le n^{D+k} n^{-(D+k)} n^{\beta - D \epsilon } \\&= n^{\beta - D\epsilon } \\&= o(1). \end{aligned}$$

The last line holds by our choice of D.

As there are finitely many isomorphism classes of strongly connected \((k-1)\)-complexes on \(D+k\) vertices, a union bound shows that w.h.p. none of them are subcomplexes of X. We complete our proof by observing that any such complex with more vertices must contain a strongly connected subcomplex on \(D+k\) vertices. For example, under the ordering of the faces and vertices defined at the beginning of the proof, the subcomplex induced by the first \(D+k\) vertices must be strongly connected. \(\square \)

8.2 The Threshold for a Simplex Boundary

Here we prove our lower threshold for vanishing homology, which is sharp when \(p_k \ne 1\).

Proof of Theorem 1.4

We consider some nontrivial \((k-1)\)-cycle \(\gamma \) with strongly connected support and K, its induced subcomplex in X. By our hypothesis we have

$$\begin{aligned} k+1 < \sum _{i=1}^{k-1} \alpha _i \left( {\begin{array}{c}k+1\\ i+1\end{array}}\right) , \end{aligned}$$

and either X will w.h.p. contain no \((k-1)\)-faces, making the result trivial, or

$$\begin{aligned} \sum _{i=1}^{k-1} \alpha _i \left( {\begin{array}{c}k\\ i+1\end{array}}\right) < k. \end{aligned}$$

Moreover,

$$\begin{aligned} \sum _{i=1}^{k-1} \alpha _i \left( {\begin{array}{c}k-1\\ i\end{array}}\right)&= \sum _{i=1}^{k-1} \alpha _i \,\frac{i+1}{k} \left( {\begin{array}{c}k\\ i+1\end{array}}\right) \\&= \sum _{i=1}^{k-1} \alpha _i \,\frac{i+1}{k}\, \frac{k-i}{k+1} \left( {\begin{array}{c}k+1\\ i+1\end{array}}\right) \\&\ge \frac{1}{k+1} \sum _{i=1}^{k-1} \alpha _i \left( {\begin{array}{c}k+1\\ i+1\end{array}}\right) > 1. \end{aligned}$$

Thus we may invoke Lemma 8.1 to conclude K is w.h.p. supported on less than \(D+k\) vertices. As in that proof, we may order the vertices \(v_1, \ldots , v_{k+m}\) for some \(m < D\). We prove our result by removing one vertex at a time from K and counting the faces containing it that must also be removed.

Since we have a nontrivial cycle every vertex is contained in at least k faces of dimension \(k-1\). Removing \(v_{k+m}\) first, we observe the fewest faces are removed if \(v_{k+m}\) is contained in exactly k faces of dimension \(k-1\). In this case we then remove \(\left( {\begin{array}{c}k\\ i\end{array}}\right) \)i-dimensional faces for each i. We then remove vertices \(v_{k+m-1}, \ldots , v_{k+1}\), and by construction each one was contained in a \((k-1)\)-face comprised exclusively of vertices before it, so at each removal step we remove at least that simplex. Thus at each removal we account for at least \(\left( {\begin{array}{c}k-1\\ i\end{array}}\right) \)i-faces for each i. The last k vertices correspond to our initial \((k-1)\)-simplex. Putting this together we get a lower bound on the probability of a subcomplex isomorphic to K appearing. Letting \(B_K\) denote the probability X contains such a subcomplex,

$$\begin{aligned} {\mathbb {P}}(B_K)&\le (k+m)! \left( {\begin{array}{c}n\\ k+m\end{array}}\right) \left( \prod _{i=1}^{k-1} p_i^{\left( {\begin{array}{c}k\\ i\end{array}}\right) } \right) \left( \prod _{i=1}^{k-1} p_i^{\left( {\begin{array}{c}k-1\\ i\end{array}}\right) } \right) ^{m-1} \left( \prod _{i=1}^{k-1} p_i^{\left( {\begin{array}{c}k\\ i+1\end{array}}\right) } \right) \\&\le n^{k+m} \left( \prod _{i=1}^{k-1} p_i^{\left( {\begin{array}{c}k+1\\ i+1\end{array}}\right) } \right) \left( \prod _{i=1}^{k-1} p_i^{\left( {\begin{array}{c}k-1\\ i\end{array}}\right) } \right) ^{m-1} \\&\le \left( n^{k+1} \prod _{i=1}^{k-1} p_i^{\left( {\begin{array}{c}k+1\\ i+1\end{array}}\right) } \right) \left( n^{m-1} \prod _{i=1}^{k-1} p_i^{\left( {\begin{array}{c}k-1\\ i\end{array}}\right) } \right) ^{m-1} \\&= o(1). \end{aligned}$$

The last line holds since

$$\begin{aligned} k+1< \sum _{i=1}^{k-1} \alpha _i \left( {\begin{array}{c}k+1\\ i+1\end{array}}\right) \; \text { and }\; 1 < \sum _{i=1}^{k-1} \alpha _i \left( {\begin{array}{c}k-1\\ i\end{array}}\right) . \end{aligned}$$

As there are finitely many isomorphism types of strongly connected \((k-1)\)-complexes on less than \(D+k\) vertices, we may apply this argument to each of them and apply a union bound to conclude that w.h.p. none of them are subcomplexes of X. Thus we w.h.p. have no nontrivial \((k-1)\)-cycles, and \(H_{k-1}(X, {\mathbb {Z}}) = 0\). \(\square \)