##### Department of Mathematics,

University of California San Diego

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

### Advancement to Candidacy

## Paul Horn

#### UCSD, Graduate Student

## The spectral gap of a random subgraph of a graph

##### Abstract:

The spectral gap of the normalized Laplacian of a graph is strongly related to many important graph properties, including the mixing rate of random walks as well as expansion and discrepancy properties. Here we consider a random subgraph $H$ of a given graph $G$ where each edge in $G$ is taken to be in $H$ independently with probability $p$, and derive bounds on the spectral hap of $H$ in terms of the spectral gap of $G$. This can be thought of as an extension of earlier work on the Erd\H{o}s-R\'enyi $G(n,p)$ mode, which effectively treats a special case where the underlying graph is the complete graph $K_n$. We also survey some history and related problems.

Advisor: Fan Chung Graham

### March 4, 2008

### 10:00 AM

### AP&M 7218

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