Combinatorics: Zur Luria (JCE) "On the threshold for simple connectivity in random 2-complexes"

Speaker: Zur Luria, JCE
Title: On the threshold for simple connectivity in random 2-complexes
Let Y ~ Y_2(n,p) be a random Linial-Meshulam 2-dimensional simplicial complex in which each 2-face is chosen with probability p. In this talk, we consider Y's fundamental group. Babson, Hoffman and Kahle proved that the threshold for the fundamental group to vanish, i.e. simple connectivity, is approximately p=n^(-1/2). We show that in fact this threshold is at most (c n)^(-1/2) for c=4^4/3^3, and conjecture that this is the true threshold. In fact, we prove a sharp threshold for the stronger property that every cycle has a triangulation that uses only triangles from Y. Interestingly, although the second moment method fails, due to strong dependencies between trianguations, this difficulty can be overcome by selecting an appropriate subfamily F of triangulations, and proving that every cycles has a triangulation from F that uses only the triangles of Y.
The talk is based on a joint work with Yuval Peled.


Mon, 31/12/2018 - 11:00 to 13:00


CS bldg, room B500, Safra campus Givat Ram