From propp(at-sign)math.mit.edu Mon Aug 30 12:55:06 1993
To: combinatorics(at-sign)math.mit.edu
Subject: MIT Combinatorics Seminar

[It seems that mailer problems prevented this from getting circulated,
so I'm trying once more.  Apologies to those who have already received
this message.]

There are still many slots available for the coming semester; anyone
who is interested in giving a talk (or who knows of someone who might
be) should send me e-mail.

Also, let me know if there are new faculty or grad students who
should be put on the distribution list.

Jim Propp (propp(at-sign)math.mit.edu)

From propp(at-sign)math.mit.edu Thu Sep  2 11:57:45 1993
To: combinatorics(at-sign)math.mit.edu

I've been asked to shift the Wednesday seminar so that it runs from 4:30 to 5:30
(instead of 4:15 to 5:15).  *N.B.: The Fridays meetings would remain in the 
4:15-5:15 slot.*  Before I make a decision on this, I'd like to know whether 
anyone has strong feelings on the matter, one way or the other.

Jim

From grabiner(at-sign)math.harvard.edu Thu Sep  2 12:08:54 1993
To: propp(at-sign)math.mit.edu
Reply-To: grabiner(at-sign)math.harvard.edu

You write:

> I've been asked to shift the Wednesday seminar so that it runs from 4:30 to 5:30
> (instead of 4:15 to 5:15).  *N.B.: The Fridays meetings would remain in the 
> 4:15-5:15 slot.*  Before I make a decision on this, I'd like to know whether 
> anyone has strong feelings on the matter, one way or the other.

I don't care this semester, but I will have a slight preference for 4:15
next semester, since this is immediately after Kleitman's 3:00-4:00
seminar.  It isn't that important.

David Grabiner

From rota(at-sign)math.mit.edu Thu Sep  2 19:00:23 1993
To: propp(at-sign)math.mit.edu

I have no feelings on the matter, please let me know your decision.
Best regards, Gian-Carlo.

From ira(at-sign)cs.brandeis.edu Fri Sep  3 16:53:29 1993
To: propp(at-sign)math.mit.edu

I don't have strong feelings either way. On the one hand, making the
seminar later allows me to get more done here first. On the other
hand, making it later means getting home later. But 15 minutes isn't a
big deal either way.

Ira

From propp(at-sign)math.mit.edu Wed Sep  8 14:16:06 1993
To: combinatorics(at-sign)math.mit.edu

This semester, the combinatorics seminar will meet from 4:15 to 5:15
on Wednesdays (as before), but on Fridays it will meet from 4:30 to 5:30.

Jim Propp

From propp(at-sign)math.mit.edu Wed Sep  8 14:17:48 1993
To: combinatorics(at-sign)math.mit.edu
Subject: MIT Combinatorics Seminar: Correction

Oops!  I got that backwards.

This semester, *Wednesday* meetings will be from 4:30 to 5:30; *Friday*
meetings will continue to be held from 4:15 to 5:15.

Sorry for the confusion!

Jim Propp

From propp(at-sign)math.mit.edu Wed Sep  8 14:18:21 1993
To: combinatorics(at-sign)math.mit.edu
Subject: Krattenthaler, 9/15

Wednesday, September 15, 4:30 p.m.; MIT, room 2-338
        (note new time!) ^^^^ 

		    Christian Krattenthaler (Vienna)

		The Major Counting of Nonintersecting Lattice Paths
		       and Generating Functions for Tableaux
 
We develop a theory of counting nonintersecting lattice paths by the 
major index and generalizations of it. As application we prove refinements 
of two theorems in plane partition theory, the Bender-Knuth and MacMahon 
(Ex-)Conjectures, respectively.

From propp(at-sign)math.mit.edu Sat Sep 18 14:40:14 1993
To: combinatorics(at-sign)math.mit.edu
Subject: Wild, 9/22

Wednesday, September 22, 4:30 p.m.; MIT, room 2-338
        (note new time!) ^^^^ 

		        Marcel Wild (M.I.T.)

		An enumerative principle of exclusion
 
Let M be a finite set and P a ``property'' enjoyed by some subsets
X of M.  With N(P) we denote the number of X in 2^M with property P.
For any properties P_1,...,P_n let C=C(P_1,...,P_n) be the family of 
those X in 2^M which enjoy {\it all} properties P_i.  According to 
the well known principle of "inclusion-exclusion" one has

|C| = N(P_1 wedge ... wedge P_n) = 
	   sum_{1 <= i <= n} N(P_i)  
	-  sum_{1 <= i < j <= n} N(P_i vee P_j)
	+  ...

Unfortunately 2^n-1 many terms N(P_i vee P_j vee ... vee P_k) need to be
added and substracted from each other on the righthand side. Moreover, 
sometimes there is no easy way to compute the terms themselves.  We shall 
present an often better method for determining |C|, which is based on a 
principle of ``exclusion''.  It is demonstrated for arbitrary _closure_systems_
C (which fit a lot of applications in Algebra and Combinatorics), but we 
believe that variations would apply to other counting problems as well. 

