From propp(at-sign)math.mit.edu Tue Jan 17 17:40:40 1995
To: combinatorics(at-sign)math.mit.edu
Subject: Combinatorics and Graph Theory day at Smith

Posted on behalf of Karen Collins:

Come to the fourteenth one day conference on

Combinatorics and Graph Theory

Saturday, February 18, 1994

10 a.m. to 4:30 p.m.
at
Smith College
Northampton MA 01063

Schedule

10:00  Neil Calkin
Random Birthdays, Random Walks and Random Vectors

11:10  Nate Dean
Interactive and Incomprehensible Graphs

12:10  Lunch

2:00   Kathleen Romanik
A Three Dimensional Visibility Representation for Graphs

3:10   Jay Goldman
Knots, Tangles, and Electrical Networks

Directions to Burton Hall, Smith College  (Updated 8/3/94)

1. Take I-91 to exit 18. Make a left off the ramp.

2. You are now on Pleasant Street (Rte. 5) heading towards Northampton
Center. Go about 1 mile to the first light.

3. Make a left here onto Main Street (Rte. 9).

4. Go to the second light and make a left onto West Street (Rte. 66).

5. Make the next right onto Green Street.

6. Take the second right into the parking lot.  This will lead you into
the Dickenson parking lot. You can park here.  If this lot is full,
go back onto Green Street the same way you were going until the road
forks at College Lane.  Turn left down the hill.  The Ainsworth Gym
parking lot entrance is the second left.

7. To get to Burton from the Dickenson lot, walk back out to Green Street
and continue down it to the end. Make a right onto College Lane.  To get
to Burton from the Ainsworth lot, walk up the hill along College Lane
and enter Burton from the courtyard area, see 8 below.

8. Burton is the third building on your right. Just before Burton is a
small courtyard area with a skyway between buildings. Enter Burton from
this courtyard area. The only door open on Saturday is the first one you
will come to (it has a handicap accessible ramp).

9. Enter the building and go straight until you see a circular stairway
on your right. Take the stairway (or elevator in the middle of it) to the
third floor of Burton (not Sabin Reed). (If you take the elevator this
will mean that you exit on the opposite side than you entered.) Once on
the third floor go left to the Math forum area.

We have received an NSF grant to support these conferences. This will allow
us to provide a modest transportation allowance to those attendees who are
not local.

Mike Albertson (Smith College), (413) 585-3865, albertson(at-sign)smith.smith.edu

Karen Collins (Wesleyan Univ.), (203) 685-2169, kcollins(at-sign)eagle.wesleyan.edu

Ruth Haas (Smith College), (413) 585-3872, rhaas(at-sign)smith.smith.edu

From propp(at-sign)math.mit.edu Sun Jan 29 19:55:41 1995
To: combinatorics(at-sign)math.mit.edu
Subject: MIT Combinatorics: February schedule

MIT COMBINATORICS SEMINAR

Here is the current list of talks scheduled for the month of February.

Wednesday, February 8, 4:15 p.m.: Christos Athanasiadis,
Spectra of graphs and the branching operation

Friday, February 10, 4:15 p.m.: Dan Ullman,
Multicolorings of graphs

Wednesday, February 15, 4:15 p.m.: Michael Albertson,
The normalized chromatic difference sequence of a graph

Friday, February 17, 4:15 p.m.: Julian West,
Recent forbidden-subsequenciana

Wednesday, February 22, 4:15 p.m.: David Wagner,
Toric varieties associated with finite distributive lattices

All talks will meet in room 2-338.

From propp(at-sign)math.mit.edu Wed Feb  1 19:34:22 1995
To: combinatorics(at-sign)math.mit.edu
Subject: Athanasiadis, 2/8 (at 4:30 p.m.)

Wednesday, February 8, 4:30 p.m.; MIT, room 2-338
^^^^
(note changed starting time!)

Spectra of graphs and the branching operation

The "branching" operation, defined by J. Propp, assigns to a given
digraph G another digraph D(G), whose vertices are the oriented spanning
rooted trees of G.  Using an elementary counting argument, we describe
eigenvalues of the induced subgraphs and the Laplacian of G.  A conjecture
of Propp follows as a special case.  We also attempt a brief introduction
to the theory of spectra of graphs.

Please note that the starting time for this lecture has been changed
from the time originally announced.

From propp(at-sign)math.mit.edu Thu Feb  2 12:01:50 1995
To: combinatorics(at-sign)math.mit.edu
Subject: Talk by Michel Brion

The following talk may be of interest to subscribers to this list:

Harvard-Brandeis-MIT-Northeastern Colloquium at Northeastern U, Feb. 9

Michel Brion (U. Grenoble)

"Convex Polytopes, Piecewise Polynomial Functions, and
Enumerative Geometry"

4:30 PM at 200 Richards Hall, Thursday Feb. 9

(Tea at 4 PM, Churchill Hall Faculty Dining Room)

Abstract: The talk will be about recent results of McMullen
concerning the polytope algebra, and of Morelli, Fulton, Sturmfels,
and others concerning its connections with the Chow rings of toric
varieties.

For further info or directions, see posted announcements, or
phone (617)-373-2450, e-mail iarrobin(at-sign)neu.edu. Parking vouchers available.

From propp(at-sign)math.mit.edu Mon Feb  6 15:17:08 1995
To: combinatorics(at-sign)math.mit.edu
Subject: Ullman, 2/10

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

Dan Ullman (George Washington)

Multicolorings of graphs

