Structures in Random Graphs: New Connections

on YouTube ↗01h 03m

" summary

Proves an upper bound on clique and independence numbers in uniformly random Cayley graphs of any finite group of order N at order log N · log log N, tight for vector spaces over F2; shows a simple random tweak on generators in F5^d removes subgroup obstructions and yields C‑Ramsey Cayley graphs for most N. Establishes the Kahn–Kalai conjecture (thresholds ≈ expectation obstructions) via Talagrand‑style selector analysis, and builds an optimally spread distribution on Latin squares using iterative absorption plus Lovász Local Lemma sampling, giving the log n / n threshold.

AI-written summary · about

" chapters (6)

1. 0:00Random graphs introduction
2. 4:02Cliques in random Cayley graphs
3. 29:43Beyond group structures
4. 40:38Thresholds in random graphs
5. 55:15Lovász local lemma connections
6. 1:01:00Summary of open problems