On the threshold for simple connectivity in random 2-complexes

Yuval Peled, New York University

Date and time: 6pm, Tuesday, April 16, 2019

Place: Courant Institute, WWH1314

Let $Y \sim Y_2(n,p)$ be a random 2-dimensional simplicial complex in which each 2-face is chosen independently with probability $p$. Babson, Hoffman and Kahle proved that $Y$ is not simply connected with high probability, provided that $p \ll n^{-1/2}$. We show that $Y$ is simply connected with high probability if $p > (c n)^{-1/2}$ where the constant $c=4^4/3^3$, and conjecture that this is a sharp threshold. In fact, we prove that $(cn)^{-1/2}$ is a sharp threshold for the stronger property that every cycle of length 3 is the boundary of a triangulated disk that is contained in $Y$. The proof uses the Poisson paradigm, and relies on a classical result of Tutte on the enumeration of planar triangulations.

The talk is based on a joint work with Zur Luria.