The n-chromatic number  \chi_n (G)  of a graph G is the smallest number
of colors needed to color the vertices, putting n colors on each vertex,
subject to the constraint that adjacent vertices get disjoint sets of
colors.  Recently, Saul Stahl showed that the 11-chromatic number of the
so-called Grotzsch graph is 32.  In this talk, we survey results about
sequences of the form  \chi (G) , \chi_2 (G) , \chi_3 (G) , ...  and
explain the importance of Stahl's discovery.

From propp(at-sign)math.mit.edu Mon Feb  6 20:48:01 1995
To: combinatorics(at-sign)math.mit.edu
Subject: travel to Northampton on the 18th

If anyone is planning to travel to the Smith one-day conference on the 18th

Jim Propp

From propp(at-sign)math.mit.edu Wed Feb  8 15:50:08 1995
To: combinatorics(at-sign)math.mit.edu
Subject: Albertson, 2/15

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

Michael Albertson (Smith)

The normalized chromatic difference sequence of a graph

Almost twenty years ago Greene and Kleitman showed that the chain
and antichain partition sequences of a poset are conjugate.  Partially
in response to that result David Berman and I began investigations into
what we called the chromatic difference sequence of a graph.  This talk
will introduce the natural generalization of the antichain partition
sequence, highlight the results that have been obtained, propose several
open (dare I say intriguing) questions, and describe recent progress
(mostly joint work with Ruth Haas) on edge versions.

From propp(at-sign)math.mit.edu Wed Feb  8 16:08:09 1995
To: combinatorics(at-sign)math.mit.edu
Subject: West, 2/17

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

Julian West (CECM, SFU, Vancouver)

Recent forbidden-subsequenciana

A survey of papers and preprints, by myself and others, which have
appeared in the 28 months since my last address to this seminar.
The general theme remains the enumeration of permutations under certain
forbidden-subsequence restrictions, a problem which continues to
sustain a small cottage industry.  As usual, there will be a number
of open problems cited, and an effort will be made to suggest directions
for future research.

From propp(at-sign)math.mit.edu Wed Feb 15 11:12:27 1995
To: combinatorics(at-sign)math.mit.edu
Subject: Wagner, 2/22

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

David Wagner (Waterloo)

Toric varieties associated with finite distributive lattices

With each finite lattice L one associates a projectively embedded
scheme V(L) in a natural way.  As Hibi has observed, the lattice D
is distributive if and only if V(D) is irreducible, in which case it
is a toric variety.  We will review this result and investigate further
connections between the combinatorics of D and the geometry of V(D),
including its orbit decomposition, locus of singularities, and structure
of the normal cones of orbit closures.  The methods employed are primarily
combinatorial, relying on the Birkhoff structure theorem for finite
distributive lattices, Mobius inversion, the matrix-tree theorem, and
combinatorial/topological properties of the Hasse graph of the poset
P of join-irreducibles of D.  We will sketch a proof that each orbit
closure of V(D) has an irreducible normal cone if and only if P is a
dismantlable poset.  This result indicates that for dismantlable posets P
(in particular, for planar posets) intersection theory on V(D) may be
more easily described than in the general case.

From propp(at-sign)math.mit.edu Fri Feb 17 15:25:16 1995
To: combinatorics(at-sign)math.mit.edu
Subject: MIT Combinatorics: March schedule

MIT COMBINATORICS SEMINAR

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

Wednesday, March 1, 4:15 p.m.: Ivan Cherednik,
Products of symmetric polynomials through Hecke algebras

Friday, March 3, 4:15 p.m.: Anatol Kirillov,
Combinatorics of the Kostka-Foulkes polynomials

Wednesday, March 8, 4:15 p.m.: Richard Ehrenborg,
Sheffer posets and $r$-signed permutations

Friday, March 10, 4:15 p.m.: Egon Schulte,
The combinatorics and geometry of chiral polytopes

Wednesday, March 15, 4:15 p.m.: Francesco Brenti,
The combinatorics of Kazhdan-Lusztig polynomials

Friday, March 17, 4:15 p.m.: Sergey Fomin,
Parametrizing canonical bases and totally positive matrices

Wednesday, March 22, 4:15 p.m.: Dan Klain,
A short proof of Hadwiger's characterization theorem

On Wednesday, April 5, there will be an open mike'' (a combinatorial
free-for-all).  We all know that some of the most important exchanges
of ideas take place at conferences -- not during talks, but between them.
Why not try to create some of that atmosphere while we're here in our own
town?  Bring short explanations of nice recent results of yours (whether
they're cute lemmas you needed in your work or solutions to problems you
saw in the Monthly), or bring questions about the combinatorial literature,
or bring a list of good open problems you want to advertise, or just come
to listen.  If you're planning on presenting something, let Jim Propp know
ahead of time (call 253-6544 or write to propp(at-sign)math.mit.edu).

All talks will meet in room 2-338.

From propp(at-sign)math.mit.edu Tue Feb 21 21:45:45 1995
To: combinatorics(at-sign)math.mit.edu
Subject: Cherednik, 3/1

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

Ivan Cherednik (North Carolina, Harvard)

Products of symmetric polynomials through Hecke algebras

As it was found recently, double affine Hecke algebras arise naturally
when we multiply the monomial symmetric functions  x^{n}+x^{-n}  by
Schur functions  (x^{m+1}-x^{-m-1})/(x^{1}-x^{-1})  and "uniformly"
express the products in terms of the latter.  This observation can be
extended to arbitrary Macdonald's polynomials.

