Contagious Sets in Random Graphs

on YouTube ↗35m

" summary

Studies contagious sets in Erdős–Rényi random graphs G(n,p): given an activation threshold r, determines how large an initial set is required to eventually activate the whole graph and identifies threshold values of p for which small contagious sets (often of size r) exist. Uses probabilistic methods to analyze bootstrap percolation dynamics and to locate phase transitions in contagious-set size as functions of n, p, and r.

AI-written summary · about

" chapters (18)

1. 0:00Intro
2. 0:59Bootstrap Percolation Cont'd
3. 1:33Random activation
4. 4:20More recent
5. 6:40Our work
6. 9:26Bootstrap Percolation in Gin,p
7. 10:44Contagious sets in G(np)
8. 12:49Threshold for m(Gr)=r cont'd
9. 13:40Key Idea
10. 14:49Upper Bound in G(np)
11. 15:25Upper Bound Cont'd
12. 17:30UB cont'd
13. 18:02Summing up
14. 19:32Lower Bound
15. 21:44Threshold for m(6,2)=2: cont'd
16. 23:02Threshold for m(G,2)=2
17. 25:53Number of generations
18. 27:14Open Problem III

" 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)
• 45mOn the Estimation of the Cheeger ConstantEry Arias-Castro · Spectral Algorithms: From Theory to Practice 2014
• 45mRandom Walks on Directed GraphsFan Chung · Spectral Algorithms: From Theory to Practice 2014
• 41mGeneral Network Models with Transitive StructuresSharmodeep Bhattacharyya · Statistics in the Big Data Era 2022
• 35mDistributed Models for Private Analysis of Graph DataAdam M. Smith · Trust in Decentralized Systems 2026
• 54mExact Matching Of Random Graphs With Constant CorrelationCheng Mao · Algorithmic Advances for Statistical Inference with Combinatorial Structure