HUJI Combinatorics Seminar 


When: Monday January 3rd, 2022, at 3PM (Israel time)


Where: B400 in the CS\Engineering building



Speaker: Yuval Peled (HUJI)

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) contains, 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.