From propp(at-sign)math.mit.edu Tue Feb 21 22:01:57 1995
To: combinatorics(at-sign)math.mit.edu
Subject: Kirillov, 3/3

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

Combinatorics of the Kostka-Foulkes polynomials

We describe a bijection between the set of semi-standard Young tableaux
and the set of rigged configurations.  Applications to the combinatorics
of Kostka-Foulkes-Lusztig polynomials will be discussed.

From propp(at-sign)math.mit.edu Tue Feb 28 15:35:57 1995
To: combinatorics(at-sign)math.mit.edu
Subject: MIT Combinatorics: March schedule (REVISED)

MIT COMBINATORICS SEMINAR

Here is the revised list of talks currently scheduled for the month of March.
Note the added talks by Kauffman on the 9th and Rota on the 24th.

Wednesday, March 1, 4:15 p.m.: Ivan Cherednik,
Products of symmetric polynomials through Hecke algebras

Friday, March 3, 4:15 p.m.: Anatol Kirillov,
Combinatorics of the Kostka-Foulkes polynomials

Wednesday, March 8, 4:15 p.m.: Richard Ehrenborg,
Sheffer posets and $r$-signed permutations

Thursday, March 9, 1:00 p.m.: Louis Kauffman,
Quantum groups, Hopf algebras and knots

Friday, March 10, 4:15 p.m.: Egon Schulte,
The combinatorics and geometry of chiral polytopes

Wednesday, March 15, 4:15 p.m.: Francesco Brenti,
The combinatorics of Kazhdan-Lusztig polynomials

Friday, March 17, 4:15 p.m.: Sergey Fomin,
Parametrizing canonical bases and totally positive matrices

Wednesday, March 22, 4:15 p.m.: Dan Klain,
A short proof of Hadwiger's characterization theorem

Friday, March 24, 4:15 p.m.: Gian-Carlo Rota,
Combinatorial methods in homological algebra

And don't forget:

Wednesday, April 5, 4:15 p.m.: Combinatorial free-for-all

All talks will meet in room 2-338.

From propp(at-sign)math.mit.edu Wed Mar  1 09:53:50 1995
To: combinatorics(at-sign)math.mit.edu
Subject: Talk at Northeastern by Kirillov on March 6

Of possible interest to subscribers to this mailing-list:

Anatol Kirillov will speak at the Northeastern University Geometry-Algebra-
Singularities Seminar on Monday, March 6, at 1:30 PM, in 509 Lake Hall.  His
topic will be "Dilogarithm Identities".

From propp(at-sign)math.mit.edu Wed Mar  1 10:04:18 1995
To: combinatorics(at-sign)math.mit.edu
Subject: Ehrenborg, 3/8

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

Richard Ehrenborg (UQAM)

Sheffer posets and r-signed permutations

We study a class of posets, which we call Sheffer posets.
These posets were also studied by Vic Reiner.  Sheffer
posets are a generalization of binomial posets.  Their
incidence algebra has two interesting subspaces.  These
spaces behave like a ring and a module, and are isomorphic
to certain generating functions.

We also generalize the concept of R-labelings to linear
edge-labelings, and prove a result analogous to a theorem
of Bjorner and Stanley about R-labelings.  This, together
with the theory of rank-selections from a Sheffer poset,
enables us to study augmented r-signed permutations.

This is joint work with Margaret Readdy.

From propp(at-sign)math.mit.edu Wed Mar  1 10:22:20 1995
To: combinatorics(at-sign)math.mit.edu
Subject: Kauffman, 3/9

Thursday, March 9, 1:00 p.m.; MIT, room 2-338
^^^^^^^^
(note unusual time)

Special meeting:
Louis Kauffman (University of Chicago at Illinois)

Quantum groups, Hopf algebras and knots

This is an introductory talk about the relationships of the subjects
in the title.  We discuss how Hopf algebras give rise to knot invariants
and to invariants of 3-manifolds and raise questions about how these
approaches are related to combinatorics and state sums.

From propp(at-sign)math.mit.edu Wed Mar  1 11:54:51 1995
To: combinatorics(at-sign)math.mit.edu
Subject: Schulte, 3/10

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

Egon Schulte (Northeastern)

The combinatorics and geometry of chiral polytopes

Abstract polytopes are discrete geometric structures which generalize the
traditional notion of a convex polytope.  These objects usually have a quite
sophisticated combinatorics and topology.  Chirality in abstract polytopes
is a fascinating phenomenon which competes with the more well-behaving
regularity.  Chiral polytopes are those abstract polytopes which have
maximal symmetry by (combinatorial) rotation, in contrast to the abstract
regular polytopes which have maximal symmetry by (combinatorial)
reflection.  The geometric structure of chiral polytopes is currently best
understood in ranks 3 and 4. We discuss some of the main problems in
this area including the classification of polytopes by topological type,
the phenomenon of enantiomorphism, and certain extension problems for
chiral polytopes and their groups.

From propp(at-sign)math.mit.edu Fri Mar  3 20:06:50 1995
To: combinatorics(at-sign)math.mit.edu
Subject: Garsia, 3/9

Thursday, March 9, 4:15 p.m.; room to be announced

Special meeting:

Science fiction and Macdonald polynomials

The talk will give a science-fiction explanation to some patterns
that have been observed in the table of the q,t-Kostka coefficients.

This work is joint with Francois Bergeron and Mark Haiman.