From propp(at-sign)math.mit.edu Sat Sep 18 15:12:32 1993
To: combinatorics(at-sign)math.mit.edu
Subject: Stanley, 9/24

Friday, September 24, 4:15 p.m.; MIT, room 2-338

		       Richard Stanley (M.I.T.)

		 A symmetric function generalization
		of the chromatic polynomial of a graph
 
Let G be a finite graph. We will define a symmetric function X_G =
X_G(x_1,x_2,...) which generalizes the chromatic polynomial of G.
Classical results on chromatic polynomials dealing with Mobius
functions and acyclic orientations can be extended to X_G.  For
certain graphs G, the expansion of X_G in terms of elementary
symmetric functions is related to the theory of Hecke algebras and
Kazhdan-Lusztig polynomials.

From propp(at-sign)math.mit.edu Wed Sep 22 21:14:34 1993
To: combinatorics(at-sign)math.mit.edu
Subject: MIT Combinatorics Seminar: time change

One final change in this semester's schedule (hopefully the last):
the Wednesday talks will start at 4:35, not 4:30.  I hope this
doesn't inconvenience anyone too much.

Jim

From propp(at-sign)math.mit.edu Wed Sep 22 21:59:45 1993
To: combinatorics(at-sign)math.mit.edu
Subject: MIT Combinatorics Seminar

The semester is filling up fast.  Here's the current tentative schedule
(a more detailed schedule will follow, once the question-marks get removed):

Month	 W			 F

 9:	15 Krattenthaler    	17
 9:	22 Wild	   		24 Stanley
 9:	29 Arnold		 1 Fishel    
10:	 6 Almkvist		 8 Larose
10:	13 Goemans		15 Thomas
10:	20 Landau?		22 Collins
10:	27    			29 Schulte    
11:	 3 Brenti		 5 Reeves
11:	10			12 Okada?
11:	17 Hanlon		19
11:	*			 *
11:	 1			 3
12:	 8			10
12:	15			17 

Those who are interested in speaking this semester should definitely
contact me during the next week or two.

Jim

From propp(at-sign)math.mit.edu Thu Sep 23 11:47:09 1993
To: combinatorics(at-sign)math.mit.edu
Subject: Arnold, 9/29

Wednesday, September 29, 4:35 p.m.; MIT, room 2-338
 (note REALLY new time!  ^^^^ )

		    Vladimir Arnold (Moscow)

             Euler, Bernoulli and Springer numbers 
         of Coxeter groups and of Morsification spaces
 

The classical sequence 1,1,1,2,5,16,61,272,1385,... occurs in many 
combinatorial problems.  It has recently been discovered that the 
same sequence governs the topological classification of Morsifications 
of simplest degenerate critical points of smooth functions.  This 
observation leads to the generalizations of the Euler and tangent 
numbers which can be associated with any simple Lie algebra or even 
to any Coxeter group.  This gives new information even in the classical 
case (corresponding to the sl(n) algebras and to the symmetries of
simplices), for instance new congruences for the classical Euler and
Bernoulli numbers, generalising those found by Kummer, von Staudt and 
Knuth.

From propp(at-sign)math.mit.edu Thu Sep 23 11:47:32 1993
To: combinatorics(at-sign)math.mit.edu
Subject: Fishel, 10/1

Friday, October 1, 4:15 p.m.; MIT, room 2-338

	     Susanna Fishel (Southern Connecticut State)

		The combinatorics of certain entries
		 in the two-parameter Kostka matrix

Kirillov and Reshetikhin introduced rigged configurations as a new way
to calculate the entries  K_{\lambda\mu}(t)  of the Kostka matrix.
Macdonald defined the two-parameter Kostka matrix whose entries
K_{\lambda\mu}(q,t)  generalize  K_{\lambda\mu}(t) .  I use rigged
configurations and a formula of Stembridge to provide a combinatorial
interpretation of  K_{\lambda\mu}(q,t)  in the case where  \mu  is a
partition with no more than two columns.  In particular, I show that
in this case,  K_{\lambda\mu}(q,t)  has nonnegative coefficients.

From yuzvinsk(at-sign)math.wisc.edu Sat Sep 25 18:52:28 1993
Subject: accomodations
To: combinatorics(at-sign)math.mit.edu
X-Mailer: ELM [version 2.4 PL21]
Content-Type: text
Content-Length: 343       

Dear Colleague,
I am going to visit the Boston area for about two months in January -
February with Tony Iarrobino (NEU) as the principal host. If you
know any available accomodation for 2 adults and a 13-year old for
this period please let me know. A decent high school in the area
is important.
TIA,
Sergey Yuzvinsky (yuz(at-sign)math.uoregon.edu)

From SCHULTE(at-sign)neu.edu Tue Sep 28 15:11:11 1993
Subject: Northeastern Combinatorics Seminar
To: combinatorics(at-sign)math.mit.edu
X-Envelope-To: combinatorics(at-sign)math.mit.edu
X-Vms-To: IN%"combinatorics(at-sign)math.mit.edu"
Mime-Version: 1.0
Content-Transfer-Encoding: 7BIT

                 COMBINATORICS SEMINAR 
            
                NORTHEASTERN UNIVERSITY  

                 Schedule for Fall 1993
            ______________________________

