Richard P. Stanley Seminar in Combinatorics

Let F_n (x) be an inversion polynomial. It is well known that

F_n (-1) = #{ sigma in S_n | sigma(1) < sigma(2) > sigma(3) < ... }

Our main result is a generalization of this identity to symmetric functions. We also generalize this identity to any type of permutation.

Our proof is based on a direct involution on a set of skew tableaux. Applications to tree-enumeration are given.

The r-majority action on a cyclic 0-1 sequence simultaneously replaces each digit by the majority digit of the 2r+1 (cyclic) interval it centers. The ultimate patterns obtained by iterating this action puzzled for a while its users - theoretical biologists. The talk will focus on the puzzle and its solution.

Consider first an analogous linear operation of averaging an entry over the 2r+1 segment it centers. When this operation is iterated on any initial numerical cyclic sequence, an 'exponential' decay to a fixed-value-sequence occurs, the fixed value being the average value of the initial sequence.

When the liberty of averaging is replaced by the more restrictive (and not linear anymore) requirement of forcing one to choose one of two possible values, namely the more frequent one, we obtain the r-majority operation. As one would expect in passing into a quantized realm, the fixed ultimate sequences are replaced by a well defined hierarchy of r+1 "energy" levels into which the ultimate patterns of the r-majority split, labeled 0,...,r , with the population of the levels decreasing from 0 to r (the top level having only the two alternating sequences, ...0101..., ...1010...).

We actually deal with this action on two way infinite sequences, and obtain all possible periodic (in time) patterns, all of which have period at most 2, and all but those of 0 energy are also space-periodic (with period bounded by 2r(r-1)).

This time periodicity property - The Period Two Property (p2p) - is studied for the iteration of the majority operation on an arbitray (possibly infinite) locally finite graph (here one transforms an 0-1 vertex-labeled-graph into another one by simultaneously relabeling each vertex by the majority digit of its neighbors, leaving it unchanged in case of a tie).

We come up with 'as wide as possible' class of graphs with this property. It turns out that the p2p is associated with two graph-theoretic properties, namely, a universal finite bound on the degrees and subexponential growth. Examples show that these two conditions are in fact indispensable in general. (A kind of "phase transition" seems to occur as you change your graph so that one of the above mentioned properties is lost).

Let T be a tournament of n vertices with a hamiltonian cycle gamma. The main result is that for any k, 3 leq k leq n, there exists a directed cycle C_k of length k with at most 4 arcs not in gamma. Depending on the relation between k and n even a larger intersection between C_k and gamma, denoted f(n,k), is guaranteed. In this work we characterize f(n,k).

New results on path enumeration in the poset of compositions of integers will be presented, along with the steps that lead to establishing the statement and proofs of these results. These steps include computer algebra experiments, combinatorial constructions and solving differential equations for generating functions.

Conjectures related to these questions will also be suggested.

In a joint work with A. Berenstein and H. Knight we study an involution which first appeared in the representation theory of reductive p-adic groups and affine Hecke algebras more than 10 years ago. More recently it was discovered to be related to quantum groups. This involution acts on the partitions of weights into the sum of positive roots of some root system. It can be defined in a quite elementary way, using only linear algebra (more specifically, representations of quivers).

Our main result is an unexpectedly explicit formula for the involution: after some change of coordinates its every component is given as the minimum of a system of linear forms. The proof has a strong combinatorial flavor; it uses the "Max Flow = Min Cut" type theorem from the theory of network flows, and the results of S. Poljak describing the maximal rank of a power of a matrix with a given pattern of zeros.

We present explicit Fourier transform formulas, with nice combinatorial interpretation involving eulerian numbers, for the center of Solomon's descent algebras for Coxeter groups of type An, Bn and some of the others. We illustrate how these results can be applied to card shuffling problems.

The genus series for maps is the generating series for embeddings of graphs on surfaces, with respect to the number of vertices, faces and edges. This series can be expressed as a character sum, and as an integral involving Hermitian complex matrices. Both representations of the genus series lead to combinatorial properties of maps. These maps arise independently in mathematical physics: for example, in connection with 2-dimensional quantum gravity, where vertex 4-regular maps are of particular interest.

There is also interest in a seemingly unrelated question of determining a set of symmetric functions which have the same connection coefficients as the elements of the class algebra of the symmetric group. I will show how there is a relationship between this and the maps problem, and how information about one may assist the other.

