# MIT-Harvard-MSR Combinatorics Seminar

## Schedule 1993 Fall

Organizer: Jim Propp

### Wednesday, September 15, 4:30 p.m.; MIT, room 2-338

(note new time!)

Christian Krattenthaler (Vienna)

The Major Counting of Nonintersecting Lattice Paths and Generating Functions for Tableaux

We develop a theory of counting nonintersecting lattice paths by the major index and generalizations of it. As application we prove refinements of two theorems in plane partition theory, the Bender-Knuth and MacMahon (Ex-)Conjectures, respectively.

### Wednesday, September 22, 4:30 p.m.; MIT, room 2-338

(note new time!)

Marcel Wild (M.I.T.)

An enumerative principle of exclusion

Let M be a finite set and P a "property" enjoyed by some subsets X of M. With N(P) we denote the number of X in 2^M with property P. For any properties P_1,...,P_n let C=C(P_1,...,P_n) be the family of those X in 2^M which enjoy {\it all} properties P_i. According to the well known principle of "inclusion-exclusion" one has

|C| = N(P_1 wedge ... wedge P_n) =
sum_{1 <= i <= n} N(P_i)
- sum_{1 <= i < j <= n} N(P_i vee P_j)
+ ...

Unfortunately 2^n-1 many terms N(P_i vee P_j vee ... vee P_k) need to be added and substracted from each other on the righthand side. Moreover, sometimes there is no easy way to compute the terms themselves. We shall present an often better method for determining |C|, which is based on a principle of "exclusion". It is demonstrated for arbitrary _closure_systems_ C (which fit a lot of applications in Algebra and Combinatorics), but we believe that variations would apply to other counting problems as well.

### Friday, September 24, 4:15 p.m.; MIT, room 2-338

Richard Stanley (M.I.T.)

A symmetric function generalization of the chromatic polynomial of a graph

Let G be a finite graph. We will define a symmetric function X_G = X_G(x_1,x_2,...) which generalizes the chromatic polynomial of G. Classical results on chromatic polynomials dealing with Mobius functions and acyclic orientations can be extended to X_G. For certain graphs G, the expansion of X_G in terms of elementary symmetric functions is related to the theory of Hecke algebras and Kazhdan-Lusztig polynomials.

### Wednesday, September 29, 4:35 p.m.; MIT, room 2-338

(note REALLY new time!)

Euler, Bernoulli and Springer numbers of Coxeter groups and of Morsification spaces

The classical sequence 1,1,1,2,5,16,61,272,1385,... occurs in many combinatorial problems. It has recently been discovered that the same sequence governs the topological classification of Morsifications of simplest degenerate critical points of smooth functions. This observation leads to the generalizations of the Euler and tangent numbers which can be associated with any simple Lie algebra or even to any Coxeter group. This gives new information even in the classical case (corresponding to the sl(n) algebras and to the symmetries of simplices), for instance new congruences for the classical Euler and Bernoulli numbers, generalising those found by Kummer, von Staudt and Knuth.

### Combinatorics Seminar Northeastern University, Fall 1993

The seminars are usually Wednesday at 1:30 p.m. in 509 Lake Hall.

Schedule

Sept. 22 Roy Meshulam, Technion, Haifa On subsets of abelian groups with no 3-term arithmetic progression Vladimir Retakh (visiting Harvard) Non-commutative determinants and their combinatorics Klaus Altmann (M.I.T.) Deformation theory of toric varieties

### Friday, October 1, 4:15 p.m.; MIT, room 2-338

Susanna Fishel (Southern Connecticut State)

The combinatorics of certain entries in the two-parameter Kostka matrix

Kirillov and Reshetikhin introduced rigged configurations as a new way to calculate the entries K_{\lambda\mu}(t) of the Kostka matrix. Macdonald defined the two-parameter Kostka matrix whose entries K_{\lambda\mu}(q,t) generalize K_{\lambda\mu}(t) . I use rigged configurations and a formula of Stembridge to provide a combinatorial interpretation of K_{\lambda\mu}(q,t) in the case where \mu is a partition with no more than two columns. In particular, I show that in this case, K_{\lambda\mu}(q,t) has nonnegative coefficients.

### Wednesday, October 6, 4:35 p.m.; MIT, room 2-338

