Math 796 (Topics in Algebraic Combinatorics), Spring 2008
Section 78865

Basic Information | Problem Sets | Lecture Notes | Final Exam / Project | Textbooks | Links

Basic Information

Problem Sets

Problem Set #1 (due Friday 2/1/08)
Problem Set #2 (due Friday 2/15/08)
Problem Set #3 (due Friday 2/29/08)
Problem Set #4 (due Friday 3/14/08)
Problem Set #5 (due Friday 4/11/08)
Problem Set #6 (due Wednesday 5/6/08)

Lecture Notes

Posets: definition and examples (1/18)
More posets; lattices (1/23)
Lattices and distributive lattices (1/25)
Birkhoff's theorem on distributive lattices (1/28)
Modular lattices (1/30)
Semimodular lattices (2/1)
Geometric lattices (2/4)
Matroids and geometric lattices; uniform and graphic matroids (2/8)
Graphic matroids; basis and independence systems (2/11)
Circuit systems; duality (2/13)
Direct sum; deletion and contraction (2/15)
The Tutte polynomial I (2/18)
The Tutte polynomial II (2/20)
The Tutte polynomial III (2/22)
The incidence algebra and the Möbius function (2/25)
Möbius inversion; the characteristic polynomial (2/27)
The Möbius algebra of a lattice, and applications (2/29)
The crosscut theorem; introduction to hyperplane arrangements (3/3)
Counting regions I: examples and deletion/restriction (3/5)
Counting regions II: Zaslavsky's theorems and finite fields (3/7)
Projectivization and coning; complex arrangements; graphic arrangements (3/10)
Modular elements in lattices; supersolvable arrangements (3/12)
The big face lattice of an arrangement (3/24)
Oriented matroids (3/26)
Maximum flows in networks (3/28)
Applications of the Max-Flow/Min-Cut Theorem; Dilworth's Theorem (3/31)
Dilworth's Theorem; perfect graphs; the Greene-Kleitman Theorem (4/2)
Counting group orbits with Polyá theory (4/4)
Representation theory: example, isomorphisms and homomorphisms (4/7)
Maschke's Theorem; characters (4/9)
Operations on characters; the scalar product on class functions (4/11)
Schur's Lemma; orthonormality; computing character tables (4/14)
Proof that the irreducible characters span; characters of abelian groups (4/16)
Characters of the symmetric group (4/18)
Restricted and induced representations (4/21)
Monomial, elementary and homogeneous symmetric functions (4/23)
Power-sum and Schur symmetric functions; proof of basishood (4/25)
The involution ω; a lot of identities; the Hall inner product (4/28)
The Robinson-Schensted-Knuth correspondence, and some consequences (4/30)
Frobenius characteristic; Murnaghan-Nakayama Rule; hook-length formula (5/2)

Also, for reference, here is a list of notation used in these notes (last updated 4/30).

Final Exam / Project

Each student enrolled in Math 796 will have the choice of taking a comprehensive final exam or doing a final project. The final project will consist of reading a research paper or book chapter and giving a short (20-25 minute) presentation to the class. The presentations will take place during the last week of classes (May 5 and 7).

According to the KU Registrar, the final exam is scheduled for Thursday May 15 from 10:30 AM - 1:00 PM, presumably in Snow 408.


All the books in the list below can be perused in Jeremy's office. The official textbook is #1 in the list below; however, you may want to substitute #3, whose material is a bit closer to what will be covered in the class. (All the homework assignments will be self-contained.) You should definitely obtain #4 and #5, which are free downloads.

  1. R.P. Stanley, Enumerative Combinatorics, volume 1 (Cambridge, 1997)
    (Enumeration; posets and lattices; generating functions)
    Amazon | Google Books
  2. R.P. Stanley, Enumerative Combinatorics, volume 2 (Cambridge, 1999)
    (More enumeration, including exponential generating functions; symmetric functions)
    Amazon | Google Books
  3. M. Aigner, Combinatorial Theory (Springer, 1997)
    (Enumeration; posets, lattices, and matroids)
    Amazon | Google Books
  4. R.P. Stanley, Hyperplane Arrangements (lecture notes available free online)
  5. A. Schrijver, A Course in Combinatorial Optimization (lecture notes available free online)
  6. T. Brylawski and J. Oxley, The Tutte polynomial and its applications, Chapter 6 of Matroid applications, N. White, ed. (Cambridge Univ. Press, 1992)
  7. B. Sagan, The Symmetric Group, 2nd edn. (Springer, 2001)


Mathematics links:

Mathematical and technical writing information:

KU links:

Outside KU:

Last updated Fri 5/2/08