Equitable Colorings

on YouTube ↗44m

" summary

Random d‑regular graphs have a chromatic lower bound from Hoffman’s spectral bound, and evidence here argues that the bound is essentially tight: an equitable planting constructs colorings whose planted cut is an exact eigenvector so usual spectral and BP/local‑statistics and low‑degree tests fail, suggesting Hoffman bound optimal up to constants (gap about factor two). Construction needs a subsequent small random edge flip (noise) to hide the algebraic signature; small‑d cases and finding the correct noise operator remain open practical obstacles.

AI-written summary · about

" chapters (8)

1. 0:00Introduction and setup
2. 4:20Graph coloring basics
3. 8:17Spectral bounds and cuts
4. 13:26Hoffman's bound analysis
5. 18:57Computational quiet planting
6. 27:22Eigenvector construction
7. 34:00Technical challenges
8. 36:16Questions and discussion

" related talks

• 35mOn the Chromatic Number of Random Regular GraphsSamuel Hetterich · Random Instances and Phase Transitions (Simons Institute, 2016)
• 45mRandom Walks on Directed GraphsFan Chung · Spectral Algorithms: From Theory to Practice 2014
• 11mSharp Threshold for the Planted Matching ProblemDana Yang · Meet the Fellows Welcome Event
• 49mRecent Advances in Counting Sparse GraphsSourav Chatterjee · Random Instances and Phase Transitions (Simons Institute, 2016)
• 29mSampling Algorithms for Combinatorial Pure ExplorationAnupam Gupta · Optimization, Statistics and Uncertainty
• 56mGraph Matching: Relax or Not?Alex Bronstein · Spectral Algorithms: From Theory to Practice 2014
• 49mExtremal Cuts of Sparse Random GraphsAmir Dembo · Random Instances and Phase Transitions (Simons Institute, 2016)
• 52mConstrained Subset Selection Problems under Diversity MeasuresMohit Singh · Hyperbolic Polynomials and Hyperbolic Programming