Probabilistic Methods in Combinatorics - 0366.4873.01
Procedural Matters:
Prerequisite Courses:
Discrete Mathematics, Introduction to Probability.
Exercises will be given during the course and their solutions will
be graded.
Text books:
Most of the topics covered in the course appear in the
books listed below (especially the first one). Other topics appear in
recent papers, many of which can be found in the journal
Random Structures and Algorithms.
N. Alon and J. H. Spencer,
The Probabilistic Method,
Wiley, 1992. (Second Edition, 2000, Third Edition 2008).
B. Bollobas,
Random Graphs,
Academic Press, 1985. (Second Edition, Cambridge University Press, 2001.)
S. Janson, T. Luczak and A. Rucinski,
Random Graphs,
Wiley, 2000.
M. Molloy and B. Reed,
Graph Colouring and the Probabilistic Method,
Springer,
2002.
Course syllabus:
Probabilistic methods in Combinatorics and their
applications in theoretical Computer Science. The topics include
linearity of expectation, the second moment method, the local
lemma, correlation inequalities, martingales, large deviation
inequalities, geometry, derandomization.
Course Outline (to be updated during the term):