Seminars & Colloquia Calendar

Download as iCal file

Discrete Math

On the threshold for simple connectivity in random 2-complexes

Yuval Peled (NYU)

Location:  Hill 705
Date & time: Monday, 16 September 2019 at 2:00PM - 3:00PM

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.

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.