MATH 4032 - Combinatorial Analysis
Spring 2011 - Tuesday/Thursday 16:30-18:00
Binomial Theorem, Binomial Coefficients and some identities involving
Number of subsets of size 0 (mod 4). Recurence relation for Bell
numbers. Multinomial Expansion.
Lucas' Theorem. Basic Asypmtotic Analysis. Different ways of estimating
n! and the Binomial Coefficients.
Analysis of Divide and Conquer Recurrences.
Average number of comparisons in Quicksort. Lower bound for number of
comparisons in sorting.
Pigeonholes, Double Counting and Ramsey's Theorem
Examples of Pigeonhole Pinciple: equal degrees in a graph, largest
subset of [2n] with no divising pairs and the Erdos-Szekeres Lemma.
Dirichlet Rational Approximation. Ramsey's Theorem.
Lower bound for graph Ramsey numbers. Hypergraph Ramsey numbers. Convex
sets in the plain.
Schur's Theorem and Fermat's Last Theorem over F_p. Mantel's Theorem.
Average number of divisors.
Turan Problem of the 4-cycle (upper/lower bound).
Hand-Shaking Lemma, Sperner's Lemma and Brouwer's Fixed-Point Theorem.
Zermelo's Theorem and Stealing Strategies. Konig's Infinity Lemma and
Partially Ordered Sets
Basic notions: chains, anti-chains and linear extentions. Dual Dilworth
Theorem (Mirsky's Theorem) and Erdos-Szekeres Lemma.
Dilworth's Theorem and its relation to the Theorems of Hall and
Gallay-Roy Theorem. Covering P([n]) using symmetric chains and Sperner's
Theorem. Bollobas's Theorem and LYM Inequality.
The Littlewood-Offord Problem. Erdos-Ko-Rado Theorem using Cyclic
Permutations and using the Kruskal-Katona Theorem.
Proof of Kruskal-Katona Theorem.
Arrow's Impossibility Theorem.
The Inclusion-Exclusion Principle. Number of Derangements and Euler's
The Menage Problem. Stirling Numbers of the second kind.
Stirling numbers of the first kind. Even and odd permutations.
The Matrix Tree Theorem using Inclusion-Exclusion.
Gessel-Viennot Lemma and its applications to determinantal identities.
Mobius Inversion over the integers and over the Boolean Lattice.
Two perspectives on Mobius Inversion over general posets. Product rule for
function of a product poset.
More properties of the Totient Fucntion. Basic properties of Lattices.
Inclusion-Exclusion over Ranked Distributive Lattices.
Relation between number of Acyclic Orientations and the Chromatic
Polynomial (Stanley's Theorem). The BEST Theorem.