Math 880

MSU MATHEMATICS

MTH 880
Graduate Combinatorics

Fall 2017

Instructor: Prof. Peter Magyar, magyar@math.msu.edu, tel. 353-6330, Wells Hall D-326.
Office hours: after class Mon, Wed, Fri 12:30−2:00, and by appointment.
Course Information: Textbook list, grading and homework policies, administrative dates.
Syllabus: Course outline and class schedule.
Announcements
Homework: Usually due Mon. You should discuss homework with other students, but you must write out solutions in your own words. LaTeX is encouraged. Use Wolfram Alpha or the like whenever helpful. Please do not look up answers; but if you do get help from any reference or person, give explicit credit. Click ⊞ to open sections.
- ⊞ HW Style Guide
  - Write short. Give all needed information in minimum words.
  - Adapt to your audience. Omit details obvious to them, expand arguments unfamiliar to them. In your homework, consider your audience as other students in our course who have not done this problem.
  - Give the setup. At the beginning of each problem or section, state what it is about. Always state the Proposition before a proof. Do not assume the reader knows what you are talking about: you yourself will have forgotten when reviewing after a year.
- Homework 1 due Wed 9/7 (tex).
- Homework 2 due Wed 9/13 (tex). Solutions
- Homework 3 due Wed 9/20 (tex). Solutions
- Homework 4 due Fri 9/29 (tex).
- Homework 5 due Mon 10/9 (tex).
- Homework 6 due Fri 10/20 (tex).
- Homework 7 due Mon 10/30 (tex).
- Homework 8 due Mon 11/13 (tex).
- Homework 9 due Wed 11/29 (tex).
- Homework 10 - Part 1 due Wed 12/6 (tex).
- Extra Credit: Homework 10 - Part 2 due Fri 12/15 (tex).
Notes
- Textbooks
  - [St] Stanley, Enumerative Combinatorics. Two-volume main text.
    - Volume I, 2nd ed, Ch 1−4. Page numbers differ in online vs printed versions. I will refer to section numbers.
    - Volume II, Ch 5−7, at MSU Library.
  - [FS] Flajolet & Sedgewick, Analytic Combinatorics. Supplementary text.
  - [HHM] Harris, Hirst, Mossinghoff, Combinatorics and graph theory, 2nd ed. Undergrad background.
  - [W] Herbert Wilf, Generatingfunctionology. Undergrad background.
  - [Stanton-White] Stanton & White, Constructive Combinatorics. Interesting material about bijections and involutions.
  - [Kerber] A. Kerber, Applied Finite Group Actions, 2nd ed. Detailed study of the Polya-Redfield method.
  - Doubilet, Rota, Stanley, The Idea of Generating Function. Expanded version of [St] §3.18-19.
- Math 481, 482. Undergrad course pages, with HW and notes.
- 8/31: Method of generating functions for binomial coefficients
  Reading: [St] §1.1.1−1.1.5, 1.1.12, 1.1.17, 1.2; [FS] pp. 16, 19, 23; [HHM] pp. 131−133, 138−140, 164−165.
  Math 481 Notes 1/13, 1/22, 2/3.
- 9/2: Method of generating functions for Fibonacci numbers.
  Reading: Math 481 Notes 2/1, HW 2/12.
- 9/6 & 9/8: Twelvefold Way
  Reading: [St] §1.9. Math 482 Notes 1/8.
- 9/11 & 9/13: Number partition generating functions
  Reading: [St] §1.8. Math 482 HW 2/28. Wikipedia on Pentagonal Number Theorem.
- 9/15: Principle of Inclusion-Exclusion: Math 481 Notes 1/25−1/29.
  Catalan numbers and Reflection Transform: Math 481 Notes 2/17−2/19.
- 9/18: Labeled classes and labeled product.
  Reading: [St] §5.1-5.2. [FS] §II.2, II.3, II.5, p 100−130; [W] §3.4, 3.6, 3.12. Example: connected graphs.
- 9/20: Stirling set partition numbers
  Reading: [St] §1.9 #3. [HHM] §2.8.3, pp 231−235. Math 481 Notes 1/27.
