Probabilistic Methods in Combinatorics - 0366.4913.01

Noga Alon ( nogaa@tau.ac.il )
Fall 2012-2013, Monday 16-19, Orenstein 111
School of Mathematical Sciences,
Tel-Aviv University

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):

  1. : October 22
    The basic method, Ramsey numbers, Dominating sets in graphs, Hypergraph 2-coloring, Sum-free subsets, Set pairs theorem.
  2. : October 29
    Linearity of expectation, Hamiltonian paths in tournaments and the conjecture of Szele, Minc Conjecture.
  3. : November 5
    The second moment method, Turan's proof of the Hardy Ramanujan theorem, distinct sums, random graphs and threshold functions, cliques in random graphs.
  4. : November 12
    More on cliques in random graphs. Alterations: Graphs with high girth and high chromatic number. Bounding of large deviations and consistent arcs in tournaments.
  5. : November 19
    Dependent Random Choice and its applications (guest lecture by W. Samotij)
  6. : November 26
    The local lemma: the general lemma and its symmetric version, Straus' problem, directed cycles.
  7. : December 3
    More on the local lemma, solution of (some) exercises.
  8. : December 10
    Correlation inequalities: the four functions theorem and its applications, the FKG Inequality, Kleitman's Theorem, correlation between properties of random graphs.
  9. : December 17
    Martingales: the edge exposure and the vertex exposure martingales, Azuma's Inequality.
  10. : December 24
    More martingales, chromatic number of sparse random graphs.
  11. : December 31
    Poisson approximation: The Janson Inequalities and their application for constructing Ramsey type graphs.
  12. : January 7
    No class
  13. : January 14
    The chromatic number of G(n,1/2). Geometry: the VC dimension of a range space and its applications.
  14. : January 21
    Dominating sets in k-majority tournaments, summary.

Exercises