Random graphs and percolation////////////////////////////////////////////
After decades of study, random graphs are fundamental objects of interest in combinatorics, probability, and statistical physics. These days there are also many connections to other areas of mathematics and applications outside of mathematics: theoretical computer science, mathematical biology, neuroscience, epidemiology, etc.
The following are a sampling of the topics I hope for us to cover in this course.
---Erdős–Rényi models: G(n,p) and G(n,m)
---subgraph containment, second moment method, limiting distributions
---the Erdős–Rényi theorem: threshold for connectivity
---long paths and cycles in random graphs
---expander-like properties of random graphs: Cheeger numbers and spectral gaps
---the emergence of the giant component in the Erdős–Rényi model, and related topics such as Galton-Watson branching processes
---sharp thresholds for monotone properties, Friedgut and Kalai's theorem, etc.
---other kinds of random graphs: random regular graphs, preferential attachment models
---random graphs on lattices: percolation theory
---Kesten's theorem: the threshold for bond percolation on the square lattice is 1/2
Resources: I have put the following texts on reserve for 3 day checkout in the Science/Engineering library:
Alon and Spencer, The probabilistic method, 3rd edition (available electronically)
Bollobas, Random graphs, 2nd edition
Bollobas and Riordan, Percolation
Dubhashi and Panconesi, Concentration of measure for the analysis of randomized algorithms (available electronically)
Janson, Luczak, and Rucinski, Random graphs