Gert Almkvist (KTH)

From plane partitions to Fermat's last theorem: some excerpts from the notebook of a Maple-user

Attempting to find "exact" asymptotic formulas for the number of plane partitions various byproducts are obtained: generalized Dedekind sums, values of Bernoulli polynomials at rational points. Wilf's conjecture is proved.

### Friday, October 8, 4:15 p.m.; MIT, room 2-338

Benoit Larose (Universite de Montreal)

Products of finite posets and the fixed point property

If P and Q are finite posets with the fixed point property, does the product PxQ also have this property? In 1985, E. Corominas introduced the notion of "projective" (idempotent trivial) poset to attack this problem: the fixed point property is preserved under products if the so-called "minimal automorphic" posets are projective. We prove that the projection property is equivalent to quasiprojectivity (tightness) for posets of arbitrary cardinality; universal algebraic methods can then be used to determine if a poset is projective. We relate Corominas' conjecture to the notion of representability by irreducibles in varieties of ordered sets.

### Wednesday, October 13, 4:35 p.m.; MIT, room 2-338

Michel Goemans (M.I.T.)

Minimizing submodular functions over families of sets

Submodular set-functions arise in a variety of fields, including combinatorics, probability and geometry. Classical examples include the rank function of a matroid, the cuts in a directed or undirected graph, the probability that a subset of events do not simultaneously occur, or the logarithm of the volume of the parallelepiped spanned by a subset of linearly independent vectors.

We consider the problem of characterizing the minimum of a submodular function when the minimization is restricted to a family of subsets. We show that, for many interesting families, the problem can be reduced to a sequence of submodular function minimizations over all subsets. Our results apply, for example, to the families of odd cardinality subsets or even cardinality subsets, leading to a characterization of the minimum even cut in a graph. These results generalize and unify many classical results in combinatorial optimization.

This is joint work with V.S. Ramakrishnan.

### Friday, October 15, 4:15 p.m.; MIT, room 2-338

Rekha Thomas (Cornell)

Grobner basis methods for integer programming

Consider the family of integer programs of the form

Min cx : Ax = b, x in N^n

obtained by varying the right hand side vector b but keeping A and c fixed. We describe a unique minimal test set for this family, called the reduced Grobner basis. Algebraically, this test set arises as the reduced Grobner basis of the toric ideal associated with A. We present a combinatorial version of Buchberger's Grobner basis algorithm for this class of problems.

As a special case we discuss the perfect f-matching problem on the complete graph K_n. An explicit description is given of test sets for all graphs with eight vertices or less. We briefly indicate the role of the above test sets in studying triangulations of the second hypersimplex, that is, the convex hull of columns of the vertex-edge incidence matrix of K_n.

### Wednesday, October 20, 4:35 p.m.; MIT, room 2-338

Susan Landau (U. Mass. Amherst)

Embedding linkages on an integer lattice

Using links and joints, one can build an "erector set" type linkage in which angles are free to change, but lengths and collinearity properties are fixed. A problem in computer-aided design raised the question of when such a linkage can be embedded in an integer lattice, assuming one is allowed to shift lengths by epsilon, but collinearity properties must be preserved. What is the minimal epsilon that will allow an embedding where each of the edges has its endpoints on integer vertices in the lattice?

We show here that the question of whether a linkage can be embedded on the integer lattice is NP-complete, an unhappy situation. But all is not lost: for applications, it is quite reasonable to assume that lengths are bounded, as are the number of "co-incident" polygons. With these caveats, we show there is a polynomial time solution to the problem.

We note that the problem has some nice ties to number theory: the linkage can be embedded only if each of its links can, and this can happen if and only if each of the links has a length whose square can be written as the sum of two squares. We explore these connections further in the paper.

### Friday, October 22, 4:15 p.m.; MIT, room 2-338

Karen Collins (Wesleyan)

Chromatic difference sequences

Define G to be stable if the normalized chromatic difference sequence of G is equal to the normalized chromatic difference sequence of G times G, the Cartesian product of G with itself. Zhou has shown that circulants and Cayley graphs are stable. The chromatic difference sequence of a stable graph G begins with omega terms equal to alpha where omega is the clique number and alpha is the independence number of the graph. If G contains partitionable graph H with the same clique size, then the omega+1st term is at least alpha(G)/alpha(H). For stable graphs of large odd girth, this gives upper bounds on the independence ratio of the graph which agree with previously known lower bounds. We also prove nice bounds on the independence ratios of circulants.

