Richard P. Stanley Seminar in Combinatorics

The sequence of Schur polynomials for a fixed partition $\lambda$ in an increasing number of variables can be comfortably and effectively generated by the application of multiplication and shift operators (Baxter operators) to the sequence of variables. We review this result of G.P. Thomas and indicate how it is generalised in different directions:

• more general sequences of symmetric polynomials (Hall-Littlewood, Jack, and Macdonald polynomials);
• nonsymmetric Schubert polynomials.

In the symmetric case the construction starts from Standard Young Tableaux and in the case of Schubert polynomials from reduced words of permutations.

Recently, attention has been paid to the problem of counting the number of permutations of length n containing a given number r (as opposed to 0) of subsequences of a certain type q. The main question is to describe this function for any given r, not just for r=0 or 1. Zeilberger and Noonan have conjectured that for any given subsequence q and for any given r, the number of n-permutations containing exactly r subsequences of type q is a P-recursive function of n. To illustrate how far the solution of this conjecture can be we note that if q is longer than three, then we do not have a proof even for r=0.

In this talk we solve this conjecture for the subsequence 132. This is the first result we know of when the case of each r is solved for some given q. Some interesting consequences and special cases are included.

Just as (semi)standard Young tableaux index a basis for the irreducible representations of S_n (or GL_n) associated to the diagram of a partition, one can ask for bases of the representations associated to more general shapes. Considerable progress has been made, notably by Magyar and by Reiner and Shimozono towards finding bases and character formulas for the representations associated to a generalized shape. Most of these results rely on either the Schensted algorithm or on jeu-de-taquin.

In the case of row-convex shapes, i.e., shapes like this which have no gaps in any row, it is possible to tell if a tableau indexes a basis element by an easy combinatorial criterion involving only pairs of rows. Furthermore, for any pair of rows not fitting the criterion, there exists a simple "straightening law" that replaces the original pair of rows by a linear combination of "better" two-rowed tableaux. Repeated applications of this straightening law expand any tableau into a linear combination of basis elements.

The row-convex straightening law is characteristic-free and generalizes to supertableaux and to quantum tableaux.

The representations used here are constructed, following Deruyts, as subspaces (of a polynomial ring) which are spanned by products of certain minors of a generic matrix. In keeping with the elementary nature of the underlying construction, this talk should be accessible to non-specialists.

We define and study a generalization of the necklace algebra defined by N. Metropolis and G.-C. Rota [Adv. Math, 50 , 1983, 95--125]; the generalized necklace algebra is associated with an arbitrary formal group law F(X,Y) over a torsion free ring A. The map from the ring of Witt vectors associated with F(X,Y) to the necklace algebra is constructed in terms of certain generalizations of the necklace polynomials. The actions of the Verschiebung and Frobenius operators, as well as of the p-typification idempotent, are described and interpreted combinatorially. A formal group-theoretic generalization of the cyclotomic identity is also presented. In general, the necklace algebra can only be defined over the rationalization of A, that is, A tensored with the rationals. Nevertheless, we show that for an important family of formal group laws over the integers, namely F(X,Y)=(X+Y-(1+q)XY)/(1-qXY) with integer q, the corresponding necklace algebra can be defined over the integers. Furthermore, the generalized necklace polynomials turn out to be integral polynomials in the variables $x$ and $q$, and they can be interpreted combinatorially when $q$ is a prime power. We have thus defined a q-deformation of the necklace algebra of Metropolis and Rota. Our results imply the existence of nice ring structures on the group of Witt vectors and the group of curves associated with the formal group law parametrized by q.

We will discuss the Kostant polynomials and their relationship to Schubert polynomials and the Schubert calculus for G/B. These polynomials are defined by vanishing properties on the orbit of a regular point under the action of the Weyl group. For each element w in the Weyl group the polynomials also have non-zero values on the orbit points corresponding to elements which are larger in the Bruhat order than w. Our main theorem is an explicit formula for these values. The matrix of orbit values can then be used to determine the cup product for the cohomology ring for G/B, using only linear algebra. The main focus of the discussion will be for the case W is the symmetric group, however the results all hold for the Weyl group of a Kac-Moody algebra.

Suppose you would like to evalute the sum of the values of a particular rational function over all the isolated roots of a given polynomial system. Recent approaches to this question apply Grothendieck's theory of residues and manage to (sometimes) reduce this question to some heavy Grobner basis calculations.

We propose a potentially faster and simpler method based on the sparse resultant. We also obtain a new point of view on the degenerate cases of this problem via the geometry of toric varieties. As another corollary, we obtain a sparse resultant based method for counting the exact number of toric roots of a polynomial system.

(No prior knowledge of toric varieties or sparse resultants is assumed.)

As you know, a word in a free group with n generators can be represented as a path in n-space. This representation has led to a number of conjectures and theorems about words in free groups. Chen's idea is to extend the notion of a free group so as to allow a generalized word to be associated with any directed path in n space. I will describe how this is done, in the hope that someone will get interested in getting "continuous" analogs of several known facts about words.

