MATH 7018 - Probabilistic Methods in Combinatorics
Fall 2009 - Tuesday/Thursday 15:00-16:30
Upper bound and lower bound for Ramsey numbers. Probabilistic and
deterministic approximation for Max-Cut.
Bollobas's Theorem. Sum-free sets. Property-B (lower bound). Dominating
sets in graphs with large min-degree.
Property B (upper bound). Coloring non-linear hypergraphs. Dominating sets
in graphs of high min-degree (probabilistic and algorithmic version).
Tournaments with property S_k. Maximum number of hamiltonian paths in a
tournament (lower bound). Local-vs-global satisfiability. Balancing
Sperner's Theorem. Turan and Ramsey using the deletion method.
Gilbert-Vershamov bound (greedy and probabilistic constructions).
Approximate sum of binomial coefficients. Turan's Theorem. High girth and
Maximum number of hamiltonian paths in a tournament (upper bound).
Hardy-Ramanujan Theorem. Distinct Sums. G(n,p) threshold for isolated vertices.
G(n,p) threshold for connectivity and for appearance of K_4.
Solution of home assignments. 2-point concentration of clique-number of
Arithmetic progressions in quasi-random integer sets. Chernoff bound
More Chernoff bounds.
Bennett/Bernstein Inequality. Consistent arcs in tournaments. Lower
relaxed Ramsey problem. Improved lower bound for property B.
Applications of the The Lovasz Local Lemma. Property B. Cycles in
directed graphs. Non-repetative strings.
Proof of Local Lemma. Improved bound for R(3,k). Independent Transversals.
Four Functions (Ahlswede-Daykin) Theorem. Kleitman's Lemma. FKG
Inequality. Correlated events in random graphs.
Marica-Schonheim Theorem. Chebyshev's Association Inequality.
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).
The Chromatic number of G(n,1/2) (Bollobas's Theorem). An isoperimetric
inequality on the Hamming cube.
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).
Near Gaussian tail for Stochastic TSP
via method of bounded average differences. Choice number of G(n,1/2)
Janson's Inequalities. Triangles in sparse random graphs. Chromatic number of G(n,1/2) via Janson.
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
Concentration around median vs expectation. Concentration of certifiable functions using Talagrand's Inequality.
Concentration of Longets Increasing Subsequence.