A graph G has a threshold rank k if the normalized adjacency matrix of G has at most k ``large’’ eigenvalues. In this talk we discuss structural properties of graphs that have small threshold rank. We see that these graphs can be seen as a union of at most k expander graphs. We also discuss a natural extension of the weak regularity lemma to (sparse) low threshold rank graphs. 

 

Based on joint works with Luca Trevisan.