Inside the critical window for cohomology of random k‐complexes

We prove sharper versions of theorems of Linial–Meshulam and Meshulam–Wallach which describe the behavior for ‐cohomology of a random k‐dimensional simplicial complex within a narrow transition window. In particular, we show that if Y is a random k‐dimensional simplicial complex with each k‐simplex appearing i.i.d. with probability with and fixed, then the dimension of cohomology is asymptotically Poisson distributed with mean . In the k = 2 case we also prove that in an accompanying growth process, with high probability, vanishes exactly at the moment when the last ‐simplex gets covered by a k‐simplex, a higher‐dimensional analogue of a “stopping time” theorem about connectivity of random graphs due to Bollobás and Thomason. Random Struct. Alg., 2015 © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 102–124, 2016     

The asphericity of random 2‐dimensional complexes

We study random 2‐dimensional complexes in the Linial–Meshulam model and prove that for the probability parameter satisfying a random 2‐complex Y contains several pairwise disjoint tetrahedra such that the 2‐complex Z obtained by removing any face from each of these tetrahedra is aspherical. Moreover, we prove that the obtained complex Z satisfies the Whitehead conjecture, i.e. any subcomplex is aspherical. This implies that Y is homotopy equivalent to a wedge where Z is a 2‐dimensional aspherical simplicial complex. We also show that under the assumptions where c > 3 and , the complex Z is genuinely 2‐dimensional and in particular, it has sizable 2‐dimensional homology; it follows that in the indicated range of the probability parameter p the cohomological dimension of the fundamental group of a random 2‐complex equals 2. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 261–273, 2015     

Simplicial complexes: Spectrum,homology and random walks

This paper studies the dynamical and asymptotic aspects of high‐dimensional expanders. We define a stochastic process on simplicial complexes of arbitrary dimension, which detects the existence of homology in the same way that a random walk on a finite graph reflects its connectedness. Through this, we obtain high‐dimensional analogues of graph properties such as bipartiteness, return probability, amenability and transience/recurrence. In the second part of the paper we generalize Kesten's result on the spectrum of regular trees, and of the connection between return probabilities and spectral radius. We study the analogue of the Alon‐Boppana theorem on spectral gaps, and exhibit a counterexample for its high‐dimensional counterpart. We show, however, that under some assumptions the theorem does hold ‐ for example, if the codimension‐one skeletons of the complexes in question form a family of expanders. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 225–261, 2017     

On k‐connectivity for a geometric random graph

For n points uniformly randomly distributed on the unit cube in d dimensions, with d≥2, let ρ_n (respectively, σ_n) denote the minimum r at which the graph, obtained by adding an edge between each pair of points distant at most r apart, is k‐connected (respectively, has minimum degree k). Then P[ρ_n=σ_n]→1 as n→∞. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 15, 145–164, 1999     

On the vanishing of homology in random Čech complexes

We compute the homology of random ?ech complexes over a homogeneous Poisson process on the d‐dimensional torus, and show that there are, coarsely, two phase transitions. The first transition is analogous to the Erd?s ‐Rényi phase transition, where the ?ech complex becomes connected. The second transition is where all the other homology groups are computed correctly (almost simultaneously). Our calculations also suggest a finer measurement of scales, where there is a further refinement to this picture and separation between different homology groups. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 51, 14–51, 2017     

The threshold for d‐collapsibility in random complexes*

In this paper we determine the threshold for d‐collapsibility in the probabilistic model X_d(n,p) of d‐dimensional simplicial complexes. A lower bound for this threshold was established in (Aronshtam and Linial, Random Struct. Algorithms 46 (2015) 26–35), and here we show that this is indeed the correct threshold. Namely, for every c > η_d, a complex drawn from is asymptotically almost surely not d‐collapsible. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 260–269, 2016     

On random k‐out subgraphs of large graphs

