The giant component in a random subgraph of a given graph
- Series
- Combinatorics Seminar
- Time
- Thursday, October 9, 2008 - 16:00 for 1 hour (actually 50 minutes)
- Location
- Skiles 255
- Speaker
- Lincoln Lu – University of South Carolina
We consider a random subgraph G_p of a host graph G formed by retaining each edge of G with probability p. We address the question of determining the critical value p (as a function of G) for which a giant component emerges. Suppose G satisfies some (mild) conditions depending on its spectral gap and higher moments of its degree sequence. We define the second order average degree \tilde{d} to be \tilde{d}=\sum_v d_v^2/(\sum_v d_v) where d_v denotes the degree of v. We prove that for any \epsilon > 0, if p > (1+ \epsilon)/\tilde{d} then almost surely the percolated subgraph G_p has a giant component. In the other direction, if p < (1-\epsilon)/\tilde{d} then almost surely the percolated subgraph G_p contains no giant component. (Joint work with Fan Chung Graham and Paul Horn)