MIT-Harvard-MSR Combinatorics Seminar

Schedule 1993 Spring

Organizer: Jim Propp


MIT, ROOM 2-105

Xavier Gerard Viennot

Nonlinear controlled systems and 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:

                     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.

Wednesday, February 10, 4:15 p.m.; MIT, room 2-338

Xavier Gerard Viennot (Bordeaux I)

Heaps of segments and q-enumeration of convex polyominoes

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.

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

Although Andrei Gabrielov's two talks next week (Feb. 10 at Northeastern and Feb. 12 at MIT) have the same title and abstract, they will not be identical and will stress different aspects of his theory (although they will definitely have some repetitions to make them formally independent).

Andrei Gabrielov (visiting Cornell)

Avalanches, sandpiles and Tutte decompositions

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.

Wednesday, February 17, 4:15 p.m.; MIT, room 2-338

Anders Bjorner (KTH)

Subspace arrangements, linear decision trees and Mobius functions

Friday, February 26, 4:15 p.m.; MIT, room 2-338

Gian-Carlo Rota (MIT)

A probabilistic interpretation of the Riemann zeta function

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.

Monday, March 8, 4:00 p.m.; MIT LCS, building NE43, room 518 (LCS)

(note unusual location of talk!)

Ray Hill (University of Salford)

Searching with Lies: The Ulam Problem

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)

Wednesday, March 10, 4:15 p.m.; MIT, room 2-338

Aviezri Fraenkel (Weizmann Institute, visiting U.\ of Penn.)

Some of my favorite problems in combinatorial game theory

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.

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

Persi Diaconis (Harvard)

The combinatorics of Haar measure

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.

Wednesday, March 17, 4:15 p.m.; MIT, room 2-338

Ann Trenk (Wellesley)

Bipartite Bitolerance Orders

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.

Wednesday, April 7, 4:15 p.m.; MIT, room 2-338

Gian-Carlo Rota (MIT)

The theory of Baxter algebras

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.

Friday, April 9, 4:15 p.m.; MIT, room 2-338

Moved to April 30

Andrew Gleason

Hadamard matrices and the Matthieu groups

Wednesday, April 14, 4:15 p.m.; MIT, room 2-338

Erwin Lutwak (Brooklyn Polytechnic)

Larger bodies that cast smaller shadows

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'.

Friday, April 16, 4:15 p.m.; MIT, room 2-338

Michael Albertson (Smith)

Some degree-constrained extremal graph problems

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.

Wednesday, April 21, 4:15 p.m.; MIT, room 2-338

Rachel Rue (Williams)

On covering an independent set in a grid with another one

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.

Friday, April 23, 4:15 p.m.; MIT, room 2-338

After the talk on Friday, some people will be going out to dinner with the speaker, Bruce Sagan. All are welcome.

Bruce Sagan (Michigan State)

Why the characteristic polynomial factors

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.

Wednesday, April 28, 3:30 p.m.; MIT, room 2-338

(note unusual time of talk!)

Ivan Cherednik (U.N.C. at Chapel Hill)

The Macdonald constant term conjecture

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.

Friday, April 30, 4:15 p.m.; MIT, room 2-338

Andrew Gleason (Harvard)

Hadamard matrices and the Matthieu groups

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

Monday, May 10, 4:15 p.m.; MIT, room 2-338

David Grabiner (Harvard)

Random walks and Lie groups

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.

Wednesday, May 12, 4:15 p.m.; MIT, room 2-338

Larry Harper (U.N.C. at Chapel Hill)

Discrete isoperimetric problems and Steiner operations

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.

Discrete Math Dinner, May 12, 6:00 p.m., Taj India

Undergraduates will pay $\$$9 a head and graduate students will pay $\$$12 a head (beverages not included); the rest of us will make up the difference.

Friday, May 14, 4:15 p.m.; MIT, room 2-338

Ira Gessel (Brandeis)

Counting 2-stack-sortable multipermutations

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.

Wednesday, May 19, 4:15 p.m.; MIT, room 2-338

Barbara Nostrand (Northeastern)

Chiral Polytopes from Hyperbolic Honeycombs

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}.

Wednesday, May 26, 4:15 p.m.; MIT, room 2-338

Paul Erdos (Hungarian Academy of Sciences)

Some of my favorite combinatorial problems

Friday, May 28, 4:15 p.m.; MIT, room 2-338

Serge Kerov (St. Petersburg University and the University of Iowa)

Combinatorial problems in asymptotic representation theory

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 .

Wednesday, June 2, 4:15 p.m.; MIT, room 2-338

Tom Roby (University of Tokyo)

A two-dimensional pictorial presentation of Berele's insertion algorithm for symplectic tableaux

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.

Wednesday, July 7, 4:15 p.m.; MIT, room 2-338

Ludwig Danzer (University of Dortmund, Germany)

How to define quasiperiodicity especially with respect to quasicrystals


All announcements since Fall 2007 are in the Google Calendar