We consider random subgraphs of a fixed graph with large minimum degree. We fix a positive integer k and let G_k be the random subgraph where each independently chooses k random neighbors, making kn edges in all. When the minimum degree then G_k is k‐connected w.h.p. for ; Hamiltonian for k sufficiently large. When , then G_k has a cycle of length for . By w.h.p. we mean that the probability of non‐occurrence can be bounded by a function (or ) where . © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 143–157, 2017     

Vanishing of cohomology groups of random simplicial complexes

We consider k‐dimensional random simplicial complexes generated from the binomial random (k + 1)‐uniform hypergraph by taking the downward‐closure. For 1 ≤ j ≤ k ? 1, we determine when all cohomology groups with coefficients in from dimension one up to j vanish and the zero‐th cohomology group is isomorphic to . This property is not deterministically monotone for this model, but nevertheless we show that it has a single sharp threshold. Moreover we prove a hitting time result, relating the vanishing of these cohomology groups to the disappearance of the last minimal obstruction. We also study the asymptotic distribution of the dimension of the j‐th cohomology group inside the critical window. As a corollary, we deduce a hitting time result for a different model of random simplicial complexes introduced by Linial and Meshulam, previously only known for dimension two.     

Law of large numbers for Betti numbers of homogeneous and spatially independent random simplicial complexes

The Linial–Meshulam complex model is a natural higher dimensional analog of the Erd?s–Rényi graph model. In recent years, Linial and Peled established a limit theorem for Betti numbers of Linial–Meshulam complexes with an appropriate scaling of the underlying parameter. The present article aims to extend that result to more general random simplicial complex models. We introduce a class of homogeneous and spatially independent random simplicial complexes, including the Linial–Meshulam complex model and the random clique complex model as special cases, and we study the asymptotic behavior of their Betti numbers. Moreover, we obtain the convergence of the empirical spectral distributions of their Laplacians. A key element in the argument is the local weak convergence of simplicial complexes. Inspired by the work of Linial and Peled, we establish the local weak limit theorem for homogeneous and spatially independent random simplicial complexes.     

The VC dimension of k‐uniform random hypergraphs

A set of vertices is shattered in a hypergraph if any of its subsets is obtained as the intersection of an edge with the set. The VC dimension is the size of the largest shattered subset. Under the binomial model of k‐uniform random hypergraphs, the threshold function for the VC dimension to be larger than a given integer is obtained. The same is done for the testing dimension, which is the largest integer d such that all sets of cardinality d are shattered. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

When does the top homology of a random simplicial complex vanish?

Several years ago Linial and Meshulam (Combinatorica 26 (2006) 457–487) introduced a model called of random n‐vertex d‐dimensional simplicial complexes. The following question suggests itself very naturally: What is the threshold probability at which the d‐dimensional homology of such a random d‐complex is, almost surely, nonzero? Here we derive an upper bound on this threshold. Computer experiments that we have conducted suggest that this bound may coincide with the actual threshold, but this remains an open question. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 26–35, 2015     

Eigenvalue confinement and spectral gap for random simplicial complexes

We consider the adjacency operator of the Linial‐Meshulam model for random simplicial complexes on n vertices, where each d‐cell is added independently with probability p to the complete ‐skeleton. Under the assumption , we prove that the spectral gap between the smallest eigenvalues and the remaining eigenvalues is with high probability. This estimate follows from a more general result on eigenvalue confinement. In addition, we prove that the global distribution of the eigenvalues is asymptotically given by the semicircle law. The main ingredient of the proof is a Füredi‐Komlós‐type argument for random simplicial complexes, which may be regarded as sparse random matrix models with dependent entries. © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 51, 506–537, 2017     

Graph limits of random graphs from a subset of connected k‐trees

For any set Ω of non‐negative integers such that , we consider a random Ω‐k‐tree G_n,k that is uniformly selected from all connected k‐trees of (n + k) vertices such that the number of (k + 1)‐cliques that contain any fixed k‐clique belongs to Ω. We prove that G_n,k, scaled by where H_k is the kth harmonic number and σ_Ω > 0, converges to the continuum random tree . Furthermore, we prove local convergence of the random Ω‐k‐tree to an infinite but locally finite random Ω‐k‐tree G_∞,k.     

