MATH 583

ORDER AND OPTIMIZATION, Fall 2006

Summary of Lectures

This page contains a summary of the lectures in this course for Fall 2006. 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 2004, so that can be used as a rough guide to upcoming material. However, the material previously discussed on linear and integer programming has moved to Math 588, which will leave more time for the other chapters in this course.

Lec 1, 8/23 Wed, Sec 11.1: Course overview, Dilworth's Theorem, Gallai-Milgram Theorem.
Lec 2, 8/25 Fri, Sec 11.1: Greene-Kleitman Theorem (ideas of proof, related conjectures postponed to Lec 3).

Lec 3, 8/28 Mon, Sec 11.2: Berge optimal path partitions, semiantichain conjecture, polyunsaturated posets (from 11.1), LYM Inequality, characterization of LYM orders.
Lec 4, 8/30 Wed, Sec 11.2: Subspace lattice, partition lattice, weighted version of LYM inequality, LYM for products.

Lec 5, 9/1 Fri, Sec 11.3: Bollobas generalization of LYM, application to disjoint chains of subsets (from 11.2). Symmetric chain orders (products), bracketing for multisets, reminder of counting monotone Boolean functions, Orthogonal chain decompositions with probability application, 2-part Sperner property.
Lec 6, 9/6 Wed, Sec 11.3: L(3,n), comment on symmetric chains for LYM orders, strong Hall condition.
Lec 7, 9/8 Fri, Sec 11.3-11.4: symmetric chains for locally self-dual posets, examples of lattices, sublattices, elementary lattice properties.

Lec 8, 9/11 Mon, Sec 11.4: Distributive lattices, characterization by join-irreducibles.
Lec 9, 9/13 Wed, Sec 11.4: Characterizations of distributive and modular lattices.

Lec 10, 9/15 Fri, Sec 11.5: Comparability graphs (G-H Theorem).
Lec 11, 9/18 Mon, Sec 11.5: Edge-classes and knotting graph, modular decomposition tree, incomparability graphs, k-asteroids (cover graphs skipped).

Lec 12, 9/20 Wed, Sec 12.1: Rankings, voting paradoxes, Arrow's Theorem, median rankings.
Lec 13, 9/22 Fri, Sec 12.1: Characterization of semiorders, interval orders, and Ferrers digraphs (biorders).

Lec 14, 9/25 Mon, Sec 12.2: Dimension of posets (examples, characterizations, 2-dimensional posets)
Lec 15, 9/27 Wed, Sec 12.2: Alternating cycles, unforced pairs, one-point removal, Hiraguchi theorems, brief treatment of four-point removal.
Lec 16, 9/29 Fri, Sec 12.2: Dimension of products, compositions, semiorders, interval orders; interval and Ferrers dimension.

Lec 17, 10/2 Mon, Sec 12.3: Dimension of generalized crowns, bipartite posets (suitable sets), dn(1,k) (Dushnik, Furedi-Kahn).
Lec 18, 10/4 Wed, Sec 12.3: k-scrambling sets, dn(1,2), four problems with answer lg lg n + (1/2) lg lg lg n,
Lec 19, 10/6 Fri, Sec 12.3: shift graph and double shift graph, planar posets with large dimension, Dimension of planar posets with upper bounds,
Lec 20, 10/9 Mon, Sec 12.3-4: Containment posets (circle orders, angle orders), Alon-Scheinerman Theorem), correlation (Chebyshev's Inequality, Kleitman's Inequality).

Lec 21, 10/11 Wed, Sec 12.4: FKG Inequality, Four Function Inequality).
Lec 22, 10/16 Mon, Sec 12.4: XYZ Inequality, expected height.
Lec 23, 10/18 Wed, Sec 12.5: balanced comparisons (Linial for width 2, brief idea of Kahn-Linial for general width), producing posets (second largest element).

Lec 24, 10/20 Fri, Sec 13.1: intersecting families, Erdos-Ko-Rado Theorem for t=1. general Erdos-Ko-Rado Theorem (sketch), colex ordering.
Lec 25, 10/23 Mon, Sec 13.1: Kruskal-Katona Theorem, cross-intersecting families, S-intersecting families (intro).
Lec 26, 10/25 Wed, Sec 13.1: RayChaudhuri-Wilson Theorem, Berge Lemma for partitioning ideals, Chvatal's Conjecture (Snevily's Theorem),

Lec 27, 10/26 Thu, Sec 13.2: on-line antichain partitioning (algorithm & lower bound), on-line chain partitioning (width 2 algorithm, sketch for larger width).
Lec 28, 10/27 Fri, Sec 13.2-3: on-line chain partitioning (width 2 lower bd, upper bound for bounded dimension), cutsets/fibres (antichain hypergraph is 3-colorable).

Lec 29, 10/30 Fri, Sec 13.3-14.1: cutset of small width in 2n, regressions, LP duality, Farkas Lemma.
Lec 30, 11/1 Wed, Sec 14.1: LP bound on pancake problem, application of Farkas to Dean's Conjecture (Seymour second neighborhood conj for tournaments).

Lec 31, 11/3 Fri, Sec 15.1: Matroid examples and basic axiomatics.
Lec 32, 11/6 Mon, Sec 15.1: Dual base exchange, greedy algorithm, axiomatics of span function.
Lec 33, 11/8 Wed, Sec 15.1: Duality (cocircuits and bonds), minors, start Whitney's planarity criterion.

Lec 34, 11/10 Fri, Sec 15.1-2: Rank of dual matroid, finish Whitney, Matroid Intersection Theorem.
Lec 35, 11/13 Mon, Sec 15.2: Rank of transversal matroids, CSDR from MIT, Matroid Union Theorem.
Lec 36, 11/15 Wed, Sec 15.2: Matroid Union applications, matroid parity problem.
Lec 37, 11/17 Fri, Sec 15.2: Polymatroids (max independent set is hard), polymatroidal network flow.

Lec 38, 11/27 Mon, Sec 15.3: Connected matroids, discussion of Whitney's 2-Isomorphism Theorem.
Lec 39, 11/29 Wed, Sec 15.3: Gammoids, Linkage Lemma, duality between Konig and Menger Theorems.
Lec 40, 12/1 Fri, Sec 15.3: Duals of linear matroids, characterization of binary matroids.

Lec 41, 12/4 Mon, Sec 15.4: Lattices and matroids (closed sets, geometric, semimodular)
Lec 42, 12/6 Wed, Sec 15.4: Convexity and antimatroids (convex geometry, shelling, rooted circuits)
Lec 43, 12/8 Fri, Sec 15.4: Greedoids (languages, branching greedoid, interval properties, diameter of basis graph)