Seminars & Colloquia Calendar

Download as iCal file

Discrete Math

Threshold for stacked triangulations

Eyal Lubetzky (Courant Inst. at NYU)

Location:  Hill Center Room 705
Date & time: Monday, 18 April 2022 at 2:00PM - 3:00PM

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.

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.