If L is the intersection lattice of a central arrangement A of hyperplanes then every element X of L of rank 2 produces a logarithmic 1-form f(X) with poles along the union D of the hyperplanes. A neccessary and sufficient condition is given for these forms to generate the whole module of logarithmic 1-forms with poles along D. A free graded resolution of this module is exhibited. We also discuss cohomology of the complex of logarithmic forms with certain differentials.

The talk provides a general account of renewal sequences and the transfer matrix method, illustrated in the example of counting Hamitonian cycles on grids of fixed width.

Let G^n denote the n-th power of a graph G under the cartesian product. We investigate the properties of graphs admitting a homomorphism f: G^(n+1) --> G^n, for a certain integer n. These questions arise in the study of the ultimate independence ratio of a graph and other related parameters. Our findings are the following:

Theorem 1: A graph G admits a homomorphism f: G^2 --> G if and only if it is homomorphically equivalent to a normal Cayley graph.

Theorem 2: Let G be an edge-transitive graph. If there exists an n such that there is a homomorphism f: G^(n+1) --> G^n , then there is a homomorphism g: G^2 --> G.

Theorem 3: For each n > 1, there exists a Cayley graph G such that there exists a homomorphism f: G^(n+1) --> G^n , but no homomorphism g: G^n --> G^(n-1).

Consider a polynomial ring in n variables and an ideal of it which contains an n-element homogeneous system of parameters of degree two. Eisenbud, Green and Harris conjecture that the h-vector of the factor of the ring by such an ideal is the f-vector of a simplicial complex. They illustrate their conjecture with the ideal generated by the squares of the variables.

We will see an infinite set of other examples which occur in the study of the Stanley ring of cubical polytopes. We show that the face ideal of the boundary complex of a convex cubical polytope is generated by homogeneous forms of degree two. Then we show a numbering of the vertices of an edge-orientable shellable cubical complex which allows us to construct a completely balanced triangulation of such cubical complexes. Finally we will use Stanley's result claiming that the h-vector of a completely balanced simplicial complex is the f-vector of another simplicial complex.

Most of the proofs presented will be geometric and combinatorial, and the constructions might be of interest even for those unfamiliar with the commutative algebraic background.

Let M_n denote the distribution of the fraction of black balls in a Polya urn after n balls were drawn (at each stage the extracted ball returns to the urn along with a new ball of the color drawn). If the initial urn contained A black and B white balls, the limit of M_n is well known to be the beta distribution. The beta integral follows:

          Gamma(A+B)   
      ----------------- Integral_0^1 x^{A-1} (1-x)^{B-1} dx = 1
      Gamma(A) Gamma(B)           

I will describe a Markov chain (similar to Polya urns) on the set of 
Young diagrams and use it to derive the following Selberg type integral:

      Integral_{Delta_m} Z_lambda (t; 1/theta)  times

      Product_{1 leq i < j leq m} |t_i - t_j|^{2 theta}  times

      Product_{j=1}^m t_j^{A-1} dt_1 ... dt_{m-1}

  =   
       Z_lambda (1,...,1; 1/theta)  
      ------------------------------  times 
      Gamma(N + A m + (m-1) m theta)

                      Gamma(lambda_j + A + (m-j) theta) Gamma(j theta + 1)
      Product_{j=1}^m ----------------------------------------------------  .
                                         Gamma(theta + 1)

Here Z_lambda are zonal (Jack) symmetric polynomials, and Delta_m
is the standard simplex 

      Delta_m = {t=(t_1,...,t_m) in R_+^m: t_1+...+t_m = 1}.

ABSTRACT: Finding formulas for the Todd class of a toric variety is an interesting problem partly because such formulas allow one to give formulas for the number of lattice points in an integral convex polytope. In this talk, we show that Todd class of a simplicial toric variety has a canonical expression in terms of products of torus- invariant divisors. The coefficients in this expression, which generalize the classical Dedekind sum, are shown to satisfy a reciprocity relatio which characterizes them uniquely.

