Lec 1, 8/22 Wed, Sec 1.1:
Course overview, general principles of enumeration, counting of words & subsets,
binomial theorem, multisets/compositions.
Lec 2, 8/24 Fri, Sec 1.2:
Lattice paths, basic identities, extended binomial coefficient,
summing polynomials, Delannoy numbers.
Lec 3, 8/27 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/29 Wed, Sec 1.3-2.1:
Catalan numbers (generalization, bijections, recurrence),
Fibonacci numbers and 1,2-lists, derangements.
Lec 5, 8/31 Fri, Sec 2.1-2:
recurrences in two indices (distribution problems, Delannoy numbers),
characteristic equation method (through repeated roots).
Lec 6, 9/5 Wed, Sec 2.2:
Characteristic equation method (inhomogeneous terms),
generating function method (linear constant coefficients, Catalan solution).
Lec 7, 9/7 Fri, Sec 2.3-3.1:
Substitution method (Tower of Hanoi, derangements, Stirling's approximation),
generating functions (sum/product operations, multisets, restricted
multiplicity).
Lec 8, 9/10 Mon, Sec 3.1:
Generating functions in two variables (subsets), permutation statistics (OGFs
by #inversions, #cycles), Eulerian numbers (#runs, Worpitzky's Identity by
barred permutations, A(n,k) formula by inversion).
Lec 9, 9/12 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/14 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/17 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/19 Wed, Sec 3.4:
Asymptotic number of partitions,
Combinatorics of partitions (Ferrers diagrams, conjugation, Fallon's Identity,
classes of triangles, Euler's Identity). [Start of PIE: basic formula]
Lec 13, 9/21 Fri, Sec 4.1:
Inclusion-exclusion applications (totients,
Stirling numbers, derangements, Eulerian numbers)
Lec 14, 9/24 Mon, Sec 4.1:
PIE to prove identities, Permutations
with restricted positions (rook polynomials), OGF by number of
properties.
Signed involutions (inclusion-exclusion as special case)
.
Lec 15, 9/26 Wed, 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/28 Fri, Sec 4.2-3:
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).
Chapter 5, First Concepts for Graphs, for background reading
Lec 17, 10/1 Mon, Sec 5.1-3 highlights, 6.1:
Properties of Petersen graph, degree-sum formula and rectangle partition,
characterization of bipartite graphs, Eulerian circuits.
Bipartite Matching (Hall's Theorem).
Lec 18, 10/3 Wed, Sec 6.1-2:
Marriage Theorem, orientations with specified outdegrees.
Min/max relations (Ore's defect formula, Konig-Egervary Theorem,
Gallai's Theorem, Konig's Other Theorem).
General Matching (augmenting paths).
Lec 19, 10/5 Fri, Sec 6.2:
Tutte's 1-Factor Condition, Berge-Tutte Formula.
1-factors in regular graphs,
Petersen's 2-Factor Theorem (via Eulerian circuit and Hall's Theorem),
reduction of f-factor to 1-factor in blowup),
Lec 20, 10/8 Mon, Sec 7.1:
Connectivity (definitions, Harary graphs).
Connectivity under cartesian product, edge-connectivity definitions, Whitney's
Theorem.
Edge-connectivity for diameter 2 (Plesnik, postponed), ....bonds and blocks
skipped.
Lec 21, 10/11 Wed, 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 (postponed),
Expansion and Fan Lemmas, cycles through specified vertices), ear decomposition
and Robbins' Theorem (postponed to Fri).
Lec 22, 10/12 Fri, Sec 7.3:
Spanning cycles: necessary condition, Thomason's lollipop,
Ore & Dirac conditions, closure,
skipped statement of Chvatal condition & Chvatal example,
postponed Chvatal-Erdos Theorem.
Lec 23, 10/15 Mon, Sec 8.1:
Vertex coloring: examples, easy bounds, greedy coloring, interval graphs,
degree bounds, Minty Theorem.
Lec 24, 10/17 Wed, Sec 8.1-2:
Triangle-free graphs & Mycielski's construction,
color-critical graphs (minimum degree, edge-connectivity),
list coloring (examples).
Lec 25, 10/19 Fri, Sec 8.2-3:
List coloring (degree choosability and extension of Brooks' Theorem),
edge-coloring (complete graphs, Petersen graph, bipartite graphs),
color fans and Vizing for graphs, skipped
Anderson-Goldberg generalization of Vizing's Theorem.
Lec 26, 10/22 Mon, Sec 9.1:
Planar graphs and their duals, cycles vs bonds, bipartite plane graphs,
Euler's Formula and edge bound,
skipped regular polyhedra
Lec 27, 10/24 Wed, Sec 9.2:
Kuratowski's Theorem and convex embeddings, 5-coloring of planar graphs
Lec 28, 10/26 Fri, Sec 9.3:
Coloring of planar graphs (5-choosability, Kempe),
discharging (approach to 4CT, list edge-coloring of planar graphs),
Tait's Theorem (skipped Grinberg's Theorem)
Lec 29, 10/29 Mon, Sec 10.1:
Applications of pigeonhole principle (divisible pairs, paths in cubes,
domino tilings, monotone sublists, increasing trails).
Lec 30, 10/31 Wed, Sec 10.2:
Ramsey's Theorem and applications (convex m-gons, table storage).
Lec 31, 11/2 Fri, Sec 10.3:
Ramsey numbers, graph Ramsey theory (tree vs complete graph),
Schur's Theorem, Van der Waerden Theorem (statement and example)
Lec 32, 11/5 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 (postponed).
Lec 33, 11/7 Wed, Sec 12.2:
graded posets & Sperner property, symmetric chain decompositions for subsets
and products, bracketing decomposition, application to monotone Boolean
functions.
Lec 34, 11/9 Fri, 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, CSDR from Menger, statement of log-concavity & product result).
Lec 35, 11/12 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, postponed pebbling in hypercubes).
Lec 36, 11/14 Wed, Sec 14.2:
Deletion method (Ramsey numbers, dominating sets, sketch for large girth and
chromatic number)
.
Lec 37, 11/16 Fri, Sec 14.2-3:
Symmetric Local Lemma & applications (Ramsey number, list coloring, Mutual
Independence Principle). Random graph models, almost-always properties,
connectedness of the random graph.
Markov's Inequality and connectedness, notion of threshold function.
Lec 38, 11/26 Mon, Sec 14.3:
Random graphs (Second moment method, threshold functions for disappearance of
isolated vertices and appearance of balanced graphs, comments on evolution
of graphs).
Lec 39, 11/28 Wed, Sec 14.3:
connectivity/cliques/coloring of random graphs;
lower bound for crossing number of graphs (Chapter 16).
Introduction to orthogonal families of Latin squares (4-by-4 example,
upper bound).
Lec 40, 11/30 Fri, Sec 17.1:
Latin squares (MOLS(n,k), complete families, Moore-MacNeish construction),
block designs (examples, elementary constraints on parameters,
Fisher's Inequality).
Lec 41, 12/03 Mon, Sec 17.1-2:
Symmetric designs (Bose), necessary conditions (example of Bruck-Chowla-Ryser),
Hadamard matrices (restriction on order, skipped relation to
designs and application to bipartite Ramsey problem).
Equivalence of projective planes and (q^2+q+1,q+1,1)-designs.
Lec 42, 12/05 Wed, Sec 17.2:
projective planes (relation to Latin squares, polarity graph with application
to extremal problems).
Lec 43, 12/07 Fri, Sec 17.2-3:
difference sets and multipliers, Steiner triple systems.
!-->