First homework, hand in Tuesday, September 8.
Second homework, hand in Tuesday, September 15.
Third homework, hand in Tuesday, September 22.
Fourth homework, hand in Thursday, October 1.
Fifth homework, hand in Tuesday, October 6.
Sixth homework, hand in Tuesday, October 13.
Seventh homework, hand in Thursday, October 22.
September 3rd: Inclusion-Exclusion. The pigeon hole principle. The Erdos-Szekeres Theorem.
September 8th: Graphs, trees, degree sequences, comparison based algorithms for sorting. Material covered: Breslauer and Dubhashi, pages 73-89.
September 10th: Eulerian and Hamiltonian paths and cycles. Connectivity. Menger's theorem. Material covered: B and D, pages 90-104.
September 15th: Matchings, maximal and maximum. Alternating and augmenting paths. Berge's theorem. Hall's Theorem. Vertex covers. Konig-Egervary theorem. Tutte's theorem (without proof). Maximum independent sets. Edge covers. Gallai's theorem (size of maximum matching + minimum edge cover is n). Vertex and edge colourings. Brooks' and Vizing's theorems (without proof). Material covered: B and D, pages 105-118.
September 17th: Plane and planar graphs. Faces of planar graphs. Dual graphs. Subdivisions. Kuratowski's theorem (without proof). The four color theorem (without proof!). Graph minors.
September 22th: Turan's theorem. Erdos-Stone theorem (without proof) and corollaries. Hypergraphs/set systems. Chains and anti-chains. Sperner's theorem. LYM inequality. Bollobas' theorem. Erdos-Ko-Rado theorem. Helly's theorem. Statement of Sunflower lemma.
September 24th: Why extremal combinatorics is useful in the theory of computation. Proof of sunflower lemma. Applications of the sunflower lemma to bitprobe complexity. Introduction to the probabilistic method.
September 29th: Linearity of expectation. Application of the probabilistic method in theory of computation: Polynomial size monotone formulae for majority.
October 1st: The probabilistic method, advanced stuff: Lovasz local lemma. Alteration.
October 6th: Ramsey's theorem for graphs, with applications to approximation algorithms for MIS. Ramsey's theorem for hypergraphs, with applications to lower bounds for CRCW PRAM computation.
October 8th: Class canceled as Peter is away.
October 13th: Applications of Ramsey's theorem to CRCW PRAM computation, continued. Hales-Jewett theorem and corollaries. The linear algebra method: Oddtown theorem, Fischer's inequality.
October 15th: Algebraic constructions. Projective planes. Small sample spaces. Applications in TOC: Hashing, derandomization.
Handouts on flows in directed graphs.
Jukna: Extremal Combinatorics.