From propp(at-sign)math.mit.edu Fri Jan  7 16:41:35 1994
To: combinatorics(at-sign)math.mit.edu

The MIT combinatorics seminar will resume in February.  Six speakers
have already been scheduled, so it's definitely not too soon for you
to let me know if you'd like to give a talk this semester.

Jim Propp

From propp(at-sign)math.mit.edu Tue Jan 25 11:20:59 1994
To: combinatorics(at-sign)math.mit.edu
Subject: Combinatorics Seminar: February Schedule

COMBINATORICS SEMINAR

Here is a list of all talks currently scheduled for the month of February.

Wednesday, February 2, 4:15 p.m.: Igor Pak,
A resolution for skew-hook S_n-modules and combinatorial applications

Friday, February 4, 4:15 p.m.: Gadi Moran,
The r-majority action on 0-1 sequences

Wednesday, February 9, 4:15 p.m.: Sergio Rajsbaum,
Cycle-pancyclism in tournaments

Friday, February 11, 4:15 p.m.: Andrei Zelevinsky,
Representations of quivers of type A and the multisegment duality

Wednesday, February 16, 4:15 p.m.: Francois Bergeron,
Fourier transform formulas for descent algebras

Friday, February 18, 4:15 p.m.: David Jackson,
Some connections between maps on surfaces and symmetric functions

Wednesday, February 23, 4:15 p.m.: Sergey Yuzvinsky,
Combinatorial generators for logarithmic forms with poles
along an arrangement of hyperplanes

All talks, as usual, will meet in room 2-338.

From propp(at-sign)math.mit.edu Thu Jan 27 12:53:39 1994
To: combinatorics(at-sign)math.mit.edu

SEMINAR ON COMBINATORICS (HARVARD)

Asymptotics of the Plancherel measure of the symmetric group

Sergei Kerov  (Visiting Harvard)

Starting date:  Tuesday, Feb 1, 1994
Time:           4:15 p.m.
Place:          Science Center 530.

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.

Nantel Bergeron and Persi Diaconis

From propp(at-sign)math.mit.edu Sat Jan 29 14:30:15 1994
To: combinatorics(at-sign)math.mit.edu

A new talk for February is being scheduled; Douglas Rogers will speak
on February 25th.  Details will be forthcoming.

On another matter: A member of this mailing-list has asked to be removed
from it, complaining about the amount of traffic unrelated to the MIT
combinatorics seminar.

