The indications of Section have been updated to the corresponding sections in the Fall 2003 version of the text, which has been substantially reorganized from 2002. The order of the 2003 text will be followed in 2003.
Lecture 1, Wed Aug 28: Section 1.1 (Classical Counting Models)
course overview, counting of simple words, subsets, multisets,
words with fixed alphabet and length
Lecture 2, Fri Aug 30: Section 1.3 (More Bijective Arguments)
Cayley's Formula, words with fixed multiplicities, multinomial coefficients,
Fermat's Little Theorem, lattice paths, lattice paths, Pascal's Formula
committee with chair identity
Lecture 3, Wed Sep 4: Section 1.2-3 (More Identities, Catalan and Bijections)
Summation Identity, Vandermonde convolution, ballot problem, Catalan numbers,
Cycle Lemma, ballot lists (skipped bijection with ordered binary trees)
Lecture 4, Fri Sep 6: Section 3.1 (Ordinary Generating Functions)
product rule, multisets, permutations of [n] by number of cycles
Lecture 5, Mon Sep 9: Section 3.3 (Exponential Generating Functions)
product rule, words, derangements, Stirling numbers of second and first kinds
Lecture 6, Wed Sep 11: Section 3.2 (Coefficients of Generating Functions)
formal differentiation, multisets, extended binomial coefficient,
manipulations of generating functions, summation of powers (especially squares),
Eulerian numbers (permutations of [n] with k runs)
Lecture 7, Fri Sep 13: Section 3.4 & 2.1 (Partitions of Integers, Recurrences)
OGFs for partitions, Ferrer's diagrams, distinct parts vs odd parts,
congruence classes of triangles, Euler Identity (distinct odd parts vs
self-conjugate partitions), first examples of recurrences (regions formed
by n lines, Fibonacci model by 1,2-lists with sum n)
Lecture 8, Mon Sep 16: Section 2.1-2 (More Recurrences, Characteristic Equation Method)
Recurrences for derangements and Catalan numbers, characteristic equation method
for linear recurrences with constant coefficients (examples for Fibonacci,
repeated roots, and exponential inhomogeneous term)
Lecture 9, Wed Sep 18: Section 2.2 (Generating Function Method)
Generating function approach to solving recurrences, characterization theorem
for solutions of linear recurrences with constant coefficients by OGFs,
OGF for Catalan numbers by generating function method, first example of
substitution method
Lecture 10, Fri Sep 20: Section 2.3 (Substitution Method)
Solution of derangement recurrence, application of substitution to Stirling's
Formula, basic inclusion-exclusion formula
Lecture 11, Mon Sep 23, Section 4.1 (Inclusion-Exclusion & Restricted Perms.)
Applications of inclusion-exclusion to Euler totient, chromatic polynomial,
Stirling numbers, proofs of identities, derangements by inclusion-exclusion,
generalization to permutations with forbidden positions, rook polynomials.
Lecture 12, Wed Sep 25, Section 4.1 (Multiple Properties & Signed Involutions)
OGF for elements by number of properties, expected number of fixed points,
probleme des menages, signed involutions, application to nonintersecting
lattice n-paths (simplified to number only, without weights), brief mention
of signed involution argument for formula for Eulerian numbers
Lecture 13, Fri Sep 27, Section 4.3 (Young Tableaux - presented without proofs)
Ballot problem over many candidates, Hook-length Formula, RSK correspondence,
Schensted's Theorem, up-down and right-left sequences, jeu de taquin,
unions of k increasing sequences (Greene's Theorem), reversal transposes
P-symbol
Lecture 14, Mon Sep 30, Section 4.2 (Polya-Redfield Counting)
Batons, 3-cornered hats, equivalence classes of colorings, Burnside's Lemma,
4-bead necklaces, cycle structure and cycle index, pattern inventory for
4-bead necklaces
Lecture 15, Wed Oct 2, Section 4.2 & 3.3 (Polya, Exponential Formula, etc.)
Counting isomorphism classes of graphs, EGF for connected graphs, the
Exponential Formula, EGFs for partitions of sets & permutations,
application to Cayley's Formula (invoking Lagrange Inversion Formula
without proof)
Lecture 16, Fri Oct 4, Chapter 5, Section 6.1 (Elementary Graph Theory, Matchings)
Paths/trails/walks, examples of proof by extremality,
transitivity of connection relation, characterization of cut-edges and
bipartite graphs, Eulerian circuits, Hall's Theorem, Marriage Theorem,
Birkhoff-von Neumann Theorem (rational case)
Lecture 17, Mon Oct 7, Section 6.1-2 (Matchings)
Min-max relations, Ore's Theorem, Konig-Egervary Theorem, Konig's Other
Theorem (without proof), augmenting paths and maximum matchings,
relation between Tutte's 1-factor Theorem and Berge-Tutte formula,
Parity Lemma, application of Tutte's 1-factor theorem to regular graphs
Lecture 18, Wed Oct 9, Section 6.2-3, 7.1 (Matchings, Connectivity)
Proof of Berge-Tutte formula, 2-factors in even regular graphs,
reduction of f-factor to 1-factor problem, connectivity definitions,
hypercube example
Lecture 19, Fri Oct 11, Section 7.1-2 (Connectivity)
Harary graphs, vertex k-split, edge-connectivity, edge cuts,
Menger's Theorem via Pym's Theorem
Lecture 20, Mon Oct 14, Section 7.2 (Connectivity)
Line graphs, Menger for edges, Ford-Fulkerson CSDR Theorem, expansion lemma,
fan lemma, cycles in k-connected graphs (Dirac), 3-contractible edges
(Thomassen), edge subdivision, ear decomposition, Robbins' Theorem
Lecture 21, Wed Oct 16, Section 7.3, 8.1 (Spanning Cycles, start Coloring)
Necessary condition, Sufficient conditions of Dirac and Ore,
Hamiltonian closure, Chvatal-Erdos Condition, statements without proof of
(Chvatal's Condition, Fan's Condition, analogues for circumference),
definitions and elementary bounds on coloring
Lecture 22, Fri Oct 18, Section 8.1-2 (Coloring)
Upper bounds on chromatic number (Welsh-Powell, Szekeres-Wilf, Minty;
Gallai-Roy without proof), Mycielski's construction, critical graphs through
edge-connectedness (Dirac)
Lecture 23, Mon Oct 21, Section 8.2-3 (Coloring)
List coloring (examples, application to Gallai's Theorem on k-critical graphs
and Brooks' Theorem), edge-coloring (fat triangle, statement of Vizing Theorem,
bipartite graphs in Class 1 - include 1-factorization of even cliques)
Lecture 24, Wed Oct 23, Section 8.3, 9.1 (Edge-Coloring, Planarity)
Extensions of Vizing's Theorem, proof of Anderson-Goldberg extension,
planar graphs and duality (K5 and K3,3,
cycles vs bonds)
Lecture 25, Fri Oct 25, Section 9.1-3 (Planarity)
Bipartite planar graphs, Euler's Formula (application to edge bound),
maximal planar graphs, sketch Kuratowski's Theorem, 5-choosability of
planar graphs (Thomassen), Tait's Theorem with relation to 4-color Theorem
Lecture 26, Mon Oct 28, Section 9.3, 10.1 (Planarity, Pigeonhole)
Mention of cycle double covers, Tutte graph, Grinberg's Theorem,
applications of pigeonhole principle (covering Kn with
bipartite subgraphs, divisible pairs in [n], domino tilings,
long cycles in spanning tree of hypercube, Erdos-Szekeres, Graham-Kleitman
increasing trails
Lecture 27, Wed Oct 30, Section 10.2 (Ramsey Theory)
Ramsey's Theorem, application to convex m-gons (Happy End Theorem),
application to table storage and search (Yao)
Lecture 28, Fri Nov 1, Section 10.2-3 (Ramsey Theory)
Ramsey numbers (small examples, large bounds, triangle-free graphs),
graph Ramsey theory (tree vs. complete graph), Schur's Theorem
Lecture 29, Mon Nov 4, Section 12.1 (Partially Ordered Sets)
Definitions & examples (order relation, comparability graph, cover graph,
chains/antichains, ideals), Dilworth's Theorem, equivalence to Konig-Egervary,
dimension (bounded by width)
Lecture 30, Wed Nov 6, Section 13.1 (Linear Extensions)
Dimension by realizer or embedding, "standard example", unforced pairs &
alternating cycles, characterization of 2-dimensional posets, one-point
removal theorem, Hiraguchi's inequality (dim P <= |P|/2)
Lecture 31, Fri Nov 8, Section 12.2-3 (Partially Ordered Sets)
Symmetric Chain Orders (2^n, chain-product, bracketing decomposition,
application to monotone Boolean functions), LYM Orders (Sperner's Theorem,
regular covering, LYM Inequality, normalized matching)
Lecture 32, Mon Nov 11, Section 12.3, 14.1 (Partially Ordered Sets, Probability)
LYM Orders (finish Kleitman's theorem, symmetric chain decomposition for
rank-symmetric rank-unimodal by CSDR, strong Sperner property, mention of
products), existence and expectation arguments (Ramsey numbers,
upper bound on binomial coefficients, Caro-Wei Theorem)
Lecture 33, Wed Nov 13, Section 14.1 (Probability)
Applications of expectation (Turan's Theorem from Caro-Wei,
Fibonacci formula, proper dissections of products),
deletion method (Ramsey numbers, dominating sets)
Lecture 34, Fri Nov 15, Section 14.1-2 (Probability)
Deletion method (comment on graphs with large chromatic number and girth,
non-2-colorable hypergraphs), Local Lemma (application to Ramsey numbers),
notion of "almost always" (application to diameter 2), Markov's Inequality
Lecture 35, Mon Nov 18, Section 14.2 (Probability)
Threshold functions, Second Moment Method, disappearance of isolated
vertices, graph evolution and connectedness, balanced graphs
Lecture 36, Wed Nov 20, Section 14.3, 17.1 (Latin squares)
Comments on parameters of random graphs, martingales and chromatic number,
mention of algebraic and geometric techniques, families of mutually orthogonal
Latin squares
Lecture 37, Fri Nov 22, Section 17.1 (Designs)
Combinatorial designs, symmetric designs, Hadamard matrices,
start projective planes
Lecture 38, Mon Dec 2, Section 17.2 (Projective Planes)
Properties of projective planes (symmetric designs), equivalence to complete
family of orthogonal latin squares, application to extremal problems
(smallest maximum degree for diameter 2, largest size for avoiding 4-cycles)
Lecture 39, Wed Dec 4, Section 17.3 (Designs)
Fisher's Inequality, Bruck-Chowla-Ryser theorem (odd case stated only),
difference sets and projective planes, statement and application of the
Multiplier Theorem
Lecture 40, Fri Dec 6, Section 18.1 (Matroids)
Hereditary systems, examples of matroids
Lecture 41, Mon Dec 9, Section 18.1 (Matroids)
Further examples, axiomatics of matroids
Lecture 42, Wed Dec 11, Section 18.1 (Matroids)
Duality and minors
Lecture 43, Fri Dec 13, Section 18.2 (Matroids)
Matroid intersection and applications