# The Threshold for Integer Homology in Random d-Complexes

@article{Hoffman2017TheTF, title={The Threshold for Integer Homology in Random d-Complexes}, author={Christopher Hoffman and Matthew Kahle and Elliot Paquette}, journal={Discrete \& Computational Geometry}, year={2017}, volume={57}, pages={810-823} }

Let $$Y \sim Y_d(n,p)$$Y∼Yd(n,p) denote the Bernoulli random d-dimensional simplicial complex. We answer a question of Linial and Meshulam from 2003, showing that the threshold for vanishing of homology $$H_{d-1}(Y; \mathbb {Z})$$Hd-1(Y;Z) is less than $$40d (d+1) \log n / n$$40d(d+1)logn/n. This bound is tight, up to a constant factor which depends on d.

#### Topics from this paper

#### 24 Citations

On simple connectivity of random 2-complexes

- Mathematics
- 2018

The fundamental group of the $2$-dimensional Linial-Meshulam random simplicial complex $Y_2(n,p)$ was first studied by Babson, Hoffman and Kahle. They proved that the threshold probability for simple… Expand

Small Simplicial Complexes with Prescribed Torsion in Homology

- Mathematics, Computer Science
- Discret. Comput. Geom.
- 2019

It is proved that for every d≥2 there exist constants c_d and C_d so that for any finite abelian group Td(G) which matches the known lower bound up to a constant factor. Expand

Topology and geometry of random 2-dimensional hypertrees

- Mathematics
- 2020

A hypertree, or $\mathbb{Q}$-acyclic complex, is a higher-dimensional analogue of a tree. We study random $2$-dimensional hypertrees according to the determinantal measure suggested by Lyons. We are… Expand

Eigenvalue confinement and spectral gap for random simplicial complexes

- Mathematics, Computer Science
- Random Struct. Algorithms
- 2017

The main ingredient of the proof is a Furedi-Koml\'os-type argument for random simplicial complexes, which may be regarded as sparse random matrix models with dependent entries, and it is proved that the global distribution of the eigenvalues is asymptotically given by the semicircle law. Expand

Vanishing of cohomology groups of random simplicial complexes

- Computer Science, Mathematics
- Random Struct. Algorithms
- 2020

A hitting time result is proved, relating the vanishing of these cohomology groups to the disappearance of the last minimal obstruction, and the asymptotic distribution of the dimension of the $j$-th cohomological group inside the critical window is studied. Expand

Integral Homology of Random Simplicial Complexes

- Mathematics, Computer Science
- Discret. Comput. Geom.
- 2018

It is proved that with probability tending to 1 as narrowarrow n→∞, the first homology group over Z, Z vanishes at the very moment when all the edges are covered by triangular faces. Expand

The threshold for d-collapsibility in random complexes

- Mathematics, Computer Science
- Random Struct. Algorithms
- 2016

For every c>i¾?d, a complex drawn from Xdn,cn is asymptotically almost surely not d-collapsible, and here it is shown that this is indeed the correct threshold. Expand

Algebraic and combinatorial expansion in random simplicial complexes

- Mathematics
- Random Structures & Algorithms
- 2021

In this paper we consider the expansion properties and the spectrum of the combinatorial Laplace operator of a $d$-dimensional Linial-Meshulam random simplicial complex, above the cohomological… Expand

Cohomology groups of non-uniform random simplicial complexes

- Mathematics
- 2019

We consider a generalised model of a random simplicial complex, which arises from a random hypergraph. Our model is generated by taking the downward-closure of a non-uniform binomial random… Expand

Spectral Gaps of Random Graphs and Applications

- Mathematics
- International Mathematics Research Notices
- 2019

We study the spectral gap of the Erdős–Rényi random graph through the connectivity threshold. In particular, we show that for any fixed $\delta> 0$ if $$\begin{equation*} p \geq \frac{(1/2 +… Expand

#### References

SHOWING 1-10 OF 20 REFERENCES

Homological connectivity of random k-dimensional complexes

- Mathematics, Computer Science
- Random Struct. Algorithms
- 2009

It is shown that p=(k \log n)/n is a sharp threshold for the vanishing of H_{k-1}(Y;R), the reduced homology group of Y with coefficients in a finite abelian group R. Expand

Sharp vanishing thresholds for cohomology of random flag complexes

- Mathematics
- 2012

For every $k \ge 1$, the $k$th cohomology group $H^k(X, \Q)$ of the random flag complex $X \sim X(n,p)$ passes through two phase transitions: one where it appears, and one where it vanishes. We… Expand

The fundamental group of random 2-complexes

- Mathematics
- 2007

We study Linial-Meshulam random 2-complexes, which are two-dimensional analogues of Erd\H{o}s-R\'enyi random graphs. We find the threshold for simple connectivity to be p = n^{-1/2}. This is in… Expand

Collapsibility and Vanishing of Top Homology in Random Simplicial Complexes

- Mathematics, Computer Science
- Discret. Comput. Geom.
- 2013

It is shown that there exists a constant $$\gamma _d< c_d c-d$$ and a fixed field $$\mathbb{F }$$, asymptotically almost surely $$H_d(Y;\mathBB{F }) \ne 0$$, and conjecture this bound to be sharp. Expand

Topology of Random 2-Complexes

- Mathematics, Computer Science
- Discret. Comput. Geom.
- 2012

This paper studies the Linial–Meshulam model of random two-dimensional simplicial complexes and proves that for p≪n−1 a random 2-complex Y collapses simplicially to a graph and, in particular, the fundamental group π1(Y) is free and H2(Y)=0, asymptotically almost surely. Expand

Homological Connectivity Of Random 2-Complexes

- Mathematics, Computer Science
- Comb.
- 2006

It is shown that for any function ω(n) that tends to infinity, H_{1) is the first homology group of Y with mod 2 coefficients. Expand

Spectral Gaps of Random Graphs and Applications

- Mathematics
- International Mathematics Research Notices
- 2019

We study the spectral gap of the Erdős–Rényi random graph through the connectivity threshold. In particular, we show that for any fixed $\delta> 0$ if $$\begin{equation*} p \geq \frac{(1/2 +… Expand

Enumeration ofQ-acyclic simplicial complexes

- Mathematics
- 1983

Let (n, k) be the class of all simplicial complexesC over a fixed set ofn vertices (2≦k≦n) such that: (1)C has a complete (k−1)-skeleton, (2)C has precisely (kn−1)k-faces, (3)Hk(C)=0. We prove that… Expand

A random graph

- Mathematics
- 1981

Abstract : Let X(1),X(2), ..., X(n) be independent random variables such that P(X(i) = j) = P sub j , j = 1,2, ..., n, sum from j = 1 to n of P sub j = 1 and consider a graph with n nodes numbered… Expand

Perfect forms and the Vandiver conjecture

- Mathematics
- 1998

Let p be an odd prime, n an odd positive integer and C the p-Sylow subgroup the class group of the p-cyclotomic extension of the rationals. When log(p) is bigger than n**(224n**4), we prove that the… Expand