Richard P. Stanley Seminar in Combinatorics

We present a new combinatorial method to compute the characteristic polynomial of subspace arrangements using the theory of valuations. This method applies to any subspace arrangement over an infinite field. Examples include complex subspace arrangements, the Dowling divisor lattice and its interpolations. We also consider the effect of the Dowlingization transformation on the characteristic polynomial of real subspace arrangements.

In this talk we'll describe one way to visualize the action of a semisimple Lie algebra on a weight basis. The resulting picture will actually be a poset with colored edges which we will call a {\em supporting diagram}. (Often, many weight bases give rise to the same supporting diagram.) Supporting diagrams have some notable combinatorial structure: in particular, for irreducible representations, they are always rank symmetric, rank unimodal, and strongly Sperner posets.

Some well-known distributive lattices, such as the "boolean lattice" $B_{n}$ and the lattice $L(m,n)$ of all partitions that fit inside an $m \times n$ box, arise naturally as supporting diagrams for certain representations. In this talk we'll describe virtually all of the posets that we know of that arise as supporting diagrams for irreducible representations. However, this is a program that is far from complete; the problem is that many irreducible representations have not been explicitly constructed in such a way that it is possible to easily write down the supporting diagrams.

We take as our model the explicit bases obtained by Gelfand and Zetlin for the irreducible representations of $sl(n,\Bbb{C})$. We will describe explicit bases (and the associated supporting diagrams) for the fundamental representations of $sp(2n,\Bbb{C})$ and $so(2n+1,\Bbb{C})$ that "analogize" the GZ bases in a certain sense. We will also look at supporting diagrams for other special families of representations.

This talk will be example-oriented, and we will use these examples to begin to explore some more general questions. Does every supporting diagram contain the associated crystal graph? Which supporting diagrams are the most "efficient"? And when is a weight basis "uniquely specified" by its supporting diagram?

We prove an inequality involving the cd-indices of a convex polytope P, a face F of the polytope and the link P/F. As a consequence we settle a conjecture of Stanley that the cd-index of d-dimensional polytopes is minimized on the d-dimensional simplex. Moreover, we show how this gives quadratic inequalities on the flag f-vector of polytopes. Lastly, we present an upper bound theorem for the cd-index of polytopes.

We show that the action of classical operators associated to the Macdonald polynomials on the basis of Schur functions, S_\lambda[X(t-1)/(q-1)], can be reduced to addition in \lambda rings. This provides explicit formulas for the Macdonald polynomials expanded in this basis as well as in the ordinary Schur basis, S_\lambda[X].

It is shown that a large class of events in a product probability space are highly sensitive to noise, in the sense that with high probability, the configuration with a few random errors gives almost no prediction whether the event occurs. This may be viewed as a concentration of measure phenomenon.

Consider, for example, bond percolation on an $n+1$ by $n$ grid. A configuration is a function that assigns to every edge the value $0$ or $1$. Let $\omega$ be a random configuration, selected according to the uniform measure. A crossing is a path that joins the left and right sides of the rectangle, and consists entirely of edges $e$ with $\omega(e)=1$. By duality, the probability for having a crossing is $1/2$. Fix an $\epsilon\in(0,1)$. For each edge $e$, let $\omega'(e)=\omega(e)$ with probability $1-\epsilon$, and $\omega'(e)=1-\omega(e)$ with probability $\epsilon$, independently of the other edges. Let $p(\tau)$ be the probability for having a crossing in $\omega'$, conditioned on $\omega=\tau$. Then for all $n$ sufficiently large, $\mbox{Prob}\big\{\tau : |p(\tau)-1/2|>\epsilon\big\}<\epsilon$.

Alexander duality for monomial ideals has until now been applicable only when the monomial generators are squarefree. In this talk, the construction will be broadened to include all monomial ideals. It will also be shown how Alexander duality interacts with certain canonically defined free resolutions of monomial ideals

Regular polyhedra have been investigated since antiquity. In ordinary euclidean 3-space, the class of regular polyhedra has been considerably extended to what are now called the Gr\"unbaum--Dress polyhedra. The talk presents a new approach to these polyhedra, which also leads to a quicker proof of the completeness of the enumeration than that found by Dress. Presentations of their symmetry groups will also be discussed. This is joint work with Peter McMullen.