From propp(at-sign)math.mit.edu Wed Mar  8 15:51:13 1995
To: combinatorics(at-sign)math.mit.edu
Subject: MIT Combinatorics Seminar

This is just a reminder that there are FOUR talks this week:

Wednesday, March 8, 4:15 p.m.; MIT, room 2-338
Richard Ehrenborg (UQAM)
Sheffer posets and r-signed permutations

Thursday, March 9, 1:00 p.m.; MIT, room 2-338
Louis Kauffman (University of Chicago at Illinois)
Quantum groups, Hopf algebras and knots

Thursday, March 9, 4:15 p.m.; MIT, room 2-338
Science fiction and Macdonald polynomials

Friday, March 10, 4:15 p.m.; MIT, room 2-338
Egon Schulte (Northeastern)
The combinatorics and geometry of chiral polytopes

From propp(at-sign)math.mit.edu Thu Mar  9 22:32:47 1995
To: combinatorics(at-sign)math.mit.edu
Subject: Brenti, 3/15

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

Frencesco Brenti (IAS)

The combinatorics of Kazhdan-Lusztig polynomials

In 1979 Kazhdan and Lusztig defined, for every Coxeter group W, a family
of polynomials, indexed by pairs of elements of W, which have become known
as the Kazhdan-Lusztig polynomials of W.  These polynomials are intimately
related to the Bruhat order of W and to the algebraic geometry and topology
of Schubert varieties, and have proved to be of fundamental importance in
representation theory.

While Kazhdan-Lusztig polynomials are usually defined algebraically in
terms of Hecke algebras, in recent years purely combinatorial rules
to compute them have been found.  These rules not only make these objects
more concrete, and accessible to a wider audience, but also enable
combinatorial reasoning and techniques to be applied to them.  Since
these polynomials are still not very well understood, and several
conjectures and open problems exist about them, many of a combinatorial
nature, we feel that these combinatorial rules are worthy of further
investigation.

In this talk we survey and illustrate one of these rules as well as the
main combinatorial properties which are known for the Kazhdan-Lusztig
polynomials, and we present some intriguing conjectures and open problems
(some old and some new) together with the evidence that exists for them.

From propp(at-sign)math.mit.edu Thu Mar  9 22:35:39 1995
To: combinatorics(at-sign)math.mit.edu
Subject: Fomin, 3/17

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

Sergey Fomin (MIT)

Parametrizing canonical bases and totally positive matrices

Let N be the group of n by n unipotent upper-triangular matrices.
G. Lusztig discovered a close connection between the following two problems:
(i)  studying the piecewise-linear maps that relate different labelings of
the canonical basis in the quantized enveloping algebra of the Lie
algebra of N;
(ii) studying the variety of totally positive elements of N.
(Lusztig's theory holds in greater generality, when N is a maximal unipotent
subgroup of a semisimple group of simply-laced type; for the moment, we only
treat the A case.)

Jointly with A. Berenstein and A. Zelevinsky, we obtained:
(i)  explicit closed formulas for these piecewise-linear maps;
(ii) formulas for decomposing an upper-triangular matrix into a product of
elementary Jacobi matrices, and related total positivity criteria.

Our methods employ a combinatorial Ansatz based on representing
commutation classes of reduced words by pseudoline arrangements.

No background in quantum groups will be required for understanding.

From propp(at-sign)math.mit.edu Tue Mar 14 17:44:27 1995
To: combinatorics(at-sign)math.mit.edu
Subject: Klain, 3/22

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

Dan Klain (Georgia Tech)

A characterization theorem for volume

One of the most beautiful and important results in geometric convexity
is Hadwiger's characterization theorem for the elementary mixed volumes
(quermassintegrals).  Hadwiger's theorem classifies all convex-continuous
valuations that are invariant under rotations and translations as consisting
of the linear span of the elementary mixed volumes (or, equivalently, of
the intrinsic volumes of McMullen).  This characterization theorem leads
to effortless proofs of numerous results in integral geometry (including
various kinematic formulas and the mean projection formulas for convex
bodies) and also provides a connection between rigid motion invariant set
functions and symmetric polynomials.

Hadwiger's theorem is easily shown to be equivalent to a characterization
theorem for the volume as a valuation on compact convex subsets of Euclidean
space.  Unfortunately the original proof of this volume characterization
(the only known proof until now) is the product of a long and arduous
sequence of cut and paste arguments scattered through over 100 pages of
text.  The purpose of this talk is to present a new and more general
characterization of volume in Euclidean space, whose proof is digestible
within a few minutes.

(Note: This supersedes an earlier announcement that gave a different title
and abstract.)

From propp(at-sign)math.mit.edu Tue Mar 14 17:56:43 1995
To: combinatorics(at-sign)math.mit.edu
Subject: Rota, 3/24

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

Gian-Carlo Rota (M.I.T.)

Combinatorial methods in homological algebra

This is a survey of the work done so far in collaboration with David
Buchsbaum obtaining a characteristic-free resolution of Schur and Weyl
functors.  Some of the general techniques that we were led to in the
course of working on this problem will be described.

From propp(at-sign)math.mit.edu Tue Mar 28 16:10:21 1995
To: combinatorics(at-sign)math.mit.edu
Subject: MIT Combinatorics: April schedule

MIT COMBINATORICS SEMINAR

Here is a revised list of talks scheduled for the month of April.
Note the new talks scheduled for April 5, April 19, and April 28.
Also note that the open mike originally scheduled for April 5
has been moved to April 12.

