Talks
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.
AttachmentSize
906.67 KB