Univ. of Minnesota Combinatorics Seminar Schedule 2006-2007

Time: Fridays at 3:35 pm
Location: Vincent Hall 570

Fall 2006 schedule

September 8: No seminar-- 1st week of class

September 15: John Hall U. C. San Diego

Title: Counting Descent Pairs with Prescribed Tops and Bottoms

Abstract: Given sets X and Y of positive integers and a permutation sigma, an X,Y-descent of sigma is a descent pair whose ``top'' (first element) is in X and whose ``bottom'' (second element) is in Y. We give a formula for the number P_{n,s}^{X,Y} of permutations sigma in S_n with s X,Y-descents. P_{n,s}^{X,Y} is also shown to be a ``hit number'' of a certain Ferrers board. This work generalizes results of Kitaev and Remmel on counting descent pairs whose top (or bottom) is equivalent to 0 mod k.

September 22: Brendon Rhoades Univ. of Minnesota

Title: Triangularity in immanents

Abstract: An immanant is a polynomial in C[x_{11},x{12}, ..., x_{nn}] which belongs to the span of the monomials { x_{1,w(1)} *...* x_{n,w(n)} : w in S_n }. We study the transition matrix between two bases of this vector space, one defined by Rhoades and Skandera using Kazhdan-Lusztig polynomials and one defined by Desarmenien, Kung, and Rota, and prove that this matrix can be taken to be unitriangular. Then, we generalize this result to the full polynomial ring C[x_{11}, ... , x_{nn}] and the dual canonical basis. The proofs of both of these results rely heavily on a partial order on S_n defined using the dominance order. Using this order we define a 'P-filtration' of the vector space of immanants and determine where certain classical immanants fit in this structure. This is joint with Mark Skandera at Lehigh University.

September 29: Stephen Griffeth Univ. of Minnesota

Title: Rational Cherednik Algebras and Descent Bases for Coinvariant Rings

Abstract: If W is a complex reflection group acting on a vector space V, then the ring of "coinvariants" for W is the quotient of the ring of polynomial functions on V by the ideal generated by the positive degree W-invariant polynomials. The group W also has a natural "diagonal" action on the ring of polynomial functions on the direct sum V+V, and one can study the "diagonal coinvariant ring" for W. Both types of coinvariant rings have been well-studied, but there are still some interesting unanswered questions. Rational Cherednik algebras are certain deformations of the algebra generated by W together with differential operators on V with polynomial coefficients. Some rational Cherednik algebras are closely connected to ordinary coinvariant rings, and others to diagonal coinvariant rings. We will study these connections and show how some classical results on "descent bases" can be recovered and generalized to the infinite family G(r,p,n) of complex reflection groups using the representation theory of the rational Cherednik algebras.

October 6: (no seminar-cancelled)

October 13: Drew Armstrong Univ. of Minnesota

Title: k-divisible noncrossing partitions

October 20: Sen-Peng Eu Univ. of Minnesota

Title: Enumeration of parking functions by leading terms

Abstract: We introduce an algorithm to performed on labeled trees and colored labelled trees, which can be applied to parking functions and gives exact formulae for the number of parking functions of some types by leading numbers.

October 27: Uwe Nagel (Univ. of Kentucky/IMA)

Title: Invariants of ideals related to Ferrers graphs

November 3: No seminar-- Blackwell-Tapia conference at IMA

November 10: Alex Yong (Univ. of Minnesota)

Title: A combinatorial rule for (co)minuscule Schubert calculus

