MATH 583

ORDER AND OPTIMIZATION, 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 2006, so that can be used as a rough guide to upcoming material.

Lec 1, 8/24 Mon, Sec 11.1: Course overview, Dilworth's Theorem, Gallai-Milgram Theorem.
Lec 2, 8/26 Wed, Sec 11.1: saturated chain partitions, set-up for Greene-Kleitman Theorem.
Lec 3, 8/28 Fri, Sec 11.1: proof of Greene-Kleitman Theorem, skipped polyunsaturated posets.

Lec 4, 8/31 Mon, Sec 11.1-2: k-cofamilies, Berge optimal path partitions, semiantichain conjecture, LYM Inequality, reminder of characterization of LYM orders, partition lattice.
Lec 5, 9/02 Wed, Sec 11.2: weighted LYM inequality and strong Sperner property, LYM for products, Bollobas generalization of LYM, application to disjoint chains of subsets

Lec 6, 9/04 Fri, Sec 11.3: Symmetric chain orders (products), bracketing for multisets, reminder of counting monotone Boolean functions, orthogonal chain decompositions with probability application, (skipped) 2-part Sperner property, open problem for M(n).
Lec 7, 9/09 Wed, Sec 11.3: symmetric chains for L(3,n), comment on symmetric chains for LYM orders, strong Hall condition.
Lec 8, 9/11 Fri, Sec 11.3-11.4: symmetric chains for locally self-dual posets, examples of lattices, sublattices, elementary lattice properties.

Lec 9, 9/14 Mon, Sec 11.4: Distributive lattices, characterization by join-irreducibles.
Lec 10, 9/16 Wed, Sec 11.4: Characterizations of distributive and modular lattices.

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

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

Lec 15, 9/28 Mon, Sec 12.2: Dimension of posets (examples, characterizations, 2-dimensional posets) Alternating cycles, unforced pairs
Lec 16, 9/30 Wed, Sec 12.2: one-point removal, Hiraguchi theorems, four-point removal.
Lec 17, 10/2 Fri, Sec 12.2: Dimension of products, compositions, semiorders, interval orders; interval dimension.

Lec 18, 10/5 Mon, Sec 12.3: Dimension of generalized crowns, bipartite posets (suitable sets), dn(1,k) (Dushnik's Theorem).
Lec 19, 10/7 Wed, Sec 12.3: Furedi-Kahn bound for dn(1,k), k-scrambling sets, dn(1,2)
Lec 20, 10/9 Fri, Sec 12.3: Four-problem answer (lg lg n + (1/2) lg lg lg n), shift graph and double shift graph, dimension of planar posets (very brief mention only).

Lec 21, 10/12 Mon, Sec 12.3-4: Containment posets (circle orders, angle orders), Alon-Scheinerman Theorem), correlation (Chebyshev's Inequality)
Lec 22, 10/14 Wed, Sec 12.4: Kleitman's Inequality, FKG Inequality, Four Function Inequality.
Lec 23, 10/16 Fri, Sec 12.4: XYZ Inequality, expected height.
Lec 24, 10/19 Mon, Sec 12.5: δ-balanced comparisons (Linial for width 2, idea of Kahn-Linial for general width), Aigner on second largest element (details on Aigner and idea of poset searching postponed to next lecture.)

Lec 25, 10/21 Wed, Sec 13.1: intersecting families, Erdos-Ko-Rado Theorem for t=1 and Bollobas extension, general Erdos-Ko-Rado Theorem (sketch).
Lec 26, 10/23 Fri, Sec 13.1: colex ordering and Kruskal-Katona Theorem, cross-intersecting families (details and mention of S-intersecting families postponed, RayChaudhuri-Wilson Theorem skipped).
Lec 27, 10/26 Mon, Sec 13.1: Berge Lemma for partitioning ideals, Chvatal's Conjecture (Snevily's Theorem),

Lec 28, 10/28 Wed, Sec 13.2: on-line antichain partitioning (algorithm & lower bound), on-line chain partitioning (width 2 algorithm, sketch for larger width postponed).
Lec 29, 10/30 Fri, Sec 13.2: (was postponed to after next two lectures) on-line chain partitioning (width 2 lower bd, comment on interval orders) [continued with cutsets/fibres]
Lec 30, 11/2 Mon, Sec 13.3: linear discrepancy (bounds for interval orders, width 2, chain products)
Lec 31, 11/4 Wed, Sec 13.3: linear discrepancy (arbitary extension, product of two chains), cutsets/fibres (examples, antichain hypergraph is 3-colorable), width of cutset in subset lattice (brief mention)

Lec 32, 11/6 Fri, Sec 15.1: Hereditary systems, matroid examples, basic axiomatics (augmentation, exchange, absorption, uniformity)
Lec 33, 11/9 Mon, Sec 15.1: Matroid axiomatics (submodularity, elimination, dual base exchange, greedy algorithm)
Lec 34, 11/11 Wed, Sec 15.1: span function of hereditary systems, dual matroids (cocircuits and bonds)
Lec 35, 11/13 Fri, Sec 15.1: Minors, Whitney's planarity criterion.

Lec 36, 11/16 Mon, Sec 15.2: Matroid Intersection Theorem, Konig-Egervay and CSDR applications.
Lec 37, 11/18 Wed, Sec 15.2: Matroid Union Theorem and applications (covering/packing proved, Shannon switching game stated), skipped Matroid intersection algorithm.

Lec 38, 11/20 Fri, Sec 15.3: Statement of matroid parity problem (skipped polymatroids and polymatroidal network flow), Connected matroids (skipped Whitney's 2-Isomorphism Theorem).
Lec 39, 11/30 Mon, Sec 15.3: Gammoids, Linkage Lemma, duality between Konig and Menger Theorems.
Lec 40, 12/2 Wed, Sec 15.3: Duals of linear matroids, characterization of binary matroids.

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