Eyal Lubetzky, New York University (NYU)

Abstract

The K_4^3 bootstrap percolation process is defined as follows: start with an initial set of "infected'' triangles Y, where each of the {n choose 3} triangles with vertices [n]={1,2,…,n} appears independently with probability p; then repeatedly add to it a new triangle {a,b,c} if there exists a tetrahedron in which this is the only missing face (i.e. if for some x the 3 triangles {a,b,x},{a,x,c},{x,b,c} are already infected). Let Y_infty denoted the final state of the process. What is the critical probability p(n) so that Y_infty would typically contain a specific triangle {1,2,3}? How many triangles would Y_infty typically have below that threshold? When would Y_infty typically contain all triangles? 

Equivalently, a stacked triangulation of a triangle with labels in [n], a.k.a. an Appolonian Network, is one obtained by repeatedly subdividing a triangle {a,b,c} into 3 new triangles {a,b,x},{a,x,c},{x,b,c} via a label x in [n]. The above questions would amount to asking, e.g., about the critical probability so that the random simplicial complex Y_2(n,p) would typically contain the faces of a stacked triangulation of every triangle {a,b,c}.

We consider these questions for a general dimension d geq 2, and our results identify the critical threshold p_c for stacked triangulations: we show that p_c is asymptotically (C(d) n)^(-1/d), where the constant 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 Yuval Peled.