Basic Combinatorics - 0366.3036 (Spring 2024)
Grading: I will hand out several (about 5) sets of
exercises, which will be graded. There might also be a final exam.
Home Assignments
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.