Lec 1, 8/24 Wed, Sec 1.1:
Course overview, general principles of enumeration, counting of words & subsets,
binomial theorem. (Leftover to Lec 2: multisets and compositions.)
Lec 2, 8/26 Fri, Sec 1.2:
Lattice paths, basic identities, extended binomial coefficient,
summing initial values of polynomials, Delannoy numbers.
Lec 3, 8/29 Mon, Sec 1.3:
Counting graphs and trees, multinomial coefficients (trees by degrees,
Fermat's Little Theorem), Ballot problem, central binomial convolution.
Lec 4, 8/31 Wed, Sec 1.3-2.1:
Catalan numbers (Cycle Lemma, bijections, recurrence),
Recurrences (regions among lines, Fibonacci numbers and 1,2-lists).
Lec 5, 9/2 Fri, Sec 2.1-2:
Derangements, recurrences in two variables (distribution problems,
Delannoy numbers), characteristic equation method (through Fibonacci solution).
Lec 6, 9/7 Wed, Sec 2.2:
Characteristic equation method (repeated roots, inhomogeneous),
generating function method (linear constant coefficients, Catalan).
(Catalan solution left to Friday's class.)
Lec 7, 9/10 Fri, Sec 2.3-3.1:
Substitution method (Tower of Hanoi, derangements, Stirling's approximation),
generating functions (sum/product operations, multisets).
Lec 8, 9/12 Mon, Sec 3.1:
Generating functions (restricted multisets, subsets (two variables)),
permutation statistics (OGFs by #inversions, #cycles),
Eulerian numbers (Worpitzky's Identity by barred permutations, A(n,k)
formula by substitution).
Lec 9, 9/14 Wed, Sec 3.2:
Generating function manipulations (differentiation, evaluation at special
values, shifting index, summing initial coefficients),
summation by convolutions, Snake Oil method.
Lec 10, 9/16 Fri, Sec 3.3:
Exponential generating functions. Products of EGFs (words),
examples and applications of EGFs (flags on poles, restricted words,
Stirling numbers, binomial inversion, derangements).
Lec 11, 9/19 Mon, Sec 3.3-4:
The Exponential Formula (graphs, partitions, permutations, recurrence),
Lagrange Inversion Formula (statement and application to trees),
partitions of integers (basic generating functions).
Lec 12, 9/21 Wed, Sec 3.4:
Asymptotic number of partitions,
Combinatorics of partitions (Ferrers diagrams, conjugation, Fallon's Identity,
classes of triangles, Euler's Identity).
Lec 13, 9/23 Fri, Sec 4.1:
Inclusion-exclusion (basic formula and totient application),
inclusion-exclusion applications (Stirling numbers, Eulerian numbers,
identities, derangements),
Lec 14, 9/26 Mon, Sec 4.1:
Permutations with restricted positions (rook polynomials), OGF by number of
properties, probleme des menages (brief summary).
Signed involutions (inclusion-exclusion formula, partitions into distinct
odd parts (skipped), path systems in digraphs, application to disjoint-path
systems of lattice paths and rhombus tilings).
Lec 15, 9/28 Wed, Sec 4.2:
Examples for counting under symmetry, Lagrange's Theorem,
Burnside's Lemma, cycle indices, symmetries of cube,
pattern inventory.
Lec 16, 10/1 Fri, Sec 4.2-3:
Applications of pattern inventory (Polya's Theorem) to
isomorphism classes of graphs and to crowns,
Young tableaux (brief presentation of Hook-length formula,
RSK correspondence, and consequences of RSK correspondence).
Chapter 5, First Concepts for Graphs, for background reading
Lec 17, 10/3 Mon, Sec 6.1:
Bipartite Matching (Hall's Theorem, Marriage Theorem, Birkhoff-von Neumann
Theorem, transveral with "large" minimum (ranchers/farmers),
Ore's min/max formula, Konig-Egervary Theorem.
Lec 18, 10/5 Wed, Sec 6.2:
Brief treatment of Gallai's Theorem and Konig's Other Theorem (Sec 6.1).
General Matching (Augmenting paths, Berge-Tutte Formula, Tutte's 1-Factor
Theorem, application of Tutte's Theorem to regular graphs.
Lec 19, 10/7 Fri, Sec 7.1:
Petersen's 2-Factor Theorem (via Eulerian circuit and Hall's Theorem) (Sec 6.2).
(Vertex) connectivity definitions, superadditivity of connectivity under
cartesian product, Harary graphs, edge-connectivity definitions, Whitney's
Theorem (statement only), edge-connectivity for diameter 2 (Plesnik).
Lec 20, 10/10 Mon, Sec 7.2:
k-Connected Graphs (Independent x,y-paths, linkage and blocking sets,
Pym's Theorem, Menger's Theorems (8 versions), Ford-Fulkerson CSDR,
Expansion and Fan Lemmas, cycles through specified vertices).
Lec 21, 10/12 Wed, Sec 7.3:
Hamiltonian cycles (necessary condition, Ore & Dirac conditions,
closure, statement of Chvatal condition, Chvatal example).
Lec 22, 10/14 Fri, Sec 7.3-8.1:
Spanning cycles (Chvatal-Erdos Theorem, statement of Lu's Theorem),
circumference (brief sketch of Bondy's Lemma, application to Fan's Theorem),
vertex coloring (examples, easy bounds, greedy coloring, degree bounds, Minty's
Theorem).
Lec 23, 10/17 Mon, Sec 8.1-2:
chromatic number (interval graphs, Triangle-free graphs & Mycielski's
construction), color-critical graphs (minimum degree, edge-connectivity),
list coloring (examples and degree-choosability).
Lec 24, 10/19 Wed, Sec 8.2-3:
List extension of Brooks' Theorem,
edge-coloring (complete graphs, Petersen graph, bipartite graphs),
Lec 25, 10/21 Fri, Sec 8.3-4:
Anderson-Goldberg generalization of Vizing's Theorem,
perfect graphs (examples, Perfect Graph Theorem).
Lec 26, 10/24 Mon, Sec 9.1:
planar graphs and their duals, cycles vs bonds, bipartite = dual Eulerian,
Euler's Formula and edge bound.
Lec 27, 10/26 Wed, Sec 9.2-3:
Kuratowski's Theorem (brief sketch of proof via convex embeddings),
coloring of planar graphs (6CT, 5CT, 5-list-coloring, Kempe).
Lec 28, 10/28 Fri, Sec 9.3:
Discharging (approach to 4CT, list edge-coloring of planar graphs),
Tait's Theorem, Grinberg's Theorem,
Lec 29, 10/31 Mon, Sec 10.1-2:
Applications of pigeonhole principle (divisible pairs, paths in cubes,
domino tilings, monotone sublists, increasing trails), Ramsey's Theorem.
Lec 30, 11/2 Wed, Sec 10.2:
Applications of Ramsey's Theorem (convex m-gons, table storage),
Ramsey numbers, graph Ramsey theory (tree vs complete graph).
Lec 31, 11/4 Fri, Sec 10.3-12.1:
Ramsey theory (Schur, Van der Waerden Theorem statement and example),
partially ordered sets (definitions and examples, Dilworth's Theorem,
equivalence of Dilworth and Konig-Egervary).
Lec 32, 11/7 Mon, Sec 12.1-2:
Dilworth's Theorem (proof by Perfect Graph Theorem, statement of
generalizations), graded posets, (symmetric chain decompositions for subsets
and products, bracketing decomposition, application of monotone Boolean
functions).
Lec 33, 11/9Wed, Sec 12.3:
LYM posets (Sperner's Theorem via LYM, equivalence with regular covering and
normalized matching, LYM and symmetric unimodal rank-sizes => symmetric chain
decomposition).
Lec 34, 11/11 Fri, Sec 14.1:
existence arguments (Ramsey number, 2-colorability of k-uniform
hypergraphs), pigeonhole property of expectation (linearity and indicator
variables, Caro-Wei bound on independence number, application of Caro-Wei to
Turan's Theorem).
Lec 35, 11/14 Mon, Sec 14.2:
Deletion method (Ramsey numbers, dominating sets, sketch for large girth and
chromatic number), Local Lemma (symmetric version, Ramsey number application).
Lec 36, 11/16 Wed, Sec 14.2-3:
List coloring by Local Lemma, random graph models,
almost-always properties, connectedness of the random graph.
Markov's Inequality, diameter 2, threshold functions.
Lec 37, 11/18 Fri, Sec 14.3-4
Second moment method, disappearance of isolated vertices.
threshold for appearance of balanced graphs, comments on graph evolution,
connectivity/cliques/coloring of random graphs.
Lec 38, 11/28 Mon, Sec 17.1:
Latin squares (orthogonal families, Moore-MacNeish construction),
block designs (examples, elementary constraints on parameters).
Lec 39, 11/30 Wed, Sec 17.1-2:
Fisher's Inequality, discussion of Bruck-Chowla-Ryser,
Hadamard matrices (restriction on order, relation to designs & coding).
Lec 40, 12/02 Fri, Sec 17.2:
projective planes (elementary properties, relation to designs and Latin
squares, application to extremal problems).
Lec 41, 12/05 Mon, Sec 17.2, 18.1:
difference sets and multipliers, matroid examples.
Lec 42, 12/07 Mon, Sec 18.1:
Matroid axiomatics and duality.
Lec 43, 12/10 Fri, Sec 18.1-2:
Matroid minors, Whitney's characterization of planar graphs by abstract duals,
matroid intersection and its applications (brief!).