MATH 580 / CS 571

COMBINATORIAL MATHEMATICS, Fall 2009

Summary of Lectures

This page contains a summary of the lectures in this course for Fall 2009. It lists only the topics discussed in each lecture. The text provides extensive discussion and additional material, so no additional notes are provided here. The order and coverage of topics is similar to Fall 2008, so that can be used as a rough guide to upcoming material.

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.