My impression is that most people don't mind the other announcements that
have been sent.  (Correct me if I'm wrong!)  Still, people should keep in
mind the original purpose of this mailing-list.

Jim Propp

From propp(at-sign)math.mit.edu Mon Jan 31 15:46:55 1994
To: combinatorics(at-sign)math.mit.edu
Subject: Pak, 2/2

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.

From propp(at-sign)math.mit.edu Mon Jan 31 16:31:18 1994
To: combinatorics(at-sign)math.mit.edu
Subject: Moran, 2/4

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.

From propp(at-sign)math.mit.edu Tue Feb  1 15:20:32 1994
To: combinatorics(at-sign)math.mit.edu
Subject: Extended abstract of Gadi Moran's talk (February 4)

University of Haifa

THE r-MAJORITY ACTION ON 0-1 SEQUENCES

The r-majority action on a cyclic 0-1 sequence replaces simultaneously 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 - theorettcal 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.                                 s

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

From propp(at-sign)math.mit.edu Mon Feb  7 15:15:23 1994
To: combinatorics(at-sign)math.mit.edu
Subject: Rajsbaum, 2/9

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

From propp(at-sign)math.mit.edu Mon Feb  7 15:44:17 1994
To: combinatorics(at-sign)math.mit.edu
Subject: Zelevinsky, 2/11

Friday, February 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.

From propp(at-sign)math.mit.edu Tue Feb  8 13:18:49 1994
To: combinatorics(at-sign)math.mit.edu

I have copies of Gadi Moran's extended one-page abstract, as well as copies
of his articles:

The r-Majority-Vote Action on 0-1 Sequences (preprint)
On the Period-Two-Property of the Majority Operator in
Infinite Graphs (preprint)
Parametrization for Stationary Patterns of the r-Majority Operators
on 0-1 sequences (preprint)
Phase Transitions via Cellular Automata (manuscript, 3 Dec. 1993)

Anyone who wants a copy (and has not already told me so) should contact me,
by e-mail or by phone (253-6544), in the next few days.

Jim

From propp(at-sign)math.mit.edu Tue Feb  8 14:35:52 1994
To: combinatorics(at-sign)math.mit.edu
Subject: Preview

COMBINATORICS SEMINAR

Here is a REVISED list of all remaining talks scheduled for the month of
February.  (Note the new talk on February 25.)

Wednesday, February 9, 4:15 p.m.: Sergio Rajsbaum,
Cycle-pancyclism in tournaments

Friday, February 11, 4:15 p.m.: Andrei Zelevinsky,
Representations of quivers of type A and the multisegment duality

Wednesday, February 16, 4:15 p.m.: Francois Bergeron,
Fourier transform formulas for descent algebras

Friday, February 18, 4:15 p.m.: David Jackson,
Some connections between maps on surfaces and symmetric functions

Wednesday, February 23, 4:15 p.m.: Sergey Yuzvinsky,
Combinatorial generators for logarithmic forms with poles
along an arrangement of hyperplanes

Friday, February 25, 4:15 p.m.: Douglas Rogers, title to be announced.

All talks, as usual, will meet in room 2-338.

From fomin(at-sign)math.mit.edu Tue Feb  8 19:41:37 1994
To: combinatorics(at-sign)math.mit.edu
Subject: Bergeron, 2/14

MIT Applied Mathematics Colloquium

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

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.

From propp(at-sign)math.mit.edu Fri Feb 11 16:07:01 1994
To: combinatorics(at-sign)math.mit.edu
Subject: TODAY'S SEMINAR

Andrei Zelevinsky's talk (originally scheduled for today) has been postponed
until March 11.

Jim Propp

From propp(at-sign)math.mit.edu Fri Feb 11 16:57:34 1994
To: combinatorics(at-sign)math.mit.edu
Subject: Bergeron, 2/16

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.

From propp(at-sign)math.mit.edu Sun Feb 13 20:21:44 1994
To: combinatorics(at-sign)math.mit.edu
Subject: Jackson, 2/18

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.

From propp(at-sign)math.mit.edu Wed Feb 16 18:06:10 1994
To: combinatorics(at-sign)math.mit.edu
Subject: Jackson, 2/18

[Since connections with Harvard's computers have been down, I am re-sending
this announcement; apologies to non-Harvard people.]

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.

From propp(at-sign)math.mit.edu Fri Feb 18 14:40:21 1994
To: combinatorics(at-sign)math.mit.edu
Subject: Yuzinsky, 2/23

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.

From propp(at-sign)math.mit.edu Fri Feb 18 15:05:15 1994
To: combinatorics(at-sign)math.mit.edu
Subject: Rogers, 2/25

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.

From propp(at-sign)math.mit.edu Wed Feb 23 18:27:18 1994
To: combinatorics(at-sign)math.mit.edu
Subject: Combinatorics Seminar: March Schedule

COMBINATORICS SEMINAR

Here is a list of all talks currently scheduled for the month of March.

Wednesday, March 2, 4:15 p.m.: Gabor Hetyei,
Edge-orientable cubical polytopes and a conjecture of
Eisenbud, Green and Harris

Friday, March 4, 4:15 p.m.: Sergei Kerov,
Random Young tableaux and Selberg integrals

Wednesday, March 9, 4:15 p.m.: Richard Ehrenborg,
Simple and multiplex juggling sequences

Friday, March 11, 4:15 p.m.: Andrei Zelevinsky,
Representations of quivers of type A and the multisegment duality

Wednesday, March 16, 4:15 p.m.: George Andrews,
q-Series and random graphs

Wednesday, March 30, 4:15 p.m.: Jim Propp,
Domino tilings and the arctic circle conjecture

All talks will meet in room 2-338.

From propp(at-sign)math.mit.edu Fri Feb 25 15:58:25 1994
To: combinatorics(at-sign)math.mit.edu
Subject: Tardif, 2/28

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

From propp(at-sign)math.mit.edu Fri Feb 25 16:06:56 1994
To: combinatorics(at-sign)math.mit.edu
Subject: Hetyei, 3/2

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.

From propp(at-sign)math.mit.edu Mon Feb 28 15:30:27 1994
To: combinatorics(at-sign)math.mit.edu
Subject: Kerov, 3/4

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

From propp(at-sign)math.mit.edu Mon Feb 28 15:42:01 1994
To: combinatorics(at-sign)math.mit.edu
Subject: Dinner

It's time once again for a Discrete Dinner together.

This time, the venue will be Bertucci's, right near MIT; the cost will
be $10 for grad students and undergraduates and$15 for professors (tax
and tip included).  I hope that the closeness to campus and the low cost
than has been the case in recent semesters.

Proposed dates are March 9, March 16, and March 30.  Send me your
votes and I'll pick the most popular of the three dates.

Jim Propp

From propp(at-sign)math.mit.edu Mon Feb 28 18:02:41 1994
To: combinatorics(at-sign)math.mit.edu
Subject: Re: dinner

I've just realized that March 30 is during Passover, so that some people
who would normally attend the dinner would not be able to.  I'll put April
6 forward as an additional proposed day.

Jim

From propp(at-sign)math.mit.edu Tue Mar  1 14:42:50 1994
To: combinatorics(at-sign)math.mit.edu
Subject: Discrete Dinner

I've been proposing Wednesday dates, but several people have said that
Wednesday is the one day of the week that's nearly always impossible for
them, so I'd like to put Fridays under consideration, too.

However, I don't know which Fridays yet.

So, hold off for a bit, and don't send me any more replies about my
proposed dinner-dates; I will have an emended list of proposed dates
by the end of the week.

Jim

From propp(at-sign)math.mit.edu Fri Mar  4 15:31:14 1994
To: combinatorics(at-sign)math.mit.edu
Subject: Ehrenborg, 3/9

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.

From propp(at-sign)math.mit.edu Fri Mar  4 15:38:02 1994
To: combinatorics(at-sign)math.mit.edu
Subject: Zelevinsky, 3/11 (this time for sure!)

Friday, February 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.

From propp(at-sign)math.mit.edu Fri Mar  4 15:45:36 1994
To: combinatorics(at-sign)math.mit.edu
Subject: Discrete Dinner; revised list of dates

The REVISED proposed dates for the Discrete Dinner at Bertucci's are:

Friday, March 11
Wednesday, March 16
Wednesday, March 30
Friday, April 1
Wednesday, April 6
Friday, April 8

Please let me know which days you prefer, and which days are simply
impossible for you.

Jim

From propp(at-sign)math.mit.edu Tue Mar  8 11:13:46 1994
To: combinatorics(at-sign)math.mit.edu
Subject: TODAY: counting lattice points in polytopes

The following may be of interest to some subscribers to this mailing list:

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

From propp(at-sign)math.mit.edu Wed Mar  9 13:57:50 1994
To: combinatorics(at-sign)math.mit.edu
Subject: George Andrews' talk on 3/14

The Applied Mathematics Colloquium this coming Monday may be of interest
to many subscribers to this list.

George Andrews will speak in room 2-105 at 4:15 p.m. on Monday, March 14.
His talk will be entitled "The Borwein Conjectures".

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.

From propp(at-sign)math.mit.edu Wed Mar  9 17:53:50 1994
To: combinatorics(at-sign)math.mit.edu
Subject: schedule change

The seminar speaker on March 30 will be Robert Calderbank (not Jim Propp
as originally scheduled).  Calderbank will speak on "The linearity of
several notorious families of nonlinear codes".  I will post an abstract
for the talk when it becomes available.

Jim Propp's lecture "Domino tilings and the arctic circle conjecture"
will be postponed until early April.

From propp(at-sign)math.mit.edu Wed Mar  9 17:55:15 1994
To: combinatorics(at-sign)math.mit.edu
Subject: Discrete Dinner

I plan to choose the date for the Discrete Dinner on Friday, so anyone
who hasn't replied to my latest request for preferences (the one wher
I specified three Wednesdays and three Fridays) should reply by
Thursday afternoon at the latest.