The seminars are usually Wednesday at 1:30 p.m. in 509 Lake Hall.

Sept. 22      Roy Meshulam, Technion, Haifa

              On subsets of abelian groups with no 
              3-term arithmetic progression

Any questions? Call 373-5511.
              

From SCHULTE(at-sign)neu.edu Tue Sep 28 15:11:40 1993
Subject: Northeastern Combinatorics Seminar
To: combinatorics(at-sign)math.mit.edu
X-Envelope-To: combinatorics(at-sign)math.mit.edu
X-Vms-To: IN%"combinatorics(at-sign)math.mit.edu"
Mime-Version: 1.0
Content-Transfer-Encoding: 7BIT

                 COMBINATORICS SEMINAR 
            
                NORTHEASTERN UNIVERSITY  

                 Schedule for Fall 1993
            ______________________________

The seminars are usually Wednesday at 1:30 p.m. in 509 Lake Hall.

Sept. 29      Vladimir Retakh (visiting Harvard)

              Non-commutative determinants and
              their combinatorics

Oct. 6        Klaus Altmann (M.I.T.)
     
              Deformation theory of toric varieties

Any questions? Call 373-5511.
              

From SCHULTE(at-sign)neu.edu Tue Sep 28 15:11:45 1993
Subject: Northeastern Combinatorics Seminar
To: combinatorics(at-sign)math.mit.edu
X-Envelope-To: combinatorics(at-sign)math.mit.edu
X-Vms-To: IN%"combinatorics(at-sign)math.mit.edu"
Mime-Version: 1.0
Content-Transfer-Encoding: 7BIT

                 COMBINATORICS SEMINAR 
            
                NORTHEASTERN UNIVERSITY  

                 Schedule for Fall 1993
            ______________________________

The seminars are usually Wednesday at 1:30 p.m. in 509 Lake Hall.

Sept. 29      Vladimir Retakh (visiting Harvard)

              Non-commutative determinants and
              their combinatorics

Oct. 6        Klaus Altmann (M.I.T.)
     
              Deformation theory of toric varieties

Any questions? Call 373-5511.
              

From SCHULTE(at-sign)neu.edu Tue Sep 28 15:18:56 1993
Subject: Northeastern Combinatorics Seminar
To: combinatorics(at-sign)math.mit.edu
X-Envelope-To: combinatorics(at-sign)math.mit.edu
X-Vms-To: IN%"combinatorics(at-sign)math.mit.edu"
Mime-Version: 1.0
Content-Transfer-Encoding: 7BIT

                 COMBINATORICS SEMINAR 
            
                NORTHEASTERN UNIVERSITY  

                 Schedule for Fall 1993
            ______________________________

The seminars are usually Wednesday at 1:30 p.m. in 509 Lake Hall.

Sept. 29      Vladimir Retakh (visiting Harvard)

              Non-commutative determinants and
              their combinatorics

Oct. 6        Klaus Altmann (M.I.T.)
     
              Deformation theory of toric varieties

Any questions? Call 373-5511.
              

From propp(at-sign)math.mit.edu Wed Sep 29 16:11:41 1993
To: combinatorics(at-sign)math.mit.edu
Subject: Almkvist, 10/6

Wednesday, October 6, 4:35 p.m.; MIT, room 2-338

		 Gert Almkvist (KTH)

		(Title not yet known)
 

(Abstract not yet available)

From propp(at-sign)math.mit.edu Wed Sep 29 16:18:03 1993
To: combinatorics(at-sign)math.mit.edu
Subject: Larose, 10/8

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

                  Benoit Larose (Universite de Montreal)

         Products of finite posets and the fixed point property

If P and Q are finite posets with the fixed point property, does
the product PxQ also have this property?  In 1985, E. Corominas
introduced the notion of "projective" (idempotent trivial) poset
to attack this problem: the fixed point property is preserved
under products if the so-called "minimal automorphic" posets 
are projective.  We prove that the projection property is equivalent
to quasiprojectivity (tightness) for posets of arbitrary cardinality;
universal algebraic methods can then be used to determine if a poset 
is projective.  We relate Corominas' conjecture to the notion of 
representability by irreducibles in varieties of ordered sets.

From propp(at-sign)math.mit.edu Wed Sep 29 21:37:52 1993
To: combinatorics(at-sign)math.mit.edu
Subject: Almkvist, 10/6 (more info now available)

Wednesday, October 6, 4:35 p.m.; MIT, room 2-338

		 Gert Almkvist (KTH)

	From plane partitions to Fermat's last theorem:
	some excerpts from the notebook of a Maple-user
 

Attempting to find "exact" asymptotic formulas for the number of plane
partitions various byproducts are obtained: generalized Dedekind sums,
values of Bernoulli polynomials at rational points. Wilf's conjecture
is proved.

From propp(at-sign)math.mit.edu Fri Oct  1 21:09:52 1993
To: combinatorics(at-sign)math.mit.edu
Subject: Combinatorics Seminar: on-line preprints