Wednesday, April 5, 4:15 p.m.: Kimmo Eriksson,
Combinatorial aspects of Fulton's essential set

Friday, April 7, 4:15 p.m.: Jim Haglund,
Colored rook placements

Wednesday, April 12, 4:15 p.m.: Jim Propp, Richard Stanley, and others,
Open mike

Wednesday, April 19, 4:15 p.m.: Lenore Cowen,
Defective colorings revisited

Friday, April 21, 4:15 p.m.: Susanna Fishel,
Canonical bases for the Birman-Wenzl algebra

Wednesday, April 26, 4:15 p.m.: Margaret Readdy,
The r-cubical lattice and a generalization of cd-index

Friday, April 28, 4:15 p.m.: Dana Randall,
Generating random surfaces, tilings and Eulerian orientations

At the combinatorial open mike day to be held on April 12, Richard Stanley
will speak about a particular determinant that counts paths in acyclic
digraphs, and Jim Propp will give a quasi-combinatorial interpretation of
the relation  2^{-1} = 1/2  via the Euler characteristic'' of an infinite-
dimensional polytope.  Others wishing to give short presentations should
contact Jim Propp (propp(at-sign)math.mit.edu; 253-6544).

All talks will meet in room 2-338.

From propp(at-sign)math.mit.edu Tue Mar 28 16:13:32 1995
To: combinatorics(at-sign)math.mit.edu
Subject: Eriksson, 4/5

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

Kimmo Eriksson (KTH)

Combinatorial aspects of Fulton's essential set

A square matrix with one "dot" in each row and column defines a
permutation.  The "diagram" of this permutation is obtained by
deleting the squares in each row from the dot and eastwards, and
deleting the squares in each column from the dot and southwards.
The _essential_set_ of a permutation was defined by Fulton as
the set of southeast corners of the diagram. I will discuss some
combinatorial aspects: characterization,  enumeration, and
application, of the essential set.  For example, how big is the
essential set on average?  Some nice formulas appear!

For the nicest formula, one needs to know the number of "extendably
321-avoiding dotted matrices".  Pursuing my old interest in chips
games, I will show how this problem can be solved by considering
a game of moving around chips.

This is joint work with Svante Linusson.

From propp(at-sign)math.mit.edu Tue Mar 28 16:17:15 1995
To: combinatorics(at-sign)math.mit.edu
Subject: Haglund, 4/7

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

Jim Haglund (Kennesaw)

Colored rook placements

Recent work in rook theory by Chung, Graham and others has centered around
enumerating permutations by number of cycles.  In this talk we introduce a
number of parameters which generalize the cycle parameter, and show that
for Ferrers boards the rook factorial polynomial factors as in the classical
case.  Applications include an interpretation in terms of rook polynomials
of certain types of hypergeometric series which arise in physics.

This is joint work with Richard Ehrenborg and Margaret Readdy.

From propp(at-sign)math.mit.edu Tue Mar 28 17:36:58 1995
To: combinatorics(at-sign)math.mit.edu
Subject: MIT Combinatorics: April schedule (NOTE CANCELLATION!)

MIT COMBINATORICS SEMINAR

Here is a re-revised list of talks scheduled for the month of April.

Kimmo Eriksson's talk, announced for April 5 earlier today, will be
moved to another date (to be announced) so as not to conflict with
John Harbison's Killian lecture.

Friday, April 7, 4:15 p.m.: Jim Haglund,
Colored rook placements

Wednesday, April 12, 4:15 p.m.: Jim Propp, Richard Stanley, and others,
Open mike

Wednesday, April 19, 4:15 p.m.: Lenore Cowen,
Defective colorings revisited

Friday, April 21, 4:15 p.m.: Susanna Fishel,
Canonical bases for the Birman-Wenzl algebra

Wednesday, April 26, 4:15 p.m.: Margaret Readdy,
The r-cubical lattice and a generalization of cd-index

Friday, April 28, 4:15 p.m.: Dana Randall,
Generating random surfaces, tilings and Eulerian orientations

At the combinatorial open mike day to be held on April 12, Richard Stanley
will speak about a particular determinant that counts paths in acyclic
digraphs, and Jim Propp will give a quasi-combinatorial interpretation of
the relation  2^{-1} = 1/2  via the "Euler characteristic" of an infinite-
dimensional polytope.  Others wishing to give short presentations should
contact Jim Propp (propp(at-sign)math.mit.edu; 253-6544).

All talks will meet in room 2-338.

From propp(at-sign)math.mit.edu Tue Apr  4 10:22:51 1995
To: combinatorics(at-sign)math.mit.edu
Subject: Haglund, 4/7

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

Jim Haglund (Kennesaw)

Colored rook placements

Recent work in rook theory by Chung, Graham and others has centered around
enumerating permutations by number of cycles.  In this talk we introduce a
number of parameters which generalize the cycle parameter, and show that
for Ferrers boards the rook factorial polynomial factors as in the classical
case.  Applications include an interpretation in terms of rook polynomials
of certain types of hypergeometric series which arise in physics.

This is joint work with Richard Ehrenborg and Margaret Readdy.

From propp(at-sign)math.mit.edu Tue Apr  4 10:22:51 1995
To: combinatorics(at-sign)math.mit.edu
Subject: MIT Combinatorics: April schedule (new talk added)

MIT COMBINATORICS SEMINAR

Here is a final list of talks scheduled for the month of April.
Note that Kimmo Eriksson's talk has been re-scheduled for April 14.

