Lec 1, 8/24 Mon, Sec 1.1:
Course details, general principles of enumeration, counting of words & subsets,
binomial theorem, multisets/compositions.

Lec 2, 8/26 Wed, Sec 1.2:
Lattice paths, basic identities, extended binomial coefficient,
summing polynomials, Delannoy numbers, Hamming ball/Delannoy correspondence.

Lec 3, 8/28 Fri, 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 Mon, Sec 1.3-2.1:
Catalan numbers (generalization, bijections, recurrence),
Fibonacci numbers and 1,2-lists, derangements.

Lec 5, 9/2 Wed, Sec 2.1-2:
Recurrences in two indices (distribution problems, Delannoy numbers),
characteristic equation method (through repeated roots).

Lec 6, 9/4 Fri, Sec 2.2:
Characteristic equation method (inhomogeneous terms),
generating function method (linear w. constant coefficients,
relation to char.eqn. method)

Lec 7, 9/9 Wed, Sec 2.3-3.1:
Catalan solution,
substitution method (factorials, derangements, Stirling's approximation),
generating functions (sum/product operations, multisets)

Lec 8, 9/11 Fri, Sec 3.1:
Generating functions: multisets with restricted multiplicity, functions in two
variables (skipped), permutation statistics (by #inversions, #cycles), Eulerian
numbers (#runs, Worpitzky's Identity by barred permutations)

Lec 9, 9/14 Mon, Sec 3.2:
Generating function manipulations: sum & product
(*A(n,k)* formula by inversion from Worpitzky), shifted index,
differentiation & evaluation at special values, summing initial coefficients,
summation by convolutions. First Snake Oil example.

Lec 10, 9/16 Wed, Sec 3.3:
More Snake Oil, exponential generating functions: products of EGFs (words),
examples and applications of EGFs (flags on poles, restricted words,
Stirling numbers)

Lec 11, 9/19 Fri, Sec 3.3:
EGF applications (binomial inversion, derangements),
the Exponential Formula (graphs, partitions, permutations, recurrence),
Lagrange Inversion Formula (statement and application to trees).

Lec 12, 9/21 Mon, Sec 3.4:
Partitions of integers (basic generating functions, bounds on coefficients).
combinatorics of partitions (Ferrers diagrams, conjugate, Fallon's Identity
(mentioned), congruence classes of triangles, Euler's Identity).

Lec 13, 9/23 Wed, Sec 4.1:
Basic inclusion-exclusion formula, applications (totients,
Stirling numbers, alternating sums, skipped Eulerian numbers)

Lec 14, 9/25 Fri, Sec 4.1:
Permutations with restricted positions (rook polynomials), OGF by number of
properties (skipped probleme des menages),
signed involutions (inclusion-exclusion as special case,
partitions into distinct odd parts).

Lec 15, 9/28 Mon, Sec 4.1-2:
Disjoint-path systems in digraphs, application to lattice paths and rhombus
tilings. Examples for counting under symmetry, Lagrange's Theorem,
Burnside's Lemma.

Lec 16, 9/30 Wed, Sec 4.2-3:
Examples for Burnside's Lemma, Cycle indices, symmetries of cube, pattern
inventory (Polya's Theorem), counting isomorphism classes of graphs.
Young tableaux (brief presentation of Hook-length formula,
RSK correspondence, and consequences of RSK correspondence).

Lec 17, 10/2 Fri, Sec 5.1-3 highlights, Sec 6.1:
Properties of Petersen graph, degree-sum formula and rectangle partition,
characterization of bipartite graphs, Eulerian circuits
(Chapter 5, First Concepts for Graphs, for background reading).
Bipartite Matching (Hall's Theorem).

Lec 18, 10/5 Mon, Sec 6.1:
Marriage Theorem, orientations with specified outdegrees.
Min/max relations (Ore's defect formula, Konig-Egervary Theorem,
Gallai's Theorem, Konig's Other Theorem).

Lec 19, 10/7 Wed, Sec 6.2:
General Matching: Tutte's 1-Factor Theorem from Berge-Tutte Formula, 1-factors
in regular graphs, Petersen's 2-Factor Theorem (via Eulerian circuit and Hall's
Theorem), augmenting paths, reduction of *f*-factor to 1-factor in blowup
(mentioned only briefly)

Lec 20, 10/9 Fri, Sec 7.1:
Connectivity (definitions, Harary graphs, cartesian products).
Edge-connectivity (definitions, Whitney's Theorem, edge cuts, diameter 2).
Bonds and blocks skipped.

Lec 21, 10/12 Mon, Sec 7.2:
k-Connected Graphs (Independent *x,y*-paths, linkage and blocking sets,
Pym's Theorem, Menger's Theorems (8 versions),
Expansion and Fan Lemmas, cycles through specified vertices),

Lec 22, 10/14 Wed, Sec 7.2-3:
Ford-Fulkerson CSDR, ear decomposition and Robbins' Theorem.
Spanning cycles: necessary condition, Ore & Dirac conditions, closure,
statement of Chvatal condition & sketch.

Lec 23, 10/16 Fri, Sec 7.3-8.1:
Chvatal-Erdos Theorem, comments on Lu's Theorem, Fan's Theorem, regularity,
pancyclicity, statements for circumference.
Vertex coloring: examples, easy bounds, greedy coloring, interval graphs,
degree bounds, start Minty's Theorem.

Lec 24, 10/19 Mon, Sec 8.1-2:
Triangle-free graphs (Mycielski's construction, *√n* bound),
color-critical graphs (minimum degree, edge-connectivity).
List coloring for complete bipartite graphs.

Lec 25, 10/21 Wed, Sec 8.2-3:
List coloring (degree choosability and extension of Brooks' Theorem),
edge-coloring (complete graphs, Petersen graph, bipartite graphs).

Lec 26, 10/23 Fri, Sec 8.3:
Edge-coloring (color fans and Vizing's Theorem for graphs,
Anderson-Goldberg generalization of Vizing's Theorem for multigraphs),
brief mention of perfect graphs (chordal graphs, PGT).

Lec 27, 10/26 Mon, Sec 9.1:
Planar graphs and their duals, cycles vs bonds, bipartite plane graphs,
Euler's Formula and edge bound, brief application to regular polyhedra, skipped
outerplanar graphs

Lec 28, 10/28 Wed, Sec 9.2:
Kuratowski's Theorem and convex embeddings, 6-coloring of planar graphs

Lec 29, 10/30 Fri, Sec 9.3:
Coloring of planar graphs (5-choosability, Kempe), Discharging (approach to
4CT, planar graphs with forbidden face lengths),
Tait's Theorem (skipped Grinberg's Theorem)

Lec 30, 11/2 Mon, Sec 10.1:
Applications of pigeonhole principle (covering by bipartite graphs,
divisible pairs, domino tilings, paths in cubes, monotone sublists, increasing
trails, girth 6 with high chromatic number).

Lec 31, 11/4 Wed, Sec 10.2:
Ramsey's Theorem and applications (convex m-gons, table storage).

Lec 32, 11/6 Fri, Sec 10.3:
Ramsey numbers, graph Ramsey theory (tree vs complete graph),
Schur's Theorem, Van der Waerden Theorem (statement and example)

Lec 33, 11/9 Mon, Sec 12.1:
Partially ordered sets (definitions and examples, comparability graphs and
cover graphs), Dilworth's Theorem, equivalence of Dilworth and Konig-Egervary,
relation to PGT.

Lec 34, 11/11 Wed, Sec 12.2:
graded posets & Sperner property, symmetric chain decompositions for subsets
and products, bracketing decomposition, application to monotone Boolean
functions.

Lec 35, 11/13 Fri, Sec 12.2:
LYM posets (Sperner's Theorem via LYM, equivalence with regular covering and
normalized matching, LYM and symmetric unimodal rank-sizes => symmetric chain
decomposition, statement of log-concavity & product result).

Lec 36, 11/16 Mon, 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, pebbling in hypercubes)

Lec 37, 11/18 Wed, Sec 14.2:
Crossing number (expectation application), Deletion method (Ramsey numbers,
dominating sets, large girth and chromatic number)

Lec 38, 11/20 Fri, Sec 14.2-3:
Symmetric Local Lemma & applications (Ramsey number, list coloring, Mutual
Independence Principle). Random graph models, almost-always properties,
connectedness for constant *p*, Markov's Inequality.

Lec 39, 11/30 Mon, Sec 14.3:
Second moment method, threshold functions for disappearance of
isolated vertices and appearance of balanced graphs, comments on evolution
of graphs, comments on connectivity/cliques/coloring of random graphs.

Lec 40, 12/2 Wed, Sec 13.1:
Latin squares (4-by-4 example, MOLS(n,k), upper bound, complete families,
Moore-MacNeish construction). Block designs (examples, elementary constraints
on parameters, Fisher's Inequality).

Lec 41, 12/4 Fri, Sec 13.1:
Symmetric designs (Bose), necessary conditions (example of Bruck-Chowla-Ryser),
Hadamard matrices (restriction on order, relation to designs, relation to
coding theory).

Lec 42, 12/7 Mon, Sec 13.2:
Projective planes (equivalence with (q^2+q+1,q+1,1)-designs, relation to Latin
squares, polarity graph with application to extremal problems).

Lec 43, 12/9 Wed, Sec 13.2-3:
difference sets and multipliers, Steiner triple systems.