MATH 7018 - Probabilistic Methods in Combinatorics

Fall 2009 - Tuesday/Thursday 15:00-16:30

School of Mathematical Sciences
Georgia Institute of Technology

Instructor: Asaf Shapira

Course procedures, syllabus and text books

Home Assignments

• Home Assignment I

• Home Assignment II

• Home Assignment III

• Home Assignment IV

Topics covered:

• Lecture 1: Upper bound and lower bound for Ramsey numbers. Probabilistic and deterministic approximation for Max-Cut.

• Lecture 2: Bollobas's Theorem. Sum-free sets. Property-B (lower bound). Dominating sets in graphs with large min-degree.

• Lecture 3: Property B (upper bound). Coloring non-linear hypergraphs. Dominating sets in graphs of high min-degree (probabilistic and algorithmic version).

• Lecture 4: Tournaments with property S_k. Maximum number of hamiltonian paths in a tournament (lower bound). Local-vs-global satisfiability. Balancing vectors.

• Lecture 5: Sperner's Theorem. Turan and Ramsey using the deletion method.

• Lecture 6: Gilbert-Vershamov bound (greedy and probabilistic constructions). Approximate sum of binomial coefficients. Turan's Theorem. High girth and high chromatic number.

• Lecture 7: Maximum number of hamiltonian paths in a tournament (upper bound). Erdos-Ko-Rado Theorem.

• Lecture 8: Hardy-Ramanujan Theorem. Distinct Sums. G(n,p) threshold for isolated vertices.

• Lecture 9: G(n,p) threshold for connectivity and for appearance of K_4.

• Lecture 10: Solution of home assignments. 2-point concentration of clique-number of G(n,p).

• Lecture 11: Arithmetic progressions in quasi-random integer sets. Chernoff bound (special case).

• Lecture 12: More Chernoff bounds.

• Lecture 13: Bennett/Bernstein Inequality. Consistent arcs in tournaments. Lower bound for relaxed Ramsey problem. Improved lower bound for property B.

• Lecture 14: Applications of the The Lovasz Local Lemma. Property B. Cycles in directed graphs. Non-repetative strings.

• Lecture 15: Proof of Local Lemma. Improved bound for R(3,k). Independent Transversals.

• Lecture 16: Four Functions (Ahlswede-Daykin) Theorem. Kleitman's Lemma. FKG Inequality. Correlated events in random graphs.

• Lecture 17: Marica-Schonheim Theorem. Chebyshev's Association Inequality. Azuma's Inequality.

• Lecture 18: Examples of Martingales. Doob's Martingale. Method of bounded differences (Mcdiarmid's Inequality). Applications to Chernoff Bounds, and Balls-Bins. Vertex exposure and edge exposure Martingales. Concentration of Chromatic number of G(n,p) (Shamir-Spencer Theorem).

• Lecture 19: The Chromatic number of G(n,1/2) (Bollobas's Theorem). An isoperimetric inequality on the Hamming cube.

• Lecture 20: 4-point concentration for the chromatic number of sparse random graphs. Local-vs-global coloring (Erdos's Theorem). TSP in the unit square (deterministic upper bound).

• Lecture 21: Near Gaussian tail for Stochastic TSP via method of bounded average differences. Choice number of G(n,1/2)

• Lecture 22: Janson's Inequalities. Triangles in sparse random graphs. Chromatic number of G(n,1/2) via Janson.

• Lecture 23: Diameter of random graphs via Janson's Inequality. Method of non-uniform bounded differences using Talagrand's Inequality. Gaussian tail for Stochastic TSP. Improved bound for Balls-Bins.

• Lecture 24: Concentration around median vs expectation. Concentration of certifiable functions using Talagrand's Inequality. Concentration of Longets Increasing Subsequence.