Reading Class 290-046: Combinatorics and Representation Theory
Winter and Spring 2004

Course description

• crystal bases, representations of quantum algebras and Hecke algebras (suggested texts are Hong, Kang "Introduction to Quantum Groups and Crystal Bases", Ariki "Representations of Quantum Algebras and Combinatorics of Young tableaux")
• relation between representation theory and polytopes (recent papers by Knutson, Berenstein, Kirillov, Zelevinsky,...)
• Schubert polynomials and varieties (Manivel "Symmetric functions, Schubert polynomials and degeneracy loci" and recent papers by Fomin, Kirillov, Billey, Buch, Fulton, Knutson, Miller, Shimozono,....)

Schedule Winter

• January 9: Organizatorial meeting
• January 16: Isaiah Lankham
• January 23: Robin Endelman
• January 30: Jesus De Loera
• February 6: Gus Wiseman
• February 13: Tyrrell McAllister
• February 20: Philip Sternberg
• February 27: Philip Sternberg/Lipika Deka
• March 5: Janos Pach
• March 12: Lipika Deka

Schedule Spring

• April 9: Anne Schilling
• April 16: Gus Wiseman
• April 23: Philip Sternberg
• April 30: Lipika Deka
• May 7: Tyrrell McAllister
• May 14: no seminar (Schwarz conference)
• May 21: Isaiah Lankham
• May 28: James Parmenter
• June 4: Mark Shimozono

• Organizatorial meeting, January 9, 2004
  
  During this meeting I will hand out a list of papers appropriate for presentation. We can also discuss the class time if interested participants have a conflict with Friday 2-3pm.



• Isaiah Lankham, January 16, 2004
  
  Title: A Gentle Introduction to Pattern Avoiding Permutations and the Stanley-Wilf Conjecture
  
  Abstract: The study of Pattern Avoiding Permutations has recently become a hot topic for research because it has many applications to fields ranging from Algebraic Combinatorics to Statistical Learning Theory. In the early 1990's Richard Stanley and Herbert Wilf made a very insightful and fundamental conjecture that gives a useful upper bound on the number of permutations avoiding permutation patterns. Until recently, various authors have tried repeated to prove this theorem but had only been able to prove it for certain special cases. However, in November 2003 A. Marcus and G. Tardos were able to prove the full conjecture as a corollary to other well-known conjecture.
  
  In this talk we will first discuss what a permutation pattern is and why one might want to avoid them. Then we will discuss the Stanley-Wilf Conjecture, its refinements, other important related conjecture, and how A. Marcus and G. Tardos were able to prove it. Specifically, we will give D. Zeilberger's recent half page proof of the Fueredi-Hajnal conjecture, from which the Stanley-Wilf conjecture will almost trivially follow.
  
  Required prerequisite knowledge of combinatorics will be kept to a minimum.
  
  References:
  
  A. Marcus and G. Tardos. "A Linear Bound on the Excluded Permutation Matrices." Preprint.
  
  MR1798218 (2001k:05005) Klazar, Martin "The Fueredi-Hajnal conjecture implies the Stanley-Wilf conjecture." Formal power series and algebraic combinatorics (Moscow, 2000), 250--255, Springer, Berlin, 2000.
  
  MR1736130 (2000i:05007) Alon, Noga; Friedgut, Ehud. "On the number of permutations avoiding a given pattern." J. Combin. Theory Ser. A 89 (2000), no. 1, 133--140.
  
  MR1710623 (2000e:05005) Arratia, Richard. "On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern." Electron. J. Combin. 6 (1999), no. 1, Note, N1, 4 pp. (electronic).
  
  MR1659444 (99i:05005) Bona, Miklos. "The solution of a conjecture of Stanley and Wilf for all layered patterns." J. Combin. Theory Ser. A 85 (1999), no. 1, 96--104.



• Robin Endelman, January 23, 2004
  
  Title: Flag varieties and the Yang-Baxter equation
  
  Paper Abstract: We investigate certain bases of Hecke algebras defined by means of the Yang-Baxter equation, which we call Yang-Baxter bases. These bases are essentially self-adjoint with respect to a canonical bilinear form. In the case of the degenerate Hecke algebra, we identify the coefficients in the expansion of the Yang-Baxter basis on the usual basis of the algebra with specializations of double Schubert polynomials. We also describe the expansions associated to other specializations of the generic Hecke algebra.
  
  References:
  
  MR1445968 (98d:05150) A. Lascoux, B. Leclerc, J.-Y. Thibon, "Flag varieties and the Yang-Baxter equation." Lett. Math. Phys. 40 (1997), no. 1, 75--90.



