Lec 1, 8/23 Mon, Sec 1.1:
Course details, general principles of enumeration, counting of words & subsets,
binomial theorem, multisets/compositions.
Lec 2, 8/25 Wed, Sec 1.2: Lattice paths, basic identities, extended binomial coefficient, summing polynomials, Delannoy numbers, taxi ball/Delannoy correspondence.
Lec 3, 8/27 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/30 Mon, Sec 1.3-2.1: Catalan numbers (generalization, bijections, recurrence), Fibonacci numbers and 1,2-lists, derangements.
Lec 5, 9/1 Wed, Sec 2.1-2:
Recurrences in two indices (distribution problems, Delannoy numbers),
characteristic equation method (through repeated roots).
Lec 6, 9/3 Fri, Sec 2.2: Characteristic equation method (inhomogeneous terms), generating function method (linear w. constant coefficients, relation to char.eqn. method), Catalan solution (by email).
Lec 7, 9/8 Wed, Sec 2.3-3.1: substitution method (factorials, derangements, Stirling's approximation), generating functions (sum/product operations, multisets), multisets with restricted multiplicity.
Lec 8, 9/10 Fri, Sec 3.1:
Generating functions: (functions in two variables - skipped), permutation
statistics (by #inversions, #cycles), Eulerian numbers (#runs, Worpitzky's
Identity by barred permutations, A(n,k) formula by inversion from
Lec 9, 9/13 Mon, Sec 3.2: Generating function manipulations: sum & product (review inversion), shifted index, differentiation & evaluation at special values, summing initial coefficients, summation by convolutions.
Lec 10, 9/15 Wed, Sec 3.2-3.3: Snake Oil, exponential generating functions: products of EGFs (words), examples and applications of EGFs (flags on poles, restricted words, Stirling numbers)
Lec 11, 9/17 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/20 Mon, Sec 3.4: Partitions of integers (basic generating functions, bounds on coefficients). combinatorics of partitions (Ferrers diagrams, conjugate, Fallon's Identity, congruence classes of triangles, Euler's Identity).
Lec 13, 9/22 Wed, Sec 4.1:
Basic inclusion-exclusion formula (marbles with restricted multiplicity first),
applications (totients, Stirling numbers, alternating sums, hint at PIE for
Lec 14, 9/24 Fri, Sec 4.1: Permutations with restricted positions (rook polynomials), OGF by number of properties (#fixed points, problème des ménages), 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 Cauchy-Benet (brief mention), 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/1 Fri, Sec 5.1-3, Sec 6.1:
Properties of Petersen graph, degree-sum formula and rectangle partition,
characterization of bipartite graphs, Eulerian circuits (highlights only,
Chapter 5 for background reading). Bipartite Matching (Hall's Theorem).
Lec 18, 10/4 Mon, Sec 6.1: Orientations with specified outdegrees, Marriage Theorem. Min/max relations (Ore's defect formula, Konig-Egervary Theorem, Gallai's Theorem, Konig's Other Theorem).
Lec 19, 10/6 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 (left for email), reduction of f-factor to 1-factor in blowup (skipped)
Lec 20, 10/8 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/11 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/13 Wed, Sec 7.2-3: Ford-Fulkerson CSDR, ear decomposition and Robbins' Theorem. Spanning cycles: necessary condition, Ore & Dirac conditions, closure,
Lec 23, 10/15 Fri, Sec 7.3-8.1: Chvatal's Theorem (proof sketched), Chvatal-Erdos Theorem, comments on Fan's Theorem, regularity, long-cycle versions. Vertex coloring: examples, easy bounds, greedy coloring, interval graphs, degree bounds.
Lec 24, 10/18 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/20 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/22 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/25 Mon, Sec 9.1:
Planar graphs and their duals, cycles vs bonds, bipartite plane graphs,
Euler's Formula and edge bound, application to regular polyhedra,
outerplanar graphs (brief comments)
Lec 28, 10/27 Wed, Sec 9.2: Kuratowski's Theorem and convex embeddings, 5-coloring of planar graphs
Lec 29, 10/29 Fri, Sec 9.3: Coloring of planar graphs (5-choosability, Kempe), Discharging (light subgraphs, comments on 4CT, dynamic coloring), Tait's Theorem (comments only), (skipped Grinberg's Theorem)
Lec 30, 11/1 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/3 Wed, Sec 10.2: Ramsey's Theorem and applications (convex m-gons, table storage).
Lec 32, 11/5 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/8 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/10 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/12 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/15 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/17 Wed, Sec 14.2: Crossing number (expectation application), Deletion method (Ramsey numbers, dominating sets, large girth and chromatic number), motivation for Local Lemma
Lec 38, 11/19 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/29 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/1 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/3 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/6 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/8 Wed, Sec 13.2-3: difference sets and multipliers, Steiner triple systems.