Approximating Graph Isomorphism through Linear Maps

on YouTube ↗31m

" summary

Defines a family of partition‑refinement equivalences parameterized by K, L and a set of primes Omega that refine k‑dimensional Weisfeiler‑Leman by using ranks of linear combinations of 0/1 matrices; shows Cai‑Fürer‑Immerman counterexamples force inclusion of specific primes and that iterations are bounded by n^{O(K)} with each refinement reducible to a polynomial‑time test via simultaneous similarity (Chistov et al.); constructs a tractable strengthening that distinguishes CFI graphs mod p and leaves open tight bounds on the smallest K(n) needed for isomorphism.

AI-written summary · about

" chapters (12)

1. 0:00Start
2. 1:25Graph Isomorphism
3. 2:59Equitable Partitions
4. 7:04Facts about Weisfeiler-Leman
5. 9:16Cai-Fürer-Immerman
6. 13:42Stable Colouring Schemes
7. 15:07Rank Logic
8. 16:26Matrix Rank Partitions
9. 18:51General Prime Fields
10. 22:04Invertible Map Partitions
11. 26:01Relationship to Homomorphism Tests
12. 27:24Invertible Strategies