Yale University
Department of Statistics
Seminar

Monday, October 16, 1995
Professor Joel Spencer
Courant Institute, New York University

"The Percolation of the Random Graph"

Seminar to be held in Room 107, 24 Hillhouse Ave at 4:15 pm

Paul Erdos and Alfred Renyi showed thirty years ago that the random graph G(n,p) undergoes percolation (what they called The Double Jump) at p=1/n. Today we know how to slow down the process, using the parametrization np-1=an^{-1/3}. We approach this through classic percolation, considering a branching process with mean near one. The infinite and finite components have analogs in our finite, asymptotic, case. As a surprising Corollary we get asymptotic enumeration of unicylic (bicyclic, etc.) graphs in terms of moments of the area under a Brownian Bridge.