##### Department of Mathematics,

University of California San Diego

****************************

### Food For Thought Seminar

## Franklin Kenter

#### Rice University

## Eigenvector Norms Matter in Spectral Graph Theory

##### Abstract:

We investigate the role of eigenvector norms in spectral graph theory to various combinatorial problems including the densest subgraph problem, the Cheeger constant, among others. We introduce randomized spectral algorithms that produce guarantees which, in some cases, are better than the classical spectral techniques. In particular, we will give an alternative Cheeger â€œsweepâ€ (graph partitioning) algorithm which provides a linear spectral bound for the Cheeger constant at the expense of an additional factor determined by eigenvector norms. Finally, we apply these ideas and techniques to problems and concepts unique to directed graphs.

### December 18, 2014

### 10:00 AM

### AP&M B412

****************************