Math 8668: Combinatorial theory

(Graduate combinatorics, 1st semester)

Fall 2019


Instructor: Sam Hopkins (call me "Sam")
Office: Vincent Hall 204
E-mail: shopkins@umn.edu 
Classes: Mon-Wed-Fri 2:30-3:20pm, Ford Hall B60
Office hours: Mon-Wed: 10:00-11:00am, Vincent Hall 204
Course content: This is the first semester of the two semester Math 8668-69 sequence;
Math 8669 will be taught by Chris Fraser in Spring 2020.
We will study basic combinatorial objects (subsets, multisets, permutations, set/number partitions, compositions, graphs, trees, etc.), their enumeration, and additional structures they carry (such as partial orders). Roughly speaking we will discuss this in the first semester:
  • Generating functions (ordinary and exponential)
  • Basic objects:
    • Integer partitions and compositions,
    • Subsets and multisets,
    • Permutations,
    • Set partitions,
    • the Catalan families
  • Combinatorial statistics and q-analogs:
    • q-binomial and q-multinomial coefficients,
    • Permutation statistics (Mahonian and Eulerian)
  • Basic methods:
    • Pólya theory,
    • Lagrange inversion,
    • Inclusion-exclusion,
    • Sign-reversing involutions
  • Determinantal formulas:
    • Matrix-tree and BEST theorems,
    • Lindström-Gessel-Viennot lemma,
    • Permanent-determinant (Hafnian-Pfaffian) method,
    • Transfer-matrix method
  • Partially ordered sets and lattices:
    • Distributive lattices, Birkhoff's Theorem,
    • Möbius functions and Möbius inversion,
    • (maybe) Hyperplane arrangements,
    • (maybe) the Sperner property
Prerequisites: Calculus, linear algebra, undergraduate algebra (groups, rings, fields)
Main text: R.P. Stanley, Enumerative combinatorics, Vol. I, 2nd ed., Cambridge University Press.
Available as a pdf online here.
Other nice sources: F. Ardila, Algebraic and geometric methods in enumerative combinatorics, Part I.
H. Wilf, generatingfunctionology
D. Stanton and D. White, Constructive combinatorics
N. Loehr, Bijective combinatorics
Class notes: Batch 1, Batch 2, Batch 3, Batch 4, Batch 5
Grading: There will be 3 homework assignments for the semester.
The grading of the assignments will depend on both the quality and quantity of homework turned in. Beyond that, I expect you to show up to class and be engaged. Collaboration on the homework is encouraged, as long as each person understands the solutions, writes them up in their own words, and indicates on the homework page with whom they have collaborated.
Homework assignments: Problems will be exercises from Stanley's EC1, or these bonus problems (BPs) I came up with.
Assignment Due date Problems
HW #1 Fri., Oct. 11th
Any 8 of these:
[2-]: EC1 Ch.1 #66, 113
[2 ]: EC1 Ch.1 #5, 20, 21, 26, 29, 38, 47(a,b), 54, 68, 69, 123; BP1(a)
[2+]: EC1 Ch.1 #12, 18, 47(c), 121(a,b,c); BP1(b)
HW #2 Fri., Nov. 8th
Mon., Nov. 11th
All of the following EC1 Ch. 2 exercise:
[2-]: #2
[2 ]: #25(a,b) (the LHS of (b) has some typos)
[2+]: #14(a,b) (for (a) ok just to do A1, A2, A3)
And one of the following:
[2 ]: BP2(a), BP2(b)
HW #3 Wed., Dec. 11th Any 5 of these:
[2-]: EC1 Ch.3 #10(a); BP3(a)
[2 ]: EC1 Ch.3 #34, 42(b), 45(a), 46(a), 53, 70(b); EC1 Ch.4 #67, 68(a&b), 69, 73(a); BP3(b)
[2+]: EC1 Ch.3 #10(b), 14(a), 46(b), 85