BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
The d-dimensional algebraic connectivity ad(G) of a graph G=(V,E), introduced by Jordán and Tanigawa, is a quantitative measure of the d-dimensional rigidity of G that is defined in terms of the eigenvalues of stiffness matrices (which are analogues of the graph Laplacian) associated to mappings of the vertex set V into Rd. Here, we analyze the d-dimensional algebraic connectivity of complete graphs. In particular, we show that, for d≥3, ad(Kd+1)=1, and for n≥2d, ⌈2dn⌉−2d+1≤ad(Kn)≤3(d−1)2n+31.
We consider the Erdős-Rényi evolution of random graphs, where a new uniformly distributed edge is added to the graph in every step. For every fixed d≥1, we show that with high probability, the graph becomes rigid in Rd at the very moment its minimum degree becomes d, and it becomes globally rigid in Rd at the very moment its minimum degree becomes d+1.
A \emph{stacked triangulation} of a d-simplex o={1,…,d+1} (d≥2) is a triangulation obtained by repeatedly subdividing a d-simplex into d+1 new ones via a new vertex (the case d=2 is known as an Appolonian network). We study the occurrence of such a triangulation in the Linial--Meshulam model, i.e., for which p does the random simplicial complex Y∼Yd(n,p) contain the faces of a stacked triangulation of the d-simplex o, with its internal vertices labeled in [n]. In the language of bootstrap percolation in hypergraphs, it pertains to the threshold for Kd+2d+1, the (d+1)-uniform clique on d+2 vertices. Our main result identifies this threshold for every d≥2, showing it is asymptotically (αdn)−1/d, where αd is the growth rate of the Fuss--Catalan numbers of order d. The proof hinges on a second moment argument in the supercritical regime, and on Kalai's algebraic shifting in the subcritical regime.
We study noise sensitivity of properties of the largest components (Cj)j≥1 of the random graph G(n,p) in its critical window p=(1+λn−1/3)/n. For instance, is the property "∣C1∣ exceeds its median size" noise sensitive? Roberts and Şengül (2018) proved that the answer to this is yes if the noise ε is such that ε≫n−1/6, and conjectured the correct threshold is ε≫n−1/3. That is, the threshold for sensitivity should coincide with the critical window---as shown for the existence of long cycles by the first author and Steif (2015). We prove that for ε≫n−1/3 the pair of vectors n−2/3(∣Cj∣)j≥1 before and after the noise converges in distribution to a pair of i.i.d. random variables, whereas for ε≪n−1/3 the ℓ2-distance between the two goes to 0 in probability. This confirms the above conjecture: any Boolean function of the vector of rescaled component sizes is sensitive in the former case and stable in the latter. We also look at the effect of the noise on the metric space n−1/3(Cj)j≥1. E.g., for ε≥n−1/3+o(1), we show that the joint law of the spaces before and after the noise converges to a product measure, implying noise sensitivity of any property seen in the limit, e.g., "the diameter of C1 exceeds its median."
The random 2-dimensional simplicial complex process starts with a complete graph on n vertices, and in every step a new 2-dimensional face, chosen uniformly at random, is added. We prove that with probability tending to 1 as n→∞, the first homology group over Z vanishes at the very moment when all the edges are covered by triangular faces.
It is well-known that the G(n,p) model of random graphs undergoes a dramatic change around p=n1. It is here that the random graph is, almost surely, no longer a forest, and here it first acquires a giant (i.e., order Ω(n)) connected component. Several years ago, Linial and Meshulam have introduced the Xd(n,p) model, a probability space of n-vertex d-dimensional simplicial complexes, where X1(n,p) coincides with G(n,p). Within this model we prove a natural d-dimensional analog of these graph theoretic phenomena. Specifically, we determine the exact threshold for the nonvanishing of the real d-th homology of complexes from Xd(n,p). We also compute the real Betti numbers of Xd(n,p) for p=c/n. Finally, we establish the emergence of giant shadow at this threshold. (For d=1 a giant shadow and a giant component are equivalent). Unlike the case for graphs, for d≥2 the emergence of the giant shadow is a first order phase transition.
This article surveys some of the work done in recent years on random simplicial complexes. We mostly consider higher-dimensional analogs of the well known phase transition in G(n,p) theory that occurs at p=n1 . Our main objective is to provide a more streamlined and unified perspective of some of the papers in this area.
Given a random 3-uniform hypergraph H=H(n,p) on n vertices where each triple independently appears with probability p, consider the following graph process. We start with the star G0 on the same vertex set, containing all the edges incident to some vertex v0, and repeatedly add an edge xy if there is a vertex z such that xz and zy are already in the graph and xzy∈H. We say that the process propagates if it reaches the complete graph before it terminates. In this paper we prove that the threshold probability for propagation is p=2n1. We conclude that p=2n1 is an upper bound for the threshold probability that a random 2-dimensional simplicial complex is simply connected.
Let F be an n-vertex forest. We say that an edge e∈/F is in the shadow of F if F∪{e} contains a cycle. It is easy to see that if F is "almost a tree", that is, it has n−2 edges, then at least ⌊4n2⌋ edges are in its shadow and this is tight. Equivalently, the largest number of edges an n-vertex cut can have is ⌊4n2⌋. These notions have natural analogs in higher d-dimensional simplicial complexes, graphs being the case d=1. The results in dimension d>1 turn out to be remarkably different from the case in graphs. In particular the corresponding bounds depend on the underlying field of coefficients. We find the (tight) analogous theorems for d=2. We construct 2-dimensional "Q-almost-hypertrees" (defined below) with an empty shadow. We also show that the shadow of an "F2-almost-hypertree" cannot be empty, and its least possible density is Θ(n1). In addition we construct very large hyperforests with a shadow that is empty over every field. For d≥4 even, we construct d-dimensional F2-almost-hypertree whose shadow has density on(1). Finally, we mention several intriguing open questions.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.