Topics in Combinatorics - the Probabilistic Method (MAT577 and MAT478)
Noga Alon (first name initial followed by last name at
math dot princeton dot edu)
Spring 2024, Tuesday and Thursday 9:30-10:50, Room: Fine Hall 214
The webpage of the course in Canvas:
The Probabilistic Method
Procedural Matters:
Prerequisites:
Basic knowledge of Discrete Mathematics and Probability.
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, Fourth Edition,
Wiley, 2016.
B. Bollobas,
Random Graphs, 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 and possibly more as time permits.
Grading:
For undergrads who need to receive a grade, there will be a few
problem sets over the semester. There will be no final exam.