Friday, April 7, 4:15 p.m.: Jim Haglund,
Colored rook placements

Wednesday, April 12, 4:15 p.m.: M. Albertson, J. Propp, R. Stanley et al.,
Open mike

Friday, April 14, 4:15 p.m.: Kimmo Eriksson,
Combinatorial aspects of Fulton's essential set

Wednesday, April 19, 4:15 p.m.: Lenore Cowen,
Defective colorings revisited

Friday, April 21, 4:15 p.m.: Susanna Fishel,
Canonical bases for the Birman-Wenzl algebra

Wednesday, April 26, 4:15 p.m.: Margaret Readdy,
The r-cubical lattice and a generalization of cd-index

Friday, April 28, 4:15 p.m.: Dana Randall,
Generating random surfaces, tilings and Eulerian orientations

At the combinatorial open mike day to be held on April 12, Richard Stanley
will speak about a particular determinant that counts paths in acyclic
digraphs, Jim Propp will give a quasi-combinatorial interpretation of
the relation  2^{-1} = 1/2  via the Euler characteristic'' of an
infinite-dimensional polytope, and Mike Albertson will present on a problem
on automorphism groups acting on graphs.  Others wishing to give short
presentations should contact Jim Propp (propp(at-sign)math.mit.edu; 253-6544).

All talks will meet in room 2-338.

From propp(at-sign)math.mit.edu Thu Apr  6 12:40:50 1995
To: combinatorics(at-sign)math.mit.edu
Subject: Discrete Dinner

The next Discrete Dinner will be held at newly re-opened Mary Chung's
near MIT.

The cost for graduate students and undergraduates will be held down to $7 (drinks included), with the rest of us making up the difference. (The cost for the rest of us will of course depend on the ratio between the two classes of diners, but the total paid by each non-student should be less than$20.)  Please let me know the relative convenience of the
following proposed dates:

Weds., April 26
Fri., April 28
Weds., May 3
Fri., May 5
Weds., May 10
Fri., May 12

Jim Propp

(Send replies to propp(at-sign)math.mit.edu)

From propp(at-sign)math.mit.edu Thu Apr  6 13:28:21 1995
To: combinatorics(at-sign)math.mit.edu
Subject: Free-for-all, 4/12

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

All of Us (from All Over the Boston Area)

Open Mike Session / Combinatorial Free-for-All

We all know that some of the most important exchanges of ideas take
place at conferences -- not during talks, but between them.  Why not
try to create some of that atmosphere while we're here in our own
town?  Bring short explanations of nice recent results of yours
(whether they're cute lemmas you needed in your work or solutions to
problems you saw in the Monthly), or bring questions about the
combinatorial literature (What should I read to learn about
oriented matroids?''), or bring a list of good open problems you want
to advertise.  Or whatever.  Let me know ahead of time what you're
bringing, if you plan on presenting something that will take longer
than five minutes.

Currently scheduled presenters are Richard Stanley, who will talk about
a particular determinant that counts paths in acyclic digraphs, and
Jim Propp, who will give a quasi-combinatorial interpretation of the
relation  2^{-1} = 1/2  via the Euler characteristic'' of an infinite-
dimensional polytope; and Mike Albertson, who will present a problem
on automorphism groups acting on graphs.

Others wishing to give short presentations should contact Jim Propp
(propp(at-sign)math.mit.edu; 253-6544).

From propp(at-sign)math.mit.edu Thu Apr  6 14:02:59 1995
To: combinatorics(at-sign)math.mit.edu
Subject: Eriksson, 4/14

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

Kimmo Eriksson (KTH)

Combinatorial aspects of Fulton's essential set

A square matrix with one "dot" in each row and column defines a
permutation.  The "diagram" of this permutation is obtained by
deleting the squares in each row from the dot and eastwards, and
deleting the squares in each column from the dot and southwards.
The _essential_set_ of a permutation was defined by Fulton as
the set of southeast corners of the diagram. I will discuss some
combinatorial aspects: characterization,  enumeration, and
application, of the essential set.  For example, how big is the
essential set on average?  Some nice formulas appear!

For the nicest formula, one needs to know the number of "extendably
321-avoiding dotted matrices".  Pursuing my old interest in chips
games, I will show how this problem can be solved by considering
a game of moving around chips.

This is joint work with Svante Linusson.

From propp(at-sign)math.mit.edu Tue Apr 11 19:46:04 1995
To: combinatorics(at-sign)math.mit.edu
Subject: Reminder

Today's combinatorics seminar (Wednesday, April 12) will be an Open Mike.
Currently scheduled "mini-speakers" are Mike Albertson, Tim Chow, Kimmo
Eriksson, Igor Pak, Alexander Postnikov, Jim Propp, Richard Stanley, Herb
Wilf, and Andrei Zelevinsky.  (This doesn't leave much room for spontaneous
mini-talks by others, but if we run out of time, we can schedule another
Open Mike in May.)

From propp(at-sign)math.mit.edu Tue Apr 11 20:03:22 1995
To: combinatorics(at-sign)math.mit.edu
Subject: Cowen, 4/19

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

Lenore Cowen (Johns Hopkins)

Defective colorings revisited