(It goes without saying that this coming Friday is no longer in the
running as one of the possible days for the Dinner.)

Jim Propp

From propp(at-sign)math.mit.edu Fri Mar 11 14:45:08 1994
To: combinatorics(at-sign)math.mit.edu
Subject: First talk by Robert Calderbank, 3/29

The following 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

A. R. Calderbank
Mathematical Sciences Research Center
AT&T Bell Labs, Murray Hill, NJ 07974

Abstract:

Error-correcting and error-detecting codes play important roles in
applications ranging from data networking to satellite communication
to compact disks.  Most coding theory emphasizes linear codes''.
Here the codewords are vectors with entries in some finite field,
and the code is closed under vector addition and multiplication by
scalars from the finite field.  Linear codes have a clean structure
that makes them simpler to discover, to understand, and to encode
and decode.  However, in order to get the largest possible number
of codewords with a fixed block size and correction capability (the
most efficient'' code), it is sometimes necessary to consider more
general codes, having little or no special structure to them.  Some
of the best known examples of nonlinear binary error-correcting codes
that are better than any corresponding linear code are the Nordstrom-
Robinson, Kerdock, and Preparata codes.  The Nordstrom-Robinson and
Preparata codes, for example, are twice as large as the best possible
linear codes for the same parameters.

The Kerdock and Preparata codes have long been known to be dual''
to one another in a particular formal sense, even though mathematically
_duality_ is defined only for linear codes.  The sense in which they
look like duals'' is that the MacWilliams transform of the distance
distribution of one yields the distance distribution of the other.
(This property is known always to hold for linear codes that actually
are duals of one another.)  For roughly 20 years this curious observation
has left coding theorists with the open question of whether these
non-linear codes might not be duals in some stronger sense.  Roger
Hammons (Hughes), Vijay Kumar (USC), Neil Sloane (AT\&T-BL), Patrick
Sol\'{e} (CNRS) and the speaker have now resolved this question by
showing that the Kerdock and Preparata codes are in fact linear, if
one views them in the right way over the ring of integers mod 4 instead
of the binary field, and that, over this larger ring, the two codes
_are_ mathematical duals.  The mappings between the binary and mod 4
versions of the codes are extremely simple.  Further implications of
this revelation are under study.

