Lecture 1, Wed Aug 27: Section 1.1 (Classical Counting Models)
Course overview, general principles of enumeration,
counting of words & subsets & multisets, alternative multiset models,
binomial theorem
Lecture 2, Fri Aug 29: Section 1.2 (Identities)
Basic identities (Pascal, committee-chair, Summation, Vandermonde),
Lattice paths and Delannoy numbers
Lecture 3, Wed Sep 3: Section 1.3 (Applications)
Cayley's Formula, multinomial coefficients, Fermat's Little Theorem,
ballot problem
Lecture 4, Fri Sep 5: Section 1.3-2.1 (Recurrences)
Catalan bijections, cycle lemma, examples of recurrences
(regions among lines, Fibonacci and 1,2-lists, derangements, Catalan)
Lecture 5, Mon Sep 8: Section 2.1-2.2 (Solution of Recurrences)
Recurrences in two variables (distribution problems, Delannoy numbers),
characteristic equation method (homogeneous, inhomogeneous)
Lecture 6, Wed Sep 10: Section 2.2-2.3 (Solution of Recurrences)
Generating function method (linear constant coefficients, Catalan),
substitution method (derangements)
Lecture 7, Fri Sep 12: Section 2.3-3.1 (Ordinary Generating Functions - OGF)
substitution method for asymptotic solutions (Stirling approximation),
combinatorics of OGFs (sum/product operations, multisets, compositions),
ogf in two variables for subsets.
Lecture 8, Mon Sep 15: Section 3.1-3.2 (Coefficients and Summations)
enumerating permutations of [n] by #cycles,
OGF manipulations (differentiation, shifting index, evaluation at x,
extracting even/odd terms, summing initial terms (mult by 1/(1-x)),
convolution), examples of evaluating summations
Lecture 9, Wed Sep 17: Section 3.2-3.3 (Exponential Generating Functions)
Snake Oil, combinatorics of EGFs (labeled products, words)
applications (Stirling numbers, binomial inversion, derangements)
Lecture 10, Fri Sep 19: Section 3.3 (Exponential Generating Functions)
The Exponential Formula (graphs, partitions, permutations),
Lagrange Inversion Formula (statement and application to trees)
Lecture 11, Mon Sep 22: Section 3.4 (Partitions of Integers)
Generating functions for partitions (asymptotics), combinatorial arguments
(Ferrers diagrams)
Lecture 12, Wed Sep 24: Section 3.4-4.1 (Inclusion-Exclusion)
Euler's Identity, classical applications of inclusion-exclusion,
permutations with restricted positions (rook polynomials)
Lecture 13, Fri Sep 26: Section 4.1 (Signed Involutions)
OGF by number of properties, probleme des menages,
inclusion-exclusion by signed involution, determinants by path systems
Lecture 14, Mon Sep 29: Section 4.1-2 (Polya-Redfield Counting)
Disjoint-path systems and lattice paths (rhombic tilings),
examples for counting under symmetry, Lagrange's Theorem
Lecture 15, Wed Oct 1: Section 4.2 (Polya-Redfield Counting)
Burnside's Lemma, cycle indices, pattern inventory, Polya's Theorem,
isomorphism classes of graphs
partitions of integers (OGFs and asymptotics)
Lecture 16, Fri Oct 3: Section 4.3 (Young tableaux, without proofs)
Hook-length formula, RSK correspondence, involutions, planarization,
monotone subsequences
Chapter 5, First Concepts for Graphs, for background reading
Lecture 17, Mon Oct 6: Section 6.1 (Bipartite Matching)
Hall's Theorem, Marriage Theorem, Birkhoff-von Neumann Theorem,
Ore's min/max formula, Konig-Egervary Theorem, statement of
Gallai's Theorem and Konig's Other Theorem
Lecture 18, Wed Oct 8: Section 6.2 (Matching in General Graphs)
Augmenting paths, Berge-Tutte Formula and Tutte's 1-Factor Theorem,
application of Tutte's Theorem to regular graphs, Petersen's 2-Factor Theorem
(via Eulerian circuit and Hall's Theorem), momentary mention of f-factors
Lecture 19, Fri Oct 10: Section 7.1 (Connectivity Parameters)
(Vertex) connectivity definitions, cartesian product with K2,
Harary graphs, edge-connectivity definitions, Whitney's Theorem,
edge cuts vs vertex sets, edge-connectivity for diameter 2 (Plesnik),
brief mention of bonds and blocks
Lecture 20, Mon Oct 13: Section 7.2 (k-Connected Graphs)
Independent x,y-paths, linkage and blocking sets, Pym's Theorem,
Menger's Theorems (eight versions), Ford-Fulkerson CSDR, Expansion and Fan
Lemmas, cycles through specified vertices
Lecture 21, Wed Oct 15: Section 7.2-3 (Spanning Cycles)
Characterizations of 3-connected and 2-connected graphs (3-contractible edges,
ear decompositions, statements about k-connected orientations),
Spanning cycles (necessary condition, sufficient conditions of Ore/Dirac,
Hamiltonian closure, Chvatal's Condition (statement only),
Chvatal-Erdos Theorem)
Lecture 22, Fri Oct 17: Section 8.1 (Vertex Coloring)
Definitions and examples, easy lower bounds, behavior under join,
greedy coloring, upper bounds from degrees, Minty's Theorem
Lecture 23, Mon Oct 20: Section 8.1-2 (Structural Aspects of Coloring)
Intersection graphs, interval graphs, perfect graphs (definition and comments
only), triangle-free graphs (Mycielski's construction), list coloring
(examples and degree-choosability)
Lecture 24, Wed Oct 22: Section 8.2-3 (Edge-Coloring)
Finish Brooks' Theorem and color-critical graphs,
edge-coloring (complete graphs, Class 1 vs 2, Petersen graph, bipartite
graphs), preparation for Vizing's Theorem
Lecture 25, Fri Oct 24: Section 8.3-9.1 (Planarity)
Anderson-Goldberg generalization of Vizing's Theorem,
planar graphs and their duals, cycles vs bonds, bipartite = dual Eulerian
Lecture 26, Mon Oct 27: Section 9.1-3 (More Planarity)
Euler's Formula (edge bound, duals, etc.),
Kuratowski's Theorem (sketch of proof via convex embeddings),
coloring of planar graphs (6CT, 5CT, Kempe, idea of discharging)
Lecture 27, Wed Oct 29: Section 9.3-10.1 (Planar coloring, Pigeonhole)
5-list-coloring, Tait & Grinberg, applications of pigeonhole
Lecture 28, Fri Oct 31: Section 10.1-2 (Pigeonhole and Ramsey)
Pigeonhole Principle (applications to divisible pairs, monotone sublists,
increasing trails in edge-ordered complete graphs), Ramsey's Theorem
(intuition, proof, convex m-gon application)
Lecture 29, Mon Nov 3: Section 10.2 (Ramsey theory)
Ramsey application to table storage, Ramsey numbers,
graph Ramsey theory (tree vs complete graph, briefly)
Lecture 30, Wed Nov 5: Section 10.3 & 12.1 (more Ramsey, poset introduction)
Comments on infinite Ramsey theory, Schur's Theorem, Van der Waerden's Theorem
(statement and example), poset definitions and examples, Dilworth's Theorem
Lecture 31, Fri Nov 7: Section 12.1-2 (Posets)
Statement of characterizations of comparability graphs, equivalence of Dilworth
and Konig-Egervary Theorems, relation to Perfect Graph Theorem, graded posets,
symmetric chain decompositions for subsets and products
Lecture 32, Mon Nov 10: Section 12.2-3 (Symmetric chains and LYM orders)
Bracketing decomposition, application to monotone Boolean functions,
LYM Inequality and Sperner's Theorem, equivalence of LYM with regular
covering and normalized matching, strong Sperner property
Lecture 33, Wed Nov 12: Section 12.3-13.1 (LYM orders and dimension)
LYM and symmetric unimodal rank-sizes => symmetric chain decomposition,
dimension (definition and examples, bound in terms of width)
Lecture 34, Fri Nov 14: Section 14.1 (Probability)
Existence arguments (Ramsey number, 2-colorability of k-uniform
hypergraphs), pigeonhole property of expectation (linearity and indicator
variables, Caro-Wei bound on independence number, Turan's Theorem)
Lecture 35, Mon Nov 17: Section 14.2 (Probability)
Binet's Formula for Fibonacci numbers by conditional probability,
deletion method (Ramsey numbers, dominating sets, large girth and chromatic
number)
Lecture 36, Wed Nov 19, Section 14.2-3 (Probability)
Local Lemma (Ramsey numbers, list coloring), random graph models,
almost-always properties, connectedness, Markov's Inequality
Lecture 37, Fri Nov 21, Section 14.3 (Probability)
Threshold functions, second moment method, disappearance of isolated
vertices, appearance of balanced subgraphs, comments on evolution and
graph parameters
Lecture 38, Mon Dec 1, Section 17.1 (Latin Squares / Block Designs)
Latin squares (orthogonal families, Moore-MacNeish construction),
block designs (examples, constraints on parameters, symmetric designs)
Lecture 39, Wed Dec 3, Section 17.1-2 (Hadamard Matrices / Projective Planes)
Hadamard matrices (constructions, relation to designs),
projective planes (elementary properties, relation to designs)
Lecture 40, Fri Dec 5, Section 17.2 (Projective Planes)
relation to Latin squares, construction from finite fields,
application to extremal problems
Lecture 41, Mon Dec 8, Section 17.2, 18.1 (Difference Sets / Matroids)
Difference sets (definitions/examples, multipliers, statement of
Multiplier Theorem), matroids (definitions and examples)
Lecture 42, Wed Dec 10, Section 18.1 (Matroids) Matroid axiomatics, matroid duality
Lecture 43, Fri Dec 12, Section 18.1-2 (Matroids) Matroid duality, matroid characterization of planar graphs, matroid intersection and its applications