Yuval Peled, New York University (NYU)

Abstract

Connectivity of random graphs is one of the classical and well-studied topics in random graph theory. We will talk about a topological 2-dimensional counterpart of this question. Consider a random 2-dimensional simplicial complex Y ~ Y_2(n,p) in which each 2-dimensional face is chosen independently with probability p=p(n). Babson, Hoffman and Kahle proved that Y is not simply connected with high probability, provided that p << n^{-1/2}. Here 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 threshold is sharp.

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 topological disk that is embedded in Y. The proof uses the Poisson paradigm and a classical theorem of Tutte on the enumeration of planar triangulations.

Joint work with Zur Luria.