Richard P. Stanley Seminar in Combinatorics

Edrei's theorem describes all so-called totally positive (or Polya frequency) sequences. By definition, a sequence (a_i) is called totally positive if

\det [a_{i_p j_q}]_{1 \le p,q \le k}

for all k greater than or equal to 0 and all

i_1 < i_2 < ... < i_k,

j_1 < j_2 < ... < j_k .

Such sequences arise in approximation theory, probability, ..., and representation theory of S(\infty), U(\infty), O(\infty), Sp(\infty). Two proofs of this theorem were known: Edrei's original proof, based on results of Nevanlinna about entire functions, and the "ergodic" proof of Vershik and Kerov, based on the calculation of the asymptotics of the characters of S(n) as n goes to infinity. New methods in the representation theory of infinite-dimensional classical groups provide a new proof of Edrei's theorem as well as a remarkable simplification of the existing proofs.

We present a new proof of the hook-length formula for the dimension of the irreducible representation of the symmetric group. In order to do that we construct an explicit bijection between two sets of tableaux.

Those who are interested may refer to http://www.labri.u-bordeaux.fr/~betrema/pak/pak.html for definitions and nice examples.

Chung and Graham's cover polynomial generalizes Goldman, Joichi, and White's "factorial" rook polynomial to two variables. We factor the cover polynomial completely for Ferrers boards with either increasing or decreasing column heights. For column permuted Ferrers boards, we find a sufficient condition for its partial factorization. We apply this to column permuted "staircase boards," getting a partial factorization in terms of the column permutation, as well as a sufficient condition for complete factorization.

Classical representation theory of the symmetric groups (Young, Frobenius, Schur, Weyl, von Neumann, et al.) involves from the outset the notion of Young diagrams and some nontrivial combinatorics of the Young lattice.

Since the branching rule for the irreducible representations of S_n (n=1,2,...) is described by the Young lattice, one could wonder: is it possible to find this rule a priori, i.e., before all the representation theory of S_n is constructed? For beginners, the "yes" answer would justify the introduction of the Young diagrams, whereas the experts could say that the representation theory of the symmetric groups at last (a century after its creation) becomes a part of general representation theory.

Now we can say "yes"! Using Coxeter generators, Murphy-Jusys elements, Gel'fand-Tsetlin subalgebra for the symmetric groups, its spectrum, and adding some simple arguments, we obtain a new and very natural version of this remarkable classical theory.

MacMahon showed that the number of plane partitions with at most n rows, at most n columns, and all parts of size at most n is equal to

                     n-1     n-1     n-1
                   ------- ------- -------
                    |   |   |   |   |   |   i+j+k+2
                    |   |   |   |   |   |   --------
                    |   |   |   |   |   |   i+j+k+1
                     i=0     j=0     k=0

(a generalization of binomial coefficients). The problem can also be viewed as one of counting plane partitions whose solid Young diagram fits inside an n-by-n-by-n box, or as one of counting tilings of a regular hexagon of side-length n by rhombuses of side 1.

Working with Michael Larsen, we have recently shown that for n large, a "typical" tiling of the hexagon (i.e., one chosen uniformly at random from the set of all tilings with n fixed) has one sort of behavior near the boundary of the hexagon and a qualitatively different sort in the interior, where the border between the two regions is asymptotically given by the circle inscribed in the hexagon. The local behavior inside the circle varies from place to place, and we can give a formula for how it varies. Our results can be interpreted as giving an asymptotic law for the typical shape of the solid Young diagram of a constrained plane partition.

The Feynman path integral for two-dimensional quantum gravity, which is a sum over geometries and matter configurations, can be calculated by taking the continuum limit of a discretized theory of triangulated surfaces with combinatorial data representing matter fields. I will discuss an approach to such a calculation using recursion equations in free variables. The flexibility of this method allows the computation of a number of quantities which would be difficult to compute using traditional "matrix model" approaches to these theories.

