MATH 4032 - Combinatorial Analysis
Spring 2011 - Tuesday/Thursday 16:30-18: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 Erdos-Szekeres 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 4-cycle (upper/lower bound).
-
Lecture 11:
Hand-Shaking Lemma, Sperner's Lemma and Brouwer's Fixed-Point Theorem.
-
Lecture 12:
Zermelo's Theorem and Stealing Strategies. Konig's Infinity Lemma and
De-Bruijn-Erdos Theorem.
Partially Ordered Sets
-
Lecture 13:
Basic notions: chains, anti-chains and linear extentions. Dual Dilworth
Theorem (Mirsky's Theorem) and Erdos-Szekeres Lemma.
-
Lecture 14:
Dilworth's Theorem and its relation to the Theorems of Hall and
Konig-Egervary.
-
Lecture 15:
Gallay-Roy Theorem. Covering P([n]) using symmetric chains and Sperner's
Theorem. Bollobas's Theorem and LYM Inequality.
-
Lecture 16:
The Littlewood-Offord Problem. Erdos-Ko-Rado Theorem using Cyclic
Permutations and using the Kruskal-Katona Theorem.
-
Lecture 17:
Proof of Kruskal-Katona Theorem.
-
Lecture 18:
Arrow's Impossibility Theorem.
Sieving
-
Lecture 19:
The Inclusion-Exclusion 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 Inclusion-Exclusion.
-
Lecture 23:
Gessel-Viennot 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:
Inclusion-Exclusion over Ranked Distributive Lattices.
-
Lecture 28:
Relation between number of Acyclic Orientations and the Chromatic
Polynomial (Stanley's Theorem). The BEST Theorem.