Abstract: I'll state and prove a root system uniform, concise combinatorial rule for Schubert calculus of minuscule and cominuscule flag manifolds G/P (the latter are also known as compact Hermitian symmetric spaces). I'll connect this geometry to the poset combinatorics of [Proctor '04], thereby giving a generalization of the [Schutzenberger `77] jeu de taquin formulation of the Littlewood-Richardson rule that computes the intersection numbers of Grassmannian Schubert varieties. This talk is based on a joint project math.AG/0608276 with Hugh Thomas.

NOTE This week only, the talk will be Thursday, Nov. 16, at 11:15am in VinH 203a.
November 16: Diane Maclagan (Rutgers/IMA)

Title: Combinatorics in the moduli space of genus zero curves

Abstract: I will describe some open combinatorial questions that arise in the study of the moduli space of genus zero curves with n marked points. These involve relationships between polyhedral cones whose constructions involve set partitions of the set of n elements. No algebraic geometry will be assumed. I will also hint at joint work with Angela Gibney that uses some related combinatorics to explicitly describe these moduli spaces.

November 24: No seminar-- Thanksgiving break

December 1: Achilleas Sinefakopoulos (Cornell Univ.)

Title: Cellular resolutions of Borel fixed ideals

Abstract: We construct a (shellable) polyhedral cell complex that supports a minimal free resolution of a Borel fixed ideal, which is minimally generated (in the Borel sense) by just one monomial in S=k[x_1,x_2,...,x_n]; this includes the case of powers of the homogeneous maximal ideal (x_1,x_2,...,x_n) as a special case. In our most general result we prove that for any Borel fixed ideal I generated in one degree, there exists a polyhedral cell complex that supports a minimal free resolution of I.

December 8: Ellen Veomett (Univ. of Michigan)

Title: The Computational Complexity of Convex Bodies

Abstract:: For convex bodies associated to many interesting and important questions, deciding whether a given point is a member of the body is computationally hard. Thus, one looks for an approximating body for which deciding membership is more computationally feasible. In this talk, I will discuss using polytopes, projections of polytopes, and sections of the cone of positive semidefinite quadratic forms to approximate convex bodies. I will discuss in particular the case where the set approximated is the Traveling Salesman Polytope.

December 15: No seminar-- Final exam week

Spring 2007 schedule

Colloquium of combinatorial interest:
Thursday, January 18 at 3:30pm in Vincent 16: Igor Pak (MIT)

Title: Inflating polyhedral surfaces

Abstract: Can you have a non-convex polyhedron with bigger volume than a convex polyhedron with isometric surface? Imagine you start blowing air into a polyhedron with a bendable but non-stretchable surface. What can be said about the limiting shape? These are the key questions I will consider. I will start the talk by discussing the history of the problem, presenting examples, and surveying earlier work on realizaiton of surfaces. In the second part of the talk I will discuss my recent results on volume-increasing deformations of polyhedral surfaces.

January 19: No seminar-- 1st week of class

January 26: Vic Reiner (Univ. of Minnesota)

Title: When are two skew Schur functions the same?

Abstract: Two different skew shapes sometimes give rise to the same skew Schur function. Understanding exactly when this occurs is subtle. After reviewing the definitions, we will discuss the significant recent progress on this problem, based on three recent papers of Stephanie van Willigenburg and various coauthors (Hugh Thomas and Lou Billera, myself, Peter McNamara).

February 2: No seminar

February 9: Jennifer Galovich (St. John's Univ.)

Title: Combinatorics and RNA Secondary Structure

Abstract: RNA secondary structures have been modeled in a variety of ways, e.g., as certain linear trees and as certain non-crossing set partitions. The collection of all non-crossing set partitions is well-known to be counted by the Catalan number. We exploit this idea to find models of RNA secondary structure in the context of other Catalan counted sets, in particular, as 3-2-1 avoiding permutations. We give a complete characterization of those permutations which correspond to RNA secondary structures, describe some statistics on the RNA secondary structures and their relationship to well-known permutation statistics, and suggest some ways in which these statistics could be used by biologists to distinguish difference types of RNA.

February 16: Calin Chindris (Univ. of Minnesota)

Title: Counterexamples to Okounkov's log-concavity conjecture

Abstract: Motivated by physical considerations, Okounkov conjectured that the Littlewood-Richardson coefficients are log-concave as a function of their highest weights. The conjecture, if true, would immediately imply Knutson-Tao saturation theorem , a conjecture of Fulton proved by Belkale, and the log-concavity theorem for skew-Schur functions proved by Lam-Postnikov-Pylyavskyy. Using quiver representations, I will expalin why Okounkov's conjecture for Littlewood-Richardson is bound to fail and present explicit counterexamples. The talk is based on joint work with Harm Derksen and Jerzy Weyman.

February 23: Seth Sullivant (Harvard Univ.)
Title: Combinatorial symbolic powers

Abstract: I will explore the combinatorial structure of symbolic powers of ideals in a polynomial ring over a field of characteristic zero. When the underlying ideal is of a combinatorial nature, the generators of the symbolic powers often have natural combinatorial interpretations. For instance, when the underlying ideal is a squarefree monomial the generators of the symbolic powers are obstructions to vertex covering in the underlying hypergraph and its blowups. As a consequence, perfect graphs play an important role in the theory. Among the applications are a new, unified approach to the study of the symbolic powers of determinantal and Pfaffian ideals. I will try to emphasize the combinatorial aspects of all of this, including connections to graph theory, packing problems, partially ordered sets, and regular triangulations.

March 2: Nicholas Eriksson (Stanford Univ.)
Title: Fourier analysis and statistics on groups

Abstract: Group valued data arises in many contexts: rankings ($S_n$), $k$-sets of a $n$-set ($S_n / S_{n-k} \times S_k$), random matrices ($U_n$), etc. The Fourier analysis of data on such groups is related to algebraic statistics and combinatorics. In particular, I will show how toric ideals can be used to analyze voting data and how Schur polynomials can tell whether a collection of matrices is really ``random''. Some of this talk is joint work with Persi Diaconis, much of it is expository based on his work. It should partially serve as an introduction to next week's IMA workshop.

March 9: Jessica Striker (Univ. of Minnesota)
Title: The alternating sign matrix polytope

Abstract: Alternating sign matrices (ASMs) are square matrices with entries 0, 1, and -1 in which the rows and columns each sum to 1 and the nonzero entries in any row and column alternate in sign. Many enumerative aspects of ASMs have been studied. In this more geometrical talk I will introduce and discuss properties of the polytope of alternating sign matrices, that is, the convex hull of n-by-n ASMs. Analogies will be drawn with the well-studied Birkhoff polytope which can be equivalently defined as the convex hull of n-by-n permutation matrices or the set of all n-by-n doubly stochastic matrices. TBA

March 16: No seminar-- Spring break

March 23: Rekha Thomas (Univ. of Washington)
Title: The Small Chvatal Rank of an Integer Matrix

Abstract: (joint work with Tristram Bogart)
The Chvatal rank of an integer matrix A is the maximum of the minimum number of rounds of cuttting planes you have to add to any polyhedron of the form Ax <= b to obtain its integer hull. In this talk I will define a related notion called the small Chvatal rank of A which is the minimum number of rounds of an iterated Hilbert basis procedure on the rows of A to obtain all facet directions of the integer hulls of all polyhedra of the form Ax <= b.

The small Chvatal rank is bounded above by Chvatal rank and is hence finite. We give families of matrices where the small Chvatal rank is small (even constant) while the Chvatal rank can be arbitrarily high. We give various other examples of the two ranks for families of well-studied polytopes in combinatorial optimization. On the negative side, we show that small Chvatal rank is not a function of dimension (i.e., the number of columns of A) and can be arbitrarily high even when n=3. Finally we relate this notion to that of supernormality, a concept introduced in the study of toric varieties and state some open problems.

March 30: Helene Barcelo (Arizona State Univ.)
Title: The Discrete Fundamental Group of the Order Complex of B_n

Abstract: We prove combinatorially that the first Betti number of the complement of the 3-equal arrangement is equal to 2^{n-3}(n^2-5n+8)-1. This formula was originally obtained by Bjoerner and Welker in 1995. We use a notion of discrete homotopy to reformulate the problem into one of counting certain equivalence classes of 6-cycles in the graph corresponding to the 1-skeleton of the permutahedron. We then use the language of words, over the alphabet of simple transpositions, to obtain necessary and sufficient conditions to determine if two 6-cycles belong to the same class. The proof requires only simple combinatorial arguments.

April 6: Frank Sottile (Texas A & M Univ.)
Title: The Horn recursion in the Schubert calculus
online version of abstract
Abstract: Work of Klyachko and of Knutson and Tao in the 1990's established the Horn conjecture, which posited a recursively defined set of inequalities among eigenvalues of hermitian matrices A, B, and A+B. This used representation theory, Schubert calculus, and combinatorics. A consequence is that other problems in mathematics have a similar Horn recursion, for example when is a Littlewood-Richardson number non-zero? Its geometric counterpart is to determine when a triple of Schubert varieties in a Grassmannian must meet. The partition indices of such a triple of Schubert varieties is called a feasible triple.

The answer is that a triple is feasible if and only if the three partitions satisfy Horn inequalities parametrized by all feasible triples for smaller Grassmannians. In brief, the Schubert calculus on a Grassmannian is controlled (to some degree) by the Schubert calculus on all smaller Grassmannians.

In this talk, I will begin by discussing the Horn inequalities for eigenvalues of hermitian matrices A, B, and A+B, and what they mean for geometry. Then I will discuss Belkale's geometric proof of the Horn recursion. This suggests that perhaps other related feasibility problems in Schubert calculus have a similar recursive description. The last part of my talk will describe a Horn recursion for other problems in the Schubert calculus, discovered in collaboration with Kevin Purbhoo.

April 13: Christos Athanasiadis (Univ. of Athens)
Title: Combinatorics and topology of generalized cluster complexes

Abstract: Generalized cluster complexes were introduced by S. Fomin and N. Reading. They include as special cases (i) the cluster complexes of S. Fomin and A. Zelevinsky, which are certain simplicial spheres of importance in the context of Y-systems and cluster algebras and (ii) the simplicial complex with faces the sets of pairwise noncrossing "m-allowable" diagonals of a convex polygon with number of vertices congruent to 2 modulo m. Both families include as a special case the boundary complex of the simplicial associahedron, a traditional object of study in enumerative and polyhedral combinatorics.

We will survey some of the interesting combinatorial and topological properties of generalized cluster complexes, including their shellability and higher Cohen-Macaulay connectivity. Part of this is joint work with E. Tzanaki.

April 20: Sami Assaf (U.C. Berkeley)
Title: Dual equivalence graphs, ribbon tableaux and Macdonald polynomials.

Abstract: We introduce a new combinatorial construction, called a dual equivalence graph, based on Haiman's 1992 discovery of an equivalence relation on tableaux which is "dual" to jeu-de-taquin. We define a generating function on the vertices of such graphs and show that it is always Schur positive. We outline the construction of a graph on standard k-tuples of young tableaux which we prove is a dual equivalence graph for $k \leq 3$. This gives a combinatorial description of the Schur coefficients of the ribbon tableaux generating functions introduced by Lascoux, Leclerc and Thibon. Recalling Haglund's monomial expansion for Macdonald polynomials, we conclude with a combinatorial formula for the Schur expansion of Macdonald polynomials indexed by a partition with at most 3 columns.

April 27: Cristian Lenart (SUNY Albany)
Title: A combinatorial model in Lie theory

Abstract: I will present a simple combinatorial model for the irreducible representations of complex semisimple Lie algebras. Based on the same model, I will present an explicit multiplication formula in the equivariant K-theory of generalized flag varieties G/B. This model is based on enumeration of chains in the Bruhat order on the corresponding Weyl group, as well as on combinatorics of the affine Weyl group. A specific application is a generalization of Schuetzenberger's involution on semistandard Young tableaux, which is presented in the context of Kashiwara's crystal graphs. Another application is related to quantum K-theory, and includes combinatorics of the so-called quantum Bruhat graph on the symmetric group. The talk, which includes joint work with A. Postnikov and T. Maeno, will be largely self-contained.

May 4: Patricia Hersh (Indiana Univ.)
Title: Coloring complexes and arrangements.

Abstract: We provide a convex ear decomposition for the coloring complex of any finite graph and for some related simplicial complexes. As a consequence, we deduce new constraints on the chromatic polynomials of all finite graphs, by using a formula of Steingrimsson which relates the chromatic polynomial of a finite graph to the h-polynomial of the double cone of its coloring complex. This is joint work with Ed Swartz.

May 11: No seminar-- Final exam week