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.
Textbooks:
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.