## Basic Combinatorics - 0366.3036 (Spring 2024)

### Course syllabus and text books

Grading: I will hand out several (about 5) sets of exercises, which will be graded. There might also be a final exam.

## Tentaive List of Topics

• Lecture 1: Binomial Coefficients and some identities involving them. Number of subsets of size 0 (mod 4). Recurrence relation for Bell numbers. Multinomial Expansion. Cayley's Formula via direct counting. Lucas's Theorem.
• Lecture 2: Basic Asymptotic Analysis. Estimating n! and the Binomial Coefficients and their relation to the Normal Distribution. Erdos-Szekeres Lemma and Ramsey's Theorem (lower/upper bounds).
• Lecture 3: Ramsey's Theorem for Hypergraphs. Three proofs of Erdos-Szekeres Theorem (convex sets in the plane). Schur's Theorem and Fermat's Theorem over F_p. Average number of divisors. Four proofs of Mantel's Theorem.
• Lecture 4: Turan Problem for the 4-cycle (upper bound and lower bound). Sperner's Lemma and Brouwer's Fixed Point Theorem.
• Lecture 5: Solving asymptotic recurrences. Average number of comparisons in Quicksort. Lower bound for number of comparisons in sorting. Basics of Partially Ordered Sets. Dual Dilworth Theorem (Mirsky's Theorem) and Gallai-Roy Theorem.
• Lecture 6: Various proofs/reduction of/between the Theorems of Hall, Konig and Dilworth. Sperner's Theorem using Hall's Theorem.
• Lecture 7: Theorems of Bollobas, Littlewood-Offord and Erdos-Ko-Rado. Arrow's Impossibility Theorem.
• Lecture 8: Kruskal-Katona Theorem and another proof of Erdos-Ko-Rado. The Inclusion-Exclusion Principle. Number of Derangements and Euler's Totient Function. The Menage Problem. Stirling numbers of the first/second kind and some identities involving them. Even and Odd Permutations.
• Lecture 9: The Matrix-Tree Theorem via Inclusion-Exclusion. The Lindstrom-Gessel-Viennot Lemma and its application to Determinantal Identities. Lattice Paths, Rhombus Tilings of the Hexagon and MacMahon's formula for the number of Plane Partitions.
• Lecture 10: Mobius Inversion over the integers and the Boolean Lattice. The abstract notion of Mobius Inversion, and the product rule over product posets.
• Lecture 11: The Partition Function and Ferrers Diagrams. Odd and Distinct Partitions (Euler's Theorem). The Pentagonal Number Theorem. An asymptotic bound for p(n).
• Lecture 12: Eigenvalues and counting spanning trees in Digraphs. The BEST Theorem and the number of De-Bruijn Sequences.