### APPLIED MATHEMATICS COLLOQUIUM, MONDAY, November 1, 1993

4:15 p.m., Room 2-105

Professor C. Itzykson, Service de Physique Theorique, Saclay, France and Department of Physics, MIT

TRIANGULATIONS

Abstract: Finite cell decompositions of surfaces (or "fat graphs") appear in the perturbative expansion of matrix models. The latter yield tau-functions for discrete or continuous integrable systems. Suitable specializations solve combinatorial problems on the moduli space of algebraic curves of given genus such as virtual characteristic (Harer, Zagier, Penner) or intersection numbers of stable characteristic classes (Witten, Kontsevich). The same data record unramified arithmetic coverings of P_1/{0,1,infinity}. This gives an action of Gal(Qbar / Q) on fat graphs (Belyi, Grothendieck, Voevodsky, Shabat). We shall attempt to give an overview of the (few) results and (many) open problems in this area.

Refreshments will be served from 3:45 p.m. in Room 2-349

### Wednesday, November 3, 4:35 p.m.; MIT, room 2-338

Francesco Brenti (Universita di Perugia)

Some combinatorial properties of Kazhdan-Lusztig polynomials

Our aim in this talk is to give a simple, nonrecursive, combinatorial formula for any Kazhdan-Lusztig polynomial of any Coxeter group W, and to study some consequences of it. The main idea involved in the proof and statement of this formula is that of extending the concept of the R-polynomial to any (finite) multichain of W (so that, for multichains of length 1, one obtains, apart from sign, the usual R-polynomials). Our main result expresses the Kazhdan-Lusztig polynomial of any Bruhat interval as the sum of the R-polynomials of its multichains.

We then use our main result to obtain combinatorial formulas for each coefficient of any Kazhdan-Lusztig polynomial. We use one of the special cases to characterize in purely combinatorial terms those Bruhat intervals whose Kazhdan-Lusztig polynomial equals the g-polynomial (as defined by R. Stanley) of the dual interval. As a consequence of it we obtain explicit formulas for the Kazhdan-Lusztig polynomials of intervals which are lattices. We also use our main result to obtain upper and lower bounds for the coefficients of Kazhdan-Lusztig polynomials. In particular, we verify a conjecture of Lascoux- Schutzenberger for all sufficiently long intervals. Finally, we briefly sketch how it is possible to obtain analogues of all the results in the talk for inverse Kazhdan-Lusztig polynomials.

### Friday, November 5, 4:15 p.m.; MIT, room 2-338

Alyson Reeves (Brandeis)

On the radius of the Hilbert scheme

Though the Hilbert scheme parametrizing subschemes of projective n-space has been the object of much investigation, its structure remains largely a mystery. This talk will combine elements from combinatorics, Grobner basis theory, and algebraic geometry to bound the component-wise radius of the Hilbert Scheme.

### Wednesday, November 10, 4:35 p.m.; MIT, room 2-338

Algebraic structures associated to the Young-Fibonacci lattice

The Young-Fibonacci lattice is an interesting example of a differential poset, of which another fundamental example is Young's lattice of partitions ordered by inclusion of Young diagrams. With Young's lattice are naturally associated the symmetric groups and the ring of symmetric functions. In this talk, I construct a Young-Fibonacci analogue of

1. the group algebra of the symmetric group,
2. the ring of symmetric functions, and
3. the character ring of the symmetric group.

### Discrete Math Dinner, November 10, Sol Azteca

We will be ordering and paying for dinners individually; graduate students will get a 20% discount.

### Friday, November 12, 4:15 p.m.; MIT, room 2-338

Extremal problems for the Mobius function

In the vein of recent work of Sagan, Yeh and Ziegler, we study extremal problems connected with the Mobius function of three families of subsets from O_n, the lattice of faces of the n-dimensional octahedron: lower order ideals, intervals of rank-selections, and arbitrary rank-selections. In each case, we illustrate the techniques used to determine the extremal configurations. Also, we briefly describe other results and present/future research.

