MATH 580 / CS 571

COMBINATORIAL MATHEMATICS, Fall 2008

Summary of Lectures

This page contains a summary of the lectures in this course for Fall 2008. It lists only the topics discussed in each lecture. The text provides extensive discussion and additional material, so no additional notes are provided here.

Lec 1, 8/25 Mon, Sec 1.1: Course overview, general principles of enumeration, counting of words & subsets, binomial theorem, multisets/compositions.
Lec 2, 8/27 Wed, Sec 1.2: Lattice paths, basic identities, extended binomial coefficient, summing polynomials, Delannoy numbers.
Lec 3, 8/29 Fri, Sec 1.3: Hamming ball/Delannoy correspondence. Counting graphs and trees, multinomial coefficients (trees by degrees, Fermat's Little Theorem), Ballot problem.
Lec 4, 9/3 Wed, Sec 1.3-2.1: Central binomial convolution, Catalan numbers (generalization, bijections, recurrence), Fibonacci numbers and 1,2-lists.

Lec 5, 9/5 Fri, Sec 2.1-2: Derangements, recurrences in two indices (distribution problems, Delannoy numbers), characteristic equation method (through repeated roots).
Lec 6, 9/8 Mon, Sec 2.2: Characteristic equation method (inhomogeneous terms), generating function method (linear w. constant coefficients, Catalan solution).
Lec 7, 9/10 Wed, Sec 2.3-3.1: Substitution method (Tower of Hanoi, derangements, Stirling's approximation), generating functions (sum/product operations, multisets)

Lec 8, 9/12 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/15 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.
Lec 10, 9/17 Wed, Sec 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/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/22 Mon, Sec 3.4: Partitions of integers (basic generating functions, asymptotic number of partitions), combinatorics of partitions (Ferrers diagrams, conjugation, Fallon's Identity (skipped), congruence classes of triangles, Euler's Identity).

Lec 13, 9/24 Wed, Sec 4.1: Basic inclusion-exclusion formula, applications (totients, Stirling numbers, alternating sums, skipped Eulerian numbers)
Lec 14, 9/26 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, (skipped partitions into distinct odd parts).
Lec 15, 9/29 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.
Lec 16, 10/1 Wed, Sec 4.2-3: 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).

Chapter 5, First Concepts for Graphs, for background reading
Lec 17, 10/3 Fri, 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/6 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/8 Wed, Sec 6.2: General Matching: augmenting paths, 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--postponed to Friday).

Lec 20, 10/10 Fri, Sec 7.1: Connectivity (definitions, Harary graphs). Connectivity under cartesian product, edge-connectivity definitions, Whitney's Theorem. Edge-connectivity for diameter 2 (mention of edge-cut/degree lemma postponed), ....bonds and blocks skipped.
Lec 21, 10/13 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 (postponed), Expansion and Fan Lemmas, cycles through specified vertices), ear decomposition and Robbins' Theorem (postponed to Wed).
Lec 22, 10/15 Wed, Sec 7.3: Spanning cycles: necessary condition, Ore & Dirac conditions, closure, statement of Chvatal condition & Chvatal-Erdos Theorem (postponed to Fri).

Lec 23, 10/17 Fri, Sec 8.1: Vertex coloring: examples, easy bounds, greedy coloring, interval graphs, degree bounds, Minty's Theorem (postponed to Mon).
Lec 24, 10/20 Mon, 8.1-2: Triangle-free graphs (Mycielski's construction, √n bound), color-critical graphs (minimum degree, edge-connectivity).
Lec 25, 10/22 Wed, Sec 8.2: coloring triangle-free graphs. List coloring (degree choosability and extension of Brooks' Theorem),
Lec 26, 10/24 Fri, Sec 8.3: edge-coloring (complete graphs, Petersen graph, bipartite graphs), color fans and Vizing for graphs, Anderson-Goldberg generalization of Vizing's Theorem (skipped), brief mention of perfect graphs.

Lec 27, 10/27 Mon, Sec 9.1: Planar graphs and their duals, cycles vs bonds, bipartite plane graphs, Euler's Formula and edge bound
Lec 28, 10/29 Wed, Sec 9.2: Kuratowski's Theorem and convex embeddings, 5-coloring of planar graphs
Lec 29, 10/31 Fri, Sec 9.3: Discharging (approach to 4CT, planar graphs with forbidden face lengths), mention of Tait's Theorem (skipped Grinberg's Theorem)

Lec 30, 11/3 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/5 Wed, Sec 10.2: Ramsey's Theorem and applications (convex m-gons, table storage).
Lec 32, 11/7 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/10 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/12 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/14 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/17 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/19 Wed, Sec 14.2: Deletion method (Ramsey numbers, dominating sets, sketch for large girth and chromatic number)
Lec 38, 11/21 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.
Lec 39, 12/1 Mon, Sec 14.3: Second moment method, threshold functions for disappearance of isolated vertices and appearance of balanced graphs, comments on evolution of graphs, lower bound for crossing number of graphs (Chapter 16).

Lec 40, 12/3 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/5 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/8 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/10 Wed, Sec 13.2-3: difference sets and multipliers, Steiner triple systems.