For details on place and time, contact Mitchell Trott (253-2359;
trott(at-sign)lids.mit.edu).

From propp(at-sign)math.mit.edu Fri Mar 11 16:15:59 1994
To: combinatorics(at-sign)math.mit.edu
Subject: Second talk by Robert Calderbank, 3/30

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

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.

From propp(at-sign)math.mit.edu Fri Mar 11 16:19:56 1994
To: combinatorics(at-sign)math.mit.edu
Subject: Discrete Dinner

By popular demand, this semester's discrete dinner will be on Friday,
April 8.  Stay tuned for further details.

Jim Propp

From propp(at-sign)math.mit.edu Mon Mar 14 13:00:32 1994
To: combinatorics(at-sign)math.mit.edu
Subject: Discrete Dinner

This semester's Discrete Dinner will be held on Friday, April 8
at 6 p.m. at Bertucci's Brick Oven Pizzeria (799 Main Street in
Cambridge).  The cost will be $10 for grad students and undergraduates and$15 for professors (tax and tip included).  I hope that the
closeness to campus and the low cost of the meal will lead more
case in recent semesters.

Please let me know by April 1 (and preferably electronically)
your probability of attendance.  (The sum of these probabilities
has proved to be a reliable indicator of the number of people who
actually attend.)

Jim Propp

From propp(at-sign)math.mit.edu Mon Mar 14 14:07:58 1994
To: combinatorics(at-sign)math.mit.edu
Subject: Andrews, 3/16

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.

From propp(at-sign)math.mit.edu Fri Mar 18 17:21:17 1994
To: combinatorics(at-sign)math.mit.edu
Subject: Combinatorics Seminar: April Schedule

COMBINATORICS SEMINAR

Here is a list of all talks scheduled for the month of April.

Wednesday, April 6, 4:15 p.m.: Jim Propp,
Domino tilings and the arctic circle conjecture

Friday, April 8, 4:15 p.m.: Tom Sundquist,
A 3-variable Pfaffian identity

Wednesday, April 13, 4:15 p.m.: Gunter Ziegler,
The random walks on digraphs corresponding to
some interesting linear programs

Friday, April 15, 4:15 p.m.: Peter McMullen,
Face-vectors of simple convex polytopes

