Fall 2005-Spring 2006 Combinatorics Seminar Schedule

Friday at 3:35, Vincent Hall 570

Spring 2006

January 27 : Robin Pemantle University of Pennsylvania

Title: Asymptotics of multivariate generating functions

February 3: Vic Reiner University of Minnesota

Title: Steinberg's proof of Bott's theorem

February 10:Alex Yong University of Minnesota

Title: Stable Grothendieck polynomials and a K-theoretic Edelman-Greene algorithm

Abstract: We formulate a nonrecursive combinatorial rule for the expansion of the stable Grothendieck polynomials of [Fomin-Kirillov '94] in the basis of stable Grothendieck polynomials for partitions. This gives a common generalization, as well as new proofs of the rule of [Fomin-Greene '98] for the expansion of the stable Schubert polynomials into Schur polynomials, and the K-theoretic Grassmannian Littlewood-Richardson rule of [Buch '02].

Our main technique is a generalization of the Robinson-Schensted and Edelman-Greene insertion algorithms. Our results are applied to prove a number of new formulas and properties for K-theoretic quiver polynomials, and the Grothendieck polynomials of [Lascoux-Sch\"{u}tzenberger '82]. In particular, we provide the first K-theoretic analogue of the factor sequence formula of [Buch-Fulton '99] for the cohomological quiver polynomials.

This is joint work with Anders Buch, Andrew Kresch, Mark Shimozono and Harry Tamvakis. See math.CO/0601514

February 17: Ezra Miller University of Minnesota

Title: h-vectors of Gorenstein polytopes

Abstract: The h-vector of a simplicial polytope is a list of numbers that records, in a slightly nontrivial way, the number of faces of each dimension. As it turns out, the h-vector of a simplicial polytope is nonnegative, symmetric, and unimodal. On the other hand, for any polytope P---simplicial or otherwise---with lattice point vertices, there is another notion of h-vector, which arises by counting the lattice points in integer multiples of P. These alternate h-vectors are more mysterious: for the special class of normal Gorenstein polytopes (I'll define these in the talk), they are nonnegative and symmetric, but their unimodality is unknown. The talk will be about recent work of Bruns and Roemer concerning the case where a Gorenstein polytope P has a unimodular triangulation.

February 24: Xun Dong University of Miami

Title: The bounded complex of an affine oriented matroid

March 3: Molly Maxwell University of Minnesota

Title: Enumerating Bases of Self-Dual Matroids

Abstract: We define involutively self-dual matroids and prove a relationship between the bases and self-dual bases of these matroids. We use this relationship to prove an enumeration formula for the higher dimensional spanning trees in a class of regular cell complexes. This gives a new proof of Tutte's theorem that the number of spanning trees of a central reflex is a perfect square and solves a problem posed by Kalai about higher dimensional spanning trees in simplicial complexes. We also give a weighted version of the latter result.

The critical group of a graph is a finite abelian group whose order is the number of spanning trees of the graph. We prove that the critical group of a central reflex is a direct sum of two copies of an abelian group. We conclude with an analogous result in Kalai's setting.

March 24: Alex Woo University of California-Davis

Title: Bruhat-restricted pattern avoidance

Abstract: Combinatorialists have been studying pattern avoidance on permutations for a few decades. Motivated by the geometry of Schubert varieties, Billey and Braden gave a definition of pattern avoidance for arbitrary Coxeter groups several years ago. I will explain a new generalization of the Billey-Braden definition also motivated by Schubert varieties. The combinatorics of this definition (as well as that of the Billey-Braden definition) is almost entirely unexplored. This being a combinatorics seminar, I will focus on this combinatorics and only briefly mention the geometry. Most of this talk will be comprehensible to someone knowing only linear algebra and basic group theory. Partially based on joint work with Alexander Yong.

March 31: Richard Ehrenborg University of Kentucky

Title: Counting pattern avoiding permutations via integral operators

Abstract: A permutation \pi=(\pi_{1},\ldots,\pi_{n}) is consecutive 123-avoiding if there is no sequence of the form \pi_{i} < \pi_{i+1} < \pi_{i+2}. More generally, for S a collection of permutations on m+1 elements, the above definition extends to define consecutive S-avoiding permutations. We show that the spectrum of an associated integral operator on the space L^{2}[0,1]^{m} determines the asymptotics of the number of consecutive S-avoiding permutations. Moreover, using an operator version of the classical Frobenius-Perron theorem due to Kre\u{\i}n and Rutman we prove asymptotics results for large classes of patterns S. This extends previously known results of Elizalde. This is joint work with Sergey Kitaev and Peter Perry.

April 7: Jay Goldman University of Minnesota

Title: Combinatorics at Minnesota: the history as I remember it

April 13: Hugh Thomas University of New Brunswick, Special Thursday seminar 2:30 pm

Title: Noncrossing partitions and quiver representations

Abstract: There is a lattice of noncrossing partitions associated to any finite reflection group. (From the symmetric group -- the type A_n reflection group -- one recovers the classical noncrossing partitions.) Last year, Brady and Watt gave the first proof that the noncrossing partitions form a lattice which didn't depend on the classification of finite reflection groups plus a computer check for the exceptional reflection groups. I will present a new proof of this fact, based on an interpretation of noncrossing partitions in terms of quiver representations. This perspective also illuminates Reading's bijections among noncrossing partitions, c-sortable elements, and clusters. Aspects of this approach generalize to the m-noncrossing partitions studied by Armstrong, which I will discuss if time permits.

This is joint work, mainly with Colin Ingalls (UNB), some of it with Drew Armstrong (Cornell).

April 14: Persi Diaconis Stanford University (joint with probability, 2:30 pm)

Title: Glauber dynamics, exponential families, and orthogonal polynomials

Abstract: Glauber dynamics (also known as the Gibbs sampler) is widely used but difficult to analyze carefully. In joint work with Kshitj Khare and Laurent Saloff-Coste, we have found a large collection of examples where sharp upper and lower bounds on rates of convergence can be given. This involves strange new identities for orthogonal polynomials.

April 21: Markus Perling Institut Fourier, Grenoble

Title: Poset representations, vector space arrangements and toric varieties

Abstract:The objective of this talk is the study of equivariant sheaves on toric varieties and their resolutions. Generalizing earlier work of Klyachko, we show that these objects have a "semi-combinatorial" description in terms of sheaves on (finite) posets, which generalize the well-known lcm-lattices of monomial ideals. The general question now to understand the underlying combinatorial invariants. For this, we use free resolutions of sheaves on posets to obtain an intrinsic an efficient method to construct divisorial resolutions for equivariant sheaves over toric varieties. This construction has an interesting interpretation in the context of vector space arrangements: every vector space arrangement can in a non-unique way be interpreted as an equivariant sheaf. By structure transport, we obtain so the notion of a free resolution of a vector space arrangement by coordinate arrangements. One can speculate whether these can be used to study properties of arrangements or whether this even may lead to a homological theory of arrangements.

April 28: Jim Haglund The Ohio State University

Title: A Combinatorial Formula for Nonsymmetric Macdonald Polynomials

Abstract: The theory of nonsymmetric Macdonald polynomials was developed by Cherednik, Macdonald and Opdam. Like their symmetric counterparts, they have versions for arbitrary root systems, which satisfy an orthogonality relation and a norm evaluation (generalizing Macdonald's constant term conjecture), and which feature in a genaralization of Selberg's integral. Their construction of these polynomials was existential however, and up to now no particularly nice expressions for them were known. In this talk we overview some of this history, and then present an explicit combinatorial formula for the type A versions of these polynomials, which is recent joint work with M. Haiman and N. Loehr. We then discuss connections of our formula to the theory of symmetric functions.

May 5: Carly Klivans University of Chicago

Title: Generalized Degree Sequences

Abstract: Degree sequences of graphs have been thoroughly studied. For example, there are many simple characterizations of when an integer sequence is the degree sequence of a graph and of graphs with "extremal" degree sequences. Notions of generalized degree sequences for higher dimensional simplicial complexes are not as well investigated. I will talk about work in progress on understanding these generalized degree sequences and those classes of complexes which exhibit analogous extremal behavior. (joint work with Uri Peled and Amitava Bhattacharya)

Talks from Fall 2005

September 16: Alexander Yong University of Minnesota,

Title: Tableau complexes

Abstract: Let X, Y be finite sets and T a set of functions from X to Y, which we will call ``tableaux''. We define a simplicial complex whose facets, all the same dimension, correspond to these tableaux, and call it a ``tableau complex''. Tableau complexes have many nice properties, and are frequently homeomorphic to balls, which we prove using vertex decompositions of Billera-Provan.

In our motivating example, the facets are labeled by semistandard Young tableaux, and the interior faces by Buch's ``set-valued'' semistandard tableaux. In the Young tableaux case, one such vertex decomposition parallels Lascoux's transition formula for vexillary double Grothendieck polynomials. Consequently, we obtain formulae (both old and new) for these polynomials. In particular, we present a common generalization of the formulae of Wachs and Buch, each of which imply the classical tableau formula for Schur polynomials.

Our inspiration (and an application) for the definition of this simplicial complex comes from certain Gr\"{o}bner degenerations of vexillary matrix Schubert varieties (see math.AG/0502144).

This is a joint project with Allen Knutson and Ezra Miller.

September 23:Vic Reiner University of Minnesota,

Title: Cyclically sieving the non-crossing partitions for reflection groups

September 30:David Bressoud Macalester College

Title: Exploiting Symmetries: Alternating Sign Matrices and the Weyl Character Formulas

Abstract: This will be an overview of some of the points of interaction between symmetric functions and representation theory on the one hand, and questions in number theory and combinatorics on the other, culminating in recent work of Okada enumerating alternating sign matrices (aka the six-vertex model of statistical mechanics) through evaluations of Weyl character formulas.

October 7: Dan Drake University of Minnesota

Title: Towards a combinatorial theory of multiple orthogonal polynomials

Abstract: In the 1980's, Viennot described an entirely combinatorial theory of orthogonal polynomials, unifying the many known combinatorial interpretations of various families of orthogonal polynomials. I will describe early attempts at a combinatorial theory of multiple orthogonal polynomials, in which the polynomials must be orthogonal to two (or more) weight functions, not just one.

October 14:Mark Skandera Haverford College

Title: On the nonnegativity properties of the dual canonical basis

Abstract: Lusztig showed that all polynomials p(x_1,...,x_n) in the dual canonical basis satisfy p(A) ≥ 0 for every totally nonnegative matrix A = (a_ij). It was shown in 2004 that the evaluation of these polynomials at Jacobi-Trudi matrices yields Schur nonnegative symmetric functions. We will discuss variations of these properties and their relation to cluster algebras and Schubert varieties.

October 21:Muge Taskin University of Minnesota

Title: Properties of four partial orders on standard Young tableaux

Abstract:1) Intervals in any of these four orders essentially describe the product in a Hopf algebra of tableaux defined by Poirier and Reutenauer.

2) The map sending a tableau to its descent set induces a homotopy equivalence of the proper parts of all of these orders on tableaux with that of the Boolean algebra $2^{[n-1]}$. In particular, the M\"obius function of these orders on tableaux is $(-1)^{n-3}$.

3) For two of the four orders, one can define a more general order on skew tableaux having fixed inner boundary, and similarly analyze the homotopy type and M\"obius function.

October 28: Ezra Miller University of Minnesota

Title: Duality of antidiagonals and pipe dreams

Abstract: Associated to every permutation w in S_n is its set of reduced pipe dreams (rc-graphs), each of which is a subset of the n by n grid. Also associated to w is a certain determinantal ideal; the generating minors have antidiagonal terms that can also be considered as subsets of the n by n grid. It is crucial for the geometry of Schubert polynomials that these two collections of subsets of the grid are dual, in a precise sense. This talk is about a direct, elementary combinatorial proof of this duality due essentially to Ning Jia.

November 4: John Stembridge University of Michigan

Title: Disproving the Neggers Conjecture

November 11: Steven Damelin IMA

Title: On the number of linear independent vectors over a finite field of prime order

Abstract: Given a set of n vectors over a finite field of prime order (for simplicity one might consider the binary case where we work with vectors with entries 0s and 1's), we are interested in counting the number of vectors from this class which are linear independent k\leq n at a time. Applications to combinatorial designs, coding and net designs will be discussed.

Several open problems will be posed with the hope of finding connections to other areas.

November 18: David Speyer University of Michigan

Title: Tropical Linear Spaces and a New Matroid Invariant

Abstract: Tropical geometry is a way of replacing problems in algebraic geometry with problems of piecewise linear geometry. In the first half of this talk we define tropical analogues of the notions of linear space and Plucker coordinate and study their combinatorics. Intersections and orthogonal complements of tropical linear spaces behave in a manner closely mirroring the classical case. All tropical linear spaces constructed from hyperplanes by repeated dualization and transverse intersection have the same f-vector and we conjecture that this f-vector is maximal for all tropical linear spaces of given dimension and codimension.

In the second half of the talk we will sketch a proof of this conjecture for tropical linear spaces "realizable in characteristic zero". This proof introduces a new matroid invariant which, although it can be described combinatorially, naturally arises from K-theory and has no good combinatorial description as yet.

December 2: Calin Chindris University of Minnesota

Title: Long exact sequences and Horn type inequalities

Abstract: Horn's conjecture gives a recursive method for the existence of short exact sequences of finite abelian p-groups. We use methods from quiver invariant theory to find necessary and sufficient inequalities for the existence of long exact sequences of m finite abelian p-groups. As it turns out, this result is also related to some generalized Littlewood-Richardson coefficients and eigenvalues of Hermitian matrices satisfying certain (in)equalities.

December 9: Sangwook Kim University of Minnesota

Title : Shellable complexes and topology of diagonal arrangements

Abstract : For a simplicial complex, one can associate a diagonal arrangement. We will show that if a simplicial complex is shellable, then the intersection lattice for the corresponding diagonal arrangement is homotopy equivalent to a wedge of spheres. Moreover, one can describe precisely the spheres in the wedge, based on the data of shelling.