MATH Seminar

Title: Random Subgraphs of a Given Graph
Colloquium: N16
Speaker: Paul Horn of The University of California, San Diego
Contact: Dwight Duffus, dwight@mathcs.emory.edu
Date: 2009-02-19 at 3:00PM
Venue: MSC W303
Download Flyer
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 involving both random trees in host graphs 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 Erdos-Renyi random graph is the special case of this where the host graph is the complete graph Kn. Additional applications include taking a contact graph as the host graph, and viewing random subgraphs as outbreaks of a disease.