The Giant Component

In 1960 Paul Erdos and Alfred Renyi showed that the random graph G(n,p) with p=c/n and c>1 contained, with high probability, a “giant component,” whose size was roughly yn for an explicit y=y(c). We today consider the phase transition at c=1 and the subcritical, c1, regimes as prime examples of percolation behavior. We give a somewhat novel approach to examining the giant component. We are able to derive the local joint distribution on the number of vertices and edges of the giant component. Applying some reverse engineering we are then able to find, in certain ranges, the asymptotics for the number C(k,l) of connected labelled graphs on k vertices with
k-1+l edges.

Speaker Details

Joel Spencer is a Professor of Mathematics and Computer Science at the Courant Institute, New York. His research centers on the intersection of Discrete Mathematics, Theoretical Computer Science, and Probability. His books include “The Probabilistic Method” (with Noga Alon) and “The Strange Logic of Random Graphs.” He is cofounder (with Michal Karonski) of the journal Random Structures and Algorithms.

Date:
Speakers:
Joel Spencer
Affiliation:
Courant Institute
    • Portrait of Jeff Running

      Jeff Running