• Jesus De Loera, January 30, 2004
  
  Title: Methods of representation theory in Combinatorial Optimization Problems
  
  Paper Abstract: An approach to combinatorial optimization problems is developed in this paper from the point of view of the theory of symmetric group representations. An assignment problem which generalizes the ordinary assignment problem is tied to each representation of a finite group. For a symmetric group, this problem also includes the travelling salesman and other problems. It is proved that, for almost all representations of a symmetric group, the assignment problem is NP-complex. An approximate algorithm which yields a guaranteed relative error is constructed for solving these problems. The investigations are based on the analysis of the convex hull of the orbit of a point relative to the group action in the space of the representation operators.
  
  Reference:
  
  MR1060934 (91e:90086) Barvinok, A. I.; Vershik, A. M. "Methods of representations theory in combinatorial optimization problems." Soviet J. Comput. Systems Sci. 27 (1989), no. 5, 1--7 (1990); translated from Izv. Akad. Nauk SSSR Tekhn. Kibernet. 1988, , no. 6, 64--71, 205 (Russian)



• Gus Wiseman, February 6, 2004
  
  Title: Factorizations of Symmetric Function Relations and a Generalization of the Binomial Theorem
  
  Abstract: When the elementary, homogeneous, and power sum symmetric function bases are expressed in terms of certain operators, the identities relating these bases have simple factorizations. In particular, the expansion of a binomial product has a form very similar to that of the binomial theorem. These factorizations are better understood as "relation graphs," which are structures that illuminate the combinatorial properties of many symmetric and quasi-symmetric functions, including Schur functions, chromatic symmetric functions, and generating functions for (P-omega) partitions.
  
  Reference: Gus Wiseman, preprint



• Tyrrell McAllister, February 13, 2004
  
  Title: Combinatorics and geometry of Littlewood-Richardson cones
  
  Reference:
  
  Igor Pak and Ernesto Vallejo, "Combinatorics and geometry of Littlewood-Richardson cones", preprint (2003) 15 pp., to appear in Europ. J. Combinatorics. (available here)



• Philip Sternberg, February 20, 2004
  
  Title: Schubert varieties
  
  Reference: L. Manivel, Symmetric functions, Schubert polynomials and degeneracy loci, chapter 3



• Lipika Deka, February 27, 2004
  
  Title: Schubert varieties (continued)
  
  Reference: L. Manivel, Symmetric functions, Schubert polynomials and degeneracy loci, chapter 3



• Janos Pach, March 5, 2004
  
  Title: Directions in discrete geometry
  
  This talk is in conjunction with The Department of Mathematics & Math Club. Note that the talk will be given in 206 Olson!!!



• Lipika Deka, March 12, 2004
  
  Title: Schubert varieties (continued)
  
  Reference: L. Manivel, Symmetric functions, Schubert polynomials and degeneracy loci, chapter 3



• Anne Schilling, April 9, 2004
  
  Title: A unified approach to combinatorial formulas for Schubert polynomials
  
  Abstract: Schubert polynomials were introduced in the context of the geometry of flag varieties. This paper investigates some of the connections not yet understood between several combinatorial structures for the construction of Schubert polynomials; we also present simplifications in some of the existing approaches to this area. We designate certain line diagrams known as rc-graphs as the main structure. The other structures in the literature we study include: semistandard Young tableaux, Kohnert diagrams, and balanced labelings of the diagram of a permutation. The main tools in our investigation are certain operations on rc-graphs, which correspond to the coplactic operations on tableaux, and thus define a crystal graph structure on rc-graphs; a new definition of these operations is presented. One application of these operations is a straightforward, purely combinatorial proof of a recent formula (due to Buch, Kresch, Tamvakis, and Yong), which expresses Schubert polynomials in terms of products of Schur polynomials. In spite of the fact that it refers to many objects and results related to them, the paper is mostly self-contained.
  
  Reference: Cristian Lenart, "A Unified Approach to Combinatorial Formulas for Schubert Polynomials", math.CO/0402397



• Gus Wiseman, April 16, 2004
  
  Title: The Chromatic Symmetric Function
  
  References:
  
  P. Doubilet, "On the Foundations of Combinatorial Theory. VII: Symmetric Functions through the Theory of Distribution and Occupancy", Studies Appl. Math. 51 (1972), 377-396
  
  D. Gebhard and B. Sagan, "A Chromatic Symmetric Function in Noncommuting Variables," Journal of Alegbraic Combinatorics 13 (2001) 227-255.
  
  R. P. Stanley "A Symmetric Function Generalization of the Chromatic Polynomial of a Graph," Advances in Math. 111 (1995), 166-194.
  
  R. P. Stanley "Graph Colorings And Related Symmetric Functions: Ideas and Applications: A description of results, interesting applications, & notable open problems," Discrete Math. 193 (1998), 267-286.



