Spring 2013: Random graphs
Complex graphs and networks are ubiquitous throughout science and engineering, and possess beautiful mathematical properties. The goal of these informal lectures is to provide an introduction to some of the most basic results in the theory of (Erdos-Renyi) random graphs from the probabilistic viewpoint: chromatic number and clique number, and the size of the largest component in the subcritical, supercritical, and critical regimes. If time permits, we will discuss Brownian limits.
Prerequisites: Probability at the level of ORF 526 is assumed.
Time and location: Thursdays, 4:50-6:20, Bendheim Center room 103.
The first lecture will be on February 28.
There will be no lecture on March 28 (colloquium).
- Alon and Spencer, “The Probabilistic Method“, Wiley.
- Durrett, “Random Graph Dynamics“, Cambridge.
- Nachmias and Peres, “The critical random graph, with martingales“, Israel J. Math. 176 (2010), p. 29-41.
- Aldous, “Brownian excursions, critical random graphs and the multiplicative coalescent“, Ann. Probab. 25 (1997), p. 812-854.
- Grimmett, “Probability on Graphs“, Cambridge.
- van der Hofstad, “Random Graphs and Complex Networks“, lecture notes
- Bollobas, “Random Graphs“, Cambridge.
- Janson, Luczak, Rucinski, “Random Graphs“, Wiley.