The purpose of this talk is to present a combinatorial interpretation for the decomposition of the tensor product of two or more irreducible representations of GL(n) in terms of certain scattering R-matrix. This R-matrix satisfies a Yang-Baxter type equation. The corresponding piecewise-linear transformation of parameters maps coincide with the transition maps for Kashiwara parametrizations of canonical bases for modules over type A quantum groups. We provide an explicit description for the cone of such parameterizations, thus solving a problem posed by Berenstein and Zelevinsky. Geometrically, our R-matrix can be interpreted via certain web diagrams, which are similar in appearance to honeycomb tinkertoys of Knutson and Tao. This is a joint work with Oleg Gleizer.

There is a remarkable set of quadratic relations among the characters of representations of gl(n) corresponding to rectangular Young diagrams, which can be derived from the Littlewood-Richardson rule. Generalizing these relations cleverly to Lie algebras of types B-C-D (for Lie theorists), it appears we are really looking at characters of the associated quantum affine algebras. These relations led to the study of "rigged configurations" (for combinatorialists) and some new formulas for decomposing tensor products of rectangles. A recent result shows that the relations actually determine the quantum characters of rectangles, and there is some hope that this can be generalized to other characters.

I will give a brief survey on stability in matching markets, the most famous example being the stable marriage theorem of Gale and Shapley. The problem of matching roommates is harder, and no stable matching need exist. But what if the players are allowed to bribe each other in order to obtain more preferable roommates? As an extra bonus, I will give the surprising answer to the question posed by my father at MIT a few months ago: "In how many block moves can the bridge player sort his hand?

