MATH 7018  Probabilistic Methods in Combinatorics
Fall 2009  Tuesday/Thursday 15:0016:30
Home Assignments
Topics covered:

Lecture 1:
Upper bound and lower bound for Ramsey numbers. Probabilistic and
deterministic approximation for MaxCut.

Lecture 2:
Bollobas's Theorem. Sumfree sets. PropertyB (lower bound). Dominating
sets in graphs with large mindegree.

Lecture 3:
Property B (upper bound). Coloring nonlinear hypergraphs. Dominating sets
in graphs of high mindegree (probabilistic and algorithmic version).

Lecture 4:
Tournaments with property S_k. Maximum number of hamiltonian paths in a
tournament (lower bound). Localvsglobal satisfiability. Balancing
vectors.

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

Lecture 6:
GilbertVershamov 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).
ErdosKoRado Theorem.

Lecture 8:
HardyRamanujan 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. 2point concentration of cliquenumber of
G(n,p).

Lecture 11:
Arithmetic progressions in quasirandom 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. Nonrepetative strings.

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

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

Lecture 17:
MaricaSchonheim 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 BallsBins. Vertex exposure and edge exposure Martingales.
Concentration of Chromatic number of G(n,p) (ShamirSpencer Theorem).

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

Lecture 20:
4point concentration for the chromatic number of sparse random graphs. Localvsglobal 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 nonuniform
bounded differences using Talagrand's Inequality. Gaussian tail for Stochastic TSP. Improved bound for
BallsBins.

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