| Monday, March 24th, 2014 | 4pm-5pm | Burnside 1205 |
A random d-regular graph G on n vertices is a graph chosen uniformly at random from the family of all such graphs. A random subgraph H of G is the subgraph induced on a set of vertices of G each chosen independently with probability p. This random subgraph model is associated with vertex percolation and has been studied in the literature. We describe how to answer a basic question: for what range of p (depending on d and n) is H connected? From a technical standpoint the innovation comes from studying a subgraph induced on a fixed vertex set of size (approximately equal to) pn. The advantage is that we replace two random processes by one, that in fact arises from the uniform distribution. It therefore becomes possible to use switchings, an elementary counting technique of McKay and Wormlad, that has been applied successfully in the context of random regular graphs. This is joint work-in-progress with McGill's very own Guillem Perarnau.