Probabilistic Methods in Combinatorics - 0366.4913.01
Discrete Mathematics, Introduction to Probability.
Exercises will be given during the course and their solutions will
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, Fourth
Academic Press, 1985. (Second Edition, Cambridge University Press, 2001.)
S. Janson, T. Luczak and A. Rucinski,
M. Molloy and B. Reed,
Graph Colouring and the Probabilistic Method,
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):
: March 14
The basic method, Ramsey numbers, Dominating sets in
graphs, Hypergraph 2-coloring, Sum-free subsets,
Set pairs theorem.
: March 21
Linearity of expectation, Hamiltonian paths in
tournaments and the conjecture of Szele, Minc Conjecture.
: March 28
: April 4
The second moment method, Turan's proof of
the Hardy Ramanujan theorem, distinct sums, random graphs and
threshold functions, cliques in random graphs.
: April 5
More on cliques in random graphs.
Alterations: Graphs with high girth and high chromatic number,
bounding of large deviations and
consistent arcs in tournaments.
: April 11,18
: April 25
The local lemma: the general lemma and its symmetric version,
Straus' problem, directed cycles.
: May 2
: May 9
the four functions theorem and its
applications, the FKG Inequality, The Harris-Kleitman Theorem, correlation
between properties of random graphs.
: May 16
Martingales: the edge exposure and the vertex exposure martingales,
: May 23
More martingales, chromatic number of sparse random graphs,
: May 30
: June 6
Poisson approximation: The Janson Inequalities and their
application for constructing Ramsey type graphs and for estimating
the chromatic number of G(n,1/2).
: June 13
Geometry: the VC dimension of a range space and its applications.
: June 20
More on the VC dimension and its applications.
Dominating sets in k-majority tournaments.
: June 27
Gems including crossing numbers, incidences and additive number
the Ramsey number r(3,k), summary.