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
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,
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)