Bootstrap Percolation on Random Graphs

on YouTube ↗42m

" summary

Proves an explicit formula for the critical initial size a_c for r-threshold bootstrap percolation on G(n,p) when n^{-1} << p << n^{-1/r}, shows the critical window has width ~sqrt(a_c), and upgrades “with high probability” to an exponential failure bound (failure ≲ exp(−const · Ω^2/t0)). Proof combines a refined martingale concentration for the early/subcritical phase, a giant-component emergence in a related r−1-neighbor subgraph, and Chernoff-type estimates to grow that giant to size n, all with concrete parameter dependencies.

AI-written summary · about

" chapters (11)

1. 0:00Introduction
2. 0:30What is Percolation
3. 1:26Populational Graph
4. 13:43Critical
5. 15:54High Probability
6. 24:01Proof
7. 26:32Whiteboard
8. 31:18Martingale
9. 33:43Total Ordering
10. 35:53Subcritical
11. 36:43Supercritical

" related talks

• 56mTesting Thresholds for High-dimensional Sparse Random Geometric GraphsSiqi Liu · Structural Results 2023
• 24mRobust Parameter Estimation For Random GraphsJayadev Acharya · Rigorous Evidence for Information-Computation Trade-offs
• 34mSampling From the Random Cluster Model at All Temperatures on Random GraphsWill Perkins · Computational Phase Transitions (Simons Institute, 2020)
• 45mRandom Walks on Directed GraphsFan Chung · Spectral Algorithms: From Theory to Practice 2014
• 01h 04mHigher-dimensional Expansion of Random Geometric ComplexesTselil Schramm · Structural Results 2023
• 41mGeneralization Bounds for Uniformly Stable AlgorithmsVitaly Feldman · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 01h 03mSampling Crash CourseAndreas Eberle · Geometric Methods in Optimization and Sampling Boot Camp
• 31mMismatched Monte Carlo Algorithms For The Planted Clique ProblemMaria Chiara Angelini · Rigorous Evidence for Information-Computation Trade-offs