Math 536, Spring 2017

Combinatorics II: Probabilistic Methods


General Course Information
Meeting time:  Monday and Wednesday 1:30 pm - 2:45 pm in E406

Instructor: Hao Huang

Textbook and Reading Materials: 
1. N. Alon and J. Spencer, The Probabilistic Method, 3rd or 4th edition, Wiley.
2. S. Janson, T. Luczak and A. Rucinski, Random Graphs, Wiley 2000.
3. B. Bollobas, Random Graphs, second edition, Cambridge University Press 2001.


Syllabus: Please click here for the syllabus of this course, which includes more details on the course goal, grading scheme, exam and homework policy.



Course Schedule 
The materials covered in the classes will be updated and posted below after each class.

Jan 11 (W)      Introduction I: Lower bound for Ramsey number, Katona's proof of Erdos-Ko-Rado, Bollobas Theorem, k-dominating tournaments.

Jan 16 (M)      --- no class (MLK day).

Jan 18 (W)      Introduction II: Property B, Dominating set in a graph.

Jan 23 (M)      Linearity of expectation I: Counting Hamiltonian cycles, Max-cut problem, Balancing vectors (two versions).

Jan 25 (W)       Linearity of expectation II: Turan's Theorem, Sum-free subsets, the statement of Max-Flow Min-Cut Theorem and its applications.

Jan 30 (M)       Linearity of expectation III: probabilistic proof of Max-Flow Min-Cut Theorem, 3-SAT problem, Crossing number inequality.

Feb 1 (W)         Linearity of expectation IV: Szemeredi-Trotter Theorem, Sum-product sets. Bregman's Theorem and its application for Hamiltonian cycles.

Feb 6 (M)         Linearity of expectation V: Proof of Bregman's Theorem. Alteration I: Turan's theorem revisited (weaker bound), Ramsey number (improved lower bound).

Feb 8 (W)         Alteration II: Maximize min area of triangle in an unit square; An improved bound for property B.

Feb 13 (M)       Alteration III: Graphs with high girth and high chromatic number. Second Moment Method I: Basics.

Feb 15 (W)       Second Moment Method II: Number of prime factors, clique number of random graph G(n, 1/2).

Feb 20 (M)       Second Moment Method III: Distinct sums, threshold function for random graphs.

Feb 22 (W)        Local Lemma I: Mutual independence, Proof of asymmetric Local Lemma, Rainbow independent set of cycles.

Feb 27 (M)        Local Lemma II: Local version of Property B, k-coloring of real numbers, Ramsey number R(3, k).

Mar 1 (W)         Local Lemma III: Satisfiability problems, Latin transversals, Shearer's Lemma, a (very brief) introduction of algorithmic Local Lemma.

Mar 6 (M)         --- no class (spring break).

Mar 8 (W)         --- no class (spring break).

Mar 13 (M)       Correlation Inequality I: Chebyshev sum inequality, Harris inequality, FKG, Holley, and Ahlswede-Daykin.

Mar 15 (W)        Correlation Inequality II: Kleitman's Theorem, Marica-Schonheim inequality, XYZ theorem.

Mar 20 (M)        Strong concentration: Chernoff's inequality, combinatorial discrepancy, randomized rounding for k-matchings.

Mar 22 (W)         Martingale I: definition of martingale, Azuma's inequality, chromatic number of G(n, 1/2).

Mar 27 (M)         Martingale II: various applications, Kim-Vu polynomial concentration and counting triangles.

Mar 29 (W)          Poissson paradigm I: Janson's inequality, Triangle-freeness of G(n, c/n), Extended Janson's inequality.

Apr 3 (M)             Poisson paradigm II: Brun's sieve method, Threshold function for EPIT.

Apr 5 (W)             Poisson paradigm III: Disjoint family and maximum disjoint family, Maximum triangle-degree of G(n, p).

Apr 10 (M)           Entropy method I: Definition and motivation, subadditivity, dropping conditioning and chain rule. Proof of Shearer's Lemma. Bounding the size of a family with given verte degree.

Apr 12 (W)           Entropy method II: Loomis-Whitney inequality, Maximum size of triangle-intersection-free family (weaker bound), Maximizing the number of graph embeddings.
 
Apr 17 (M)           Entropy method III: Counting q-colorings and independent sets in d-regular graphs, Bipartite swapping trick.

Apr 19 (W)           Discrepancy I: Discrepancy of family of n subsets of [n], Lower bound construction (via Hadamard matrix)

Apr 24 (M)           Discrepancy II: Lower bound construction (via probabilistic method), Beck-Fiala Theorem (and the conjecture), Sketch of proof for arbitrary ground set size.