We study juggling patterns where the juggler can only catch and throw one ball at a time (simple juggling), and patterns where the juggler can handle many balls at the same time (multiplex juggling). Using a crossing statistic, we obtain explicit q-enumeration formulas. Our techniques give a natural interpretation of the q-Stirling numbers of the second kind (equivalent to Garcia and Remmel's rook placements) and a bijective proof of an identity of Carlitz. This is joint work with Margaret Readdy.

In a joint work with A. Berenstein and H. Knight we study an involution which first appeared in the representation theory of reductive p-adic groups and affine Hecke algebras more than 10 years ago. More recently it was discovered to be related to quantum groups. This involution acts on the partitions of weights into the sum of positive roots of some root system. It can be defined in a quite elementary way, using only linear algebra (more specifically, representations of quivers).

Our main result is an unexpectedly explicit formula for the involution: after some change of coordinates its every component is given as the minimum of a system of linear forms. The proof has a strong combinatorial flavor; it uses the "Max Flow = Min Cut" type theorem from the theory of network flows, and the results of S. Poljak describing the maximal rank of a power of a matrix with a given pattern of zeros.

Abstract: Several years ago Peter Borwein considered questions concerning the nonnegativity of coefficients of a family of modular forms. In his empirical studies of these questions he found several fascinating sequences of polynomials which converge to the forms he was treating and possessed this same nonnegativity property. In this talk we shall extend some of Borwein's original conjectures and indicate their relationship to classical Rogers- Ramanujan type identities. Unfortunately (or perhaps fortunately) the most interesting conjectures still remain open.

This talk describes joint work with Simon and Crippa (ETH, Zurich) on a probability distribution connected with random graphs. The study of the moments of the distribution requires some old and some new results in q-series. The talk concludes with comments on related work by Dilcher, and open questions.

We describe how Kerdock codes over the binary field Z_2 and over the ring Z_4 of integers modulo 4 determine extremal sets of lines in real and complex Euclidean space with only 2 angles. Extraspecial 2-groups will serve as the bridge between discrete and Euclidean geometries. These connections involve a correspondence between binary orthogonal and symplectic geometries that is expressed as a map between binary symmetric m-by-m matrices and binary skew-symmetric (m+1)-by-(m+1) matrices.

I will discuss some surprising recent discoveries concerning the behavior of domino tilings of certain finite regions. In particular, there is a sharply-defined boundary between the portion of the tiling that is likely to be purely orderly and the portion of the tiling that is likely to be jumbled, and the asymptotic shape of the boundary is a perfect circle. Related to this behavior is a rational function in three variables whose coefficients have an unusual fractal structure.

No prior familiarity with domino tilings will be assumed.

In his 1990 paper "Non-intersecting paths, Pfaffians and plane partitions" John Stembridge mentions that the Pfaffian of a certain skew-symmetric matrix, whose entries are rational functions in the variables x_1,...,x_{2n}, has an evaluation which factors into linear factors. Interestingly, the numerator is exactly the evaluation of the Vandermonde determinant. Recent work has lead to a 2-variable generalization of this formula in which the numerator Vandermonde determinant is replaced by the skew-symmetrization of a certain monomial in the variables x_1,...,x_{2n}, and y_1,...,y_{2n}. More recently, a 3-variable generalization, involving x_1,...,x_{2n}, y_1,...,y_{2n}, and z_1,...,z_{2n}, has been discovered. We will present a sign-reversing involution proof of the 3-variable Pfaffian identity. We also discuss several variants of these identities, as well as some applications to symmetric function theory.

Abstract: I will discuss some surprising recent discoveries concerning the behavior of domino tilings of certain finite regions. In particular, there is a sharply-defined boundary between the portion of the tiling that is likely to be purely orderly and the portion of the tiling that is likely to be jumbled, and the asymptotic shape of the boundary is a perfect circle. Related to this behavior is a rational function in three variables whose coefficients have an unusual fractal structure.

No prior familiarity with domino tilings will be assumed.

(This will be identical to the talk given at MIT last Wednesday, except that some mistakes have been corrected [and the speaker will arrive on time!].)

Consider the following "game" KM(n), played on binary strings of length n: choose a random "1", and flip this bit together with all the bits to the right of it. What is the expected number of steps this game will take until it terminates with the zero-string? An upper bound of (n+1 choose 2) is easy, but better-than-linear lower bounds are surprisingly difficult to get. We obtain an Omega(n^2 / log(n)) lower bound.

The game KM(n) corresponds a random walk on the cube graph (with edges directed according to a Hamilton path), and thus to the simplex algorithm on the n-dimensional "Klee-Minty cube" with a RANDOM pivot rule. Thus its analysis leads to super-linear lower bounds for the RANDOM pivot rule on linear programs.

(Joint work with Bernd Gartner, Berlin)

The monograph "Convex Polytopes" by Branko Grunbaum, published in 1967, considerably revitalized its eponymous subject. Much of the book was focussed on the problems of determining which sequences (f_0, f_1, ..., f_{d-1}) could be the _f-vectors_ of d-polytopes P, that is, f_j = f_j (P) is the number of j-faces of P, either in general, or in some special classes. In fact, since many such problems seemed hopelessly difficult at that time, rather more restricted questions were often asked, such as bounds for some of the f_{j} in terms of others. As one consequence of the book, in 1970 the present speaker conjectured an exact description of the f-vectors of simplicial (or, equivalently, simple) d-polytopes.

Much subsequent research into polytopes was centred around this conjecture; it was finally confirmed around 1979--80. The sufficiency of the conditions of the conjecture (often now called _McMullen's_conditions_) was due to Billera and Lee, using a direct, if ingenious, geometric construction. The necessity was proved by Stanley; however, this involved deep results from algebraic geometry, namely the hard Lefschetz theorem applied to the cohomology ring of the toric variety associated with a rational simple polytope. There was thus considerable interest in finding a proof of the necessity which stuck more closely to polytope theory. In 1992, the present speaker found such a proof; it used his own recently invented _polytope_ _algebra_, which was originally devised to investigate translation-invariant valuations on polytopes, such as volume, surface area and the Euler characteristic.

Even more recently, it has been becoming clear that a great deal of the complicated machinery of the polytope algebra can itself be discarded. For one thing, the construction of the polytope algebra can be simplified. But, even more usefully, only a certain amount of the framework of the polytope algebra appears to be needed. In the talk, we describe this new approach.

We describe several algorithmic results concerning lattice point counting. These results include a polynomial time algorithm for counting lattice points in polytopes in a fixed dimension, a polynomial time algorithm for counting lattice points in totally unimodular polytopes given by their vertices, and a polynomial time reduction of the computation of the highest Ehrhart coefficients to the volume computation. The exposition is centered about Brion's formula for exponential sums over a polytope which reduces the original problem to "counting" lattice points in the supporting cones at the vertices of the polytope. The other ingredient is a procedure for "resolution of singularities", that is a representation of a given rational polyhedral cone as a linear combination of unimodular cones.

The restricted connectivity and restricted fault diameter are two reliability measures for interconnection networks, where we assume that all the neighbors of any vertex do not fail at the same time. By computing these two parameters for some well-known network families, we reaffirm that "These good network families are really good." Such recently proposed graph theoretical concepts as container and wide diameter prove to be useful in this investigation. Some open problems will also be presented.

In 1930, O. H. Keller conjectured that any tiling of Euclidean n-space by cubes always contains two cubes that meet in a complete n-1 dimensional facet. This was disproved in 1992 when Jeff Lagarias and I found a 10-dimensional counterexample. I will trace the history of Keller's conjecture for nearly 100 years, from a 1896 question of Minkowski on simultaneous approximation, of which Keller's conjecture is a generalization, through Hajos' resolution of Minkowski's conjecture via abelian groups, then Szabo's reduction of Keller's conjecture to a graph theory question that led to the counter-example and finally to a generalization of the counter-example, which appears to be related to coding theory.

For a polyhedral subdivision D of d-dimensional Euclidean space, we consider piecewise polynomial functions on D which are differential of order r. These functions are known as "splines" and are used in many areas of mathematics and applied mathematics.

For a fixed r, the set of all r-splines on D is a module over the polynomial ring in d variables over the reals. The goal of this work is to study to what extent the algebraic properties of the module are determined by the topological and combinatorial properties of D. In particular, we will describe a large class of complexes for which freeness or homological dimension of the module is a topological or combinatorial property. We will also indicate how the geometry of D comes into play in the general case.

Starting with a lattice polytope Q, we construct a non-linear system of equations in C^N (N is the number of 1-dimensional edges of Q). The associated algebraic set M of common zeros equals a union of planes encoding the several possibilities of splitting Q into a Minkowski sum of lattice polytopes. Moreover, even if M consists of a single point only, this algebraic set may carry a richer, non-reduced ring structure. This reflects the fact that certain lattice polytopes are splittable into a non-trivial Minkowski sum of non-lattice polytopes only.

On the other hand, each polytope Q defines an affine toric variety Y. We construct an algebraic family with special fiber Y by regarding the cone C(Q) of Minkowski summands of positive multiples of Q and its tautological extension. Eventually, it is the algebraic set M which arises as base space of the maximal subfamily that can be regarded as being contineous (the versal deformation of Y).

The discrete version of Minkowski's existence theorem is concerned with the existence and uniqueness of polytopes whose faces have preassigned areas and normals. Various extensions and open problems will be presented.

This is a continuation of the April 11 talk, but no knowledge of the previous material will be assumed. We shall discuss an application of the theory of flows in networks and of some recent results by S. Poljak to an explicit formula for the so-called multisegment duality for the representations of quivers of type A. As time allows, more recent results on the multisegment duality will be presented, obtained by the author jointly with A. Berenstein and S. Fomin.

Wilkinson, Cryer, and Kahan asked whether Gaussian elimination with complete pivoting can yield a growth factor bigger than n. It was long thought that Hadamard matrices might serve as examples. Non-Hadamard examples were recently found by Gould with a small correction by the speaker. Nevertheless the question remains open whether a Hadamard example can be found. We will discuss the difficulty of finding an elegant proof that a 12x12 example can not be found. We will then challenge the combinatorics community to find a general proof. (We will review the elementary numerical analysis so that no special prerequisites are assumed for this talk.)

The poset of irreducibles is a extension of Garrett Birkhoff's classic construction of finite distributive lattices from their subposets of join-irreducibles. To describe arbitrary lattices, both the join-irreducibles and meet-irreducibles must be considered. The poset of irreducibles presents a lot of information about a lattice, often in a form much more compact than the original lattice. This talk will survey the basic ideas underlying the poset of irreducibles and will describe applications of these ideas in lattice theory, combinatorics, context analysis and biology.

The Grassmann-Cayley (GC) algebra has proven to be a useful setting for proving and verifying geometric propositions in projective space. A GC algebra is essentially the exterior algebra of a vector space, endowed with the natural dual to the wedge product, an operation which is called the meet. A geometric identity in a GC algebra is an identity between expressions $P({\cal A},\vee,\wedge)$ and $Q({\cal B},\vee,\wedge)$ where ${\cal A}$ and ${\cal B}$ are sets of anti-symmetric tensors, and $P$ and $Q$ contain no summations. The idea of a geometric identity is due to Barnabei, Brini and Rota.

We show how the classic theorems of projective geometry such as the theorems of Desargues, Pappus, Mobius, as well as well as several higher dimensional analogs, can be realized as identities in this algebra.

By exploiting properties of bipartite matchings in graphs, a class of expressions, called Desarguean Polynonials, is shown to yield a set of dimension independent identities in a GC algebra, representing the higher Arguesian laws, and a variety of theorems of arbitrary complexity in projective space. The class of Desarguean polynomials is also shown to be sufficiently rich to yield representations of the general projective conic and cubic.

Combinatorial differential manifolds (CD manifolds) were introduced by Gelfand and MacPherson as a combinatorial analog to differential manifolds. Their application led to a combinatorial formula for the Pontrjagin classes of a smooth manifold, and they show promise for a number of applications in geometry and topology. Essentially, a CD manifold is a simplicial complex together with a collection of oriented matroids which play the role of tangent spaces.

An open problem in the very new theory of CD manifolds is whether all CD manifolds are topological manifolds. This can be made into a purely combinatorial problem on the geometry of oriented matroids. We will discuss progress on the two equivalent questions:

1. Is every CD manifold a PL manifold?

2. If M is an oriented matroid, is every triangulation of M a PL sphere?

We describe some classes of sub-posets of the lattice of set partitions and outline the relevance of their combinatorial and homological properties in the study of spaces of polynomials and polynomial systems which are described by imposing certain conditions on their (common) roots --- the complement of the descriminant being the well studied and well known case. The connection is provided by the theory of arrangements of linear subspaces in complex n-space. We will show how to use combinatorial methods and representation theoretic methods to provide a uniform approach to some problems arising in the study of these spaces. Generalizations of results of Orlik and Solomon for the case of hyperplane-arrangements will be provided.