Richard P. Stanley Seminar in Combinatorics

In this talk, I will present a combinatorial approach to nonlinear systems of differential equations in control theory. A typical example is the following equation associated to a simple nonlinear circuit:

                                         2
                     y'(t) = a y(t) + b y (t) + u(t).
        

The function u(t) is the input, or forcing term, y(t) is the output. Usually solutions of such systems with forcing terms are represented by Volterra type expansions. The use of functional expansions has been energetically studied in the last forty years in engineering as well as in physics.

With Pierre Leroux (LACIM, UQAM, Montreal), we propose a combinatorial approach. To each system, we associate certain families of combinatorial objects called "increasing weighted colored trees", "weighted paths" and "histories". The determination of the coefficients of the functional expansion becomes a combinatorial problem: compute the sum of the weights of certain families of trees or paths. This approach gives very efficient computation algorithms. Another interest is theoretical, by giving "combinatorial" proof of some general facts and formulae, or by leading to the introduction of certain approximants of the solutions of general systems by solutions of bilinear systems.

Heaps of pieces provide a geometrical interpretation to the so-called Cartier-Foata monoids defined with partial commutation rules. Polyominoes (or animals) are connected unions of cells drawn on a planar lattice and related to statistical physics.

In this talk (joint work with Mireille Bousquet-Melou), we show the use of heap theory in the enumeration of certain families of polyominoes: skew Ferrers diagrams and directed convex polyominoes. Related topics are Mobius inversion, q-Bessel functions, Ehrhart polytope theory and braids.

Abstract of Gabrielov's talk: Sandpile and avalanche models of failure were introduced recently (Bak et al., 1987, and an avalanche of publications with references to this paper) to simulate processes of different nature (earthquakes, charge density waves, forest fires, etc., including economics) characterized by self-organized critical behavior. Statistical properties of an important class of these models, abelian sandpiles (Dhar, 1990) and abelian avalanches (Gabrielov, 1992), can be investigated analytically due to an abelian group acting on the phase space.

It is shown that the distribution of avalanches in a discrete, stochastic abelian sandpile model is identical to the distribution of avalanches in a continuous, deterministic abelian avalanche model with the same redistribution matrix and loading rate vector. For a symmetric redistribution matrix, recurrent formulas for the distribution of avalanches in the abelian avalanche model lead to explicit expressions containing invariants of graphs known as Tutte polynomials. In the general case, an analog of the Tutte decomposition is suggested for matrices and directed graphs, and the corresponding expressions for the distribution of avalanches in terms of directed tree numbers of a directed graph are found. New combinatorial identities for graphs and directed graphs are derived from these formulas.

A probabilistic interpretation of the Riemann zeta function has been given by Golomb, but his interpretation of zeta(s) has the disatvantage that one needs a different sample space for each s > 1. We give another stochastic process, which gives a stochastic model for zeta(s) simultaneously for all integer s > 1. The idea is to develop a suitable concept of infinite Mobius inversion.

Ulam's searching problem is to determine the minimal number of yes-no queries to find an unknown integer between 1 and 2^20 if at most some given number e of the answers may be lies. Recently published papers have solved the problem for the cases e = 1,2,3 and 4. By relying more heavily on a reference published in 1968 we solve the problem for all values of e. (Joint work with ER Berlekamp and JP Karim)

Poset games, Wythoff games, ... Why are combinatorial games hard? The Divide & Conquer approach for bridging the complexity gap between Nim and chess. What's an efficient strategy? Spectra of inefficiencies... Open problems.

A variety of applied problems, from telephone encryption, through the study of the energies of nuclear collisions, through study of the zeroes of the zeta function, lead to the study of the eigenvalues of random unitary, orthogonal, or symplectic matrices. These can be understood using Schur functions and the Brauer algebra. This is joint work with Mehrdad Shahshahani.

Tolerance orders and tolerance graphs arise as a generalization of interval orders and interval graphs in which some overlap of intervals is tolerated. They can be used to model scheduling problems where some overlap between scheduled events is permitted. The classes of bounded, proper and unit tolerance orders and graphs have been studied by other authors. Here we introduce two-sided versions of these classes. We show that {\em all} the classes are identical for bipartite ordered sets and give some examples to show that the classes differ in the nonbipartite case. We also give an algorithm for determining whether a bipartite ordered set is in these classes, and if so finding a representation of it.

This is joint work with Ken Bogart at Dartmouth College.

Baxter operators are operators that satisfy an identity which is roughly the q-analogue of integration by parts. We shall develop the combinatorial properties of these operators and give some combinatorial and probabilistic applications.

Consider two solid objects (convex bodies, to be precise) in ordinary Euclidean 3-space. Suppose we are told that one of these bodies always (in all directions) casts larger (in area) shadows than the other. Does it follow that the body which casts the larger shadow is larger in volume? The answer here is an easy NO.

