printable pdf
比利时vs摩洛哥足彩 ,
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

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