- 9/22: Cycles in permutations, Stirling cycle numbers, bivariate generating functions.
  Reading: [St] §I.3. [HHM] §2.8.2, p 227. [F] §III.1-2, p 152. [HHM] §2.8.2, p 227.
- 9/25: Directed labeled product, alternating permutations, Euler numbers.
  Reading: [St] §I.6. [F] §II.6.3, p 139.
- 9/27: Cayley trees, Lagrange inversion.
  Reading: [St] Vol 2, §5.3, p 22; §5.4, p 36. [F] §I.5, p 64; §II.5, p 125. [HHM] §1.3.4, p 43.
  Math 481 Graph Notes II, HW 3/25.
- 9/29: Set and MSet operations on unlabeled classes
  Reading: [F] §I.2, p 24. [W] §3.14−17, p 92.
  Dlog method for recurrences, unlabeled trees.
  Reading: [W] §1.6, pp 22−23.
- Review: Twelvefold Way with Pascal-type recurrences, with bivariate generating functions.
- 10/2: Polya theory, counting up to symmetry. Reading:
  - [HHM] §2.7, p. 190.
  - [St] vol 2, §VII.24.
  - Kerber, Applied Finite Group Actions.
  - Math 481 Polya Notes and Polya HW.
- 10/13: Finite field Grassmannians.
  Reading:
  - [St] §I.10.2, §I.7, esp. Prop 1.7.2.
  - Wikipedia on finite fields, Euclidean algorithm for reciprocals, Frobenius automorphism.
  ⊞ Notation
  - q-integer: [n]_q = 1 + q + q² + ... + qⁿ⁻¹ = ^(qⁿ−1)⁄_(q−1)
  - q-factorial: [n]^!_q = [n]_q [n−1]_q ... [1]_q = ∑_{w∈S_n} q^inv(w)
  - Gaussian q-binomial coefficient: [n | k]_q = ^{[n]^!_q} / _{[k]^!_q [n−k]^!_q} = ∑_I q^|I|, where I = {i₁ < ··· < i_k} ⊂ [n], | I | = ∑_j (i_j−j)
  - Three indexing sets for Schubert cells of Gr(k, Fⁿ)
    - subsets I = {i₁ < ··· < i_k} ⊂ [n]
    - partitions λ = (λ₁ ≥ ··· ≥ λ_k ≥ 0) = (i_k−k , . . . , i₁−1)
    - Grassmannian permutations w ∈ S_n^(k) ≅ S_n / S_k×S_n−k
      w = (i₁ < ··· < i_k | j₁ < ··· < j_n−k)
  - [St] denotes [n]_q , [n]^!_q , [n | k]_q by boldface n , n! , (n choose k)
  - Inversion diagram: Inv(w) = { (i, j) | i < j and w(i) > w(j) }.
  - Rothe diagram: D(w) = (1×w) Inv(w) = { (i, j) | i < w⁻¹(j) and w(i) > j }
  - Lehmer code: Code(w) = (c₁,..., c_n), c_i = #{ j | i < j and w(i) > w(j) }
  - Inversion length: inv(w) = #Inv(w) = #D(w) = |Code(w)|
- 10/23 Posets: examples and definitions
  Reading: [St] §3.1−3.3.
- 10/25 Incidence algebras
  Reading: [St] §3.6.
- 10/27 Mobius inversion
  Reading: [St] §3.7.
- 10/30 Posets & simplicial complexes; Mobius function & Euler characteristic
  Reading: [St] §3.8.
- 11/1 Distributive lattices
  Reading: [St] §3.3−3.5.
- 11/3 Lattices, combinatorial geometries
  Reading: [St] §3.9, 3.10.
- 11/6 Hyperplane arrangements: characteristic polynomial, Zaslavsky Theorem, finite field method.
  Reading: [St] §3.11.
- 11/8 Reduced incidence algebras, types of generating functions, binomial posets.
  Reading: [St] §3.18, Doubilet, Rota, Stanley, The Idea of Generating Function.
- 11/15 Rational generating functions, magic squares, Diophantine homogeneous linear equations.
  Reading: [St] §4.1−4.6. Lecture Notes.