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'll discuss this in the 1st 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 with whom they collaborated.

Homework assignments:

 Problems will be exercises from Stanley's EC1, or these bonus problems (BPs) I wrote.
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