Minimum spanning acycle and lifetime of persistent homology in the Linial–Meshulam process

This paper studies a higher dimensional generalization of Frieze's ‐limit theorem on the d‐Linial–Meshulam process. First, we define spanning acycles as a higher dimensional analogue of spanning trees, and connect its minimum weight to persistent homology. Then, our main result shows that the expected weight of the minimum spanning acycle behaves in . © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 51, 315–340, 2017     

Quasi‐polynomial mixing of critical two‐dimensional random cluster models

We study the Glauber dynamics for the random cluster (FK) model on the torus with parameters (p,q), for q ∈ (1,4] and p the critical point p_c. The dynamics is believed to undergo a critical slowdown, with its continuous‐time mixing time transitioning from for p ≠ p_c to a power‐law in n at p = p_c. This was verified at p ≠ p_c by Blanca and Sinclair, whereas at the critical p = p_c, with the exception of the special integer points q = 2,3,4 (where the model corresponds to the Ising/Potts models) the best‐known upper bound on mixing was exponential in n. Here we prove an upper bound of at p = p_c for all q ∈ (1,4], where a key ingredient is bounding the number of nested long‐range crossings at criticality.     

On connectivity,conductance and bootstrap percolation for a random k‐out,age‐biased graph

A uniform attachment graph (with parameter k), denoted G_n,k in the paper, is a random graph on the vertex set [n], where each vertex v makes k selections from [v ? 1] uniformly and independently, and these selections determine the edge set. We study several aspects of this graph. Our motivation comes from two similarly constructed, well‐studied random graphs: k‐out graphs and preferential attachment graphs. In this paper, we find the asymptotic distribution of its minimum degree and connectivity, and study the expansion properties of G_n,k to show that the conductance of G_n,k is of order . We also study the bootstrap percolation on G_n,k, where r infected neighbors infect a vertex, and show that if the probability of initial infection of a vertex is negligible compared to then with high probability (whp) the disease will not spread to the whole vertex set, and if this probability exceeds by a sub‐logarithmical factor then the disease whp will spread to the whole vertex set.     

A Sharp Threshold for k‐Colorability

Let k be a fixed integer and f_k(n, p) denote the probability that the random graph G(n, p) is k‐colorable. We show that for k≥3, there exists d_k(n) such that for any ϵ>0, (1) As a result we conclude that for sufficiently large n the chromatic number of G(n, d/n) is concentrated in one value for all but a small fraction of d>1. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 14, 63–70, 1999     

On an online random k‐SAT model

Given n Boolean variables x₁,…,x_n, a k‐clause is a disjunction of k literals, where a literal is a variable or its negation. Suppose random k‐clauses are generated one at a time and an online algorithm accepts or rejects each clause as it is generated. Our goal is to accept as many randomly generated k‐clauses as possible with the condition that it must be possible to satisfy every clause that is accepted. When cn random k‐clauses on n variables are given, a natural online algorithm known as Online‐Lazy accepts an expected (1 ? )cn + a_kn clauses for some constant a_k. If these clauses are given offline, it is possible to do much better, (1 ? )cn + Ω( )n can be accepted whp . The question of closing the gap between a_k and Ω( ) for the online version remained open. This article shows that for any k ≥ 1, any online algorithm will accept less than (1 ? )cn + (ln 2)n k‐clauses whp , closing the gap between the constant and Ω( ). Furthermore we show that this bound is asymptotically tight as k → ∞. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Random walks on simplicial complexes and harmonics

In this paper, we introduce a class of random walks with absorbing states on simplicial complexes. Given a simplicial complex of dimension d, a random walk with an absorbing state is defined which relates to the spectrum of the k‐dimensional Laplacian for 1 ≤ k ≤ d. We study an example of random walks on simplicial complexes in the context of a semi‐supervised learning problem. Specifically, we consider a label propagation algorithm on oriented edges, which applies to a generalization of the partially labelled classification problem on graphs. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 379–405, 2016