# MIT-Harvard-MSR Combinatorics Seminar

## Schedule 1994 Spring

Organizer: Jim Propp

### SEMINAR ON COMBINATORICS (HARVARD), Tuesday, Feb 1, 4:15pm; Science Center 530

Sergei Kerov (Visiting Harvard)

Asymptotics of the Plancherel measure of the symmetric group

Sergei Kerov is visiting Harvard this term. We will run a weekly seminar on topics related to the celebrated results on limiting shape of Young diagrams. This relates the Plancherel measure on S_\infty to the hook formulae and hook walks. These in turn are related to Markov's moment problem and the distribution of zeros of the orthogonal polynomials.

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

Igor Pak (New York)

A resolution for skew-hook S_n-modules and combinatorial applications

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.

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

The r-majority action on 0-1 sequences

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

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

Sergio Rajsbaum (UNAM and MIT)

Cycle-pancyclism in tournaments

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

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

Rescheduled to March 11

Andrei Zelevinsky (Northeastern)

### Monday, February 14, 4:15 p.m.; MIT, room 2-105

MIT Applied Mathematics Colloquium

Francois Bergeron (University of Quebec at Montreal)

Standard Paths in the Composition Poset

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.

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

Andrei Zelevinsky (Northeastern)

Representations of quivers of type A and the multisegment duality

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.

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

Francois Bergeron (UQAM)

Fourier transform formulas for descent algebras

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.

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

David Jackson (Waterloo)

Some connections between maps on surfaces and symmetric functions

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.

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

Sergey Yuzvinsky (Oregon and Northeastern)

Combinatorial generators for logarithmic forms with poles along an arrangement of hyperplanes

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.

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

Douglas Rogers (Northern Territory and Bowling Green)

A matrix method for counting Hamitonian cycles on grids

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.

### Monday, February 28, 4:15 p.m.; MIT, room 2-338

Claude Tardif (Montreal)

On graphs homomorphically equivalent to their cartesian powers

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

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

Gabor Hetyei (M.I.T.)

Edge-orientable cubical polytopes and a conjecture of Eisenbud, Green and Harris

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.

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

Sergei Kerov (St. Petersburg and Harvard)

Random Young tableaux and Selberg integrals

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


### (MOSTLY) SYMPLECTIC GEOMETRY SEMINAR, Tuesday, March 8, 3 pm; MIT, Room 4-153

James Pommersheim (M.I.T.)

"The Todd Class of a Toric Variety"

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.

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

Richard Ehrenborg (UQAM)

Simple and multiplex juggling sequences

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.

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

Andrei Zelevinsky (Northeastern)

Representations of quivers of type A and the multisegment duality

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.

### Applied Mathematics Colloquium, TMonday, March 14, 4:15pm; MIT, Room 2-105

George Andrews

"The Todd Class of a Toric Variety"

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.

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

George Andrews (Penn State)

q-Series and random graphs

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.

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

The expository talk (to be given on Tuesday, March 29, under the auspices of the Electrical Engineering department) may be of interest to those who plan to attend Robert Calderbank's more technical talk in the Combinatorics Seminar on the following day: The Linearity of Several Notorious Families of Nonlinear Binary Codes

Robert Calderbank (Bell Labs)

Codes, geometries and extremal sets of Euclidean lines with prescribed angles

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.

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

Jim Propp (M.I.T.)

Domino tilings and the arctic circle conjecture

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.

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

Tom Sundquist (Dartmouth)

A 3-variable Pfaffian identity

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.