A perfect 1-factorization of the complete graph K2n may be defined as a partition of the edge set into 1-factors, such that the union of any two of the 1-factors is connected. When viewed this way, a natural generalization is to consider 1-factorizations of K2n where the union of any three of the 1-factors is connected. We call these almost perfect 1-factorizations. We examine the automorphism group G of such 1-factorizations. For perfect 1-factorizations on K2n, strong divisibility conditions have been established for the size of the automorphism group, depending only on n. However for other types of 1-factorizations the order of the automorphism group can be relatively large in comparison with the number of vertices 2n. We ask, what restrictions can be placed on the size of the automorphism group G in the case of an almost perfect 1-factorization?

The braid or Coxeter arrangement of type A_{n-1} is the arrangement of hyperplanes in R^n given by the equations x_i - x_j = 0. We study deformations of this arrangement, i.e., hyperplane arrangements of the type

x_i - x_j = a_{ij}^1,a_{ij}^2,...,a_{ij}^k.

We calculate the number of regions and the Poincare polynomial for many arrangements of this form. In particular, we prove a conjecture by Richard Stanley that the number of regions of the arrangement in R^n given by the equations x_i - x_j = 1, i < j, is equal to the number of alternating trees on {1,2,...,n}. The number of regions and the Poincare polynomial have some interesting combinatorial and arithmetical properties. Many of the results presented here are obtained in collaboration with Richard Stanley.

Let A be an affine subspace arrangement in R^n, defined over the integers. We give a combinatorial interpretation of the characteristic polynomial chi(A, q) of A that is valid for sufficiently large prime values of q. This result, which generalizes a theorem of Blass and Sagan, reduces the computation of chi(A, q) to a counting problem and provides an explanation for the wealth of combinatorial results discovered in the theory of hyperplane arrangements in recent years. The basic idea appeared for the first time in 1970 in a theorem of Crapo and Rota, which unfortunately was overlooked in the later development of the theory of arrangements.

We give applications for various hyperplane arrangements. These include a simple, uniform proof of a result of Blass and Sagan about the characteristic polynomial of a Coxeter arrangement, simple derivations of the characteristic polynomials of the Shi arrangements and various generalizations and a another proof of Stanley's conjecture about the number of regions of the Linial arrangement. We also extend our method to the computation of all face numbers of a rational hyperplane arrangement.

\input {amstex}
\advance\voffset  by -1.0cm
\NoBlackBoxes
%\nopagenumbers
\magnification=\magstep1
%\hfuzz=3.5pt
\hsize=17truecm
\vsize=24.2truecm
\voffset=0.5truecm
%\hoffset
\document

\define \bZ {\Bbb Z}

\topmatter
\title
On the number of connected components in the intersection of 2 open
opposite Schubert
cells in $SL_n/B$
\endtitle

\author  B.~Z.~Shapiro, M.~Z.~Shapiro, A.~D.~Vainshtein
\endauthor

\affil \endaffil

\abstract We consider the space

\endabstract
\abstract
Let $T_n$ denote the group of real unitary uppertriangular matrices and
$\Delta_i,\;i=1,...,n-1$
denote the the hypersurface in $T_n$ given by vanishing of the 'principal'
$i\times i$-minor in the
right upper corner.  We study the number of connected components in $\Cal
C_n=T_n
\setminus \bigcup_i\Delta_i$ using ideas from \cite {L} and \cite {BFZ}. At
first the
problem is reduced to a purely combinatorial question about some 'action'
on the group $T_n(\bZ_2)$
of uppertriangular matrices with $0-1$-entries. The final conjecture under
consideration is as follows.
The number $\sharp_n$ of connected components in $\Cal C_n$ equals $3\times
2^n$ for all $n\ge 5$.
(Cases $n=3$ and $n=4$ are exceptional and $\sharp_3=6$, $\sharp_4=52$.)

\endabstract
\endtopmatter

\Refs
\widestnumber \key{ShSh}

\ref \key {BFZ} \by A.~Berenstein, S.~Fomin, A,~Zelevinski
\paper Parametrizations of canonical bases and totally positive matrices
 \jour preprint
\yr 1995\pages 1--98\endref

\ref \key {L} \by G.~Lusztig
\paper Total positivity in reductive groups
\inbook Lie theory and geometry: in honor of Bertram Kostant, Progress in Math
\publ Birkh\"auser\vol 123
\yr 1994
\endref

\ref \key {SS} \by B.~Z.~Shapiro,  M.~Z.~Shapiro
\paper On the totally positive upper triangular matrices
\finalinfo accepted to Lin. Alg. and Appl
\endref

