Printable PDF
Department of Mathematics,
University of California San Diego

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

Math 269 - Combinatorics

Paul Horn

UCSD

Random Subgraphs of a Given Graph

Abstract:

Data from real-world graphs often contains incomplete information, so we only observe subgraphs of these graphs. It is therefore desirable to understand how a typical subgraph relates to the underlying host graph. We consider several interrelated problems on both random trees and random subgraphs obtained by taking edges of the host graph independently with probability $p$. In the second case, we study the emergence of the giant component. We also use the spectral gap to understand discrepancy and expansion properties of a random subgraph. The Erd\H{o}s-R\'enyi random graph is the special case of this where the host graph is the complete graph $K_n$. Additional applications include taking a contact graph as the host graph, and viewing random subgraphs as outbreaks of a disease.

January 20, 2009

3:00 PM

AP&M 7321

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