Wednesday, April 20, 4:15 p.m.: Alexander Barvinok,
Efficient counting of lattice points in polytopes

Wednesday, April 27, 4:15 p.m.: Peter Shor,
Keller's conjecture

Friday, April 29, 4:15 p.m.: Lauren Rose,
Splines on polyhedral complexes

All talks will meet in room 2-338.

From propp(at-sign)math.mit.edu Thu Mar 31 16:29:17 1994
To: combinatorics(at-sign)math.mit.edu
Subject: Combinatorics Seminar: April Schedule (revised)

COMBINATORICS SEMINAR

Here is a revised list of all talks scheduled for the month of April.
Note the new talk that has been added on Monday, April 25 at a non-standard time.

Wednesday, April 6, 4:15 p.m.: Jim Propp,
Domino tilings and the arctic circle conjecture

Friday, April 8, 4:15 p.m.: Tom Sundquist,
A 3-variable Pfaffian identity

Wednesday, April 13, 4:15 p.m.: Gunter Ziegler,
The random walks on digraphs corresponding to
some interesting linear programs

Friday, April 15, 4:15 p.m.: Peter McMullen,
Face-vectors of simple convex polytopes

Wednesday, April 20, 4:15 p.m.: Alexander Barvinok,
Efficient counting of lattice points in polytopes

Monday, April 25, 2:00 p.m.: Qiao Li,
Restricted connectivity and restricted fault diameter
of interconnection networks

Wednesday, April 27, 4:15 p.m.: Peter Shor,
Keller's conjecture

Friday, April 29, 4:15 p.m.: Lauren Rose,
Splines on polyhedral complexes

All talks will meet in room 2-338.

From propp(at-sign)math.mit.edu Mon Apr  4 13:28:13 1994
To: combinatorics(at-sign)math.mit.edu
Subject: Dinner on Friday

This is just a final reminder that those of you who haven't already
on Friday should let me know today or tomorrow, unless your probability
of attendance is very close to zero.

Jim

From propp(at-sign)math.mit.edu Mon Apr  4 15:47:51 1994
To: combinatorics(at-sign)math.mit.edu
Subject: Propp, 4/6

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.

From propp(at-sign)math.mit.edu Mon Apr  4 16:20:35 1994
To: combinatorics(at-sign)math.mit.edu
Subject: Sundquist, 4/8

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.

From propp(at-sign)math.mit.edu Fri Apr  8 16:22:27 1994
To: combinatorics(at-sign)math.mit.edu
Subject: Ziegler, 4/13

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)

From propp(at-sign)math.mit.edu Fri Apr  8 17:52:30 1994
To: combinatorics(at-sign)math.mit.edu
Subject: McMullen, 4/15

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.

From propp(at-sign)math.mit.edu Sun Apr 10 22:51:35 1994
To: combinatorics(at-sign)math.mit.edu
Subject: Harvard Combinatorics Seminar, 4/12

SEMINAR ON COMBINATORICS (HARVARD)

Domino tilings and the arctic circle conjecture

Jim Propp  (MIT)

Date:           Tuesday, Apr 12, 1994
Time:           4:15 p.m.
Place:          Science Center 530.

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

From propp(at-sign)math.mit.edu Thu Apr 14 14:31:48 1994
To: combinatorics(at-sign)math.mit.edu
Subject: Barvinok, 4/20

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.

From nantel(at-sign)math.harvard.edu Thu Apr 14 16:36:22 1994
To: combinatorics(at-sign)math.mit.edu
Subject: Harvard Combinatorics

SEMINAR ON COMBINATORICS at HARVARD

Eric R. Rains (Harvard)
Increasing Subsequences and the Unitary Group

Tuesday, Apr. 19, 1994
4:15 PM
Science Center 530

From fomin(at-sign)math.mit.edu Fri Apr 15 13:30:12 1994
To: combinatorics(at-sign)math.mit.edu
Subject: Randall, 4/19

TUESDAY, APRIL 19, 1994, 3:30, NE43-518
Refreshments at 3:15

Counting in Lattices:
Combinatorial Problems from Statistical Mechanics

Dana Randall
University of California, Berkeley

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

From propp(at-sign)math.mit.edu Thu Apr 21 13:15:22 1994
To: combinatorics(at-sign)math.mit.edu
Subject: Li, 4/25

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.