A graph is said to be (n,k) colorable, if its vertices can be
colored with n colors, so that any vertex has at most k
self-colored neighbors. Cowen, Cowen and Woodall gave in 1986 a
complete characterization of for which n and k is every planar
graph (n,k) colorable. We extend to the torus, and show that every
graph on the torus is (3,2) colorable (solving an 8-year old
conjecture), and (5,1) colorable. It is still open if every torodial
graph is (4,1) colorable. We also improve some bounds for defective
chromatic number of general graphs.

We  also consider the complexity of finding defective colorings.  We
show (n,k) coloring is NP-complete for n >= 2 and k >= 1. We
show (2,1) and (3,1) coloring remain NP-complete, even for planar
graphs. We present polynomial-time approximation schemes and
discuss open questions.

This is joint work with W. Goddard and E. Jesurum.

From propp(at-sign)math.mit.edu Tue Apr 11 20:07:51 1995
To: combinatorics(at-sign)math.mit.edu
Subject: Fishel, 4/21

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

Susanna Fishel (Southern Connecticut State)

Canonical bases for the Birman-Wenzl algebra

In this talk, which is a summary of joint work with I. Grojnowski, we construct
Kahzdan-Lusztig bases for the Birman-Wenzl algebra BW_n, and so define left,
right, and two-sided cells.  We describe these objects combinatorially, using a
generalization of the Robinson-Schensted algorithm for the symmetric group, and
show that each left cell carries an irreducible representation of BW_n.  In
particular, we obtain canonical bases for each representation, defined over Z.

From CCHEN(at-sign)WELLESLEY.EDU Wed Apr 19 14:05:32 1995
Subject: Are you going to Smith on 4/22?
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"
X-VMS-Cc: CCHEN
MIME-version: 1.0
Content-type: TEXT/PLAIN; CHARSET=US-ASCII
Content-transfer-encoding: 7BIT

Hi,

I am math major at Wellesley and I would like to go to the Combinatorics
and Graph Theory conference at Smith this Saturday.  I have a ride there,
but I don't have one back.  If you are attending and coming back to MIT/
Cambridge/Boston that evening, could you give me a ride back?  I'd have no
problem getting from the MIT area back to Wellesley on my own.  Thank you

Christina Chen

From propp(at-sign)math.mit.edu Wed Apr 19 21:36:36 1995
To: combinatorics(at-sign)math.mit.edu

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

The r-cubical lattice and a generalization of the cd-index

We define a natural extension of the cubical lattice, called the r-cubical
lattice.  Recall that the cd-index is a convenient way to encode the flag
f-vector of an Eulerian poset.  We generalize the cd-index of the cubical
lattice to an r-cd-index for the r-cubical lattice.  The coefficients of
this index enumerate augmented Andre r-signed permutations, generalizing
Purtill's work relating the cd-index of the cubical lattice and signed
Andre permutations.

As an application of the r-cd-index, we find that the extremal configuration
which maximizes the Mobius function over arbitrary rank selections from the
r-cubical lattice is the odd alternating ranks, {1,3,5,...}.

This is joint work with Richard Ehrenborg.

From propp(at-sign)math.mit.edu Wed Apr 19 21:47:16 1995
To: combinatorics(at-sign)math.mit.edu
Subject: Randall, 4/28

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

Dana Randall (Institute for Advanced Study)

Generating random surfaces, tilings and Eulerian orientations

We present a technique for generating random configurations on
any finite region of a two-dimensional lattice and show it is efficient
for several important combinatorial problems arising in statistical
mechanics.  The dimer problem asks for a random tiling of the region,
where each tile covers two adjacent cells of the lattice.  Thurston,
Conway and Lagarias show that the set of tilings map bijectively to
a set of piecewise linear surfaces with a fixed boundary.  Similarly,
the set of Eulerian orientations with fixed boundary conditions
(or configurations of the ice model in statistical mechanics) are
known to correspond bijectively with solid-on-solid'' surfaces
where the difference in height between nearest neighbors is always
exactly one.  Finally, the set of 3-colorings of regions of the
Cartesian lattice (or the dominant coefficient of the q=3 Pott's model)
correspond to the union, over all boundary conditions, of the set
of Eulerian orientations.

We define a Markov chain for each family of surfaces and show that each
will converge quickly to the uniform distribution over configurations.
The proofs of the convergence rates rely on simple coupling arguments.
(This is joint work with Michael Luby and Alistair Sinclair.)

From propp(at-sign)math.mit.edu Tue Apr 25 17:32:28 1995
To: combinatorics(at-sign)math.mit.edu
Subject: Discrete Dinner

Spring 1995 Cambridge Discrete Mathematics Dinner

This semester's Discrete Dinner will be held on Friday, May 12
at 6 p.m. at the recently re-opened Mary Chung's (at 464
Massachusetts Avenue in Cambridge, just a few blocks from MIT).
with the rest of us making up the difference.  I hope that the
closeness to campus and the low cost of the meal will encourage

probability of attendance.  (The sum of these probabilities
has proved to be a reliable indicator of the number of people
who actually attend.)  Send e-mail to propp(at-sign)math.mit.edu or
call 253-6544.

From propp(at-sign)math.mit.edu Tue Apr 25 17:33:23 1995
To: combinatorics(at-sign)math.mit.edu
Subject: MIT Combinatorics: preliminary May schedule

MIT COMBINATORICS SEMINAR

Here is a preliminary list of talks scheduled for the month of May.
The talk on May 12 will be followed by this semester's Discrete Dinner,
which is open to all members of the Boston combinatorial community.
Details are given in a separate announcement.

Wednesday, May 3, 4:15 p.m.: Dan Kleitman,
A surprisingly simple proof of the box conjecture

