比利时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
****************************