From propp(at-sign)math.mit.edu Thu Apr 21 13:22:43 1994
To: combinatorics(at-sign)math.mit.edu
Subject: Shor, 4/27

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.

From nantel(at-sign)math.harvard.edu Thu Apr 21 15:35:50 1994
To: combinatorics(at-sign)math.mit.edu
Subject: Re: Shor, 4/27
Cc: maia(at-sign)math.harvard.edu, nantel(at-sign)math.harvard.edu

HARVARD SEMINAR on COMBINATORICS

The Structure of the Universal Exponential
Solution of the Yang-Baxter Equation

Nantel Bergeron

Tuesday Apr. 26
4:15 PM
Science Center 530

From nantel(at-sign)math.harvard.edu Thu Apr 21 15:43:37 1994
To: combinatorics(at-sign)math.mit.edu
Subject: HARVARD SEMINAR on COMBINATORICS
Cc: nantel(at-sign)math.harvard.edu

Oups!... Sorry,

> HARVARD SEMINAR on COMBINATORICS
>
> The Structure of the Universal Exponential
> Solution of the Yang-Baxter Equation
>
> Nantel Bergeron
>
> Tuesday Apr. 26
> 4:15 PM
> Science Center 530
>

From propp(at-sign)math.mit.edu Sun Apr 24 00:45:18 1994
To: combinatorics(at-sign)math.mit.edu
Subject: Combinatorics Seminar: May Schedule

COMBINATORICS SEMINAR

Here is a preliminary list of talks scheduled for the end of the month of April
and for the month of May.

Wednesday, April 27, 4:15 p.m.: Peter Shor,
Keller's conjecture

Friday, April 29, 4:15 p.m.: Lauren Rose,
Splines on polyhedral complexes

Monday, May 2, 4:15 p.m.: Andrei Zelevinsky,
Flows in networks and the multisegment duality

Wednesday, May 4, 4:15 p.m.: Klaus Altmann,
Minkowski sums and the versal deformation of toric singularities

Friday, May 6, 4:15 p.m.: Erwin Lutwak,
A discrete version of the Minkowski problem

Wednesday, May 11, 4:15 p.m.: Alan Edelman,
Hadamard matrices and the Gaussian elimination pivot conjecture

Friday, May 13, 4:15 p.m.: George Markowsky,
The poset of irreducibles: a basis for lattice theory

Monday, May 16, 4:15 p.m.: Mike Hawrylycz,
Geometric identities in invariant theory

All talks will meet in room 2-338.

From propp(at-sign)math.mit.edu Mon Apr 25 12:32:52 1994
To: combinatorics(at-sign)math.mit.edu
Subject: Rose, 4/29

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.

From propp(at-sign)math.mit.edu Mon Apr 25 17:58:57 1994
To: combinatorics(at-sign)math.mit.edu
Subject: May schedule (revised)

COMBINATORICS SEMINAR

Here is a revised list of talks scheduled for the month of May.

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
*                                                                   *
*    Note that the talk by Andrei Zelevinsky originally scheduled   *
*    for Monday, May 2 has been postponed to Monday, May 9.         *
*                                                                   *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

Wednesday, May 4, 4:15 p.m.: Klaus Altmann,
Minkowski sums and the versal deformation of toric singularities

Friday, May 6, 4:15 p.m.: Erwin Lutwak,
A discrete version of the Minkowski problem

Monday, May 9, 4:15 p.m.: Andrei Zelevinsky,
Flows in networks and the multisegment duality

Wednesday, May 11, 4:15 p.m.: Alan Edelman,
Hadamard matrices and the Gaussian elimination pivot conjecture

Friday, May 13, 4:15 p.m.: George Markowsky,
The poset of irreducibles: a basis for lattice theory

Monday, May 16, 4:15 p.m.: Mike Hawrylycz,
Geometric identities in invariant theory

All talks will meet in room 2-338.

From propp(at-sign)math.mit.edu Thu Apr 28 16:18:13 1994
To: combinatorics(at-sign)math.mit.edu
Subject: Altmann, 5/4

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

From propp(at-sign)math.mit.edu Thu Apr 28 17:37:20 1994
To: combinatorics(at-sign)math.mit.edu
Subject: Lutwak, 5/6

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.

