Algebraic Combinatorics Graduate course offered in the spring semester, 2009. Instructor: Lior Pachter Course number: Math 249. Course control number: 54734. Lectures: Tuesdays and Thursdays, 9:30--11:00am in 101 Wheeler. Office hours: Monday 1-3pm.

Presentation Schedule

April 14
Jon: MD Haiman. (1987). "Arguesian lattices which are not linear", Bulletin of the Maerican Mathematical Society, Volume 16, Number 1.
Elizabeth: Sperner property of the partition lattice
Pegga: M Beck and D Pixton. (2003). "The Erhart polynomial of the Birkhoff polytope". Discrete and Computational Geometry, Volume 30, Number 4, 623-637.
April 16 April 21 April 23 April 24 April 28 April 30 Tableaux combinatorics
S Corteel and LK Williams. (2007). "Tableaux combinatorics for the asymmetric exclusion process". Advances in Applied Mathematics.

Umbral calculus
GC Rota and BD Taylor. (1994). "The classical Umbral calculus". SIAM J Math. Anal., Volume 25, Issue 2, 694-711.
Ira Gessel. (2003). "Applications of the classical umbral calculus". Algebra Universalis, 397-434.

Matroids and phylogenetic trees
F Ardila and CJ Klivans. (2006). "The Bergman complex of a matroid and phylogenetic trees". Journal of Combinatorial Theory, Series B.

Happy End Theorem
Chung, F.R.K.; Graham, R.L. (1998). "Forced convex n-gons in the plane". Discrete and Computational Geometry 19: 367-371.
Kleitman, D.J.; Pachter, L. (1998). "Finding convex sets among points in the plane". Discrete and Computational Geometry 19: 405-410.
Toth G.; Valtr, P. (1998). "Note on the Erdos-Szekeres theorem". Discrete and Computational Geometry 19: 457-459.
Nicols, C. M. (2007). "The Empty Hexagon Theorem". Discrete and Computational Geometry 38: 389-397.

Fast matching algorithms
JE Hopcroft and RM Karp (1973). "An $n^{5/2}$ algorithm for maximum matchings in bipartite graphs". SIAM Journal on Computing.
A Goel, M Kapralov and S Khanna (2009). "Perfect matchings via uniform sampling in regular bipartite graphs", Symposium on Discrete Algorithms, 11-17.

Geometric identities in lattice theory
M Mainetti and CH Yan. (2000). "Geometric identities in lattice theory", Journal of Combinatorial Theory, Series A.

Permutohedra and associahedra
A Postnikov. (2009). "Permutohedra, associahedra and beyond". International Mathematics Research Notices.

E Rodney Canfield. (1998). "The size of the largest antichain in the partition lattice" Journal of Combinatorial Theory Series A, Volume 83, Issue 2, 188-201.

Tilings
R Kenyon, A Okounkov and S Sheffield. (2003) "Dimers and amoebae". Arxiv preprint.
M Korn and I Pak. (2004). "Tilings of rectangles with T-tetrominoes". Theoretical Computer Science.

Birkhoff polytope
M Beck and D Pixton. (2003). "The Erhart polynomial of the Birkhoff polytope". Discrete and Computational Geometry, Volume 30, Number 4, 623-637.

Random permutations
P Diaconis, J Fulman and R Guralnick. (2009). "On fixed points of permutations". Journal of Algebraic Combinatorics, to appear.

Binomial posets
R Ehrenborg and MA Readdy. (2007). "Classification of the factorial functions of Eulerian binomial and Sheffer posets". Journal of Combinatorial Theory Series A, Volume 114, Issue 2, 339-359.

Applications of algebraic combinatorics to biology
N Beerenwinkel, N Eriksson and B Sturmfels. (2006). "Evolution on distributive lattices". Journal of Theoretical Biology.
G. Tesler. (2008) "Distribution of segment lengths in genome rearrangements". Electronic Journal of Combinatorics.
C. Heitsch (2009) "Combinatorics on plane trees motivated by RNA secondary structure configurations" submitted to SIAM Journal of Discrete Mathematics.
F.R. McMorris, H.M. Mulder and R.C. Powers (2003) "The median function on distributive semilattices" Discrete Applied Mathematics.
N. Beerenwinkel, L. Pachter and B. Sturmfels (2007) "Epistasis and shapes of fitness landscapes" Statistica Sinica.