 |
Abstract: Some forty five years ago Paul Erdos and Alfred Renyi wrote "On the Evolution of Random Graphs." Erdos and Renyi recognized that the random graph G(n,p) (n vertices, adjacency probability p) undergoes a fundamental change when p\sim \frac{1}{n}. Parametrizing p=\frac{c}{n}, while c<1 all components are small and simple but when c>1 a complex giant component has emerged. Today we recognize this as a phase transition. Phase transitions (= sudden change, e.g., freezing) appear in mathematical physics (e.g., bond percolation on Z^d), computer science (e.g., random k-SAT), branching processes, and elsewhere. We give a general discussion of them. For Erdos-Renyi percolation we can expand the c=1 value and we explain why the "proper" parametrization" for the "critical window" is p= n^{-1}+\lambda n^{-4/3}.\par We explore this percolation phenomenon from a variety of viewpoints. One new approach (joint with Remco van der Hofstad) involves a novel analysis of the Breadth First Search algorithm on the random graph G(n,p).
This talk will be accessible to graduate students.
|