Spectral Aspects of Symmetric Matrix Signings
summary
Connection between graph lifts and signed adjacency matrices guides several concrete results: existence of Ramanujan graphs follows from choosing a 2-lift signing so signed eigenvalues stay small, but deciding whether a symmetric signing keeps the top eigenvalue ≤ λ is NP-hard to bound signed eigenvalues. For singularity the exact criterion is algebraic: a signing has nonzero determinant iff the graph has a perfect 2-matching. Moreover there is a polynomial-time algorithm finds nonzero determinant over F2 via cycle-cover reductions, giving a constructive special case of Combinatorial Nullstellensatz.
AI-written summary · about
chapters (11)
- 0:00Intro
- 0:41Spectra of Graphs
- 1:23Why do we care?
- 3:32Why signings?
- 5:332-Lifts and Eigenvalues
- 12:43Spectra of signings: questions to ask
- 16:19Polynomial Identity Testing
- 17:06Randomized Bipartite Matching Algorithm
- 17:38Signings and 2-Matchings
- 22:24Connection with Alon's Combinatorial Nullstellantsaz
- 26:05Finding non-zeros of the polynomial