Probabilistic Method

Time and Place:

Monday and Wednesday 3:00-4.50 P.M.,  ROYCE 156.    First class - October 1
 

Instructor:

Benny Sudakov, MS 7911, bsudakov@math.ucla.edu
 

Course description:

The Probabilistic Method is a powerful tool in tackling many problems in discrete mathematics. It belongs to those areas of mathematics which have experienced a most impressive growth in the past few decades. Roughly speaking, its basic idea can be described as follows. In order to prove existence of a combinatorial structure with certain properties, we construct an appropriate probability space, and show that a randomly chosen element of this space has the desired property, with positive probability.

This course provides a gentle introduction to the Probabilistic Method, with emphasis on methodology. We will try to illustrate the main ideas by showing the application of probabilistic reasoning to various combinatorial problems. The topics covered in the class will include (but are not limited to):

Linearity of expectation, the second moment method, the local lemma, correlation inequalities, martingales, large deviation inequalities, Janson and Talagrand inequalities and pseudo-randomness.
 

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.

The Probabilistic Method, by N. Alon and J. H. Spencer, 3rd Edition, Wiley, 2008.

Random Graphs, by B. Bollobas, 2nd Edition, Cambridge University Press, 2001.

Random Graphs, by S. Janson, T. Luczak and A. Rucinski, Wiley, 2000.

Graph Coloring and the Probabilistic Method, by M. Molloy and B. Reed, Springer, 2002.
 

Assignments:

During this term there will be 3 homework in this course. Students are required to submit them to get a final grade.  

  • Assignment 1
    •  

  • Assignment 2
    •  

  • Assignment 3
    •  

    Course Outline (to be updated during the term):

  • The basic method: Ramsey numbers, Set-pairs with restricted intersections, Hypergraph 2-coloring, Sum-free subsets.

  • Dominating sets in graphs. Application of dominating sets in graphs to covering codes. Linearity of expectation: Max Cut in graphs.

  • Maximum and minimum number of Hamilton paths in tournament and and the conjecture of Szele. Permanents of matrices - Minc Conjecture.

  • Existence of graphs with large girth and large chromatic number. Recoloring and new bounds on the minimum number of edges in non-2-colorable n-uniform hypergraphs.

  • The second moment method: Turan's proof of the Hardy Ramanujan theorem. Numbers with all distinct sums, random graphs and threshold functions, cliques in random graphs.

  • Bounding large deviations (Chernoff bounds) and consistent arcs in tournaments.

  • Lovasz Local Lemma: application to 2-colorability of n-uniform hypergraphs Proof of Lovasz Local Lemma, Applications of Lovasz Local Lemma to: cycles in directed graphs, acyclic edge coloring, coloring of integers which makes all shifts of given set multicolored.

  • Correlation inequalities: 4 function theorem and proof of FKG inequality, application to monotone properties in random graphs.

  • Large deviation inequalities for martingales. Chromatic number of random graphs. Isoperimetric inequality for Hamming cube.

  • Probabilistic gems: Ramsey and Turan numbers of sparse graphs, Independence number of triangle-free graph, crossing numbers, incidence and additive number theory