Courses:

Algebraic Combinatorics >> Content Detail



Study Materials



Readings

Amazon logo When you click the Amazon logo to the left of any citation and purchase the book (or other media) from Amazon.com, MIT OpenCourseWare will receive up to 10% of this purchase and any other purchases you make during that visit. This will not increase the cost of your purchase. Links provided are to the US Amazon site, but you can also support OCW through Amazon sites in other regions. Learn more.

Some of the readings are based on the suggested textbooks, which are shown in the table as:

[vL-W] = Amazon logo van Lint, J. H., and R. M. Wilson. A Course in Combinatorics. Cambridge, U.K.: Cambridge University Press, 1992. ISBN: 0521422604. (Reprinted 1994, 1996.)

[St] = Stanley, R. P., Sergey Fomin, B. Bollobas, W. Fulton, A. Katok, F. Kirwan, P. Sarnak, and B. Simon. Course notes on Topics in Algebraic Combinatorics. (PDF) (Courtesy of R. P. Stanley. Used with permission.)

[EC1] [EC2] = Amazon logo Stanley, R. P., Sergey Fomin, B. Bollobas, W. Fulton, A. Katok, F. Kirwan, P. Sarnak, and B. Simon. Enumerative Combinatorics. Vol. 1 and 2. Cambridge, U.K.: Cambridge University Press, 2001. ISBN: 0521789877.


Lec #TopicsReadings
1Catalan Numbers[EC1] [EC2] Stanley, R. P. "Exercises on Catalan and Related Numbers."

Stanley, R. P. "Catalan Addendum."
2Pattern Avoidance in Permutations, Young Tableaux, Schensted Correspondence, Longest Increasing Subsequences

[St] Section 8: "A Glimpse of Young Tableaux."

Schensted, C. "Longest Increasing and Decreasing Subsequences." Canadian Journal of Mathemetics 13 (1961): 179-191.

Knuth, D. E. "Permutations, Matrices, and Generalized Young Tableaux." Pacific Journal of Mathematics 34 (1970): 709-727.

3The Hooklength Formula

Random Hook Walks

A "Hooklength Formula" for Increasing Trees
Greene, C., A. Nijenhuis, and H. Wilf. "A Probabilistic Proof of a Formula for the Number of Young Tableaux of a given Shape." Adv. in Math. 31, no. 1 (1979): 104-109.
4q-analogues, q-binomial Coefficients, q-factorials

[St] Section 6: "Young Diagrams and q-binomial Coefficients."

[vL-W] Section 24: "Gaussian Numbers and q-analogues."

5Symmetric Group, Statistics on Permutations, Inversions and Major Index[EC1] Section 1.3: "Permutation Statistics."

[vL-W] Section 13
6Posets, Lattices, Distributive Lattices, Young's Lattice, Differential Posets[EC1] Sections 3.1-3.4
7Up and Down Operators, Unimodality of Gaussian Coefficients[St] Section 6: "Young Diagrams and q-binomial Coefficients." Section 8: "A Glimpse of Young Tableaux."
8Sperner's and Dilworth's Theorems[vL-W] Section 6: "Dilworth's Theorem and Extremal Set Theory."

[St] Section 4: "The Sperner Property."
9De Bruijn Sequences[vL-W] Section 8: "De Bruijn Sequences."
10Partitions: Euler's Pentagonal Theorem, Jacobi Triple Product[vL-W] Section 15: "Partitions."
11Lindstrom Lemma (Gessel-Viennot Method)

Exponential Formula
[EC2] Section 5.1: "Exponential Formula."
12Weighted Lattice Paths and Continued FractionsGoulden, I. P., and D. M. Jackson. "Combinatorics of Paths." Section 5 in Combinatorial Enumeration. New York, NY: John Wiley & Sons, 1983. ISBN: 0471866547.
13Review of Problem Set 1
14Review of Problem Set 2
15Cayley's Formula, Prufer's Codes, Egecioglu and Remmel's Bijection
16Spanning Trees, Matrix-Tree Theorem, Directed Matrix-Tree Theorem[vL-W] Section 2: "Trees." Section 34: "Electrical Networks and Squared Matrices."
17Electrical Networks[St] Section 11: "Cyles, Bonds, and Electrical Networks."

[vL-W] Section 34: "Electrical Networks and Squared Squares."
18Review of Problem Set 3
19BEST Theorem

Permutohedra, Newton Polytopes, Zonotopes
20Domino Tilings of Rectangles
21Birkhoff Polytope and Hall's Marriage Theorem[vL-W] Section 5: "Systems of Distinct Representatives."
22Pfaffians and Matching Enumeration, Ising Model
23Plane Partitions, Rhombus Tilings of Hexagon, Pseudoline Arrangements[EC2] Section 7.21: "Plane Partitions with Bounded Part Size."
24Review of Problem Set 4
25Eulerian Numbers and Hypersimplices
26What Next?

 








© 2010-2021 OpenCollege.com, All Rights Reserved.
Open College is a service mark of AmeriCareers LLC.