People who speak in the seminar are invited to send me electronic preprints,
which I will keep in the publically-readable directory ~propp/public.
(Subscribers to this mailing list who do not have accounts on the MIT math
department machines cannot obtain these via anonymous ftp, but I will be
happy to e-mail a preprint to anyone who asks me.)

Jim

From propp(at-sign)math.mit.edu Tue Oct  5 08:53:07 1993
To: combinatorics(at-sign)math.mit.edu
Subject: Combinatorics Seminar: October Schedule

			COMBINATORICS SEMINAR

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

Friday, October 1, 4:15 p.m.: Susanna Fishel,
	The combinatorics of certain entries in the two-parameter Kostka matrix

Wednesday, October 6, 4:35 p.m.: Gert Almkvist,
	From plane partitions to Fermat's last theorem: 
	some excerpts from the notebook of a Maple-user

Friday, October 8, 4:15 p.m.: Benoit Larose,
	Products of finite posets and the fixed point property

Wednesday, October 13, 4:35 p.m.: Michel Goemans,
	Minimizing submodular functions over families of sets

Friday, October 15, 4:15 p.m.: Rekha Thomas,
	Grobner basis methods for integer programming

Wednesday, October 20, 4:35 p.m.: Susan Landau,
	Embedding linkages on an integer lattice
	
Friday, October 22, 4:15 p.m.: Karen Collins,
	Chromatic difference sequences
	
Wednesday, October 27, 4:35 p.m.: Luis Verde-Star,
	Solution of linear matrix difference and differential equations
	by operator methods
	
Friday, October 29, 4:15 p.m.: Egon Schulte,
	Toroidal regular polytopes and their groups

All talks will meet in room 2-338.

From propp(at-sign)math.mit.edu Tue Oct 12 14:34:38 1993
To: combinatorics(at-sign)math.mit.edu
Subject: Goemans, 10/13

Wednesday, October 13, 4:35 p.m.; MIT, room 2-338

		       Michel Goemans (M.I.T.)

	Minimizing submodular functions over families of sets
 

Submodular set-functions arise in a variety of fields, including
combinatorics, probability and geometry.  Classical examples include
the rank function of a matroid, the cuts in a directed or undirected
graph, the probability that a subset of events do not simultaneously
occur, or the logarithm of the volume of the parallelepiped spanned by
a subset of linearly independent vectors.

We consider the problem of characterizing the minimum of a submodular
function when the minimization is restricted to a family of subsets.
We show that, for many interesting families, the problem can be
reduced to a sequence of submodular function minimizations over all
subsets. Our results apply, for example, to the families of odd
cardinality subsets or even cardinality subsets, leading to a
characterization of the minimum even cut in a graph. These results
generalize and unify many classical results in combinatorial
optimization. 

This is joint work with V.S. Ramakrishnan.

From propp(at-sign)math.mit.edu Tue Oct 12 15:26:46 1993
To: combinatorics(at-sign)math.mit.edu
Subject: Thomas, 10/15

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

			    Rekha Thomas (Cornell)

		Grobner basis methods for integer programming
 

Consider the family of integer programs of the form
		Min cx : Ax = b,  x in N^n  
obtained by varying the right hand side vector b but keeping A and c fixed. 
We describe a unique minimal test set for this family, called the reduced 
Grobner basis.  Algebraically, this test set arises as the reduced Grobner 
basis of the toric ideal associated with A.  We present a combinatorial 
version of Buchberger's Grobner basis algorithm for this class of problems.

As a special case we discuss the perfect f-matching problem on the complete 
graph K_n.  An explicit description is given of test sets for all graphs 
with eight vertices or less.  We briefly indicate the role of the above 
test sets in studying  triangulations of the second hypersimplex, that is, 
the convex hull of columns of the vertex-edge incidence matrix of K_n.

From propp(at-sign)math.mit.edu Thu Oct 14 12:41:50 1993
To: combinatorics(at-sign)math.mit.edu
Subject: Landau, 10/20

Wednesday, October 20, 4:35 p.m.; MIT, room 2-338

	        Susan Landau (U. Mass. Amherst)

            Embedding linkages on an integer lattice

Using links and joints, one can build an "erector set" type linkage 
in which angles are free to change, but lengths and collinearity 
properties are fixed.  A problem in computer-aided design raised the 
question of when such a linkage can be embedded in an integer lattice,
assuming one is allowed to shift lengths by epsilon, but collinearity 
properties must be preserved.  What is the minimal epsilon that will 
allow an embedding where each of the edges has its endpoints on integer 
vertices in the lattice?

We show here that the question of whether a linkage can be embedded on the
integer lattice is NP-complete, an unhappy situation.  But all is not lost:
for applications, it is quite reasonable to assume that lengths are bounded,
as are the number of "co-incident" polygons.  With these caveats, we show 
there is a polynomial time solution to the problem.

We note that the problem has some nice ties to number theory: the linkage
can be embedded only if each of its links can, and this can happen if and
only if each of the links has a length whose square can be written as the
sum of two squares.  We explore these connections further in the paper.