From nantel(at-sign)math.harvard.edu Mon May  2 08:11:27 1994
To: combinatorics(at-sign)math.mit.edu
Subject: Harvard Seminar on Combinatorics

Harvard Seminar on Combinatorics

Nathan A. M. Lulov

Rim Hook Lattices and Random Walks on the Symmetric Group

Tuesday May 3 1994
4:15 pm
Science Center 530

From propp(at-sign)math.mit.edu Tue May  3 18:00:47 1994
To: combinatorics(at-sign)math.mit.edu
Subject: May schedule (revised again)

COMBINATORICS SEMINAR

Here is what I hope is the final list of talks scheduled for the month of May.
Note the two new talks scheduled for May 18 and 20.

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
*                                                                   *
*    Note that the talk by Andrei Zelevinsky originally scheduled   *
*    for Monday, May 2 has been postponed to Monday, May 9.         *
*                                                                   *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

Monday, May 9, 4:15 p.m.: Andrei Zelevinsky,
Flows in networks and the multisegment duality

Wednesday, May 11, 4:15 p.m.: Alan Edelman,
Hadamard matrices and the Gaussian elimination pivot conjecture

Friday, May 13, 4:15 p.m.: George Markowsky,
The poset of irreducibles: a basis for lattice theory

Monday, May 16, 4:15 p.m.: Mike Hawrylycz,
Geometric identities in invariant theory

Wednesday, May 18, 4:15 p.m.: Laura Anderson,
Combinatorial differential manifolds

Friday, May 20, 4:15 p.m.: Volkmar Welker,
Lattices of partitions and their relevance in the study of
spaces of polynomials

All talks will meet in room 2-338.

From nantel(at-sign)math.harvard.edu Wed May  4 09:27:31 1994
To: combinatorics(at-sign)math.mit.edu
Subject: Harvard Combinatorics Seminar

Harvard Combinatorics Seminar

Sergey Fomin (M.I.T.)
Schubert polynomials: an introduction

Tuesday, May 10,
Science Center 530
4:15 PM

From nantel(at-sign)math.harvard.edu Wed May  4 09:27:31 1994
To: combinatorics(at-sign)math.mit.edu
Subject: Harvard Combinatorics Seminar

Harvard Combinatorics Seminar

Sergey Fomin (M.I.T.)
Schubert polynomials: an introduction

Tuesday, May 10,
Science Center 530
4:15 PM

From propp(at-sign)math.mit.edu Sun May  8 16:54:43 1994
To: combinatorics(at-sign)math.mit.edu
Subject: Zelevinsky, 5/9

The talk originally scheduled for May 2 has been postponed to May 9.
The updated information is as follows:

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.

From propp(at-sign)math.mit.edu Sun May  8 17:03:45 1994
To: combinatorics(at-sign)math.mit.edu
Subject: Edelman, 4/11

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

From propp(at-sign)math.mit.edu Sun May  8 17:11:28 1994
To: combinatorics(at-sign)math.mit.edu
Subject: Markowsky, 4/13

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.

From propp(at-sign)math.mit.edu Thu May 12 16:27:56 1994
To: combinatorics(at-sign)math.mit.edu
Subject: typo

Markowsky's talk will of course be on 5/13, not 4/13.

From propp(at-sign)math.mit.edu Thu May 12 21:13:37 1994
To: combinatorics(at-sign)math.mit.edu
Subject: Hawrylycz, 5/16

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.

From nantel(at-sign)math.harvard.edu Mon May 16 11:12:37 1994
To: combinatorics(at-sign)math.mit.edu
Subject: Harvard Combinatorics Seminar 5/17

David Grabiner, Harvard University
will speak on
"A combinatorial Correspondence for Random Walks in Weyl Chambers"

The talk will be in Science Center 530 at 4:15 PM.

From propp(at-sign)math.mit.edu Thu May 19 16:55:01 1994
To: combinatorics(at-sign)math.mit.edu
Subject: Anderson, 5/18

Apologies to all for my failure to post this.  (I'm sending it out now
so that those who missed the talk can at least read the abstract.)

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?

From propp(at-sign)math.mit.edu Thu May 19 17:40:57 1994
To: combinatorics(at-sign)math.mit.edu
Subject: Welker, 5/20

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.