5/3/2022 CMSA Combinatorics, Physics, and Probability Seminar

Venue: Virtual

Speaker: Yuval Peled (Hebrew University of Jerusalem)

Title: The threshold for stacked triangulations

Abstract: Consider a bootstrap percolation process that starts with a set of `infected’ triangles $Y \subseteq \binom{[n]}3$, and a new triangle f gets infected if there is a copy of K_4^3 (= the boundary of a tetrahedron) in which f is the only not-yet infected triangle.  
Suppose that every triangle is initially infected independently with probability p=p(n), what is the threshold probability for percolation — the event that all triangles get infected? How many new triangles do get infected in the subcritical regime?

This notion of percolation can be viewed as a simplification of simple-connectivity. Namely, a stacked triangulation of a triangle is obtained by repeatedly subdividing an inner face into three faces.
We ask: for which $p$ does the random simplicial complex Y_2(n,p) contain, for every triple $xyz$, the faces of a stacked triangulation of $xyz$ whose internal vertices are arbitrarily labeled in [n].

We consider this problem in every dimension d>=2, and our main result identifies a sharp probability threshold for percolation, showing it is asymptotically (c_d*n)^(-1/d), where c_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.

Joint work with Eyal Lubetzky.

Related Posts