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.