Random subgraphs of a given graph.

摘要

In this thesis, we explore several problems related to understanding the relationships between a random subgraph of a host graph and the host graph itself, using the spectrum of the normalized Laplacian to understand the structure of both host graph and subgraph. In particular: (1) We study the emergence of the giant component in random subgraphs of a given graph. Under some relatively mild conditions on the degree sequence and spectral gap of the Laplacian, we show that if a graph G is percolated with probability p ≤ &parl0;1-e&parr0;d , where d˜ is the ratio of the second and first moments of the degree sequence, then the resulting subgraph Gp has no giant component asymptotically almost surely, while if p ≥ &parl0;1+e&parr0;d d˜ then there is a unique giant component with volume a constant fraction of the volume of the entire graph. This extends earlier work of Erdős and Renyi, who considered the problem with host graph Kn, and Frieze, Krivelevich and Martin who considered regular pseudo-random graphs, and others. (2) For a denser range of p, we exploit the spectral gap to show similarities between the structure of a random subgraph of a graph and the underlying host graph. The spectral gap of the normalized Laplacian yields a great deal of structural information about a graph, including discrepancy and expansion properties. We show that the spectral gap of a random subgraph is asymptotically the same as the spectral gap of host graph so long as pdmin " log3/2(n). (3) We also study another model of random subgraph, namely a uniformly randomly chosen spanning tree. We study the height of random spanning trees of general graphs; improving and generalizing earlier results of Aldous. Again, the spectral gap of the Laplacian is a key parameter in our understanding.