Lec 1, 8/25 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/27 Fri, Sec 1.2:
Lattice paths, basic identities, extended binomial coefficient,
summing initial values of polynomials, identity for Delannoy numbers.
Lec 3, 8/30 Mon, Sec 1.3:
Counting graphs and trees, multinomial coefficients (trees by degrees,
Fermat's Little Theorem.
Lec 4, 9/1 Wed, Sec 1.3-2.1:
Ballot problem, central binomial convolution, Catalan numbers, Cycle Lemma,
Catalan bijections, Catalan recurrence.
Lec 5, 9/3 Fri, Sec 2.1-2:
Recurrences (regions among lines, Fibonacci and 1,2-lists, derangements),
recurrences in two variables (distribution problems, Delannoy numbers),
characteristic equation method (through Fibonacci solution).
Lec 6, 9/8 Wed, Sec 2.2:
Characteristic equation method (repeated roots, inhomogeneous),
generating function method (linear constant coefficients, Catalan).
Lec 7, 9/10 Fri, Sec 2.3-3.1:
substitution method (factorials, derangements, Stirling's approximation),
generating functions (sum/product operations, multisets, compositions).
Lec 8, 9/13 Mon, Sec 3.1-2:
generating functions (subsets, permutations by inversions, permutations by
#cycles),
manipulations (differentiation, evaluation at special values, shifting index,
summing initial coefficients).
Lec 9, 9/15 Wed, Sec 3.2-3:
Summation by convolutions, Snake Oil method, products of EGFs (words).
Lec 10, 9/17 Fri, Sec 3.3:
Examples and applications of EGFs (flags on poles, restricted words,
Stirling numbers, binomial inversion, derangements);
the exponential formula (for graphs).
Lec 11, 9/20 Mon, Sec 3.4:
The Exponential Formula (partitions, permutations, recurrence);
Lagrange Inversion Formula (statement and application to trees);
partitions of integers (generating functions and asymptotics).
Lec 12, 9/22 Wed, Sec 3.4-4.1:
Partition arguments with Ferrers diagrams (conjugation, classes of triangles,
Euler's Identity);
inclusion-exclusion (basic formula and totient application).
Lec 13, 9/24 Fri, Sec 4.1:
Inclusion-exclusion applications (Stirling numbers, derangements, identities),
permutations with restricted positions (rook polynomials), OGF by number of
properties, probleme des menages.
Lec 14, 9/27 Mon, Sec 4.1:
Signed involutions (inclusion-exclusion formula, partitions into distinct
odd parts, path systems in digraphs, application to disjoint-path systems
of lattice paths and rhombus tilings).
Lec 15, 9/29 Wed, Sec 4.2:
Examples for counting under symmetry, Lagrange's Theorem,
Burnside's Lemma, cycle indices, symmetries of cube.
Lec 16, 10/1 Fri, Sec 4.2-3:
Pattern inventory (Polya's Theorem), applications 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/4 Mon, Sec 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).
Lec 18, 10/6 Wed, Sec 6.2:
General Matching (Augmenting paths, Berge-Tutte Formula, 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).
Lec 19, 10/8 Fri, Sec 7.1:
(Vertex) connectivity definitions, cartesian product with K2,
Harary graphs, edge-connectivity definitions, Whitney's Theorem,
edge-connectivity for diameter 2 (Plesnik), brief mention of bonds and blocks.
Lec 20, 10/11 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/13 Wed, Sec 7.3:
Hamiltonian cycles (necessary condition, Ore & Dirac conditions,
closure, statement of Chvatal condition, Chvatal example).
Lec 22, 10/15 Fri, Sec 7.3-8.1:
leftover spanning cycles (statement/example of Fan's Theorem, Chvatal-Erdos
Theorem), vertex coloring (examples, easy bounds, behavior under join,
greedy coloring, interval graphs, degree bounds, Minty's Theorem).
Lec 23, 10/18 Mon, Sec 8.1-2:
Triangle-free graphs (Mycielski's construction),
color-critical graphs (minimum degree, edge-connectivity),
list coloring (examples and degree-choosability).
Lec 24, 10/20 Wed, Sec 8.2-4:
List extension of Brooks' Theorem,
edge-coloring (complete graphs, Class 1 vs 2, Petersen graph, bipartite
graphs), perfect graphs (definition and comments only).
Lec 25, 10/22 Fri, Sec 8.3-9.1:
Anderson-Goldberg generalization of Vizing's Theorem,
planar graphs and their duals, cycles vs bonds, bipartite = dual Eulerian,
Euler's Formula and edge bound.
Lec 26, 10/25 Mon, Sec 9.1-3:
Kuratowski's Theorem (sketch of proof via convex embeddings),
coloring of planar graphs (6CT, 5CT, Kempe), 5-list-coloring, Tait's Theorem.
Lec 27, 10/27 Wed, Sec 9.3-10.1:
Grinberg's Theorem, applications of pigeonhole principle (divisible pairs,
covering by bipartite graphs, domino tilings, monotone sublists, increasing
trails).
Lec 28, 10/29 Fri, Sec 10.1:
Permutation patterns (proof of Stanley-Wilf Conjecture),
Ramsey's Theorem.
Lec 29, 11/1 Mon, Sec 10.2:
Applications of Ramsey's Theorem (convex m-gons, table storage),
Ramsey numbers.
Lec 30, 11/3 Wed, Sec 10.3-12.1:
Graph Ramsey theory (tree vs complete graph)
infinite Ramsey theory, Schur's Theorem, Van der Waerden's Theorem
(statement and example), poset definitions and examples, Dilworth's Theorem
Lec 31, 11/5 Fri, Sec 12.1-2:
Equivalence of Dilworth and Konig-Egervary Theorems, relation to Perfect Graph
Theorem, graded posets, symmetric chain decompositions for subsets and products,
bracketing decomposition.
Lec 32, 11/8 Mon, Sec 12.2-3:
Application of bracketing to monotone Boolean functions,
LYM Inequality and Sperner's Theorem, equivalence of LYM with regular
covering and normalized matching
Lec 33, 11/10 Wed, Sec 12.3-14.1:
LYM and symmetric unimodal rank-sizes => symmetric chain decomposition,
existence arguments (Ramsey number, 2-colorability of k-uniform
hypergraphs), pigeonhole property of expectation (linearity and indicator
variables, Caro-Wei bound on independence number)
Lec 34, 11/12 Fri, Sec 14.1-2:
Application of Caro-Wei to Turan's Theorem, Binet's Formula for Fibonacci
numbers by conditional probability, deletion method (Ramsey numbers, dominating
sets, brief sketch for large girth and chromatic number).
Lec 35, 11/15 Mon, Sec 14.2-3:
Local Lemma (Ramsey numbers, list coloring), random graph models,
almost-always properties, connectedness of the random graph.
Lec 36, 11/17 Wed, Sec 14.3:
Markov's Inequality, diameter 2, threshold functions, second moment method,
disappearance of isolated vertices.
Lec 37, 11/19 Fri, Sec 17.1:
(second moment method for threshold for appearance of balanced graphs),
Latin squares (orthogonal families, Moore-MacNeish construction),
Lec 38, 11/29 Mon, Sec 17.1:
block designs (examples, constraints on parameters, symmetric designs)
Hadamard matrices (restriction on order, relation to designs).
Lec 39, 12/1 Wed, Sec 17.1-2:
Hadamard matrices (application to coding theory),
projective planes (elementary properties, relation to designs and Latin
squares).
Lec 40, 12/3 Fri, Sec 17.2:
projective planes from fields, polarity graph, application to extremal problems
(avoiding 4-cycles, diameter 2), difference sets and multipliers.
Lec 41, 12/6 Mon, Sec 18.1:
Matroid examples and equivalence of definitions.
Lec 42, 12/8 Wed, Sec 18.1:
Matroids: greedy algorithm, span function, 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.