Wednesday, May 10, 4:15 p.m.: David Jackson,
Maps in locally orientable surfaces, an integral representation,
zonal polynomials, and the monopole series

Friday, May 12, 4:15 p.m.: Jim Propp and David Wilson,
Random generation of combinatorial objects

Wednesday, May 31, 4:15 p.m.: Amin Shokrollahi,
Coding theory and Bernoulli numbers

From propp(at-sign)math.mit.edu Tue Apr 25 17:36:37 1995
To: combinatorics(at-sign)math.mit.edu
Subject: Kleitman, 5/3

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

Dan Kleitman (M.I.T.)

A surprisingly simple proof of the box conjecture

Recently Dave Reimer, a graduate student at Rutgers, settled the
Van den Berg - Kesten "box conjecture", a long-standing problem in
probability theory.  I shall describe the proof, which is quite simple.

Restated combinatorially, the problem is as follows.  Given two
collections A and B of 0,1-vectors of length n, we define "A box B"
to be the set of vectors x for which there is a y(x) such that every
z on a direct line between x and y is in A and such that every z' on
a direct line between x and the complement of y is in B.  Reimer's
theorem asserts that |A box B| 2^n is at most |A| |B|.

From propp(at-sign)math.mit.edu Wed May  3 13:06:41 1995
To: combinatorics(at-sign)math.mit.edu
Subject: Jackson, 5/10

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

David Jackson (Waterloo)

Maps in locally orientable surfaces, an integral representation,
zonal polynomials, and the monopole series

The genus series for maps is the generating series for the number
of rooted maps with a given number of vertices and faces of each degree,
and a given number of edges.  It captures topological information
about surfaces, and appears in questions arising in statistical mechanics,
topology, group rings, and certain aspects of free probability theory.
An expression has been given previously for the genus series for maps
in locally orientable surfaces in terms of zonal polynomials.  The purpose
of this talk is to derive an integral representation for the genus series.
We then show how this can be used in conjunction with integration
techniques to determine the genus series for monopoles in locally orientable
surfaces.  The latter result can be interpreted in terms of the Euler
characteristic for the moduli spaces of real curves, and therefore
complements the analogous result for monopoles in orientable
surfaces previously obtained by Harer and Zagier.

From propp(at-sign)math.mit.edu Wed May  3 13:26:27 1995
To: combinatorics(at-sign)math.mit.edu
Subject: Propp and Wilson, 5/12

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

Jim Propp and David Wilson (M.I.T.)

Random generation of combinatorial objects

We'll discuss our recent work on generating random combinatorial objects,
including some that arise in statistical mechanics, via the method of
coupled simulation from the past.  We will first illustrate this method
by showing how one can sample exactly from the steady-state distribution of
any (ergodic) Markov chain which one can simulate.  Next we extend these
ideas to sampling from the uniform distribution on the set of order-ideals
of a finite poset.  Surprisingly, work of Winkler and others shows that this
allows one to randomly sample the independent sets of a bipartite graph.
Finally, we will apply this approach to sample from the Gibbs distribution
for the Ising model in two different ways: a naive way that suffers from
exponential slowdown below the critical temperature, and a more sophisticated
approach that allows one to sample efficiently at any temperature.

No prior knowledge of statistical mechanics will be required, though some
knowledge of basic Markov chain theory (e.g., the concept of a steady state)

From gptesler(at-sign)math.mit.edu Mon May 15 12:59:02 1995
To: combinatorics(at-sign)math.mit.edu

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

Glenn Tesler (MIT)

Semi-primary Lattices and Schutzenberger's Evacuation Algorithm

We consider lattices, such as the subgroups of a finite abelian
p-group, in which an integer partition is assigned to every element
and every interval.  Chains in these lattices give rise to chains of
partitions, which may be encoded as tableaux.  In one class of these
lattices, Hesselink and van Leeuwen showed that, given the types of
the elements in a chain, the generic cotype, which is a certain
description of the configuration of the elements in the chain, is
computed by the well-known evacuation algorithm on standard tableaux.
We explore extensions of this to a larger class of lattices called
semi-primary lattices, consider the non-generic configurations, and
consider enumeration of the number of chains achieving each
configuration.

From propp(at-sign)math.mit.edu Thu May 25 12:26:15 1995
To: combinatorics(at-sign)math.mit.edu
Subject: Shokrollahi, 5/31

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

Amin Shokrollahi (Bonn)

Coding theory and Bernoulli numbers

A prime p is called regular if it does not divide the numerators of
the Bernoulli numbers B_k,  k=2,4,...,p-3.  Otherwise it is called
irregular; in that case, a pair (p,2i) such that p divides B_{2i} is
called an irregular pair and the number of such pairs is called the
index of irregularity of p.  Many interesting data of the cyclotomic
field K_p generated over the field of rational numbers by a primitive
p-th root of unity are encoded in the irregular pairs corresponding
to a prime.  We show a relationship between these data and certain
cyclic codes in the following way: let p>2, let G_p be the Galois
group of K_p over the field of rational numbers, and let Gamma_p =
Z[G_p] be the integral group ring of G_p.  We study the reduction of
a certain ideal of Gamma_p modulo p.  This is a cyclic code over the
finite field GF(p).  We show a relationship between the dimension
and minimum distance of this code and the index of irregularity of p.
The results might indicate that there is a deeper connection between
the minimum distance of cyclic codes and certain arithmetic invariants
of cyclotomic fields.