The cost will be $\$$10 for grad students and undergraduates and \$$15 for professors (tax and tip included). ### SEMINAR ON COMBINATORICS (HARVARD), Tuesday, April 12, 1994, 4:15 pm; Science Center 530 Jim Propp (MIT) Domino tilings and the arctic circle conjecture 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!].) ### Wednesday, April 13, 4:15 p.m.; MIT, room 2-338 Gunter Ziegler (ZIB Berlin) The random walks on digraphs corresponding to some interesting linear programs 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) ### Friday, April 15, 4:15 p.m.; MIT, room 2-338 Peter McMullen (University College, London) Face-vectors of simple convex polytopes 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. ### TUESDAY, APRIL 19, 1994, 3:30, NE43-518 Dana Randall, University of California, Berkeley Counting in Lattices: Combinatorial Problems from Statistical Mechanics We consider two classical combinatorial problems arising in statistical mechanics: counting matchings and self-avoiding walks in lattice graphs. The first problem arises in the study of the thermodynamical properties of monomers and dimers (diatomic molecules) in crystals. Fisher, Kasteleyn and Tem- perley discovered an elegant technique to exactly count the number of perfect matchings in two dimensional lattices, but it is not applicable for matchings of arbitrary size, or in higher dimensional lattices. We present the first efficient approx- imation algorithm for computing the number of matchings of any size in any d-dimensional periodic lattice. The algorithm is based on Monte Carlo simulation of a suitable Markov chain and has rigorously derived performance guarantees that do not rely on any assumptions. Counting self-avoiding walks in lattices arises in the study of the thermodynamics of long polymer chains in dilute solution. While there there are a number of Monte Carlo algorithms used to count self-avoiding walks in practice, these are heuristics and their correctness relies on unproven conjectures. In contrast, we present an efficient algorithm which relies on a single, widely- believed conjecture that is simpler than preceding assumptions and, more importantly, is one which the algorithm itself can test. Thus our algorithm is reliable, in the sense that it either outputs answers that are guaranteed, with high probability, to be correct, or finds a counterexample to the conjecture. (This is joint work with Claire Kenyon and Alistair Sinclair.) ### SEMINAR ON COMBINATORICS (HARVARD), Tuesday, April 19, 1994, 4:15 pm; Science Center 530 Eric R. Rains (Harvard) Increasing Subsequences and the Unitary Group ### Wednesday, April 20, 4:15 p.m.; MIT, room 2-338 Alexander Barvinok (Cornell) Efficient counting of lattice points in polytopes 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. ### Monday, April 25, 2:00 p.m.; MIT, room 2-338 (note unusual date and time!) Qiao Li (China) Restricted connectivity and restricted fault diameter of interconnection networks 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. ### SEMINAR ON COMBINATORICS (HARVARD), Tuesday, April 26, 1994, 4:15 pm; Science Center 530 Nantel Bergeron The Structure of the Universal Exponential Solution of the Yang-Baxter Equation ### Wednesday, April 27, 4:15 p.m.; MIT, room 2-338 Peter Shor (Bell Labs) Keller's conjecture 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. ### Friday, April 29, 4:15 p.m.; MIT, room 2-338 Lauren Rose (Wellesley, M.I.T., and Bunting Institute) Splines on polyhedral complexes 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. ### SEMINAR ON COMBINATORICS (HARVARD), Tuesday, May 3, 1994, 4:15 pm; Science Center 530 Nathan A. M. Lulov Rim Hook Lattices and Random Walks on the Symmetric Group ### Wednesday, May 4, 4:15 p.m.; MIT, room 2-338 Klaus Altmann (Humboldt University and M.I.T.) Minkowski sums and the versal deformation of toric singularities 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). ### Friday, May 6, 4:15 p.m.; MIT, room 2-338 Erwin Lutwak (Brooklyn Polytechnic) A discrete version of the Minkowski problem 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. ### Monday, May 9, 4:15 p.m.; MIT, room 2-338 Andrei Zelevinsky (Northeastern University) Flows in networks and the multisegment duality 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. ### SEMINAR ON COMBINATORICS (HARVARD), Tuesday, May 10, 1994, 4:15 pm; Science Center 530 Sergey Fomin (M.I.T.) Schubert polynomials: an introduction ### Wednesday, May 11, 4:15 p.m.; MIT, room 2-338 Alan Edelman (M.I.T.) Hadamard matrices and the Gaussian elimination pivot growth conjecture 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.) ### Friday, May 13, 4:15 p.m.; MIT, room 2-338 George Markowsky (Maine) The poset of irreducibles: a basis for lattice theory 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. ### Monday, May 16, 4:15 p.m.; MIT, room 2-338 Mike Hawrylycz (Los Alamos) Geometric identities in invariant theory 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.

### SEMINAR ON COMBINATORICS (HARVARD), Tuesday, May 17, 1994, 4:15 pm; Science Center 530

David Grabiner, Harvard University

A combinatorial Correspondence for Random Walks in Weyl Chambers

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

Laura Anderson (M.I.T.)

Combinatorial Differential Manifolds

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?

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

Volkmar Welker (Essen)

Lattices of partitions and their relevance in the study of spaces of polynomials

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.

## Archive

All announcements since Fall 2007 are in the Google Calendar