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