Printable PDF
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

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