### Wednesday, November 17, 4:35 p.m.; MIT, room 2-338

Phil Hanlon (Michigan)

Partitions with restricted block size, Lie k-algebras and the Lie(k) operad

In this lecture we will combine three very different bodies of recent work, one combinatorial and two algebraic. The first is the study of the posets of partitions where every block size is congruent to 1 mod k+1. The second is the study of certain algebraic structures called Lie k-algebras and Liebnitz k-algebras. The third is the theory of Koszul duality for operads. Although we will not assume any background knowledge in these subject areas we will try to give enough of an idea about them to demonstrate some of their close connections.

### Friday, Nov. 19, 4:15 p.m.; MIT, room 2-338

Laurent Habsieger (Bordeaux and UQAM)

Lower bounds for q-ary coverings by spheres of radius one

Let C be a q-ary covering code with covering radius one. We give lower and upper bounds for the number of elements of C that lie in a fixed subspace of {0,...,q-1}^n. These inequalities lead to lower bounds for the cardinality of C that improve on the sphere covering bound. More precisely we show that, if (q-1)n+1 does not divide q^n and if (q,n) is not in {(2,2),(2,4)}, the sphere covering bound is never reached. This enables us to characterize the cases where the sphere covering bound is attained, when q is a prime power. We also present some improvements of the already known lower bounds for binary and ternary codes.

### Wednesday, December 1, 4:35 p.m.; MIT, room 2-338

Itaru Terada (University of Tokyo and M.I.T.)

An identity generalizing the length-MAJ symmetry and the variety of N-stable flags

D. Foata and M.-P. Schutzenberger showed that the number of permutations in S_n with length i and major index j is equal to the number of those with length j and major index i. The two-variable generating function of this distribution is expressed as a sum of

K_{lambda,(1^n)}(q) . K_{lambda,(1^n)}(t)

for all partitions lambda of n.

Generalizing this identity, we give a combinatorial interpretation of the sum of

K_{lambda,mu}(q) . K_{lambda,(1^n)}(t),

for any fixed partition mu of n. This interpretation is different from that in terms of Lascoux-Schutzenberger's charge and the major index.

In showing the generalized identity, we look at the variety of flags in C^n that are stable under a nilpotent matrix N. We note that Staltenstein's partition of this variety into affine spaces is explicitly achieved by taking the N-stable parts of Schubert cells.

### Brandeis-Harvard-MIT colloquium, Thursday December 2, 4:30pm

In Goldsmith Rm 317, at Brandeis. Tea is a 4:00. There will be a dinner afterwards.

Bernd Sturmfels

Applications of Toric Ideals

### Friday, December 3, 4:15 p.m.; MIT, room 2-338

Sergey Fomin (M.I.T.)

Lattice paths, braids, and reduced decompositions

Recently, a combinatorial interpretation of stable Schubert polynomials in terms of braid configurations was found, based on a well-known geometric interpretation of the Yang-Baxter equation. In the particular case of 321-avoiding permutations, these polynomials are the skew Schur functions. Each of corresponding braid configurations breaks up into two families of paths which are exactly the Gessel-Viennot paths for the two Jacobi-Trudi determinants. An alternative description of this construction relates skew Schur functions to reduced decompositions in the Temperley-Lieb algebra. Generalizations and applications include super-Schur functions, binomial determinants, and the $P$- and $Q$-Schur functions.

This is a joint work with X. G. Viennot.

### Friday, December 10, 4:15 p.m.; MIT, room 2-338

Mark McConnell (M.I.T.)

Convex polytopes and intersection cohomology of toric varieties

McMullen's conjecture characterized the f-vectors of simplicial convex polytopes Delta. Stanley's proof of (one direction of) this conjecture used the cohomology H^*(X, C) of the toric variety X associated to Delta. Let omega in H^2(X, C) be the Lefschetz hyperplane class. Key facts for Stanley's proof were that the quotient H^*(X, C)/(omega) is a graded ring generated by H^2.

When Delta is an arbitrary rational convex polytope, one can ask about the analogues in intersection cohomology: is IH^*(X, C)/(omega) a ring, and is it generated by IH^2 ? I will discuss preliminary results on these questions, as well as approaches for computing the intersection cohomology.

## Archive

All announcements since Fall 2007 are in the Google Calendar