Extremal Cuts of Sparse Random Graphs

on YouTube ↗49m

" summary

Claim: for sparse random graphs (Erdos–Rényi or random regular) the extremal cuts have leading value nγ/4 and the first nontrivial correction is ± const · n√γ with the same constant p for max‑cut, max‑bisection and min‑bisection. Proof sketch: use concentration, interpolate the sparse Ising Hamiltonian to an SK Gaussian model, control d/dt of the log partition function via Poisson/Gaussian calculus or Lindeberg, then send β→∞. The constant p equals the SK ground‑state energy per spin.

AI-written summary · about

" chapters (11)

1. 0:00Start
2. 5:15Complexity: hard to solve (worst case)
3. 7:08Random graph models
4. 12:15A classical argument
5. 16:08Extremal cuts and Ising spins
6. 19:12Statistical physics: Ising measures
7. 21:01Insights from statistical physics Conjectures
8. 32:05Proof strategy
9. 35:45Interpolation: Two steps
10. 37:27Step 1: 'smooth max'
11. 45:20Conclusion

" related talks

• 01h 31mGraphons and Graph Limits 2Christian Borgs · Graph Limits and Processes on Networks: From Epidemics to Misinformation Boot Camp
• 01h 17mPedagogical Talk: Random Optimisation ProblemsAmin Coja-Oghlan · Computational Phase Transitions (Simons Institute, 2020)
• 52mMax Cut with Linear Programs: Sherali-Adams Strikes BackTselil Schramm · Hyperbolic Polynomials and Hyperbolic Programming
• 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
• 56mTesting Thresholds for High-dimensional Sparse Random Geometric GraphsSiqi Liu · Structural Results 2023
• 24mRandom Max-CSPs Inherit Algorithmic Hardness from Spin GlassesChris Jones, Kunal Marwaha, Juspreet Singh Sandhu, Jonathan Shi · ITCS 2023
• 24mRobust Parameter Estimation For Random GraphsJayadev Acharya · Rigorous Evidence for Information-Computation Trade-offs