Dave Anderson

Random Graphs

Suppose you build a graph on n vertices by connecting two vertices with uniform probability p. As n grows, how big is the largest connected component of the graph? This question was considered (and answered) by Erdos and Renyi in 1959. I'll discuss this and related constructions; the talk might be accessible to high school students.