\endRefs

\enddocument$

In this talk we give a preliminary report on work on posets that occur as lower intervals in the poset defined on the elements of a sub-semigroup S of N^n by divisibility within S. By work of Laudal to compute the homology of the order complexes over k of these posets is equivalent to compute Tor_i^R(k,k) for R = k[S]. We will show how to reprove some known results about Koszul rings using these techniques and show that the complexes that occur in this context are very closely related to complexes that are associated to quotients of polynomial ring by monomials of degree 2 (e.g., Stanley-Reisner rings of posets).

We had shown that given a natural number n, and a sequence T = (1,2,3,...,d,t_d,...,t_i,...,t_j) of integers satisfying t_d \geq t_{d+1} \geq ... \geq t_j and \Sigma t_i = n , then the lattice P(T) of partitions having diagonal lengths T is isomorphic to a product Q(T) = L_d \times ... \times L_j where each L_i is the lattice of partitions having no more than t_i-t_{i+1} rows and 1+t_{i-1}-t_i columns, under inclusion. The map D from P(T) to Q(T): P --> Q(P) arises from arranging the difference-one hooks of P having hands on the i-diagonal into parts according to the number of such hooks having a given hand.

It follows that the knowledge of Q_1(P) = Q(P) --- the difference-one hooks of P --- determines the difference-a hooks of T for all a. In this talk we define difference-a hook partitions and describe a composition Q_a(P) \times Q_b(P) --> Q_{a+b}(P) . Thus we define a "hook difference algebra" such that Q_a(P) = Q_1(P) \times ... Q_1(P) (a times). This algebra is related to the "strand map" S: Q(T) --> P(T) that is the inverse of D.

This is joint work with J. Yam\'eogo.

This is an account of a joint work with Bernard Leclerc. We consider the q-deformation of the coordinate ring of the flag variety of type A_r . This is the algebra with unit over the field of rational functions Q(q) generated by 2^{r+1}-1 generators [J] labeled by nonempty subsets J \subset [1,r+1] := {1,2, ..., r+1} , subject to the quantized Pl\"ucker relations. We refer to the generators [J] as _quantum_flag_minors_ (they can be identified with q-minors of a generic q-matrix whose row set consists of several initial rows). We say that [I] and [J] _quasicommute_ if [J][I] = q^n [I][J] for some integer n. We are concerned with the following problem motivated by the study of canonical bases for quantum groups of type A_r .

Problem A: describe all families of quasicommuting quantum flag minors.

We obtain a combinatorial criterion for quasicommutativity of two quantum flag minors [I] and [J]. As a consequence, we show that the maximal possible size of a quasicommuting family of quantum flag minors is {r+2 \choose 2}. An interesting special class of such families is in a bijection with the set of commutation classes of reduced expressions for the longest permutation w_0 \in S_{r+1}. This result leads to a natural extension of the _second_Bruhat_order_ by Manin-Schechtman.

The theorem I will prove is this: In a finite type Weyl group, an element w has the property that you can knock out any simple generator from any reduced expression and come up with another reduced expression if and only if w is sts-avoiding. I'll use this fact to exhibit a family of singular Schubert varieties.

One curious thing is that this fact depends on finite type and is not a purely braid relation fact since it isn't true in affine A_2, for instance.

Macdonald introduced a two parameter symmetric function basis P_\mu(x;q,t) for which various specializations of q and t yield many of the other well-established bases. The transition matrix expressing a rescaled basis J_\mu(x;q,t) in terms of a modified Schur basis s_\lambda[X(1-t)] has components denoted K_{\lambda,\mu}(q,t), and generalizes the ordinary Kostka matrix. Macdonald conjectured that K_{\lambda,mu}(q,t) are polynomials in q and t with nonnegative integer coefficients. We show that they are polynomials by determining new explicit formulas for them. These formulas separate the dependence on \mu and \lambda, and surprisingly, their structure is entirely determined by a portion of \lambda, and not at all on \mu. These formulas are themselves symmetric functions k_\gamma(x;q,t) indexed by partitions, where if we set \gamma to be \lambda with its largest row deleted, then a certain specialization ``B_\mu'' of x to q,t-monomials depending on \mu essentially expresses K_{\lambda,\mu}(q,t) as k_\gamma(B_\mu;q,t). The coefficients of k_gamma(x;q,t) when expressed in terms of Schur functions are Laurent polynomials in q and t, so that k_\gamma(B_\mu;q,t) is at least a Laurent polynomial, and the simple monomial denominator is easily eliminated to yield a true polynomial.

