Graphons and Graph Limits 1

on YouTube ↗01h 34m

" summary

Dense graph sequences have a single concrete limit object: graphon = W:[0,1]^2→[0,1], a symmetric feature-kernel that generates inhomogeneous random graphs by sampling vertex features and connecting independently with probability W(x,y). Multiple practical similarity tests—normalized induced subgraph counts, sampling distributions, multiway cut values and microcanonical free energies—are provably equivalent (technical proofs span ~100 pages). Exchangeable infinite arrays admit the Aldous–Hoover representation (possibly random W); DeFinetti/Polya‑urn intuition explains why conditioning on latent features yields conditional independence.

AI-written summary · about

" chapters (16)

1. 0:00Program introduction
2. 3:44Bootcamp agenda
3. 6:27Workshop overview
4. 8:25Graph limits introduction
5. 13:06Graphon concept
6. 15:01Modeling large graphs
7. 18:09Random graph models
8. 22:12Exchangeable sequences
9. 26:52Aldous-Hoover theorem
10. 34:48Exchangeable graphs
11. 39:08Aldous-Hoover for graphs
12. 45:28Metric spaces and graphs
13. 1:02:06Convergence definitions
14. 1:10:08Cut convergence
15. 1:15:41Physics connection
16. 1:21:50Cut metric details