Math 536, Spring 2017
Combinatorics II: Probabilistic Methods
Monday and Wednesday 1:30 pm - 2:45 pm in E406
Instructor: Hao Huang
Textbook and Reading
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.
covered in the classes will be updated and posted below after each
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
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)
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)
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.