On Structural Properties of Low Threshold Rank Graphs

on YouTube ↗35m

" summary

Defines epsilon-threshold rank as the count of normalized-adjacency eigenvalues with |λ| ≥ ε and studies graphs where that rank is small. Proves any graph admits a K-partition into near-expanders when λK is bounded away from 1, shows leading eigenvectors are approximable by 2k-step functions in L2, gives a Cheeger-style bound removing the √ gap up to factor k, and proves a weak regularity lemma expressing A as O(rank/ε^2) rank/ε^2 cut matrices with cut-norm error ε·|E|, yielding 2^k or SDP/LP algorithms for MAX-CUT on such graphs.

AI-written summary · about

" chapters (10)

1. 0:00Start
2. 1:17Spectral Graph Theory
3. 1:37Setting
4. 3:31Spectral Characterizations of Graphs
5. 6:54Low Threshold Rank Graphs Think
6. 9:54Structure of Low Threshold Rank Graphs
7. 13:50Diameter of Low Threshold Rank Graphs
8. 14:39Eigenvectors of Low Threshold Rank Graphs
9. 17:41Cheeger's Inequality for Low Threshold Rank
10. 22:15Low Threshold Rank Graphs in Optimization