From propp(at-sign)math.mit.edu Thu Oct 14 12:52:34 1993
To: combinatorics(at-sign)math.mit.edu
Subject: Collins, 10/22

Friday, October 22, 4:15 p.m.; MIT, room 2-338

		   Karen Collins (Wesleyan)

		Chromatic difference sequences
 

Define G to be stable if the normalized chromatic difference sequence of G
is equal to the normalized chromatic difference sequence of G times G, the 
Cartesian product of G with itself.  Zhou has shown that circulants and 
Cayley graphs are stable.  The chromatic difference sequence of a stable 
graph G begins with omega terms equal to alpha where omega is the clique 
number and alpha is the independence number of the graph.  If G contains 
partitionable graph H with the same clique size, then the omega+1st term 
is at least alpha(G)/alpha(H).  For stable graphs of large odd girth, this 
gives upper bounds on the independence ratio of the graph which agree with 
previously known lower bounds.  We also prove nice bounds on the 
independence ratios of circulants.

From propp(at-sign)math.mit.edu Mon Oct 18 18:18:39 1993
To: combinatorics(at-sign)math.mit.edu
Subject: Discrete Mathematics Dinner

I propose that this semester's Discrete Dinner be held at Sol Azteca
in Boston on Wednesday, November 10.

The cost would be about $20 per person (not counting drinks).  I suggest
that graduate students could pay $15 a head (excluding drinks) and the 
rest of us would pick up the difference.

Comments on this suggestion are welcome from all.

Jim

From propp(at-sign)math.mit.edu Mon Oct 25 19:24:57 1993
To: combinatorics(at-sign)math.mit.edu
Subject: Combinatorics Seminar: November Schedule

			COMBINATORICS SEMINAR

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

Wednesday, November 3, 4:35 p.m.: Francesco Brenti,
	Some combinatorial properties of Kazhdan-Lusztig polynomials

Friday, November 5, 4:15 p.m.: Alyson Reeves,
	On the radius of the Hilbert scheme

Wednesday, November 10, 4:35 p.m.: Soichi Okada,
	Algebraic structures associated to the Young-Fibonacci lattice

Friday, November 12, 4:15 p.m.: Margaret Readdy,
	Extremal problems for the Mobius function

Wednesday, November 17, 4:35 p.m.: Phil Hanlon,
	Partitions with restricted block size, Lie k-algebras 
	and the Lie(k) operad

Friday, November 19, 4:15 p.m.: Laurent Habsieger,
	Lower bounds for q-ary coverings by spheres of radius one
	

All talks will meet in room 2-338.

From propp(at-sign)math.mit.edu Mon Oct 25 19:34:19 1993
To: combinatorics(at-sign)math.mit.edu
Subject: Discrete Dinner

This semester's Discrete Dinner will be held at Sol Azteca (one of the 
best Mexican restaurants in Boston) on Wednesday, November 10.

The cost will be about $20 per person (not counting drinks).  Graduate 
students will pay $15 a head (excluding drinks) and the rest of us will
pick up the difference (aside from drinks).

I need to give the restaurant a preliminary estimate of the number of
people in our party, so if there's a positive probability that you'll 
attend, please let me know what this probability is sometime this week.
I will give the restaurant the sum of these probabilities as my estimate 
for the size of our group.

Jim Propp

From propp(at-sign)math.mit.edu Wed Oct 27 16:56:59 1993
To: combinatorics(at-sign)math.mit.edu

The following talk may be of interest to you.

		APPLIED MATHEMATICS COLLOQUIUM

	MONDAY, November 1, 1993, 4:15 p.m., Room 2-105

			TRIANGULATIONS

		     Professor C. Itzykson

	Service de Physique Theorique, Saclay, France
	        and Department of Physics, MIT

Abstract: Finite cell decompositions of surfaces (or ``fat graphs'')
appear in the perturbative expansion of matrix models.  The latter yield 
tau-functions for discrete or continuous integrable systems.  Suitable 
specializations solve combinatorial problems on the moduli space of 
algebraic curves of given genus such as virtual characteristic (Harer, 
Zagier, Penner) or intersection numbers of stable characteristic classes
(Witten, Kontsevich).  The same data record unramified arithmetic coverings 
of P_1/{0,1,infinity}.  This gives an action of  Gal(Qbar / Q)  on fat 
graphs (Belyi, Grothendieck, Voevodsky, Shabat).  We shall attempt to give 
an overview of the (few) results and (many) open problems in this area.

Refreshments will be served from 3:45 p.m. in Room 2-349

				DEPARTMENT OF MATHEMATICS
				MASSACHUSETTS INSTITUTE OF TECHNOLOGY
				CAMBRIDGE, MASSACHUSETTS 02139

From MAILER-DAEMON(at-sign)math.mit.edu Wed Oct 27 19:44:54 1993
Subject: Returned mail: Cannot send message for 2 days
To: <propp(at-sign)math.mit.edu>

   ----- Transcript of session follows -----
421 iris1.math.nctu.edu.tw: Host iris1.math.nctu.edu.tw is down

