MATH 4032  Combinatorial Analysis
Spring 2011  Tuesday/Thursday 16:3018:00
Home Assignments
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 ErdosSzekeres 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 4cycle (upper/lower bound).

Lecture 11:
HandShaking Lemma, Sperner's Lemma and Brouwer's FixedPoint Theorem.

Lecture 12:
Zermelo's Theorem and Stealing Strategies. Konig's Infinity Lemma and
DeBruijnErdos Theorem.
Partially Ordered Sets

Lecture 13:
Basic notions: chains, antichains and linear extentions. Dual Dilworth
Theorem (Mirsky's Theorem) and ErdosSzekeres Lemma.

Lecture 14:
Dilworth's Theorem and its relation to the Theorems of Hall and
KonigEgervary.

Lecture 15:
GallayRoy Theorem. Covering P([n]) using symmetric chains and Sperner's
Theorem. Bollobas's Theorem and LYM Inequality.

Lecture 16:
The LittlewoodOfford Problem. ErdosKoRado Theorem using Cyclic
Permutations and using the KruskalKatona Theorem.

Lecture 17:
Proof of KruskalKatona Theorem.

Lecture 18:
Arrow's Impossibility Theorem.
Sieving

Lecture 19:
The InclusionExclusion 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 InclusionExclusion.

Lecture 23:
GesselViennot 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:
InclusionExclusion over Ranked Distributive Lattices.

Lecture 28:
Relation between number of Acyclic Orientations and the Chromatic
Polynomial (Stanley's Theorem). The BEST Theorem.