• Philip Sternberg, April 23, 2004
  
  Title: Subword complexes in Coxeter groups
  
  Abstract: Let (\Pi,\Sigma) be a Coxeter system. An ordered list of elements in \Sigma and an element in \Pi determine a {\em subword complex}, as introduced in our paper on Grobner geometry of Schubert polynomials (math.AG/0110058). Subword complexes are demonstrated here to be homeomorphic to balls or spheres, and their Hilbert series are shown to reflect combinatorial properties of reduced expressions in Coxeter groups. Two formulae for double Grothendieck polynomials, one of which is due to Fomin and Kirillov, are recovered in the context of simplicial topology for subword complexes. Some open questions related to subword complexes are presented.
  
  Reference: Allen Knutson, Ezra Miller, "Subword complexes in Coxeter groups", math.CO/0309259



• Lipika Deka, April 30, 2004
  
  Title: Supernomial coefficients, Bailey's lemma and Rogers-Ramanujan-type identities. A survey of results and open problems.
  
  Abstract: An elementary introduction to the recently introduced $A_2$ Bailey lemma for supernomial coefficients is presented. As illustration, some $A_2$ $q$-series identities are (re)derived which are natural analogues of the classical $(A_1)$ Rogers-Ramanujan identities and their generalizations by Andrews and Bressoud. The intimately related, but unsolved problems of supernomial inversion, $A_{n-1}$ and higher level extensions are also discussed. This yields new results and conjectures involving $A_{n-1}$ basic hypergeometric series, string functions and cylindric partitions.
  
  Reference: S.O. Warnaar, "Supernomial coefficients, Bailey's lemma and Rogers-Ramanujan-type identities. A survey of results and open problems." The Andrews Festschrift (Maratea, 1998). Sem. Lothar. Combin. 42 (1999), Art. B42n, 22 pp. (electronic).



• Tyrrell McAllister, May 7, 2004
  
  Title: A positive proof of the Littlewood-Richardson rule using the octahedron recurrence
  
  Abstract: We define the_hive ring_, which has a basis indexed by dominant weights for GL(n), and structure constants given by counting hives [KT1] ( or equivalently honeycombs, or Berenstein-Zelevinsky patterns [BZ1]). We use the octahedron rule from [Robbins-Rumsey,Fomin-Zelevinsky,Propp,Speyer] to prove bijectively that this "ring" is indeed associative. This, and the Pieri rule, give a self-contained proof that the hive ring is isomorphic as a ring-with-basis to the representation ring of GL(n). In the honeycomb interpretation, the octahedron rule becomes "scattering" of the honeycombs. This recovers some of the "crosses and wrenches" diagrams from the very recent preprint [S], whose results we use to give a closed form for the associativity bijection.
  
  Reference: Allen Knutson, Terence Tao, Christopher T. Woodward, "A positive proof of the Littlewood-Richardson rule using the octahedron recurrence", math.CO/0306274



• Isaiah Lankham, May 21, 2004
  
  Title: Card shuffling and the decomposition of tensor products
  
  Abstract: Let H be a subgroup of a finite group G. We use Markov chains to quantify how large r should be so that the decomposition of the r tensor power of the representation of G on cosets on H behaves (after renormalization) like the regular representation of G. For the case where G is a symmetric group and H a parabolic subgroup, we find that this question is precisely equivalent to the question of how large r should be so that r iterations of a shuffling method randomize the Robinson-Schensted-Knuth shape of a permutation. This equivalence is rather remarkable, if only because the representation theory problem is related to a reversible Markov chain on the set of representations of the symmetric group, whereas the card shuffling problem is related to a nonreversible Markov chain on the symmetric group. The equivalence is also useful, and results on card shuffling can be applied to yield sharp results about the decomposition of tensor powers.
  
  Reference: Jason Fulman, "Card shuffling and the decomposition of tensor products", math.RT/0307053



• Mark Shimozono, June 4, 2004
  
  Title: Four positive formulae for type A quiver polynomials
  
  Abstract: We give four positive formulae for the (equioriented type A) quiver polynomials of Buch and Fulton. All four formulae are combinatorial, in the sense that they are expressed in terms of combinatorial objects of certain types: Zelevinsky permutations, lacing diagrams, Young tableaux, and pipe dreams (also known as rc-graphs). Three of our formulae are multiplicity-free and geometric, meaning that their summands have coefficient 1, and correspond bijectively to components of a torus-invariant scheme. The remaining (presently non-geometric) formula was conjectured for by Buch and Fulton in terms of factor sequences of Young tableaux; our proof of it proceeds by way of a new characterization of the tableaux counted by quiver constants. All four formulae come naturally in ``doubled'' versions, two for `double quiver polynomials', and the other two for their stable versions, the `double quiver functions', where setting half the variables equal to the other half specializes to the ordinary case.
  
  Reference: Allen Knutson, Ezra Miller, Mark Shimozono, "Four positive formulae for type A quiver polynomials", math.AG/0308142