The Spectral Gap of a Random Subgraph of a Graph

Abstract

We examine the relationship of a graph _G_ and its random subgraphs, which are defined by independently choosing each edge with probability _p_. Suppose that _G_ has a spectral gap λ (in terms of its normalized Laplacian) and minimum degree _d__min. Then we can show that a random subgraph of _G_ on _n_ vertices with edge-selection probability _p_ almost surely has as its spectral gap <inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="uinm_a_10129296_o_ilf0001.gif"></inline-graphic>.