Math 824 (Algebraic Combinatorics)
Fall 2016

General Information | Lecture Notes | Problem Sets | Textbooks | Final Project | Links

• Instructor: Jeremy Martin
  
• E-mail: (the best way to contact me)
• Office: 618 Snow Hall, (785) 864-7114
• Office hours: Wednesdays, 3-4pm, or by appointment
• Lectures: MWF, 1:00-1:50pm, 456 Snow
• Prerequisite: Math 724 (Enumerative Combinatorics) or permission of the instructor. Math 790 (Linear Algebra) is not an official requirement but is strongly encouraged.
• KU course number: 66459
• Syllabus

Lecture Notes on Algebraic Combinatorics (one big PDF file; last update 12/7/16)

These notes are licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License. In short, use them freely but do not sell them or anything derived from them. If you are a KU graduate student (or for that matter, if you aren't), do not print out the full set of notes on the department's printer!

Lecture topics, day by day:

• Mon 8/22: Posets - basic definitions and examples
• Wed 8/22: Young's lattice; simplicial complexes
• Fri 8/24: Stanley-Reisner rings; f- and h-vectors; shellability
• Mon 8/29: Polytopes
• Wed 8/31: The fundamental theorem; the Bruggesser-Mani proof of the Dehn-Sommerville relations
• Fri 9/2: Distributive lattices
• Mon 9/5: No class (Labor Day)
• Wed 9/7: Proof of the FTFDL
• Fri 9/9: Modular lattices
• Mon 9/12: Semimodular lattices
• Wed 9/14: Geometric lattices
• Fri 9/16: Matroid closure operators and rank functions
• Mon 9/19: Graphic matroids; independence systems
• Wed 9/21: Equivalence of rank functions and independence systems; matroid complexes; basis systems
• Fri 9/23: Other matroid formulations; representability; the Fano and non-Pappus matroids
• Mon 9/26: Direct sum and duality
• Wed 9/28: Deletion and contraction
• Fri 9/30: The Tutte polynomial: examples and proof of equivalence of the closed-form and recursive formulas
• Mon 10/3: The Tutte polynomial: recipe formulas and activities
• Wed 10/5: The Tutte polynomial: colorings and orientations
• Fri 10/7: Guest lecture by Hailong Dao
• Mon 10/10: No class (Fall Break)
• Wed 10/12: The incidence algbra and the Möbius function
• Fri 10/14: Möbius inversion
• Mon 10/17: The Möbius algebra; Weisner's theorem
• Wed 10/19: The crosscut theorem; introduction to hyperplane arrangements
• Fri 10/21: Hyperplane arrangements: basic facts, examples, counting regions
• Mon 10/24: Zaslavsky's theorems
• Wed 10/26: The finite field method; supersolvable arrangements
• Fri 10/28: Guest lecture by Marge Bayer: Ehrhart theory
• Mon 10/31: Introduction to representations
• Wed 11/2: Proof of Maschke's theorem; characters and functors
• Fri 11/4: Schur's Lemma and the Fundamental Theorem of Character Theory
• Mon 11/7: Character tables; one-dimensional representations and Pontrjagin duality
• Wed 11/9: Representations of the symmetric group; restriction and induction (barely)
• Fri 11/11: Symmetric functions I (Marge Bayer)
• Mon 11/14: Symmetric functions II (Marge Bayer)
• Wed 11/16: Symmetric functions III (Marge Bayer)
• Fri 11/18: Schur functions: proof of symmetry
• Mon 11/21: The Cauchy and dual Cauchy kernels and the Hall inner product
• Wed 11/23: No class - Thanksgiving
• Fri 11/25: No class - Thanksgiving
• Mon 11/28: The Robinson-Schensted-Knuth correspondence; generalized RSK and Schur functions
• Wed 11/30: Restricted and induced representations and Frobenius reciprocity; the Frobenius characteristic map
• Fri 12/2: The hook-length formula
• Mon 12/5: Presentations (Smita and Amanda)
• Wed 12/7: The Jacobi-Trudi determinant definition of Schur functions

Problem sets will be assigned approximately biweekly, at least one week before the deadline.

All solutions must be typeset using LaTeX. E-mail me your solutions as a PDF file under the name {your-last-name}{number-of-problem-set}.pdf (e.g., "Rota5.pdf"). In general, the deadline is 11:59pm of the due date.

• Problem Set 1, due Tuesday 9/6
• Problem Set 2, due Friday 9/16
• Problem Set 3, due Monday 10/3: Exercises 3.1, 3.2, 3.6, 3.7, 3.8, and at least one of 3.9 and 3.10
• Problem Set 4, due Friday 10/21: Exercises 4.3, 4.4, 5.1, 5.2
• Problem Set 5, due Friday 11/11: Exercises 5.3, 5.6, 6.2, 6.3, 8.1, 8.2
• Problem Set 6, due Thursday 12/8: Exercises 8.3, 8.4, 9.2, 9.4, 9.5, and at least one of 8.6 or 9.3

Additional resources:

• Here is a header file with useful macros (last update 8/26/16).
• Here is a sample source file that uses the header (and will produce the first couple of pages of the lecture notes).
• Packages for making figures include TikZ, Ipe, and xfig.

We will follow the lecture notes rather than any one specific textbook. However, the following books may be helpful (and you should definitely obtain the free downloads). All these books can be perused in Jeremy's office.

1. Richard P. Stanley, Enumerative Combinatorics, volume 1, 2nd ed. (Cambridge, 1997)
   (Enumeration; posets and lattices; generating functions)
   Buy it from the publisher or download the free preprint version from Stanley's website
2. Richard P. Stanley, Enumerative Combinatorics, volume 2 (Cambridge, 1999)
   (More enumeration, including exponential generating functions; symmetric functions)
   Buy it from the publisher
3. Martin Aigner, A Course in Enumeration (Springer, 2007)
   (Enumeration; posets, lattices, and matroids)
   
4. Martin Aigner, Combinatorial Theory (Springer, 1997)
   (Enumerative combinatorics, symmetric functions, and matroids)
   
5. Richard P. Stanley, Hyperplane Arrangements (lecture notes available free online)
6. Alexander Schrijver, A Course in Combinatorial Optimization (lecture notes available free online)
7. Thomas Brylawski and James Oxley, The Tutte polynomial and its applications, Chapter 6 of Matroid applications, N. White, ed. (Cambridge Univ. Press, 1992)
8. Matthias Beck and Raman Sanyal, Combinatorial Reciprocity Theorems: A Snapshot of Enumerative Combinatorics from a Geometric Viewpoint (manuscript available free online)
9. Bruce Sagan, The Symmetric Group, 2nd edn. (Springer, 2001)
10. Federico Ardila, Algebraic and geometric methods in enumerative combinatorics (free book; covers much of the same material as my notes but from a slightly different perspective, and probably a more polished presentation)

• The assignment. Everyone should meet with Jeremy and choose their paper by October 28.
• The schedule of talks and reviewers is below. If the links to papers don't work, try searching for the paper using MathSciNet (requires KUID).

Date	Presenter	Reviewer	Paper
December 5	Smita Praharaj	Amanda Wilkens	A. Knutson and T. Tao Honeycombs and sums of Hermitian matrices Notices Amer. Math. Soc. 48, no. 2 (2001), 175-186.
December 5	Amanda Wilkens	Smita Praharaj	B.E. Sagan Probabilistic proofs of hook length formulas involving trees Sém. Lothar. Combin. 61A (2009/10), Art. B61Ab, 10 pp.
December 14	Brandon Caudell	Connor Smith	J. Edmonds Minimum partition of a matroid into independent subsets J. Res. Nat. Bur. Standards Sect. B 69B (1965), 67-72.
December 14	Joseph Doolittle	Brandon Caudell	R.P. Stanley Two poset polytopes Discrete Comput. Geom. 1 (1986), 9-23.
December 14	Arturo Jaramillo	Bibekananda Mishra	A. Nica and R. Speicher Non-crossing partitions and free cumulants From Lectures on the combinatorics of free probability (Cambridge U. Press, 2006), pp. 135-194 (mainly pp. 173-194)
December 14	Bibekananda Mishra	Joseph Doolittle	P. Orlik and L. Solomon Combinatorics and topology of complements of hyperplanes Invent. Math. 56 (1980), no. 2, 167-189.
December 14	Connor Smith	Arturo Jaramillo	A. Goodall Fourier analysis on finite Abelian groups: some graphical applications From Combinatorics, Complexity and Chance: a tribute to Dominic Welsh (G. Grimmett and C. McDiarmid, eds.), Oxford U. Press, 2007, 103-129.

KU links

• Jeremy's home page
• KU Mathematics Department
• KU Registrar
• KU Bookstore
• KU policies on academic misconduct
• Student Access Services (resources for students with disabilities)

Software and online resources

• LaTeX:
  • KU Math Department LaTeX page
  • Header file for lecture notes, problem sets, etc., including lots of macros. Feel free to use and/or modify.
  • Detexify (great way to find out LaTeX symbols)
• Sage (free, open-source mathematical software), including:
  • Quick Tour and Tutorial
  • Run one command at a time on the cell server
  • Create your own notebooks and share them with others on the Sage Cloud
  • You can also install Sage on your own computer, although this can be complicated (particularly under Windows)
• The On-Line Encyclopedia of Integer Sequences