Date:           Mon, 25 Oct 93 19:13:00 EDT
From:           propp(at-sign)math.mit.edu
To:             GRADSTU(at-sign)math.mit.edu
Subject:        Discrete Mathematics Dinner

This semester's Discrete Dinner will be held at Sol Azteca (one of the 
best Mexican restaurants in Boston) on Wednesday, November 10.

The cost will be about $20 per person (not counting drinks).  Graduate 
students will pay $15 a head (excluding drinks) and the rest of us will
pick up the difference (aside from drinks).

I need to give the restaurant a preliminary estimate of the number of
people in our party, so if there's a positive probability that you'll 
attend, please let me know what this probability is sometime this week.
I will give the restaurant the sum of these probabilities as my estimate 
for the size of our group.

Jim Propp

From propp(at-sign)math.mit.edu Thu Oct 28 14:49:06 1993
To: combinatorics(at-sign)math.mit.edu
Subject: preprint

Karen Collins' article "Chromatic Difference Sequences" is now available
on-line as ~propp/public/chromatic.tex.

From propp(at-sign)math.mit.edu Mon Nov  1 13:30:27 1993
To: combinatorics(at-sign)math.mit.edu
Subject: Reeves, 11/5

Friday, November 5, 4:15 p.m.; MIT, room 2-338

		     Alyson Reeves (Brandeis)

		On the radius of the Hilbert scheme
 

Though the Hilbert scheme parametrizing subschemes of projective n-space 
has been the object of much investigation, its structure remains largely 
a mystery.  This talk will combine elements from combinatorics, Grobner 
basis theory, and algebraic geometry to bound the component-wise radius 
of the Hilbert Scheme.

From propp(at-sign)math.mit.edu Mon Nov  1 13:31:05 1993
To: combinatorics(at-sign)math.mit.edu
Subject: Brenti, 11/3

Wednesday, November 3, 4:35 p.m.; MIT, room 2-338

		   Francesco Brenti (Universita di Perugia)

	Some combinatorial properties of Kazhdan-Lusztig polynomials

Our aim in this talk is to give a simple, nonrecursive, combinatorial 
formula for any Kazhdan-Lusztig polynomial of any Coxeter group W,
and to study some consequences of it.  The main idea involved in the 
proof and statement of this formula is that of extending the concept 
of the R-polynomial to any (finite) multichain of W (so that, for 
multichains of length 1, one obtains, apart from sign, the usual 
R-polynomials).  Our main result expresses the Kazhdan-Lusztig 
polynomial of any Bruhat interval as the sum of the R-polynomials 
of its multichains. 

We then use our main result to obtain combinatorial formulas for each 
coefficient of any Kazhdan-Lusztig polynomial.  We use one of the 
special cases to characterize in purely combinatorial terms those Bruhat 
intervals whose Kazhdan-Lusztig polynomial equals the g-polynomial (as 
defined by R. Stanley) of the dual interval.  As a consequence of it 
we obtain explicit formulas for the Kazhdan-Lusztig polynomials of 
intervals which are lattices.  We also use our main result to obtain 
upper and lower bounds for the coefficients of Kazhdan-Lusztig 
polynomials.  In particular, we verify a conjecture of Lascoux-
Schutzenberger for all sufficiently long intervals.  Finally, we 
briefly sketch how it is possible to obtain analogues of all the 
results in the talk for inverse Kazhdan-Lusztig polynomials.

From propp(at-sign)math.mit.edu Mon Nov  8 13:36:27 1993
To: combinatorics(at-sign)math.mit.edu
Subject: Dinner this Wednesday

This semester's Discrete Dinner will be held at Sol Azteca (one of the 
best Mexican restaurants in Boston) on Wednesday, November 10.  

I have told the restaurant to expect us at 6:15.  Given Boston traffic 
and Boston parking, people should leave MIT at 5:45 in order to arrive
on time.  The adddress is 914A Beacon Street, in Boston; as you drive 
on Beacon away from Boston, the restaurant is on the right, a block or 
two before Brookline begins.

We will be ordering and paying for dinners individually; graduate
students will get a 20% discount (the cost of which will be shared
by the rest of us).

Jim Propp

From propp(at-sign)math.mit.edu Mon Nov  8 16:16:01 1993
To: combinatorics(at-sign)math.mit.edu
Subject: Getting to Sol Azteca

For those of you who will be coming to the restaurant by T:

Take the Red Line to Park Street in Boston.  Then take the Green Line 
(C branch) to St. Mary's Street, the first above-ground stop.  Cross 
the street and start walking back towards Boston.  The restaurant will
be half a block down Beacon on the left side (number 914).

Jim Propp

From propp(at-sign)math.mit.edu Mon Nov  8 18:58:03 1993
To: combinatorics(at-sign)math.mit.edu
Subject: Okada, 11/10

Wednesday, November 10, 4:35 p.m.; MIT, room 2-338

			     Soichi Okada (Nagoya)
 
	Algebraic structures associated to the Young-Fibonacci lattice