We study the class of embeddings of a simple closed curve in closed 2-manifolds such that {\parindent=24pt\parskip=3pt \item{(1)} there are only transversal double points, \item{(2)} each residual region of the manifold is a disc, and \item{(3)} this set of discs is two-colorable, thus furnishing the vertices and faces of a combinatorial map (`carte').

Such embeddings are characterized up to homotopy by two combinatorial structures on the set $E$ of crossing points: {\parindent=24pt\parskip=3pt \item{(1)} The double occurrence word $\Delta$, or `combinatorial lacet', giving the order of crossing points along the curve, and \item{(2)} a bipartition $(K,L)$ of the set $E$, classifying the type of reentry at each crossing.} \vskip0pt This combinatorial information gives rise to a unique map having the lacet as its diagonal.

Given a combinatorial lacet, on what 2-manifolds can it be represented? Starting from a problem and partial response by Gauss (1840), and using transformations of vector spaces over $GF(2)$, Rosenstiehl (1976) and Lins, Richter \& Shank (1987) characterized lacets representable in the Euclidean and projective planes, respectively. We show how these characterizations extend naturally to the case of arbitrary 2-manifolds, and give, in particular, simple procedures for determining whether a lacet is representable on the torus or on the Klein bottle.

This is joint work with Pierre Rosenstiehl.

For each Coxeter group we can partition the group elements in a certain way, and form a formal sum from the elements in each part. These formal sums form the basis of what is known as a descent algebra. Much study has gone into those algebras where the Coxeter group involved is either a symmetric group or a hyperoctahedral group. A vital tool in this study has been the existence of a "matrix interpretation" of multiplication in these algebras.

In this talk I shall formulate such a matrix interpretation for the descent algebra of type D, and discuss results that it has suggested.

Suppose we are given a quiver (directed graph) S, for example o--->o--->o. A representation of this quiver is triple (V,W,X) of vector spaces together with a pair (f,g) where f:V-->W and g:W-->X are linear maps. If we fix the dimensions, say (dim V,dim W, dim X)=(a,b,c), then the isomorphism classes of all representations of S with these dimensions correspond to GL(a)xGL(b)xGL(c)-orbits in the direct sum of Hom(k^a,k^b) and Hom(k^b,k^c). So very informally: "Quiver are orbits of a products of GL_n's in certain nice representations". This perspective will motivate us to give a definition of quiver representations for arbitrary reductive groups. It turns out to make sense: for orthogonal and symplectic groups our generalization has a nice interpretation, namely, they correspond to so-called orthogonal and symplectic representations of quivers with an arrow-inverting automorphism (called symmetric quivers). Among other things we will classify the symmetric quivers of finite and tame type, and their indecomposable representations.

This is joint work with Jerzy Weyman at Northeastern.

We enumerate $m$-colored $m$-gonal plane cacti according to the degree distribution of vertices of each color. We obtain explicit formulae for both the labeled and unlabeled cases. This combinatorial problem is motivated by the classification of complex polynomials having at most $m$ critical values, studied by Zvonkin and others. The corresponding problem for {\em rooted} $m$-cacti has been solved by Goulden and Jackson in connection with factorizations of a cyclic permutation into $m$ permutations with given cycle types. To achieve our goal, we prove a dissymmetry theorem for $m$-cacti extending the well-known Otter's formula for trees and use an $m$-variable generalization of Chottin's 2-variable Lagrange inversion formula.

This is joint work with Michel Bousquet, Gilbert Labelle and Pierre Leroux.

The question of wether or not two posets or two graphs are isomorphic can be phrased as an integer program. Various relaxations of this integer program give rise to the notions of fractional isomorphism and affine isomorphism. Issues such as reconstruction of graphs and posets naturally carry over to the fractional and affine isomorphism settings.

We will provide a survey of the known results, present some new ones, and discuss some of the open questions in these areas.

The asymptotic enumeration of Latin squares is still an open problem. Part of the difficulty is that if one writes down an inclusion-exclusion expression for the desired quantity, the error term quickly swamps the main term. Several number-theoretic problems suffer from the same difficulty, and number theorists have devised some clever methods of circumventing it, using both sieve methods and zeta functions. We show how some of these methods---Selberg's lambda-systems in particular---carry over readily to many combinatorial settings.

This talk will survey some combinatorial algorithms that arise in the representation theory of Lie groups. Roughly speaking, given any real Lie group $G$ two such algorithms emerge --- one from the structure of `good' bases for certain Hecke algebra representations, and the other from the structure of the canonical bases of Springer representations. When $G = GL(n,\C)$, they both reduce to the classical Robinson-Schensted algorithm. The point of this talk is to remove the ponderous representation theoretic baggage from these algorithms, and instead concentrate on their combinatorics. One combinatorial consequence is an interesting partition of the group of $r$-signed permutations into disjoint subsets. When $r=1$ or $2$, the partition recovers the (weighted) Kazhdan-Lusztig cells for types A and BC.

We introduce the {\em honeycomb} model of Berenstein-Zelevinsky polytopes. This associates a polytope of honeycombs to each triple of dominant weights of $GL_n$. The B-Z theorem says that the lattice points in these polytopes count Littlewood-Richardson numbers.

Our main result is that for each regular triple of dominant weights, at least one vertex of this polytope is a particularly nice honeycomb. One corollary of this is Klyachko's saturation conjecture, which says that the semigroup of ({\em not} necessarily regular) triples with $LR>1$ is saturated -- the nice honeycombs are necessarily integral.

In this talk we hope to get to another corollary, a description of those triples of regular dominant weights for which the Littlewood-Richardson coefficient is exactly 1.

This work is joint with Terry Tao of UCLA.

Comparative phylogenetic analysis generally reveals a large array of similarities and dissimilarities between the various species under consideration. To derive phylogenetic branching patterns from that array (so that e.g. the kinship relation between horse, cow and whale could be elucidated), a rather "brutal", yet amazingly successful procedure has been to rally all the observed similarities and dissimilarities, for any two species, in just one number -- then called the (dis)similarity index of those two species. The resulting structure then -- in most cases -- is a finite metric space, and the associated task is to detect the branching pattern in question from analysing this space.

While statistician have designed many useful procedures for analysing such spaces, most of these methods (like e.g. principal component analysis) perceive euclidean n-space as the "standard of truth" and are designed to construct "good", if not (somehow) optimal embeddings of the given space into euclidean space. Clearly, this is inadeqate if phylogenetic branching patterns (and migration or diffusion in some large (state)space accompanying these branching processes) are considered to be the cause for the observed dissimilarity patterns.

In the lecture, it will be shown that tools for a completely unprejudiced abstract, "combinatorial" analysis of finite metric spaces provide amazingly usable means for phylogenetic reconstruction. The basic concepts and the resulting mathematical theory will be reviewed, and illustrative examples including a discussion of the still somehow mysterious evolution of mammals and of a recent application of the resulting computer program regarding "The Phylogeny of The Canterbury Tales" -- NATURE, August 27, 1998 will be presented.

The crossing number of $G$, ${\mbox {cr}}(G)$ is the minimum number of crossing points in any drawing of $G$ in the plane. Ajtai, Chv\'atal, Newborn, Szemer\'edi, and independently Leighton proved that, for any graph $G$ with $n$ vertices and $e\ge 4n$ edges, the crossing number of $G$ is at least ${1\over 64}{e^3\over n^2}$. (We show that this remains true with a somewhat better constant $c={1\over 33.75}$.) The order of magnitude of this bound cannot be improved, in general. However, we establish much stronger results for graphs satisfying some monotone properties. In particular, we show that if $G$ contains no $C_4$ as a subgraph and $e\ge 400n$, then the crossing number of $G$ is at least ${1\over 10^7}{e^4\over n^3}$ and this bound is also best possible, apart from the exact value of the constant. This settles a question of M. Simonovits. The pairwise crossing number, pair-cr resp. the odd-crossing number, odd-cr of $G$ is the minimum number of pairs of edges that cross resp. cross an odd number of times over all drawings of $G$. Clearly, ${\mbox {odd-cr}}(G)\le {\mbox {pair-cr}}(G)\le {\mbox {cr}}(G)$. It is a challenging open question to decide whether these three numbers coincide for every graph $G$. We prove that the largest of these numbers, cannot exceed twice the square of the smallest.

This is joint work with J\'anos Pach.

Starting from a reduced decomposition for an element $w$ of length $l$ in a Weyl group $W$, we define a particular subgroup of $G=GL_l(GF_2)$. The orbits of this subgroup (in the standard representation of $G$) are in one-to-one correspondence with connected components in the intersection of two open Schubert cells in a real flag manifold that have relative position $w$. Explicit description of these orbits allows us to calculate the number of connected components for most $w\in W$. This is joint work with B.Shapiro, A.Vainshtein and A.Zelevinsky

We give a homotopy equivalence to explain an $S_{n-1}$-module isomorphism which occurs frequently in the homology of subposets of the partition lattice $\Pi_n.$

The isomorphism in question is a necessary, but not sufficient, condition for the existence of a lifting to the symmetric group $S_n,$ of the $S_{n-1}$-module involved. It has also been observed in certain deformations of the free Lie algebra. The topological explanation allows us to generate further examples in subposets of $\Pi_n.$ We show that, in these two contexts, it is often accompanied by an $S_{n}$-action on the $S_{n-1}$-module occurring in the isomorphism. A well-known example is the Whitehouse lifting of the homology of $\Pi_{n-1}.$

How can we determine which Schubert cell a given point on G/B is in from the vanishing pattern of its Plucker coordinates?

Different versions of this problem will be discussed, along with the problem of defining a Schubert variety/cell by the minimal number of equations/inequalities of the form "Plucker coordinate vanishes/does not vanish".

This is joint work with Andrei Zelevinsky. The paper is available from http://www-math.mit.edu/~fomin/papers.html

The Littlewood-Richardson problem in Schubert calculus is one of the main open problems in this area; it asks for a combinatorial description of the structure constants of the ring of polynomials with respect to its Schubert basis. It is not even known what formulation this rule might have. Having a Littlewood-Richardson rule in Schubert calculus is important because of the geometrical significance of the structure constants mentioned above (i.e., the number of points in a suitable triple intersection of Schubert varieties), and because it would enable us to establish various relations between these structure constants. The main ingredients for the classical Littlewood-Richardson rule (in one of its many versions) are: 1) skew tableaux, and 2) Knuth equivalence. In this talk we present analogs of these two ingredients in Schubert calculus, and then discuss a possible formulation of the Littlewood-Richardson rule.