Math 777: Random Graphs

1. Erdos-Renyi Random Graphs

• Branching processes (9/6)
• Epidemics (9/6)
• The random walk viewpoint (9/6)
• CLT for the giant component (9/15)
• The combinatorial approach (9/15)
• The critical regime (9/21)
• Threshold for connectivity (9/20)

2. Arbitrary degree distributions

• Newman-Strogatz Watts, Phys Rev E 64, paper 026118
• (notes) Supercritical proof, Molloy and Reed results.
• van der Hofstad et al. Distances in random graphs with finite variance random degrees
• notes on Chung and Lu (10/07)
• Chung and Lu - average distances - PNAS
• Chung and Lu - connected components - Ann. of Comb.

3. Random Regular Graphs

• Janson-Luczak-Rucinski - Sections 9.1-9.4
• my notes on JLR, 10/13
• Eigenvalues and Expanders, revised 10/18
• Mixing Times

4. Small Worlds

• Watts and Strogatz (1998) * News and Views
• Path Lengths
• Barbour and Reinert (2001)
• Epidemics and Percolation on Small Worlds, Moore and Newman (2000)

5. Barbasi-Albert model

• Original paper, Science (1999)
• Degree distribution
• Other powers, Krapivsky, Redner, Leyvraz (2000)
• Diameter, Bollobas and Riordan (2004) * Notes
• Mixing Times - revised 11/17
• Epidemics on Molloy Reed Graphs, Newman (2002) * Notes

6. Calloway-Hopcroft-Kleinberg-Strogatz-Watts

• Original CHKNS paper, Phys Rev. E.
• DMS proof of smooth phase transition, Phys. Rev. E.
• my paper for Discrete Random Walks 2003
• slides from my talk = class notes for Tuesday Nov. 30 ***
• Bollobas, Janson, Riordan (postscript file)
• Notes on BJR