## Topics Covered

#### Basics

• Lecture 1: Binomial Theorem, Binomial Coefficients and some identities involving them.
• Lecture 2: Number of subsets of size 0 (mod 4). Recurence relation for Bell numbers. Multinomial Expansion.
• Lecture 3: Lucas' Theorem. Basic Asypmtotic Analysis. Different ways of estimating n! and the Binomial Coefficients.
• Lecture 4: Analysis of Divide and Conquer Recurrences.
• Lecture 5: Average number of comparisons in Quicksort. Lower bound for number of comparisons in sorting.

#### Pigeonholes, Double Counting and Ramsey's Theorem

• Lecture 6: Examples of Pigeonhole Pinciple: equal degrees in a graph, largest subset of [2n] with no divising pairs and the Erdos-Szekeres Lemma.
• Lecture 7: Dirichlet Rational Approximation. Ramsey's Theorem.
• Lecture 8: Lower bound for graph Ramsey numbers. Hypergraph Ramsey numbers. Convex sets in the plain.
• Lecture 9: Schur's Theorem and Fermat's Last Theorem over F_p. Mantel's Theorem. Average number of divisors.
• Lecture 10: Turan Problem of the 4-cycle (upper/lower bound).
• Lecture 11: Hand-Shaking Lemma, Sperner's Lemma and Brouwer's Fixed-Point Theorem.
• Lecture 12: Zermelo's Theorem and Stealing Strategies. Konig's Infinity Lemma and De-Bruijn-Erdos Theorem.

#### Partially Ordered Sets

• Lecture 13: Basic notions: chains, anti-chains and linear extentions. Dual Dilworth Theorem (Mirsky's Theorem) and Erdos-Szekeres Lemma.
• Lecture 14: Dilworth's Theorem and its relation to the Theorems of Hall and Konig-Egervary.
• Lecture 15: Gallay-Roy Theorem. Covering P([n]) using symmetric chains and Sperner's Theorem. Bollobas's Theorem and LYM Inequality.
• Lecture 16: The Littlewood-Offord Problem. Erdos-Ko-Rado Theorem using Cyclic Permutations and using the Kruskal-Katona Theorem.
• Lecture 17: Proof of Kruskal-Katona Theorem.
• Lecture 18: Arrow's Impossibility Theorem.

#### Sieving

• Lecture 19: The Inclusion-Exclusion Principle. Number of Derangements and Euler's Totient function.
• Lecture 20: The Menage Problem. Stirling Numbers of the second kind.
• Lecture 21: Stirling numbers of the first kind. Even and odd permutations.
• Lecture 22: The Matrix Tree Theorem using Inclusion-Exclusion.
• Lecture 23: Gessel-Viennot Lemma and its applications to determinantal identities.
• Lecture 24: Mobius Inversion over the integers and over the Boolean Lattice.
• Lecture 25: Two perspectives on Mobius Inversion over general posets. Product rule for Mobius function of a product poset.
• Lecture 26: More properties of the Totient Fucntion. Basic properties of Lattices.
• Lecture 27: Inclusion-Exclusion over Ranked Distributive Lattices.
• Lecture 28: Relation between number of Acyclic Orientations and the Chromatic Polynomial (Stanley's Theorem). The BEST Theorem.