Representation Theory in TCS and Extremal Combinatorics

on YouTube ↗51m

" summary

Introduces association schemes as the framework for exporting Fourier methods beyond the Boolean cube and uses group representation concretely to analyze the symmetric group and the perfect matching scheme, computing character tables and Krein parameters, applying the Hoffman bound and Lovász theta to reprove Ellis Friedgut Pilpel’s t‑intersecting result, and leveraging Fourier sparsity to run a pseudorandomness proof for the matching polytope where the naive Hoffman bound fails. Shows the matchings connectivity matrix has tiny rank over GF(2) so certain parameterized Hamiltonian algorithms are SETH‑tight, and constructs a harmonic multilinear representation for permutations and matchings while flagging open modular and classification questions.

AI-written summary · about

" chapters (14)

1. 0:00Intro
2. 0:28Outline
3. 4:14Duality
4. 9:26Group Theory without groups
5. 14:05Metric and Cometric Association Schemes
6. 15:11Association Schemes from Symmetric Groups
7. 16:01The Symmetric Group Scheme
8. 18:44Juntas and Intersecting Families
9. 24:33Deza-Frankl Conjecture
10. 31:38The Birkhoff Polytope
11. 36:59The Perfect Matching Scheme
12. 38:29The Matchings Connectivity Matrix
13. 43:20Classification of Degree-d Boolean Functions of S,?
14. 45:05Harmonic Polynomials on S