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
****************************