Spring 2017

On Structural Properties of Low Threshold Rank Graphs

Tuesday, April 11th, 2017 3:30 pm4:00 pm

Add to Calendar

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.