The Young-Fibonacci lattice is an interesting example of a differential 
poset, of which another fundamental example is Young's lattice of partitions 
ordered by inclusion of Young diagrams.  With Young's lattice are naturally 
associated the symmetric groups and the ring of symmetric functions.  In this 
talk, I construct a Young-Fibonacci analogue of
 (1) the group algebra of the symmetric group,
 (2) the ring of symmetric functions, and
 (3) the character ring of the symmetric group.

From propp(at-sign)math.mit.edu Mon Nov  8 19:24:21 1993
To: combinatorics(at-sign)math.mit.edu
Subject: Readdy, 11/12

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

		    Margaret Readdy (LACIM, Montreal)

		Extremal problems for the Mobius function
 

In the vein of recent work of Sagan, Yeh and Ziegler, we study
extremal problems connected with the Mobius function of three
families of subsets from O_n, the lattice of faces of the
n-dimensional octahedron:  lower order ideals, intervals of
rank-selections, and arbitrary rank-selections.  In each case, we
illustrate the techniques used to determine the extremal
configurations.  Also, we briefly describe other results and
present/future research.

From propp(at-sign)math.mit.edu Fri Nov 12 10:40:35 1993
To: combinatorics(at-sign)math.mit.edu
Subject: Hanlon, 11/17

Wednesday, November 17, 4:35 p.m.; MIT, room 2-338

			Phil Hanlon (Michigan)

		Partitions with restricted block size,
		Lie k-algebras and the Lie(k) operad
 

In this lecture we will combine three very different bodies of recent 
work, one combinatorial and two algebraic.  The first is the study of 
the posets of partitions where every block size is congruent to 1 mod 
k+1.  The second is the study of certain algebraic structures called 
Lie k-algebras and Liebnitz k-algebras.  The third is the theory of 
Koszul duality for operads.  Although we will not assume any background 
knowledge in these subject areas we will try to give enough of an idea
about them to demonstrate some of their close connections.

From propp(at-sign)math.mit.edu Fri Nov 12 11:03:28 1993
To: combinatorics(at-sign)math.mit.edu
Subject: Habsieger, 11/19

Friday, Nov. 19, 4:15 p.m.; MIT, room 2-338

		    Laurent Habsieger (Bordeaux and UQAM)

	Lower bounds for q-ary coverings by spheres of radius one

Let C be a q-ary covering code with covering radius one.  We give lower 
and upper bounds for the number of elements of C that lie in a fixed 
subspace of {0,...,q-1}^n.  These inequalities lead to lower bounds 
for the cardinality of C that improve on the sphere covering bound. 
More precisely we show that, if (q-1)n+1 does not divide q^n and if 
(q,n) is not in {(2,2),(2,4)}, the sphere covering bound is never 
reached.  This enables us to characterize the cases where the sphere 
covering bound is attained, when q is a prime power. We also present
some improvements of the already known lower bounds for binary and 
ternary codes.

From propp(at-sign)math.mit.edu Mon Nov 22 16:25:09 1993
To: combinatorics(at-sign)math.mit.edu
Subject: Terada, 12/1

Wednesday, December 1, 4:35 p.m.; MIT, room 2-338

	    Itaru Terada (University of Tokyo and M.I.T.)

	  An identity generalizing the length-MAJ symmetry 
		 and the variety of N-stable flags

D. Foata and M.-P. Schutzenberger showed that the number of
permutations in S_n with length i and major index j is equal
to the number of those with length j and major index i.
The two-variable generating function of this distribution 
is expressed as a sum of
	K_{lambda,(1^n)}(q) . K_{lambda,(1^n)}(t) 
for all partitions lambda of n.

Generalizing this identity, we give a combinatorial interpretation
of the sum of  
	K_{lambda,mu}(q) . K_{lambda,(1^n)}(t), 
for any fixed partition mu of n.  This interpretation is different 
from that in terms of Lascoux-Schutzenberger's charge and the major
index.

In showing the generalized identity, we look at the variety of flags
in  C^n  that are stable under a nilpotent matrix N.  We note that 
Staltenstein's partition of this variety into affine spaces is
explicitly achieved by taking the N-stable parts of Schubert cells.

From propp(at-sign)math.mit.edu Mon Nov 22 16:25:22 1993
To: combinatorics(at-sign)math.mit.edu
Subject: Combinatorics Seminar: December Schedule

			COMBINATORICS SEMINAR

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

Wednesday, December 1, 4:35 p.m.: Itaru Terada,
	An identity generalizing the length-MAJ symmetry 
	and the variety of N-stable flags

Friday, December 3, 4:15 p.m.: Sergey Fomin,
	Lattice paths, braids, and reduced decompositions

Wednesday, December 8, 4:35 p.m.: Andrei Zelevinsky,
	title to be announced

Friday, December 10, 4:15 p.m.: Mark McConnell,
	Convex polytopes and intersection cohomology of toric varieties

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

I have already begun to schedule talks for next semester, so if you're
interested in speaking, let me know.

From propp(at-sign)math.mit.edu Tue Nov 23 16:30:30 1993
To: combinatorics(at-sign)math.mit.edu
Subject: Sturmfels, 12/2

