On the Chromatic Number of Random Regular Graphs

on YouTube ↗35m

" summary

Determines the chromatic number of random d‑regular graphs for almost all d by pinning explicit upper and lower bounds and showing an explicit integer D_k that matches the chromatic number for a sequence of d with asymptotic density ~0.614. Uses the second moment method on good k‑colorings and overlap matrices, works in the configuration model and planted model, controls cluster sizes (typical clusters vs expected), gets an unresolved ambiguity only on intervals of length ≈0.386, and proves a condensation phase transition.

AI-written summary · about

" chapters (5)

1. 0:00Start
2. 0:21Introduction
3. 3:12Results
4. 16:00Proof
5. 30:18Conclusion

" related talks

• 44mEquitable ColoringsAfonso Bandeira · Computational Phase Transitions (Simons Institute, 2020)
• 34mSampling From the Random Cluster Model at All Temperatures on Random GraphsWill Perkins · Computational Phase Transitions (Simons Institute, 2020)
• 01h 17mPedagogical Talk: Random Optimisation ProblemsAmin Coja-Oghlan · Computational Phase Transitions (Simons Institute, 2020)
• 56mTesting Thresholds for High-dimensional Sparse Random Geometric GraphsSiqi Liu · Structural Results 2023
• 01h 04mHigher-dimensional Expansion of Random Geometric ComplexesTselil Schramm · Structural Results 2023
• 01h 31mGraphons and Graph Limits 2Christian Borgs · Graph Limits and Processes on Networks: From Epidemics to Misinformation Boot Camp
• 35mLocal Statistics, Semidefinite Programming, and Community Detection IISidhanth Mohanty · Computational Phase Transitions (Simons Institute, 2020)
• 33mOn the Problems Related to Waring Rank and Border Waring RankPranjal Dutta · Proof Complexity and Meta-Mathematics 2023