Random Graphs - 0366.4767

Michael Krivelevich ( krivelev@post.tau.ac.il )
Fall Semester, 2010-2011 - Sundays 16-19, Orenstein 110

Procedural Matters:

Desirable background: Working knowledge of Graph Theory, familiarity with basic notions of Probability and Linear Algebra.
Exercises will be given during the course and their solutions will be graded.


N. Alon and J. Spencer, The probabilistic method, 3rd Edition, Wiley, 2008.
B. Bollobas, Random Graphs, 2nd Edition, Cambridge University Press, 2001.
S. Janson, T. Luczak and A. Rucinski, Random Graphs, Wiley 2000.

Course syllabus (tentative):

Models of random graphs and of random graph processes; illustrative examples; random regular graphs, configuration model; appearance of the giant component; small subgraphs; long paths and Hamiltonicity; coloring problems; eigenvalues of random graphs and their algorithmic applications; pseudo-random graphs.

Lecture notes from the ETH course.