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

			Gadi Moran (Haifa)

             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)

                        Gadi Moran

                    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
Subject: Gadi Moran preprints

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 
of the meal will lead more graduate students and undergraduates to attend 
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 
graduate students and undergraduates to attend than has been the 
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
notified me about the likelihood of your attending the Discrete Dinner
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 
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.) 
 

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.