Sparse Dense Dichotomy and Liquid Graphs

on YouTube ↗26m

" summary

Defines bounded expansion via shallow topological minors and degeneration and claims that planting any bounded‑degree graph then sprinkling random edges at probability d/n produces a class of liquid graphs that still has bounded expansion (proof: control of shallow minors and degeneracy). Shows sharp failure cases: tiny perturbations can create dense minors (star-of-√n stars plus d/n edges yields near‑complete contractions). Uses that bounded‑expansion classes admit linear model‑checking algorithms and restricted dualities to get efficient H‑coloring procedures for the randomized regimes.

AI-written summary · about

" chapters (13)

1. 0:00Introduction
2. 1:27Graphs and topological minors
3. 3:58Bounded expansion in graph classes
4. 7:13Sparse versus dense graphs
5. 10:25Liquid graphs and perturbations
6. 12:51Graph robustness detour
7. 14:16Nowhere dense class characterizations
8. 16:23Graph coloring applications
9. 17:31Graph coloring technical result
10. 20:23Restricted dualities and algorithms
11. 21:55Coloring algorithm conjectures
12. 23:43Summary
13. 24:29Randomness and nowhere dense classes