This is joint work with Adriano Garsia.

The problem of counting the number of lattice points inside a lattice polytope in R^n has been studied from a variety of perspectives, including the recent work of Pommersheim and Kohvanskii using toric varieties and Cappell and Shaneson using Grothendieck-Riemann-Roch. Here we show that the Ehrhart polynomial of a lattice n-simplex has a simple analytical interpretation from the perspective of function theory on the n-torus. The methods involve Poisson Summation and Fourier integrals.

We obtain closed forms for the coefficients of the Ehrhart polynomial in terms of the elementary cotangent functions. These expressions are closely related to the formulas of Cappell and Shaneson and Hirzebruch and Zagier.

This is joint work with Ricardo Diaz.

The Murnaghan-Nakayama rule is a most useful recursive rule for computing characters of the symmetric groups. We present a generalization of this rule to arbitrary Coxeter groups and their Hecke algebras. The classical version is obtained as a special case, and new combinatorial interpretations follow. The work is done via Kazhdan-Lusztig theory and combinatorics of Coxeter groups.

We compute the Gromov-Witten invariants of the flag manifold using a new combinatorial construction for its quantum cohomology ring.

This is joint work with S. Gelfand and A. Postnikov. The paper is available from http://www-math.mit.edu/~fomin/papers.html

The vexillary permutations in the symmetric group have interesting connections with the number of reduced words, the Littlewood-Richardson rule, Stanley symmetric functions, Schubert polynomials and the Schubert calculus. Lascoux and Schutzenberger have shown that vexillary permutations are characterized by the property that they avoid any subsequence of length 4 with the same relative order as 2143. In this talk, we will propose a definition for vexillary elements in the hyperoctahedral group. We show that the vexillary elements can again be determined by pattern avoidance conditions. These vexillary elements share some, but not all, of the "nice" properties of the vexillary permutations in $S_n$.

The Littlewood-Richardson rule is a combinatorial formula for structure constants of the ring of symmetric polynomials in terms of its Schur basis:

s_\mu \cdot s_\nu = \sum_\lambda c^\lambda_{\mu\,\nu} s_\lambda.

Schubert polynomials form a basis for the ring of polynomials in infinitely many variables x_1,x_2,..., so there are similar structure constants for Schubert polynomials, which I also call Littlewood-Richardson coefficients. These generalize the classical coefficients, as every Schur polynomial in x_1,...,x_k is a Schubert polynomial. They are, however, largely unknown.

This talk will discuss recent results (obtained with Nantel Bergeron) on those coefficients which arise when multiplying a Schubert polynomial by a Schur polynomial. We show these coefficients have certain symmetries, similar to symmetries of the classical Littlewood-Richardson coefficients, which facilitates their computation. We apply these results to the enumeration of chains in the strong Bruhat order on the symmetric group.

The star-triangle is the simplest form of the "Yang-Baxter" relations and plays a vital role in solvable statistical mechanical models, ensuring that transfer matrices commute.

There are models for which no star-triangle relation is known, but which satisfy a weaker "star-star" relation. These will be discussed, and it will be shown that this weaker relation is still sufficient to ensure the required commutation properties.

Certain q-analogues of Littlewood-Richardson (LR) coefficients arise naturally in the resolution of the ideal of a nilpotent conjugacy classes of matrices in a larger nilpotent conjugacy class. These polynomials may be defined using a Kostant-Heckman formula. A conjectural description is given in terms of what we call catabolizable tableaux. In the special case of tensor products of irreducibles corresponding to rectangular partitions, there is another conjectural combinatorial description using classical LR tableaux and a generalization of Lascoux, Leclerc, and Thibon's formula for the charge statistic. Monotonicity properties of these polynomials are studied using families of statistic-preserving injections. Certain compositions of these injections furnish a bijection from the LR tableaux to the catabolizables. This is joint work, part with Jerzy Weyman and part with Anatol N. Kirillov.