Basic Combinatorics - 0366.3036 (Spring 2023)
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
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.
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
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.
Turan Problem for the 4-cycle (upper bound and lower bound).
Sperner's Lemma and Brouwer's Fixed Point Theorem.
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.
Various proofs/reduction of/between the Theorems of Hall, Konig and
Dilworth. Sperner's Theorem using Hall's Theorem.
Theorems of Bollobas, Littlewood-Offord and Erdos-Ko-Rado.
Arrow's Impossibility Theorem.
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.
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.
Mobius Inversion over the integers and the Boolean Lattice. The abstract
notion of Mobius Inversion, and the product rule over product posets.
The Partition Function and Ferrers Diagrams.
Odd and Distinct Partitions (Euler's Theorem).
The Pentagonal Number Theorem.
An asymptotic bound for p(n).
Eigenvalues and counting spanning trees in Digraphs.
The BEST Theorem and the number of De-Bruijn Sequences.