Basic Combinatorics  0366.3036 (Spring 2017)
Grading: I will hand out several (about 6) 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). Recurence relation for Bell
numbers. Multinomial Expansion. Cayley's Formula via direct counting.
Lucas's Theorem.

Lecture 2:
Basic Asypmtotic Analysis. Estimating
n! and the Binomial Coefficients and their relation to the Normal
Distribution. ErdosSzekeres Lemma and Ramsey's Theorem (lower/upper
bounds).

Lecture 3:
Ramsey's Theorem for Hypergraphs.
Three proofs of ErdosSzekeres Theorem (convex sets in
the plain). 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 4cycle (upper bound and lower bound).
Sperner's Lemma and Brower's Fixed Point Theorem.

Lecture 5:
Solving asymptotic recurences.
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 GallaiRoy 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, LittlewoodOfford and ErdosKoRado.
Arrow's Imposibility Theorem.

Lecture 8:
KruskalKatona Theorem and nother proof of ErdosKoRado.
The InclusionExclusion 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 MatrixTree Theorem via InclusionExclusion.
The LindstromGesselViennot 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 deBruijn Sequences.