MATH 583

ORDER AND OPTIMIZATION, Fall 2004

Summary of Lectures

This page contains a summary of the lectures in this course for Fall 2004. 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 Wed, Sec 11.1: Course overview, Dilworth's Theorem, Gallai-Milgram Theorem.
Lec 2, 8/27 Fri, Sec 11.1: Greene-Kleitman Theorem (proof sketch and related conjectures).

Lec 3, 8/30 Mon, Sec 11.2: LYM Inequality, characterization of LYM orders, subspace lattice, partition lattice.
Lec 4, 9/1 Wed, Sec 11.2: Strong versions of LYM inequality, LYM for products, Bollobas Inequality.

Lec 5, 9/3 Fri, Sec 11.3: Symmetric chain orders, bracketing, counting monotone Boolean functions, universal subset list.
Lec 6, 9/8 Wed, Sec 11.3: Orthogonal chain decompositions, L(3,n), symmetric chains for LYM orders.
Lec 7, 9/10 Fri, Sec 11.3-11.4: Strong Hall condition, symmetric chains for locally self-dual posets, examples of lattices, sublattices.

Lec 8, 9/13 Mon, Sec 11.4: Elementary lattice properties, properties of distributive lattices.
Lec 9, 9/15 Wed, Sec 11.4: Characterizations of distributive and modular lattices.
Lec 10, 9/17 Fri, Sec 11.5: Comparability graphs, modular decomposition tree.

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

Lec 13, 9/24 Fri, Sec 12.2: Dimension of posets (examples, characterizations, 2-dimensional posets, computational aspects).
Lec 14, 9/27 Mon, Sec 12.2: Bounds and removal theorems for posets (Hiraguchi theorems, removal of one point / two chains / four points, dimension of products).
Lec 15, 9/29 Wed, Sec 12.2-3: Interval and Ferrers dimension, generalized crowns.

Lec 16, 10/1 Fri, Sec 12.3: Dimension of bipartite posets (suitable sets) dn(1,k) (Dushnik, Furedi-Kahn), planar posets with large dimension.
Lec 17, 10/4 Mon, Sec 12.3: Dimension of planar posets with upper bounds, relations among dimension of singletons/doubletons (Spencer's bound) and universal interval orders and double shift graph and antichains in 2[n].
Lec 18, 10/6 Wed, Sec 12.3: containment posets (circle orders, angle orders), Alon-Scheinerman Theorem.

Lec 19, 10/8 Fri, Sec 12.4: Correlational inequalities (Kleitman's Inequality, FKG Inequality, Four Function Inequality).
Lec 20, 10/11 Mon, Sec 12.4: XYZ Inequality, expected height.
Lec 21, 10/13 Wed, Sec 12.4: balanced comparisons (Linial for width 2, Kahn-Linial for general width).
Lec 22, 10/15 Fri, Sec 12.5-13.1: central elements & searching, second largest element, intersecting families, Erdos-Ko-Rado Theorem for t=1.

Lec 23, 10/18 Mon, Sec 13.1: general Erdos-Ko-Rado Theorem (sketch), Kruskal-Katona Theorem.
Lec 24, 10/20 Wed, Sec 13.1: cross-intersecting families, S-intersecting families (Ray-Chaudhuri-Wilson Theorem).
Lec 25, 10/22 Fri, Sec 13.1-2: Berge Lemma for partitioning ideals, Chvatal's Conjecture (Snevily's Theorem), on-line antichain partitioning (algorithm).
Lec 26, 10/25 Mon, Sec 13.2: on-line antichain partitioning (lower bound), on-line chain partitioning (width 2 proof, sketch for larger width).

Lec 27, 10/27 Wed, Sec 14.1: Linear programming duality and simplex algorithm.
Lec 28, 10/29 Fri, Sec 14.1: Shannon capacity, min-max theorem of matrix games.
Lec 29, 11/1 Mon, Sec 14.1: Tree/edge game and k-server problem.

Lec 30, 11/3 Wed, Sec 14.1-2: LP bound on pancake problem, intro to network flow.
Lec 31, 11/5 Fri, Sec 14.2: Baseball Elimination application, Baranyai's Theorem, start min-cost flow.
Lec 32, 11/8 Mon, Sec 14.2: Min-cost feasible flow (LP, algorithm), sketch of Frank's proof of Greene-Kleitman

Lec 33, 11/10 Wed, Sec 15.1: Matroid examples and basic axiomatics.
Lec 34, 11/12 Fri, Sec 15.1: Axiomatics of span function.
Lec 35, 11/15 Mon, Sec 15.1: Duality (cocircuits and bonds), minors.

Lec 36, 11/17 Wed, Sec 15.1-2: Whitney's planarity criterion, Matroid Intersection Theorem.
Lec 37, 11/19 Fri, Sec 15.2: Matroid union and applications, ideas for Matroid Intersection Algorithm.

Lec 38, 11/29 Mon, Sec 15.3: Connected matroids, Whitney's 2-isomorphism theorem.
Lec 39, 12/01 Wed, Sec 15.3: Gammoids, Menger's Theorem.
Lec 40, 12/03 Fri, Sec 15.3: Characterization of binary matroids.

Lec 41, 12/06 Mon, Sec 15.4: Brief treatment of relation to semimodular lattices.
Lec 42, 12/08 Wed, Sec 15.4: Brief treatment of antimatroids.
Lec 43, 12/10 Wed, Sec 15.4: Brief treatment of greedoids.