Recently, Y. Roichman gave a beautiful new formula for the irreducible characters of the Iwahori-Hecke algebra (and for the symmetic group and other Weyl groups). In the type A case this formula turns out to be equivalent to the "Frobenius formula" and, indeed, looking at it this way yields a very simple proof of Roichman's formula via the Robinson-Schensted-Knuth insertion scheme. Armed with this simpler proof we can generalize Roichman's formula to get new character formulas for Brauer and Birman-Wenzl algebras. Finally, we shall apply this whole setup to compute the bitrace of the regular representation of the Iwahori-Hecke algebra as a weighted sum of matrices with nonnegative integer entries.

Using topological graph theory we will develop planar graph models to study the properties of special simple families of plane and spherical Jordan curves. Utilizing these procedures we solved some geometrical and topological problems. Among the others we answered some of the problems and conjectures of Professor Grunbaum. In this talk I will present some of our results on convex and strongly convex, simple, irreducible planar and spherical Venn diagrams. One of these results finally and fully corrects the erroneous statements that started with John Venn more than a century ago in 1880 and have been repeated frequently by others since then. We also will solve a conjecture of Grunbaum: Every Venn diagram on n curves can be extended to a Venn diagram of n+1 curves by the addition of a suitable simple closed Jordan curve. This finally solves a problem that goes back a century to John Venn's paper in 1880. We also will discuss a related conjecture of Peter Winkler. I will raise several problems and conjectures that arise from our work. I believe the talk will interest graph theorists and topologists as well as geometers, but it is accessible for any faculty or student with minimal knowledge of graph theory, topology, and geometry. Some of the results are joint results with Kiran B. Chilakamarri and/or Raymond E. Pippert (IPFW).

Kreweras studied a polynomial P_n(q) which enumerates (labeled) rooted forests by number of inversions, as well as complements of parking functions by the sum of their terms. Moreover, P_n(1+q) enumerates labelled connected graphs by their number of excess edges. For any positive integer k, there are known notions of k-parking functions and of (labeled) rooted k-forests, generating the case k=1 studied by Kreweras. We show that the enumerator \overline{P}_n^{(k)}(q) for complements of k-parking functions by the sum of their terms is identical to the enumerator of I_n^{(k)}(q) of rooted k-forests by the number of their inversions. In doing so we find recurrence relations satisfied by \overline{P}_n^{(k)}(q) and I_n^{(k)}(q), and we introduce the concept of a multirooted k-graph whose excess edges and roots are enumerated by a polynomial denoted C_n^{(k)}(q). We show that C_n^{(k)}(q) satisfies the same recurrence relations as both \overline{P}_n^{(k)}(1+q) and I_n^{(k)}(1+q), proving that \overline{P}_n^{(k)}(q) =I_n^{(k)}(q).

Hall polynomials, which count invariant subspaces for a nilpotent linear transformation acting on a vector space over a finite field, are a key ingredient in the character theory of the group GL(n,q). We discuss the natural generalization of these polynomials to symplectic, orthogonal, and unitary groups over the q-element field. The speaker has developed an efficient algorithm for computing these "Hall functions", which makes it possible to discover and establish some of their properties. In particular, the algorithm shows that Hall functions are polynomials in q with rational coefficients, and that certain signed sums of these polynomials have integer coefficients.

We introduce a partial order of the symmetric group related to the multiplication of an arbitrary Schubert polynomial with a Schur polynomial. Analogously to the weak Bruhat order and the nil-Coxeter monoid, this order has an associated monoid M. Finding a well behaved Knuth-cell decomposition of M would solve the multiplication problem describe above. The conjecture proposed by Winkel was promissing, but our study discovered a counter-example to it, and to many other variation of it. We will propose a new conjecture.

We present a class of subposets of the partition lattice $\Pi_n$ with the following property: The order complex is homotopy equivalent to the order complex of $\Pi_{n-1},$ and the $S_n$-module structure of the homology coincides with a recently discovered lifting of the $S_{n-1}$-action on the homology of $\Pi_{n-1}.$ This is the Whitehouse representation on Robinson's space of fully-grown trees, and has since appeared in work of Mathieu, and Hanlon and Stanley.

One example is the subposet $P_n^{n-1}$ of the lattice of set partitions $\Pi_n,$ obtained by removing all elements with a unique nontrivial block. More generally, for $2\leq k\leq n-1,$ let $Q_n^k$ denote the subposet of the partition lattice $\Pi_n$ obtained by removing all elements with a unique nontrivial block of size equal to $k,$ and let $P_n^k=\cap_{i=2}^k Q_n^i.$ We show that $P_n^k$ is Cohen-Macaulay with free integral homology, and that $P_n^k$ and $Q_n^k$ are homotopy equivalent, with Betti number $n!/k-(n-1)!.$ The posets $Q_n^k$ are neither shellable nor Cohen-Macaulay. We give a simple formula for the homology as an $S_n$-module, in terms of the homology modules of the partition lattices $\Pi_k$ and $\Pi_n.$

We try to systematically employ observations that different combinatorial notions (polynomial sequence of binomial type, incidence coefficients, etc...) are generalizations of group characters. This allows us to develop a new sort of harmonic analysis rooted in combinatorics. Re-export of abstractly elaborated tools to combinatorics widens their scope of applications.