There are numerous similar counter intuitive results concerning ordinary bodies in Euclidean 3-space. Some of these will be presented. A number of long standing open problems will also be presented. These problems (while apparently not easy) can all be explained to the `man in the street'.

If G is any graph with at least six vertices, then either G or its complement must contain a triangle in which two vertices have the same degree. We say that a triangle has the Ramsey repeat degree property. This talk will describe how this result generalizes. For instance: One might naively expect that every graph must have the Ramsey repeat degree property - all bipartite graphs do, but the 4-clique does not. There are natural Turan bounds, theorems about independent sets, results about the total edge discrepancy of a graph, and questions.

I will prove the following conjecture by Winkler and Arasmith: For any independent set O in a grid, there is a second independent set X such that there is at least one point in X adjacent to every point in O. Or equivalently, for every maximal independent set in a grid, there is a second, disjoint maximal independent set.

Let L be a finite ranked lattice with minimal element 0, maximal element 1, rank function rho(x), and Mobius function mu(x)=mu(0,x) for x in L. The characteristic polynomial of L is chi(L,t) = sum_{x in L} mu(x) t^{rho(1)-rho(x)}. For many interesting lattices, chi(L,t) factors over the non-negative integers. We will survey various ways of proving such results, using lattices connected with Coxeter hyperplane arrangments as examples. (These arrangments are obtained by using hyperplanes perpendicular to root systems generating Coxeter groups.) Techniques may include using broken circuit complexes, supersolvability, atom decision trees, signed graph colorings, Earhart polynomials of polytopes, free modules of derivations, and results about the all-reflections length function on a Coxeter group.

The talk will be about the general (with q) Macdonald constant term conjecture which was proved recently (for reduced root systems) by means of a new approach to the harmonic analysis on symmetric spaces based on the affine Hecke algebras.

Hadamard matrices offer a short route to the Matthieu groups M_12 and M_24.

The formula for the Catalan numbers is usually obtained by a reflection argument. We consider a class of random walks on a lattice, introduced by Gessel and Zeilberger, for which the same reflection principle can be used to count the number of k-step walks between two points which stay within a Weyl chamber. For many such ``reflectable'' walks, we compute determinant formulas for walk-numbers and their generating functions. We also show that many of these walk-numbers correspond to the multiplicities of irreducibles in the kth tensor power of certain Lie group representations associated to the walk-types, including the defining representations of the classical groups. This is joint work with Peter Magyar.

Certain optimization problems on graphs are analagous to the isoperimetric problem of Greek geometry. Discrete (as well as continuous) isoperimetric theorems are notoriously difficult to prove, but we will show how a standard method, called compression, can be developed so as to give transparent proofs of many results. Compression, it turns out, is a discrete analog of Steiner symmetrization.

Julian West conjectured that the number of permutations of {1,2,...,n} that can be reduced to the identity permutation by two applications of the ``stack-sorting'' operation is 2(3n)!/(n+1)!(2n+1)!. West's conjecture was proved by Doron Zeilberger. Zeilberger used a combinatorial decomposition to find a recurrence for counting West's permutations by an additional parameter. The recurrence is easily converted into a functional equation for a generating function, but unfortunately the functional equation is of a type that no one knows how to solve. Zeilberger guessed that the solution was algebraic and with 10 hours of computer time found empirically a polynomial equation that the generating function satisfied. He then verified that the solution of this polynomial equation did indeed satisfy the functional equation.

I will describe a simplified version of Zeilberger's approach that does not require a computer, and that also yields a generalization of West's formula for certain multiset permutations.

Abstract-polytopes are partially ordered structures which generalize the notion of polyhedra in a combinatorial sense. This concept includes all of the classical regular polytopes as well as many well-known configurations. Chiral polytopes are abstract polytopes with rotational symmetry which lack reflexive symmetry. We use a technique developed by Schulte and Weiss which employs hyperbolic geometry to derive abstract polytopes with cells isomorphic to maps of type {6,3,4} and {6,3,5} to complete the classification of toroidal polytopes of rank 4 which can be realized by this construction. Of particular interest is a newly discovered flat polytope of type {6,3,4}.

Let the group G = union G_n be the union of a sequence of its finite or compact subgroups G_n . The infinite symmetric group S_infinity and the unitary group U(infinity) are important examples. Representation theory of such groups can be effectively studied in terms of the Bratteli diagram D = union D_n which is a countable ranked poset describing the restrictions of irreps of approximating groups.

The main problem is to find factor - representations of G (irreducible representations are far less interesting). It reduces to that of counting the number of saturated chains for any interval in D .

A number of examples related to Young lattice and to Young - Fibonacci lattice will be discussed in the talk. In particular, the remarkable Robinson - Schensted - Knuth algorithm and Hook Walk procedure arise in the character theory of the group S_infinity .

The usual Robinson-Schensted correspondence gives a bijection from permutations of a certain alphabet to pairs of same-shape standard Young tableaux. A generalization of Schensted gives a bijection from permutations with repetitions to pairs of tableaux of the same shape, one column-strict, one standard. The latter may be viewed from the standpoint of representation theory as giving the decomposition of the action of the group GL(n) \times S(n) on the k-fold tensor power of the natural representation \otimes ^{k} \square_{GL(n)} . Berele's correspondence, originally conceived to explain a similar representation theoretic phenomenon for the symplectic group, gives a bijective map from the set of words on a certain alphabet of size 2n to pairs of tableaux, one "symplectic", the other "up-down".

S.\ Fomin gave a two-dimensional pictorial presentation of the usual Robinson-Schensted correspondence. This presentation enhances the understanding of certain properties of R-S, and also allows it to be naturally generalized in a number of different ways. Our aim is to give a similar presentation of Berele's algorithm. The eventual goal (which has yet to be fully realized) is to explain more clearly the combinatorics of up-down tableaux.