The following talk (not part of the MIT Combinatorics Seminar)
may be of interest to local combinatorialists:

The talk, "Applications of Toric Ideals", by Bernd Sturmfels,
will be in the Brandeis-Harvard-MIT colloquium at 
4:30, in Goldsmith Rm 317, at Brandeis, on
Thursday December 2.  Tea is a 4:00.  There will be a dinner
afterwards.

From propp(at-sign)math.mit.edu Tue Nov 23 18:58:11 1993
To: combinatorics(at-sign)math.mit.edu
Subject: Combinatorics Seminar: December Schedule (updated)

			COMBINATORICS SEMINAR

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

Wednesday, December 1, 4:35 p.m.: Itaru Terada,
	An identity generalizing the length-MAJ symmetry 
	and the variety of N-stable flags

Friday, December 3, 4:15 p.m.: Sergey Fomin,
	Lattice paths, braids, and reduced decompositions

Wednesday, December 8, 4:35 p.m.: Andrei Zelevinsky,
	A piecewise-linear involution arising in representation theory

Friday, December 10, 4:15 p.m.: Mark McConnell,
	Convex polytopes and intersection cohomology of toric varieties

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

From propp(at-sign)math.mit.edu Mon Nov 29 15:47:24 1993
To: combinatorics(at-sign)math.mit.edu
Subject: Terada, 12/1

Wednesday, December 1, 4:35 p.m.; MIT, room 2-338

	    Itaru Terada (University of Tokyo and M.I.T.)

	  An identity generalizing the length-MAJ symmetry 
		 and the variety of N-stable flags

D. Foata and M.-P. Schutzenberger showed that the number of
permutations in S_n with length i and major index j is equal
to the number of those with length j and major index i.
The two-variable generating function of this distribution 
is expressed as a sum of
	K_{lambda,(1^n)}(q) . K_{lambda,(1^n)}(t) 
for all partitions lambda of n.

Generalizing this identity, we give a combinatorial interpretation
of the sum of  
	K_{lambda,mu}(q) . K_{lambda,(1^n)}(t), 
for any fixed partition mu of n.  This interpretation is different 
from that in terms of Lascoux-Schutzenberger's charge and the major
index.

In showing the generalized identity, we look at the variety of flags
in  C^n  that are stable under a nilpotent matrix N.  We note that 
Staltenstein's partition of this variety into affine spaces is
explicitly achieved by taking the N-stable parts of Schubert cells.

From propp(at-sign)math.mit.edu Mon Nov 29 16:34:49 1993
To: combinatorics(at-sign)math.mit.edu
Subject: Fomin, 12/3

Friday, December 3, 4:15 p.m.; MIT, room 2-338

		    Sergey Fomin (M.I.T.)

	Lattice paths, braids, and reduced decompositions
 

Recently, a combinatorial interpretation of stable Schubert polynomials 
in terms of braid configurations was found, based on a well-known 
geometric interpretation of the Yang-Baxter equation.  In the particular 
case of 321-avoiding permutations, these polynomials are the skew Schur 
functions.  Each of corresponding braid configurations breaks up into 
two families of paths which are exactly the Gessel-Viennot paths for the 
two Jacobi-Trudi determinants.  An alternative description of this 
construction relates skew Schur functions to reduced decompositions 
in the Temperley-Lieb algebra.  Generalizations and applications include 
super-Schur functions, binomial determinants, and the $P$- and $Q$-Schur 
functions.

This is a joint work with X. G. Viennot.

From propp(at-sign)math.mit.edu Wed Dec  1 13:33:18 1993
To: combinatorics(at-sign)math.mit.edu
Subject: Zelevinsky talk cancelled

				CANCELLATION!

Andrei Zelevinsky's talk (originally scheduled for Wednesday, December 8)
has been cancelled, on account of a conflict with the MIT math department's
holiday party, which has been scheduled at the last minute for the same
afternoon.  My apologies to all.  Prof. Zelevinsky will give a lecture on
his originally-announced topic ("A piecewise-linear involution arising in 
representation theory") in February.

From propp(at-sign)math.mit.edu Fri Dec  3 18:00:53 1993
To: combinatorics(at-sign)math.mit.edu
Subject: McConnell, 12/10

Friday, December 10, 4:15 p.m.; MIT, room 2-338

		    Mark McConnell (M.I.T.)

    Convex polytopes and intersection cohomology of toric varieties

McMullen's conjecture characterized the f-vectors of simplicial
convex polytopes Delta.  Stanley's proof of (one direction of) this
conjecture used the cohomology  H^*(X, C)  of the toric variety
X associated to Delta.  Let  omega in H^2(X, C)  be the Lefschetz 
hyperplane class.  Key facts for Stanley's proof were that the 
quotient  H^*(X, C)/(omega)  is a graded ring generated by H^2.

When Delta is an arbitrary rational convex polytope, one can ask
about the analogues in intersection cohomology: is IH^*(X, C)/(omega)
a ring, and is it generated by IH^2 ?  I will discuss preliminary 
results on these questions, as well as approaches for computing the 
intersection cohomology.