Hidden Irregularity Versus Hidden Structure: The Emergence of the Johnson Graphs

on YouTube ↗01h 07m

" summary

Claim: a graph or relational structure with symmetry defect ≥10% yields, at quasi‑polynomial multiplicative cost, one of three canonical outcomes: a vertex coloring with no color >90%, a dominant color partitioned into equal blocks, or a canonically embedded Johnson graph on the large class. Tools: individualization–refinement, coherent configurations and a “twin‑awareness” lemma about semi‑regular bipartite subgraphs. Consequence: Johnson graphs are the sole obstruction (t=2 gives cost exp(√n)), and this resolves the encasement step needed for a quasi‑polynomial graph‑isomorphism algorithm.

AI-written summary · about

" chapters (13)

1. 0:00Intro
2. 0:40Exposing irregularity: canonical coloring
3. 2:20Canonical assignment
4. 4:06Individualization retinement: a more resilient example
5. 5:10Individualization not canonical
6. 8:17Individualization: multiplicative cost
7. 19:49Iwins, symmetry detect
8. 28:08Significance to Graph Isomorphism
9. 38:47Advanced refinement: Wersteller-Leman 1968
10. 46:43Loherent configurations
11. 49:50Coherent contigurations: a crash course
12. 52:40Coherent configurations: induced subcontigurations
13. 54:48Coherent contiqurations: the fix