Date:           Fri, 17 Jan 1997 12:52:41 -0500
To:             combinatorics(at-sign)math.mit.edu
From:           schulte(at-sign)neu.edu (SCHULTE)
Subject:        combinatorics seminar


          NORTHEASTERN COMBINATORICS SEMINAR  --  Winter 1997
___________________________________________________

The seminar meets Wednesdays at 1:30 - 2:30 pm in 509 Lake Hall.

January 22:     Norman W. Johnson, Wheaton College

Abstract "QUADRATIC INTEGERS AND COXETER GROUPS"

Norman W. Johnson and Asia Ivic Weiss

ABSTRACT.  Discrete groups of transformations of inversive
n-space or hyperbolic (n+1)-space H^n+1 for n <= 8 have been
shown to be associated with matrices whose entries belong to
a suitable ring of algebraic integers.  Such groups may be
Coxeter groups, generated by reflections, or subgroups whose
generators include rotations or other direct isometries.  The
modular and Picard groups of linear fractional transformations
have well-known realizations in the hyperbolic plane and hy-
perbolic 3-space.  These and other discrete groups in H^2 and
H^3 are represented by 2x2 matrices whose entries are rational
integers or real or imaginary quadratic integers.  Matrix rep-
resentations for discrete groups in H^4 and H^5 are provided by
three basic systems of integral quaternions.


Date:           Thu, 30 Jan 1997 12:21:08 -0500
To:             combinatorics(at-sign)math.mit.edu
From:           schulte(at-sign)neu.edu (SCHULTE)
Subject:        seminar


          NORTHEASTERN COMBINATORICS SEMINAR  --  Winter 1997
___________________________________________________

The seminar meets Wednesdays at 1:30 - 2:30 pm in 509 Lake Hall.

February 5:     Christian Lenart, MIT

Symmetric Functions, Formal Group Laws, and
Lazard's Theorem

Abstract:

Lazard's theorem is a central result in formal group theory,  stating
that the ring over which the universal formal group law is defined is a
polynomial algebra over the integers with infinitely many generators.
The aim of this paper is to develop combinatorial methods which not only
allow us to present a new proof of Lazard's theorem, but also provide
explicit explanation for certain phenomena in formal group theory. The
combinatorics we develop is related to symmetric functions, and consists
of two important ingredients: some formulas for expressing the forgotten
symmetric functions in terms of those corresponding to partitions with
equal parts, and a certain Hopf algebra map from symmetric functions to
the covariant bialgebra of a formal group law. We study this map by
deriving formulas for the images of certain symmetric functions; we also
use this map to prove some symmetric function and Catalan number
identities. Based on the above results, we prove Lazard's theorem, and
present an application to the construction of certain $p$-typical formal
group laws over the integers.


Date:           Tue, 4 Feb 1997 12:29:13 -0500
To:             combinatorics(at-sign)math.mit.edu
From:           schulte(at-sign)neu.edu (SCHULTE)
Subject:        seminar


          NORTHEASTERN COMBINATORICS SEMINAR  --  Winter 1997
___________________________________________________

The seminar meets Wednesdays at 1:30 - 2:30 pm in 509 Lake Hall.

February 5:     Christian Lenart, MIT

Symmetric Functions, Formal Group Laws, and
Lazard's Theorem

To: combinatorics(at-sign)math.mit.edu
Subject: seminar tomorrow

We will have our first combinatorics seminar for 1997 tomorrow.

****Combinatorics Seminar Tomorrow, February 7 ****
4:15pm in 2-338

speaker:  Thomas Bohman
title:  On a Sum Packing Problem of Erdos
institution: MIT

abstract:
A set S of positive integers has distinct subset sums if for any
distinct subsets I and J of S the sum of the elements in I does not
equal the sum of the elements in J. For example, the sets $\{1,2,4,8\}$
and $\{3,5,6,7\}$ have distinct subset sums. How small can the largest
element of such a set be? In other words, what is
$f(n)=\text{min}\{\text{max } S :|S|=n$ and S has distinct subset sums$\}$? Erd\"os conjectures that $f(n) > c2^n$ for some constant c. In 1967 Conway and Guy constructed an
interesting sequence of sets of integers. They conjectured not only
that these sets have distinct subset sums but also that they are the
best possible (with respect to the largest element). I will show a
technique for proving that sets of integers have distinct subset
sums. This technique can be used to show that the sets from the
Conway-Guy sequence (as well as some other interesting sets) have
distinct subset sums. A generalization of the Conway-Guy sequence now
gives the best known upper bound on f(n).  }

Upcoming events:
speaker: J. Maurice Rojas
title: Multisymmetric Functions via Toric Resultants

From schulte(at-sign)neu.edu Thu Feb  6 15:39:24 1997
X-Sender: schulte(at-sign)nuhub.dac.neu.edu (Unverified)
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
To: combinatorics(at-sign)math.mit.edu
Subject: seminar

NORTHEASTERN COMBINATORICS SEMINAR  --  Winter 1997
___________________________________________________

The seminar meets Wednesdays at 1:30 - 2:30 pm in 509 Lake Hall.

February 12:    Rudolf Winkel, MIT

Sequences of symmetric polynomials and Schubert polynomials

February 19:    Herman Servatius,  Worcester

TBA

ABSTRACT of the talk by Rudolf Winkel:

The sequence of Schur polynomials for a fixed partition $\lambda$ in an
increasing number of variables can be comfortably and effectively generated
by  the application of multiplication and shift operators (Baxter
operators) to the sequence of variables.   We review this result of
G.P. Thomas and discuss its  generalizations to:
* more general sequences of symmetric polynomials (Hall-Littlewood,
Jack, and Macdonald polynomials) and
* nonsymmetric Schubert polynomials.
In the symmetric case the construction starts from Standard Young Tableaux
and in the case of Schubert polynomials from reduced words of permutations.
In fact there is an elegant combinatorial bijection between Standard Young
Tableaux and reduced words of Grassmannian permutations.

From sara(at-sign)math.mit.edu Mon Feb 10 14:49:54 1997
To: combinatorics(at-sign)math.mit.edu
Subject: Erdos video

I will be showing the new movie called "N is a number" about the life
Paul Erdos for my UROP students.  You are welcome to join us.  It will
be on Wednesday, Feb.12, at 4:30pm in 2-338.  The department now owns
the video in case you would like to borrow it.


Date:           Tue, 11 Feb 1997 10:05:31 -0500 (EST)
From:           Jim Propp <propp(at-sign)math.mit.edu>
To:             combinatorics(at-sign)math.mit.edu
Subject:        28th Southeastern Combinatorics meeting


The Twenty-Eighth Southeastern International Conference on Combinatorics,
Graph Theory, and Computing will be held March 3-7 in Boca Raton, Florida.
http://www.math.fau.edu/cgtc28/default.html

Jim Propp


Date:           Tue, 11 Feb 1997 12:25:37 -0500
To:             combinatorics(at-sign)math.mit.edu
From:           schulte(at-sign)neu.edu (SCHULTE)
Subject:        seminar -- cancellation notice


          NORTHEASTERN COMBINATORICS SEMINAR  --  Winter 1997
___________________________________________________

The seminar talk for February 12 by Rudolf Winkel was cancelled!


Date:           Fri, 14 Feb 1997 12:05:58 -0500 (EST)
From:           Sara Billey <sara(at-sign)math.mit.edu>
To:             combinatorics(at-sign)math.mit.edu
Subject:        seminar today


            ****Combinatorics Seminar Today ****
4:15pm in 2-338

speaker:  J. Maurice Rojas
title:  New Polyhedral Formulae for Affine Problems
institution: MIT

abstract:
The combinatorics of polynomial systems has grown tremendously thanks
to the the beautiful formula of Kouchnirenko, Khovanskii, and
Bernshtein (the BKK bound) relating mixed volume to the number of
roots of a system of polynomial equations. In this talk, we'll see a
new extension of this formula to different subsets of affine
space. (The original BKK bound runs into complications when applied to
counting roots with some coordinates equal to zero.) A corollary is a
new formula for local intersection multiplicities in terms of an
alternating sum of mixed volumes, generalizing an earlier result of
Kouchnirenko.

Our approach will be fairly elementary and no significant prior
knowledge of algebraic geometry is assumed.

Upcoming Events:

Feb. 21 -- NO SEMINAR

We will have at least two talks during the week of Feb. 24.  A final
schedule will be announced next week.

Feb. 26 **Wednesday**
speaker: Eva Maria Feichtner
title: On the cohomology of some classical configuration spaces
institution: Technische Universit\"at Berlin

speaker: Dmitry Kozlov.
title:Homology of the $k$-fold Boolean algebras via classifying spaces
institution: Royal Institute of Technology,Stockholm, Sweden and MSRI

Feb. 28 **Friday**
speaker: Aleksandar Peke\v{c}
title: Winning the Ramsey Graph Game
institution: University of Aarhus, Denmark


Date:           Mon, 17 Feb 1997 18:56:00 -0500
To:             combinatorics(at-sign)math.mit.edu
From:           schulte(at-sign)neu.edu (SCHULTE)
Subject:        seminar


          NORTHEASTERN COMBINATORICS SEMINAR  --  Winter 1997
___________________________________________________

The seminar meets Wednesdays at 1:30 - 2:30 pm in 509 Lake Hall.

February 19:    Herman Servatius,  Worcester

Symmetry, automorphisms, and self-duality of
infinite planar graphs and tilings


Date:           Wed, 19 Feb 1997 22:41:12 -0500 (EST)
From:           Michel Goemans <goemans(at-sign)math.mit.edu>
To:             combinatorics(at-sign)math.mit.edu
Subject:        LOVASZ --- ORC Seminar (fwd)


Date:           Tue, 18 Feb 97 06:24:41 EST
From:           "L. Beril Toktay" <toktay(at-sign)keiko.mit.edu>
To:             or_seminar(at-sign)MIT.EDU
Subject:        ORC Seminar


               OPERATIONS RESEARCH CENTER SEMINAR

DATE: February 20, 1997
LOCATION: Room E40-298 (One Amherst Street), MIT
TIME: 4:00 p.m.

SPEAKER

Laszlo Lovasz
Professor of Mathematics and Computer Science
Yale University

TITLE

Jump Systems:  Matchings, Matroids and More

ABSTRACT

A jump system is a set of lattice points satisfying a certain simple
exchange axiom. This notion was introduced by Bouchet and Cunningham, as a
common generalization of (among others) of bases of a matroid and degree
sequences of subgraphs of a graph.  It also contains as special cases
generalized polymatroids by Frank and Tardos, delta-matroids by Bouchet,
and other general combinatorial structures with nice optimization
properties.  We prove, under additional assumptions, a min-max formula for
the distance of a lattice point from a jump system.  Our formula contains
as special cases Tutte's factor-theorem and Edmonds' matroid intersection
theorem.

BIOGRAPHICAL SKETCH

Laszlo Lovasz was born on March 9, 1948 in Budapest, Hungary.  He is
married and has 4 children. He obtained his doctoral degree in mathematics
from the Eotvos Lorand University in Budapest, Hungary in 1971.  He held
the Chair of Geometry at the University of Szeged from 1975-1982 and the
Chair of Computer Science at the Eotvos Lorand University, in Budapest
from 1983 to 1993.  Currently he is Professor of Mathematics and Computer
Science at Yale University.

His field of research is discrete mathematics, in particular its
applications in the theory of algorithms and the theory of computing.
His awards include the George Polya Prize of the Society of Industrial
and Applied Mathematics (1979), the Ray D.Fulkerson Prize of the
American Mathematical Society and the Mathematical Programming
Society (1982) and the Brouwer Medal of the Dutch Mathematical Society (1993).

(Refreshments will be served after the seminar.)


Date:           Fri, 21 Feb 1997 11:12:55 -0500 (EST)
From:           Sara Billey <sara(at-sign)math.mit.edu>
To:             combinatorics(at-sign)math.mit.edu
Subject:        seminar schedule


Next week we will have three lectures in the Combinatorics Seminar;
two on Wednesday starting at 4:00, and one on Friday at the usual
time.

DATE: Wednesday, February 26, 4:00pm
SPEAKER: Eva Maria Feichtner
INSTITUTION: Technische Universit\"at Berlin
TITLE: On the cohomology of some classical configuration spaces
SUMMARY:
Our objects of study are spaces of configurations of $n$ distinct,
labeled points in a topological space $X$. Though of interest in
various contexts of algebraic topology over a long time, some of the
topological invariants of these configuration spaces remained
undetermined even for basic instances of $X$.

We present a complete and explicit description of the cohomology
algebras of configuration spaces of spheres with integer coefficients,
thereby exhibiting $2$-torsion for spheres of even dimension. Moreover,
we determine integer cohomology of the space of configurations of three
distinct points on the torus. Surprisingly, we find $2$-torsion as well
as $4$-torsion.

Our tools are elementary.  Using classical spectral sequence techniques,
the building blocks for our investigations turn out to be of combinatorial
nature, thus revealing combinatorial structure at the core of the
problem.

This is joint work with G\"unter M.\ Ziegler, TU Berlin.

DATE: Wednesday, February 26, 4:45pm
SPEAKER: Dmitry N. Kozlov
INSTITUTION: Royal Institute of Technology, Sweden and MSRI
TITLE: Homology of the $k$-fold Boolean algebras via classifying spaces
SUMMARY:
Consider an arbitrary poset $P$ with a minimal element $\hat 0$. Fix
an integer $k$. The construction of the $k$th deleted join of $P$
can be described as follows:

1) choose all possible ordered $k$-tuples of pointwise disjoint
elements of $P$ (for $x,y\in P$, $x$ and $y$ are called disjoint if
$P_{\leq x}\cap P_{\leq y}=\hat 0$);

2) form a partially ordered set by saying that one $k$-tuple is
larger than another one if every element of the first $k$-tuple is
larger or equal than some element of the second $k$-tuple.

The obtained poset is called $k$th deleted join of $P$, denoted
$P^{(k)}$.  The symmetric group $S_k$ acts on the deleted join by
permuting the $k$-tuples.

The main objects $B_{n,k}$ that we study can be obtained as follows:
let $B_n$ be an n-dimensional Boolean algebra; take its $k$th
deleted join and let $B_{n,k}$ be the quotient of $B_n^{(k)}$ under
the action of the symmetric group $S_k$ described above. For example
for $k=2$ one obtains a face poset of a triangulation of the
projective space of dimension $n$.

The rational homology groups of $B_{n,k}$ are trivial: 0 except for
the highest dimension, where it is a free group. However there is a
lot of torsion.  We compute the $p$-torsion of $B_{n,k}$, in other
words, we compute homology groups of $B_{n,k}$ with coefficients in
${\Bbb Z}_p$ using a mixture of currently available tools:
shellability, classifying spaces of the symmetric group, diagrams of
spaces and spectral sequences.

This research is joint with Eric Babson.

DATE: Friday, February 28, 4:15pm
SPEAKER: Aleksandar Peke\v{c}
INSTITUTION: University of Aarhus, Denmark
TITLE: Winning the Ramsey Graph Game
SUMMARY:
Two players, Maker (red) and Breaker (blue) alternately color previously
uncolored edges of $K_N$. Maker wins the game if there is a red $K_n$.
Breaker wins if there is no red $K_n$ after all $N(N-1)/2$ edges have
been colored. Beck showed that, for every $\epsilon >0$, Maker has a
winning strategy whenever $N \ge N_0:=(2+\epsilon)^n$ for $n$ sufficiently
large. However, Maker can claim a victory only after all edges of some
$K_{N_0}$ have been colored. In this talk I'll present a winning strategy
for Maker requiring at most $(n-3)2^{n-1}+n+1$ moves whenever
$N\ge (n-1)2^{n-1}+2$. Furthermore, unlike the most winning strategies
based on the weight function method, the problem of determining a move
according to this strategy is computationally trivial. A believer in
symmetry would conjecture that this is an optimal winning strategy for the
Ramsey graph game. If so, the startling improvement of the lower bound for
Ramsey numbers would follow.


Date:           Wed, 26 Feb 1997 15:48:16 -0500 (EST)
From:           Sara Billey <sara(at-sign)math.mit.edu>
To:             combinatorics(at-sign)math.mit.edu
Subject:        seminar


Reminder:  the combinatorics seminar starts at 4:00 today.

DATE: Wednesday, February 26, 4:00pm
SPEAKER: Eva Maria Feichtner
INSTITUTION: Technische Universit\"at Berlin
TITLE: On the cohomology of some classical configuration spaces
SUMMARY:
Our objects of study are spaces of configurations of $n$ distinct,
labeled points in a topological space $X$. Though of interest in
various contexts of algebraic topology over a long time, some of the
topological invariants of these configuration spaces remained
undetermined even for basic instances of $X$.

We present a complete and explicit description of the cohomology
algebras of configuration spaces of spheres with integer coefficients,
thereby exhibiting $2$-torsion for spheres of even dimension. Moreover,
we determine integer cohomology of the space of configurations of three
distinct points on the torus. Surprisingly, we find $2$-torsion as well
as $4$-torsion.

Our tools are elementary.  Using classical spectral sequence techniques,
the building blocks for our investigations turn out to be of combinatorial
nature, thus revealing combinatorial structure at the core of the
problem.

This is joint work with G\"unter M.\ Ziegler, TU Berlin.

DATE: Wednesday, February 26, 4:45pm
SPEAKER: Dmitry N. Kozlov
INSTITUTION: Royal Institute of Technology, Sweden and MSRI
TITLE: Homology of the $k$-fold Boolean algebras via classifying spaces
SUMMARY:
Consider an arbitrary poset $P$ with a minimal element $\hat 0$. Fix
an integer $k$. The construction of the $k$th deleted join of $P$
can be described as follows:

1) choose all possible ordered $k$-tuples of pointwise disjoint
elements of $P$ (for $x,y\in P$, $x$ and $y$ are called disjoint if
$P_{\leq x}\cap P_{\leq y}=\hat 0$);

2) form a partially ordered set by saying that one $k$-tuple is
larger than another one if every element of the first $k$-tuple is
larger or equal than some element of the second $k$-tuple.

The obtained poset is called $k$th deleted join of $P$, denoted
$P^{(k)}$.  The symmetric group $S_k$ acts on the deleted join by
permuting the $k$-tuples.

The main objects $B_{n,k}$ that we study can be obtained as follows:
let $B_n$ be an n-dimensional Boolean algebra; take its $k$th
deleted join and let $B_{n,k}$ be the quotient of $B_n^{(k)}$ under
the action of the symmetric group $S_k$ described above. For example
for $k=2$ one obtains a face poset of a triangulation of the
projective space of dimension $n$.

The rational homology groups of $B_{n,k}$ are trivial: 0 except for
the highest dimension, where it is a free group. However there is a
lot of torsion.  We compute the $p$-torsion of $B_{n,k}$, in other
words, we compute homology groups of $B_{n,k}$ with coefficients in
${\Bbb Z}_p$ using a mixture of currently available tools:
shellability, classifying spaces of the symmetric group, diagrams of
spaces and spectral sequences.

This research is joint with Eric Babson.

Upcoming events:

DATE: Friday, February 28, 4:15pm
SPEAKER: Aleksandar Peke\v{c}
INSTITUTION: University of Aarhus, Denmark
TITLE: Winning the Ramsey Graph Game


Date:           Wed, 26 Feb 1997 19:11:33 -0500
To:             combinatorics(at-sign)math.mit.edu
From:           schulte(at-sign)neu.edu (SCHULTE)
Subject:        seminar on March 5


          NORTHEASTERN COMBINATORICS SEMINAR  --  Winter 1997
___________________________________________________

The seminar meets Wednesdays at 1:30 - 2:30 pm in 509 Lake Hall.

March 5:        Rudolf Winkel, MIT

Sequences of symmetric polynomials and Schubert polynomials

ABSTRACT of the talk by Rudolf Winkel:

The sequence of Schur polynomials for a fixed partition $\lambda$ in an
increasing number of variables can be comfortably and effectively generated
by  the application of multiplication and shift operators (Baxter
operators) to the sequence of variables.   We review this result of
G.P. Thomas and discuss its  generalizations to:
* more general sequences of symmetric polynomials (Hall-Littlewood,
Jack, and Macdonald polynomials) and
* nonsymmetric Schubert polynomials.
In the symmetric case the construction starts from Standard Young Tableaux
and in the case of Schubert polynomials from reduced words of permutations.
In fact there is an elegant combinatorial bijection between Standard Young
Tableaux and reduced words of Grassmannian permutations.


Date:           Wed, 26 Feb 1997 19:11:30 -0500
To:             combinatorics(at-sign)math.mit.edu
From:           schulte(at-sign)neu.edu (SCHULTE)
Subject:        seminar on March 5


          NORTHEASTERN COMBINATORICS SEMINAR  --  Winter 1997
___________________________________________________

The seminar meets Wednesdays at 1:30 - 2:30 pm in 509 Lake Hall.

March 5:        Rudolf Winkel, MIT

Sequences of symmetric polynomials and Schubert polynomials

ABSTRACT of the talk by Rudolf Winkel:

The sequence of Schur polynomials for a fixed partition $\lambda$ in an
increasing number of variables can be comfortably and effectively generated
by  the application of multiplication and shift operators (Baxter
operators) to the sequence of variables.   We review this result of
G.P. Thomas and discuss its  generalizations to:
* more general sequences of symmetric polynomials (Hall-Littlewood,
Jack, and Macdonald polynomials) and
* nonsymmetric Schubert polynomials.
In the symmetric case the construction starts from Standard Young Tableaux
and in the case of Schubert polynomials from reduced words of permutations.
In fact there is an elegant combinatorial bijection between Standard Young
Tableaux and reduced words of Grassmannian permutations.


Date:           Fri, 28 Feb 1997 13:43:30 -0500 (EST)
From:           Sara Billey <sara(at-sign)math.mit.edu>
To:             combinatorics(at-sign)math.mit.edu
Subject:        seminar today


Due to the fact that several of our faculty are on sabbatical and/or
visiting MSRI, the Combinatorics Seminar will only meet occasionally
during March and April.  We have several interesting talks lined up
for May.

****Combinatorics Seminar Today ****
4:15pm in 2-338

speaker: Aleksandar Peke\v{c}
title: Winning the Ramsey Graph Game
institution: University of Aarhus, Denmark

SUMMARY:
Two players, Maker (red) and Breaker (blue) alternately color previously
uncolored edges of $K_N$. Maker wins the game if there is a red $K_n$.
Breaker wins if there is no red $K_n$ after all $N(N-1)/2$ edges have
been colored. Beck showed that, for every $\epsilon >0$, Maker has a
winning strategy whenever $N \ge N_0:=(2+\epsilon)^n$ for $n$ sufficiently
large. However, Maker can claim a victory only after all edges of some
$K_{N_0}$ have been colored. In this talk I'll present a winning strategy
for Maker requiring at most $(n-3)2^{n-1}+n+1$ moves whenever
$N\ge (n-1)2^{n-1}+2$. Furthermore, unlike the most winning strategies
based on the weight function method, the problem of determining a move
according to this strategy is computationally trivial. A believer in
symmetry would conjecture that this is an optimal winning strategy for the
Ramsey graph game. If so, the startling improvement of the lower bound for
Ramsey numbers would follow.


Date:           Sun, 9 Mar 1997 14:41:29 -0500
To:             kcollins(at-sign)mail.wesleyan.edu
From:           kcollins(at-sign)wesleyan.edu (Karen L. Collins)
Subject:        April meeting


              Come to the Twenty-fourth one day conference on

Combinatorics and Graph Theory

Saturday, April 5, 1997

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

Schedule

10:00  Ann Trenk (Wellesley College)
on how to pay faculty fairly

11:10  Sue Whitesides (McGill University)
On Geometric Representations of Graphs

12:30  Lunch

2:00  Glenn Hurlbert (Arizona State Univ.
and The Johns Hopkins Univ.)
Pebbling in Graphs

3:10  Sylvia Silberger (Wesleyan University)
Z

Tau-Invariant Subshifts of (Z/2Z)

The twenty-fifth conference will be May 3, 1997.

The conferences are supported by an NSF grant which allows us
to provide a modest transportation allowance to those attendees
who are not local.  We also gratefully acknowledge support from
Smith College and Wesleyan University.

Our Web page site has directions to Smith College, abstracts of
speakers, dates of future conferences, and other information.

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

Karen Collins (Wesleyan University), (860) 685-2169,
kcollins(at-sign)wesleyan.edu

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


Date:           Sat, 29 Mar 1997 08:09:33 -0500
To:             kcollins(at-sign)mail.wesleyan.edu
From:           kcollins(at-sign)wesleyan.edu (Karen L. Collins)
Subject:        second announcement


              Come to the Twenty-fourth one day conference on

Combinatorics and Graph Theory

Saturday, April 5, 1997

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

Schedule

10:00  Ann Trenk (Wellesley College)
on how to pay faculty fairly

11:10  Sue Whitesides (McGill University)
On Geometric Representations of Graphs

12:30  Lunch

2:00  Glenn Hurlbert (Arizona State Univ.
and The Johns Hopkins Univ.)
Pebbling in Graphs

3:10  Sylvia Silberger (Wesleyan University)
Z
Tau-Invariant Subshifts of (Z/2Z)

The twenty-fifth conference will be May 3, 1997.

The conferences are supported by an NSF grant which allows us
to provide a modest transportation allowance to those attendees
who are not local.  We also gratefully acknowledge support from
Smith College and Wesleyan University.

Our Web page site has directions to Smith College, abstracts of
speakers, dates of future conferences, and other information.

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

Karen Collins (Wesleyan University), (860) 685-2169,
kcollins(at-sign)wesleyan.edu

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


Date:           Thu, 3 Apr 1997 15:32:16 -0500 (EST)
From:           Sara Billey <sara(at-sign)math.mit.edu>
To:             combinatorics(at-sign)math.mit.edu, combinatorics(at-sign)euclid.ucsd.edu
Subject:        [bjorner(at-sign)msri.org: extremal conference]


From:           Anders Bjorner <bjorner(at-sign)msri.org>
Date:           Wed, 2 Apr 1997 16:36:35 -0800 (PST)
To:             compeople(at-sign)msri.org
Subject:        extremal conference


%%%%%%%%%%%%%%%%%%%%%%%%Plain TeX%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\nopagenumbers
\magnification =\magstep 1
\font\kicsi=cmr8 \font\ss=cmssdc10 \voffset -13 true mm

\noindent
{\ss                    J\'ANOS BOLYAI MATHEMATICAL SOCIETY}

\noindent               Budapest, F\H{o} utca 68., 1027

\noindent
\line{\kicsi
phone: 201 - 7656                  \hfil
phone/fax: 201 - 6974              \hfil
e-mail: {\tt lelle(at-sign)math-inst.hu}      }
\bigskip
\hrule

\vskip 1truecm
\centerline {\bf
INTERNATIONAL COLLOQUIUM ON EXTREMAL GRAPH THEORY
}\medskip
\centerline{
dedicated to the memory of Paul Erd\H{o}s
}\medskip
\centerline{  Balatonlelle, Hungary, July 27 -- August 2, 1997  }
\centerline{                 2nd announcement                   }
\vskip 1truecm

Dear Colleagues,

\medskip\noindent
The J. Bolyai Mathematical Society organizes a combinatorial
conference entitled
International Colloquium on Extremal Graph Theory''
at Balatonlelle, Hungary, on July 27-August 2, 1997.

\medskip
{\bf            Scientific program:}
\smallskip

\noindent
We  are glad to report that the following distinguished
speakers have already agreed to give invited lectures:

\settabs 3\columns {\it

\+&      A. Bondy      &    B. Bollob\'as       \cr
\+&      R. Faudree    &    Z. F\"uredi         \cr
\+&      F. Lazebnik   &    J. Pach             \cr
\+&      H.-J. Proemel &    E. Szemer\'edi      \cr }

\noindent
We are waiting for some more answers and we did not list
the Hungarian invited speakers.

\smallskip
{\bf           Contributed lectures}

\smallskip\noindent
If you plan to give a contributed lecture, please prepare an at
most  one page  abstract  and  complete the  registration  form.
{\bf May 15, 1997}.
(preferably  in  \TeX format)  to                  \hfill\break
{\tt lelle(at-sign)math-inst.hu}.

\smallskip
{\bf           Registration}

\smallskip\noindent
Please complete the attached form and return it along with a
check  (but  not  a personal check) covering the registration fee,
payable to  J\'anos  Bolyai Mathematical Society''.
(Accommodation and meals are to be paid  upon arrival at the
conference registration desk.)
We regret that we can only accept  fully convertible currencies.
You can also send your registration by e-mail
or you can register at our Web site:
{\tt http://www.math-inst.hu/$\,\tilde{}\,$lelle}
%%%% http://www.math-inst.hu/~lelle %%%%

\noindent\settabs 3\columns {\it
\+
& Registration fee & Late fee (after May 15)  \cr
\+
Regular:             & USD 100       &   USD 125             \cr
\+
Accompanying person: & USD  20       &   USD  25             \cr}

\noindent
The  regular registration fee is only applicable to those participants
whose materials are received not later than May 15.
The registration fee covers the conference materials and a reception.
The registration fee for accompanying persons includes a reception ticket.

\eject
{\bf Location and transportation}

\smallskip\noindent
The  conference will be held in Balatonlelle, a resort  area
about 140 km (90 miles) from Budapest, begins at 10.00 a.m.  on
Monday, July 28.

\noindent
There  are  frequent trains from D\'eli (or occasionally  from
Keleti)   p\'alyaudvar  (railway  station).  The  journey   takes
approximately  2:30 hours.  Detailed information  about
train schedules will be given in the 3rd announcement.
A round trip train ticket from Budapest costs about USD 15.

\smallskip
{\bf         Accommodation}

\smallskip\noindent
We  have  reserved  a  certain  number  of  rooms  at
Hotel Giuseppe,
(Balatonlelle, K\"ozt\'arsas\'ag u. 36.)
which  has  a  private beach.
The  rates  are  the following (per person, per night):
\item{---}   Single: USD 25
\item{---}   Double: USD 15
\item{---}   Apartment (4 persons): USD 12

\noindent
The  prices include breakfast. The number of apartments  is
limited and are therefore reserved for families.

\noindent
There are several restaurants in the center of Balatonlelle.
The typical prices of a three-course dinner range between
USD 6 and USD 12. There will be possible to have lunch
and/or dinner at Hotel Giuseppe for about USD 5 each.
Accommodation and meals are to be paid upon arrival at the
conference registration desk.

\medskip\noindent
Please complete the attached registration form and return it
to  the  above  address by mail or by e-mail or register
at our Web site:
{\tt http://www.math-inst.hu/$\,\tilde{}\,$lelle}.
%%%% http://www.math-inst.hu/~lelle %%%%
Also if you have  a  special  request
Since the Hotel reservations should be made in time,
accommodation reservations  received  after the cutoff date of
{\bf May  15,  1997}
may  be unsuccessful or it may happen that we are forced to
put up you elsewhere.

\medskip\noindent
third announcement in  June, 1997.

\medskip
The conference  e-mail address is: {\tt lelle(at-sign)math-inst.hu}

\bigskip
We are looking forward to  seeing you in Balatonlelle.

\vskip1truecm

Sincerely yours,

\bigskip
\centerline{\hbox{
M. Simonovits (chair),
\hskip1truecm                      A. Gy\'arf\'as,
\hskip1truecm                      E. Gy\H{o}ri (co-chairs)
}}

\medskip
\centerline{                       G. Y. Katona (secretary)
}

\bigskip             April 1, 1997
\vfill\eject

\centerline{\bf      REGISTRATION FORM      }
\medskip
\centerline {\bf
INTERNATIONAL COLLOQUIUM ON EXTREMAL GRAPH THEORY
}\medskip

\noindent
You may register at the conference Web site at
{\bf  http://www.math-inst.hu/$\,\tilde{}\,$lelle}
%%%% http://www.math-inst.hu/~lelle %%%
or by returning this form by e-mail to
{\bf lelle(at-sign)math-inst.hu} (Subject: registration)
or by mail or fax to
\smallskip

J\'ANOS BOLYAI MATHEMATICAL SOCIETY

Budapest, F\H{o} utca 68., 1027

Phone/fax: 201 - 6974.

\centerline{            before   {\bf May 15, 1997}.     }

\vskip1truecm\parindent=0pt
%%%%%beginform%%%%%

%%
\hskip3cm
First name=
%%
\par\smallskip
Sex= Male Female  %% delete one
%%
\par\smallskip
Affiliation=
%%
\par\vskip1truecm
%%
\par\vskip1truecm
%%
\par\smallskip
Number of accompanying person(s)=
%%
\smallskip
I intend to give a 20-minute
contributed talk= YES  NO %% delete one
%%
\par\smallskip
Title=
%%
\par\medskip
Key words=
%%
\par\smallskip
I enclose my abstract= YES   NO  %% delete one
%%
\par\medskip
Do you want us to make  reservation
for your accommodation?=  YES  NO %% delete one
%%
\par\smallskip
Date of arrival=
%%
\hskip3cm
Date of departure=
%%

If yes, what type of accommodation
do you choose                         \hfill\break
in Hotel Giuseppe?=
Single  /  Double / Apartment (4 pers.) %% keep one
%%
\par\smallskip
With whom would you like to share your room?=
%%
\par\smallskip
Would you like to have full board
(lunch and dinner) at Hotel Giuseppe?= YES NO  %% delete one
%%
\par\medskip
I enclose the registration fee /
I will send the registration fee by=
%%
\par\medskip
Special requests=
%%

\par\medskip
Date=
%%
%%%%%endform%%%%%

\medskip
\hskip3cm                  Signature (only on hard copy)

\bye
------- End of forwarded message -------


Date:           Sun, 6 Apr 1997 22:56:28 -0400 (EDT)
From:           G-C Rota <rota(at-sign)math.mit.edu>
To:             combinatorics(at-sign)math.mit.edu


>From athana(at-sign)msri.org Sun Apr  6 21:01:25 1997
X-Authentication-Warning: msri.org: smap set sender to <athana> using -f
To: rota(at-sign)math.mit.edu
Subject: File.tex
Mime-Version: 1.0
Content-Type: text/plain; charset=X-iso88591
Content-Transfer-Encoding: 7bit

\documentstyle[12pt]{article}
\setlength{\topmargin}{ -1.2cm}
\setlength{\oddsidemargin}{ 0.45cm}
\textwidth 16cm
\textheight 22.6cm
\parskip=7pt

\begin{document}

\vspace*{0.15 in}

\begin{center}
{\large {\bf The many lives of lattice theory}}

\vspace{0.1 in}
{\large {\bf Invited address delivered at the
Garrett Birkhoff Memorial Conference,
Harvard University,
April 1, 1997}}

\vspace{0.1 in}
{\bf
by

\vspace{0.1 in}
\begin{tabular}{c}
Gian-Carlo Rota\\
Department of Mathematics\\
MIT\\
77 Massachusetts Avenue\\
Cambridge MA 02139-4307
\end{tabular}
}

\vspace{0.2 in}
\centerline{April 2, 1997}

\vspace{0.2 in}
{\bf Contents}

\begin{tabular}{l}
1. Introduction\\
2. Distributive lattices\\
3. Modular lattices\\
4. The lattice of ideals\\
5. Linear lattices\\
6. Lattice theory and probability\\
7. Other directions
\end{tabular}

\end{center}

\section{Introduction}

Never in the history of mathematics has a mathematical theory been the object
of such vociferous vituperation as lattice theory.  Dedekind, J\'onsson,
Kurosh, Malcev, Ore, von Neumann, Tarski, and most prominently Garrett
Birkhoff have contributed a new vision of mathematics, a vision that has been
cursed by a conjunction of misunderstandings, resentment and raw prejudice.

The hostility towards lattice theory began when Dedekind published the two
fundamental papers that brought the theory into life, well over one hundred
years ago.   Kronecker in  one of his letters  accused Dedekind of "losing his
mind in abstractions", or something to that effect.

I took a course in lattice theory from Oystein Ore while a graduate student at
Yale in the fall of 1954. The lectures were scheduled at 8 a.m., and only one
other student attended besides me. Mar\'ia Wonenburger. It is the only
course I have ever attended that met at 8 in the morning.  The first lecture
was somewhat of a letdown, beginning with the words: "I think lattice theory
is played out" (Ore's  words have remained imprinted in my mind).

For some years I did not come back to lattice theory. In 1963, when I taught
my first course in combinatorics, I was amazed to find  that  lattice theory
fit combinatorics like a shoe. The temptation is strong to spend the next
fifty minutes on  the mutual stimulation  of lattice theory and  combinatorics
of the last thirty-five years.   I will, however, deal with other aspects of
lattice theory, those that were dear to Garrett Birkhoff and which  bring
together ideas from different areas of mathematics.

Lattices are partially ordered sets in which   least upper bounds and greatest
lower bounds of any two elements exist.  Dedekind discovered that this
property may be axiomatized by identities.  A lattice is a set on which two
operations are defined, called join and meet and denoted by $\vee$ and
$\wedge$, which satisfy the idempotent, commutative and associative laws,
as well as the absorption laws:
%
$a \vee (b\wedge a) = a$
%
$a\wedge (b\vee a) = a.$

Lattices are  better behaved than partially ordered sets lacking upper or
lower bounds. The contrast is evident in the examples of the lattice of
partitions of a set and the partially ordered set of partitions of a number.
The family of all partitions of a set (also called equivalence relations) is
a lattice  when partitions are ordered by  refinement. The  lattice of
partitions of a set remains to this day  rich in pleasant surprises. On the
other hand, the  partially ordered set of partitions of an integer, ordered
by refinement, is not a lattice, and  is fraught with pathological properties.

\section{Distributive Lattices}

A distributive lattice is a lattice that satisfies  the distributive law:
%
$$a \vee (b \wedge c) = (a \vee b) \wedge (a \vee c).$$

For quite some time, it was believed  that every lattice is distributive.
This misunderstanding was finally cleared up when Garrett Birkhoff in the
early thirties proved  a  fundamental theorem, which we summarize next.

There is a standard way of constructing distributive lattices.  One takes all
the order ideals of a  partially ordered set $P$.  An order  ideal is a subset
$I$ of $P$ with the property that if $x \in I$ and $y \leq x$, then $y \in I$.
Union and intersection of order ideals are order ideals.  In other words, the
set of all order ideals of a partially ordered set is a distributive lattice.

Garrett Birkhoff proved the converse of this statement: every finite
distributive lattice is isomorphic to the lattice of order ideals of some
partially ordered set.  The resulting contravariant functor from the category
of partially ordered sets to the category of distributive lattices, known as
the "Birkhoff transform", provides a systematic and useful translation of the
combinatorics of partially ordered sets into the algebra of distributive
lattices.

The definitive generalization of Birkhoff's theorem to arbitrary distributive
lattices was obtained in the sixties by Ann Priestley.  Briefly, there is a
non trivial  extension of the notion of topological space that takes order
into account, defined by Leopoldo Nachbin in his thesis. Distributive lattices
are represented as lattices of  closed order ideals  on such ordered
topological
spaces.  Point set topology has been   non trivially extended to ordered
topological spaces, but this extension  has remained  largely unknown.
Dieudonn\'e was taken with it  after he read the copy of Nachbin's thesis that
the author -- working in total isolation -- sent him from Rio de Janeiro.
Dieudonn\'e tried to drum up some interest in ordered topological spaces,
without success.

It is a miracle that families of sets closed under unions and intersections
can be characterized solely by the distributive law and by some simple
identities. Jaded as we are, we  tend to take Birkhoff's discovery for
granted, and to forget that it  was a fundamental step forward in mathematics.

\section{Modular Lattices}

Modular lattices  are lattices that satisfy the following identity, discovered
by Dedekind:
%
$$(c \wedge (a \vee b)) \vee b = (c\vee b) \wedge (a \vee b).$$

This  identity is customarily  recast in user friendlier ways. Examples of
modular lattices are lattices of subspaces of vector spaces, lattices of
ideals of a ring, lattices of submodules of a module over a ring, and lattices
of normal
subgroups of a group.  For example, in  the lattice of  subspaces of a vector
space  the meet of two subspaces is their  set theoretic intersection, and the
join of two subspaces is  the subspace spanned by the two subspaces. Join
and meet  of  linear varieties in projective space  are algebraic renderings
of projection and section of synthetic projective geometry. Synthetic
projective geometry, relying as it does on axioms of incidence  and refusing
any appeal to coordinates, is best understood   in the language of modular
lattices.

But synthetic geometry acquired a bad name, after  algebraic geometers
declared themselves unable to prove their theorems by synthetic methods. The
synthetic presentation of geometry has become in the latter half of this
century a curiosity, cultivated by Italians and by Prof. Coxeter. Modular
lattices were dismissed without a hearing, as a curious outgrowth of a
curiosity.

Garrett once described to  me  his first meeting with  von Neumann. After
exchanging a few words,  they quickly got down to their  common interest in
lattice theory, and von Neumann asked Garrett: "Do you know how many
subspaces you get when you take all joins and meets of  three subspaces of a
vector space in general position?"  Garrett immediately answered :"twenty
eight!", and their collaboration began at that moment.

The free modular lattice with three generators, which indeed has  twenty
eight elements, is a beautiful construct which is presently exiled from
textbooks in linear algebra.  Too bad, because the elements of this lattice
explicitly  describe all projective invariants of three subspaces.

One of Garrett's theorems on modular lattices states that the free modular
lattice generated by two  linearly ordered sets (or chains)  is distributive.
This result has been  shamelessly restated without credit  in disparate
mathematical languages.

The core of the theory of modular lattices is the generalization of the theory
of linear dependence of sets of vectors in a vector space to sets of linear
subspaces of any dimension. Dilworth, Kurosh, Ore and several others
defined an extended  concept of basis, and they established  invariance of
dimension  and exchange properties of bases.  The translation of their results
into  coordinate language is only now being carried out.

Two recent developments in modular lattices are:

First, the discovery of 2--distributive lattices by the Hungarian
mathematician Andras Huhn. A 2-distributive lattice is a lattice that
satisfies the identity
%
$$a \wedge (x\vee y \vee z) = (a \wedge (x\vee y)) \vee ( a\wedge (x\vee z)) \vee (a \wedge (y\vee z)).$$

This improbable identity implies that the lattice is modular, and much more.
It has been shown by Bjarni J\'onsson, J.B. Nation and several others that 2--
distributive lattices are precisely those lattices that are isomorphically
embeddable into the lattice of subspaces of a vector space over any field
whatsoever, subject only to cardinality restrictions.  Thus, 2-distributive
lattices come close to realizing the ideal of a universal  synthetic geometry,
at least for linear varieties.  They have a rich combinatorial structure.

Second:  the theory of semi-primary lattices. These lattices were  given their
unfortunate name   by Reinhold Baer, but again, only recently has their
importance been realized in the work of such young mathematicians as
Franco Regonati and Glenn Tesler.  Examples of semi-primary lattices are the
lattice of subgroups of a finite Abelian group and the lattice of invariant
subspaces of a nilpotent matrix. Semi-primary   lattices are modular,  and
hence  every element is endowed with a rank, or dimension. However, the
elements of semi-primary lattices  are additionally endowed with  a finer type
of rank,  which is a partitition of an integer, or a Young shape as we say in
combinatorics. For the lattice of  subgroups of an an Abelian group, such a
partition comes from the structure theorem for finite Abelian groups; for the
invariant subspaces of nilpotent matrices, the partition comes from the Jordan
canonical form.

This finer notion of dimension leads to a refinement of the theory of linear
dependence. One major result, due to Robert Steinberg, is the following.
Consider  a complete chain  in a semi-primary lattice.  Two successive
elements of the chain differ by one dimension, but much more is true. As
we wind up the chain, we fill a Young shape with integers corresponding to
the positions of each element of the chain, and thus every complete chain  is
made to correspond to  a standard Young tableau.

Now take two complete chains in a semi-primary lattice. It is easy to see that
a pair of complete chains in a modular lattice determine a permutation of
basis vectors.  In  a semi-primary lattice  each of the two chains is
associated
with a standard Young tableau, hence we obtain the statement and proof of the
Schensted algorithm, which precisely associates a pair of standard Young
tableaux to every permutation.

\section{Lattices of Ideals}

Dedekind outlined the program of studying the ideals of a commutative ring by
lattice--theoretic methods, but the relevance of lattice theory in commutative
algebra was not appreciated by algebraists until  the sixties, when
Grothendieck demanded  that the prime ideals of a ring should be granted
equal rights with maximal ideals.  Those mathematicians who knew some
lattice theory  watched with amazement as the algebraic geometers of the
Grothendieck school clumsily reinvented the rudiments of  lattice theory in
their own  language. To this day,  lattice theory has not made much of  a dent
in the sect of algebraic geometers; if ever it  does, it will contribute new
insights.   One elementary instance: the Chinese remainder theorem.
Necessary and sufficient conditions on a commutative ring are known that
insure the validity of the Chinese remainder theorem.  There is, however, one
necessary and sufficient condition that places the theorem in proper
perspective.  It states  that the Chinese remainder theorem holds in a
commutative ring if and only if the lattice of ideals of the ring is
distributive.

The theory of ideals in polynomial rings was given an abstract setting by
Emmy Noether and her school.   Noetherian rings  were defined, together
with  prime and primary ideals, and fundamental  factorization theorems for
ideals were proved.  It does not seem outrageous to go one step further in
Dedekind's footsteps, and extend these theorems to modular lattices. This
program was initiated by Oystein Ore, and developed by Morgan Ward of
CalTech and by his student Bob Dilworth.  Dilworth worked at this program
on and off all his life,  and in his last paper on the subject, published in
1961, he finally obtained a lattice theoretic formulation of the Noetherian
theory of ideals. I quote from the introduction of Dilworth's  paper:

\begin{quote}
The difficulty [of  the lattice theory of ideals] occurred in treating the
Noether theorem on decompositon into primary ideals. ... In this paper, I
give a new and stronger formulation for the notion of a "principal element"
and ... prove a [lattice theoretic] version of the Krull Principal Ideal
Theorem. Since there are
generally many non-principal ideals of a commutative ring which are
"principal elements" in the lattice of ideals, the [lattice theoretic] theorem
represents a considerable strengthening of the classical Krull result.''
\end{quote}

Forgive my presumptuousness for making a prediction about the future of the
theory of commutative rings, a subject in which I have never worked.  The
theory of commutative rings has been torn by two customers, number theory
and geometry.

Our concern here is the relationship between commutative rings and
geometry, not number theory.  In the latter part of this century, algebra has
so overwhelmed geometry that geometry has come to be viewed as a mere
"fa\c{c}on de parler". Sooner or later, geometry in the synthetic vein will
reassert its rights, and the lattice theory  of ideals will be its venue. We
intuitively feel that there is a geometry, projective algebraic or whatever,
whose statements hold  independently of the choice of a base field.
Desargues's theorem is the simplest  theorem of such "universal" geometry.
A new class of commutative rings remains to be discovered, that will be
completely  determined by their lattice of ideals.  Von Neumann found a class
of non commutative rings that are determined by their lattices of ideals, as
we will shortly see,   but the problem for commutative rings seems more
difficult. A first step in this direction was taken by Hochster.  Algebraic
geometry done with such rings might be a candidate for "universal geometry".

Commutative rings set the pace for  a wide class of algebraic systems in the
sense of Garrett Birkhoff's universal algebra. The lattice of congruences of
an algebraic system generalizes the lattice of ideals, and this analogy allows
algebraic systems.  An example of successful translation is the Chinese
remainder theorem in its lattice theoretic formulation, which has been proved
for general algebras. The work of Christian Herrmann and his school has
gone far in this direction. In view of  the abundance of new algebraic
structures that are being born out of wedlock in  computer science,  this
translation is likely to bear fruit.

\section{Linear Lattices}

Having argued for modular lattices, let me now argue against them.

It turns out that all modular lattices that occur in algebra are endowed with
a richer structure. They are lattices of commuting equivalence relations. What
are commuting equivalence relations?

Two  equivalence relations on a set are said to be independent when every
equivalence class of the first meets every equivalence class of the second.
This notion of independence originated in information theory, and has the
following  intuitive interpretation. In the problem of search for an unknown
element,  an equivalence relation can be viewed as a question, whose answer
will tell which equivalence class the unknown element belongs to.  Two
equivalence relations are independent when the answer to either question
gives no information on the possible answer to the other question.

Philosophers have gone wild over the mathematical definition of
independence. Unfortunately, in mathematics philosophy is permanently
condemned to play second fiddle to algebra.  The pairs of equivalence
relations that occur in algebra are seldom independent; instead, they satisfy
a sophisticated variant of independence that has yet to be philosophically
understood: they commute.

Two equivalence relations are said to commute  when the underlying set may
be partitioned  into disjoint blocks, and the restriction of the pair of
equivalence relations to each of these blocks is a pair of independent
equivalence relations. In other words, two equivalence relations commute
when they are isomorphic to disjoint sums of independent equivalence
relations on disjoint sets.

Mme Dubreil found  in her 1939 thesis an elegant characterization of
commuting equivalence relations. Two equivalence relations on the same set
commute whenever  they commute in the sense of composition of relations.
Hence the name.

The lattice of subspaces of a vector space is an example of a lattice that is
naturally isomorphic to a lattice of commuting equivalence relations on the
underlying vector space viewed as a mere set. Indeed, if $W$ is a subspace of
a the vector space $V$, one defines an equivalence relations on the set of
vectors in $V$ by setting $x\equiv_W y$ whenever $x-y\in W.$ Meet and join of
subspaces are isomorphic to meet and join of the corresponding equivalence
relations in the lattice of all equivalence relations  on the set $V$. The
lattice of subspaces of a vector space $V$ is  isomorphic to a sublattice of
the lattice of all equivalence relations on the set $V$, in which any two
equivalence relations commute.

Similar  mappings into lattices of commuting equivalence relaltions exist for
the lattice of all ideals of a ring and the lattice of all submodules of a
module.
Mark Haiman has proposed the term "linear lattice" for lattices of commuting
equivalence relations.

Sch\"utzenberger  found an identity satisfied in certain  modular lattices
that is
equivalent to Desargues's theorem. Not long afterwards, Bjarni J\'onsson
proved that every linear lattice satisfies Sch\"utzenberger's identity. At
that time, the problem of characterizing linear lattices by identities arose.
This brings us to  two  notable theorems Garrett proved in universal algebra.

The first of Birkhoff's theorems characterizes categories of algebraic systems
which can be defined by identities.  These are precisely those categories of
algebraic systems that are closed under the three operations of products,
subalgebras and homomorphic images. For example, groups and rings can be
characterized by identities,  but fields cannot, because the product of two
fields is not a field.
There are algebraic systems which are known to be definable by identities
because they have been shown to satisfy the three Birkhoff conditions, but for
which the actual identities are not known.

The second of Birkhoff's theorems  states that  a category of algebraic
systems is endowed with "free algebras" if and only if it is closed under
products and subalgebras.

The  category of linear lattices is closed under products and sublattices, so
that the free linear lattice on any set of generators  exists. A thorough
study of free linear lattices, revealing their rich structure, was carried out
by Gelfand and Ponomarev in a remarkable series of papers. Their results are
so stated as to apply  both to modular and to linear lattices. The free linear
lattice in $n$ generators is intimately related to the ring of invariants of a
set of $n$ subspaces in general position in projective space. Gelfand has
conjectured that the free linear lattice in four generators is decidable.
Recently, an explicit set of generators for the ring of invariants of a set of
four subspaces in projective space has been given by Howe and Huang; Gelfand's
conjecture is the lattice theoretic analog, and is thus probably true.

It is not known  whether  linear lattices may be characterized by identities.
Haiman has proved that linear lattices satisfy most of the classical theorems
of projective geometry, such as various generalizations of Desargues's
theorem, and he proved that not even these generalized Desarguian conditions
suffice to characterize linear lattices.

The deepest results to date on linear lattices are due to Haiman, who
developed a proof theory for linear lattices in his thesis. What does such a
proof theory consist of?  It is an iterative algorithm performed on a lattice
inequality
that splits the inequality into sub-inequalities by a tree-like procedure and
eventually  establishes that the inequality is true in all linear lattices, or
else it automatically provides a counterexample. A proof theoretic algorithm
is at least as  significant as a decision procedure, since a decision
procedure is merely  an assurance that  the proof theoretic algorithm will
eventually stop.

Haiman's proof theory for linear lattices brings to fruition  the program that
was set forth in the celebrated paper "The logic of quantum mechanics", by
Birkhoff and von Neumann. This paper argues that modular lattices provide a
new logic suited to  quantum mechanics. The authors did not know that the
modular lattices of quantum mechanics are linear lattices. In the light of
Haiman's proof theory, we may now confidently assert that  Birkhoff and von
Neumann's  logic of quantum mechanics is indeed the long awaited  new
"logic" where meet and join are endowed with a  logical  meaning that is a
direct descendant of   "and" and "or" of propositional logic.

\section{Lattice Theory and Probability}

One of the dramas of present day mathematics is the advent of non
commutative probability. Lattice theoretically, this drama is a game played
with three lattices: the lattice of equivalence relations, Boolean algebras,
and various linear lattices that are threatening to replace the first two.

Classical probability is a game of two lattices defined on a sample space: the
Boolean $\sigma$-algebra of events, and the lattice of Boolean $\sigma$-
subalgebras.

A $\sigma$-subalgebra of a sample space is a generalized equivalence relation
on the sample points.   In a sample space, the Boolean $\sigma$-algebra of
events and the lattice of $\sigma$-subalgebras are dual notions, but whereas
the Boolean $\sigma$-algebra of events has a simple structure, the same
cannot be said of the lattice of $\sigma$-subalgebras. For example, we
understand  fairly well measures on a Boolean $\sigma$-algebra, but the
analogous notion for the lattice of $\sigma$-subalgebras, namely, entropy, is
poorly understood.

Stochastic independence of two Boolean $\sigma$-subalgebras is a
strengthening of the notion of independence of equivalence relations.
Commuting equivalence relations also have a stochastic analog, which is best
expressed in terms of random variables. We say that two $\sigma$-subalgebras
$\Sigma_1$ and $\Sigma_2$ commute when any two random
variables  $X_1$ and $X_2$ defining  the $\sigma$-subalgebras $\Sigma_1$
and $\Sigma_2$ are conditionally independent. Catherine  Yan has studied
the proabilistic analog of a lattice of commuting equivalence relations,
namely, lattices of non-atomic $\sigma$-subalgebras any two of which are
stochastically commuting. There are stochastic processes where all associated
$\sigma$-subalgebras are commuting in Yan's sense, for example, Gaussian
processes.

In a strenuous tour de force, Catherine Yan has developed a proof theory for
lattices of non atomic commuting $\sigma$-subalgebras. Her theory casts new
light on  probability. It is also a vindication of Dorothy Maharam's
pioneering work in the classification of Boolean $\sigma$-algebras.

The portrait of non commutative probability is at present far from complete.
Von Neumann worked hard at a probabilistic setting for quantum mechanics.
His search for a quantum analog of  a sample space led him to the discovery
of continuous geometries. These geometries are similar to  projective spaces,
except that the dimension function takes all real values between zero and one.
Von Neumann characterized continuous geometries as modular lattices, and
showed that non commutative rings can be associated with continuous
geometries which share properties of rings of random variables, in particular,
there is the  analog of a probability distribution.

Sadly, the applications of continuous geometries have hardly been explored;
allow me to stick my neck out and mention one possible such application. It is
probable that some of the attractive $q$-identities that are now being proved
by representation theoretic methods can be given a "bijective" interpretation
in continuous geometries over finite fields. I have checked this conjecture
only for the simplest $q$-identities.

The triumph of von Neumann's ideas on quantum probability  is his
hyperfinite factor, which unlike Hilbert space has a modular lattice of closed
subspaces.  For a long time I have wondered why quantum mechanics is not
done in  the hyperfinite factor rather than in Hilbert space. Philosophically,
probability in a hyperfinite factor is more attractive than ordinary
probability,
since the duality between events and $\sigma$-subalgebras  is replaced by a
single modular lattice that plays the role of both. On several occasions I
have asked experts in quantum mechanics why the hyperfinite factor has been
physicists and mathematicians needed some  fifty years of training to grow
accustomed to  non commutative probability, and only now are the tables
beginning to turn, after the brilliant contributions to  non commutative
geometry and non commutative probability by Alain Connes and Virgil
Voicolescu.

\section{Other Directions}

It is heartening to watch every nook and cranny of lattice theory coming back
to the fore after a long period of neglect. One recent instance: MacNeille, a
student of Garrett's, developed a theory of completion by cuts of partially
ordered sets, analogous to Dedekind's construction of the real numbers. His
work was viewed as a dead end until last year, when Lascoux and
Sch\"utzenberger, in their last joint paper, showed that MacNeille's
completion neatly explains the heretofore mysterious Bruhat orders of
representations theory.

Two new structures that generalize the concept of a lattice should  be
mentioned in closing. First, Tits buildings. It is unfortunate that
presentations
of buildings avoid the lattice theoretic examples, which would  display the
continuity of thought that leads from lattices to buildings.

Second: $\Delta$-matroids, due to Kung, and developed by  Dress, Wentzel
and several others.
Garrett Birkhoff realized that Whitney's  matroids could be cast in the
language of geometric lattices,  that Garrett first defined in a paper that
appeared right after Whitney's paper in the same issue of the American
Journal. Roughly, $\Delta$-matroids are to Pfaffians as matroids are to
determinants. $\Delta$-matroids call for a generalization of lattices that
remains to be explored.

These developments, and several others that will not be mentioned because
my time is up, are a belated validation of Garrett Birkhoff's vision, which we
learned in three editions of his "Lattice Theory", and they betoken Prof.
Gelfand's oft-repeated  prediction that lattice theory will play a leading
role in the mathematics of the twenty-first century.

Thank you.

\end{document}

\end{document}


Date:           Thu, 10 Apr 1997 20:55:27 -0500
To:             kcollins(at-sign)mail.wesleyan.edu
From:           kcollins(at-sign)wesleyan.edu (Karen L. Collins)
Subject:        May 3rd meeting


               Come to the Twenty-fifth one day conference on

Combinatorics and Graph Theory

Saturday, May 3, 1997

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

Schedule

10:00  Stephen Wismath (Univ. of Lethbridge, McGill Univ.)
On Inducing Polygons of Arrangements

11:10  Hazel Everett (Universite de Quebec a Montreal)
The Homogeneous Set Sandwich Problem

12:30  Lunch

2:00  Katherine St. John (University of Pennsylvania)
Games, Logic, and Random Structures

3:10  Gabor Sarkozy (WPI)
On a New Method in Graph Theory

4:30  We invite you to celebrate the 25th CoNE meeting!
Come to a reception following the talks at Ileana Streinus
apartment on the Smith College Campus, 115 Elm Street #1.

The conferences are supported by an NSF grant which allows us
to provide a modest transportation allowance to those attendees
who are not local.  We also gratefully acknowledge support from
Smith College and Wesleyan University.

Our Web page site has directions to Smith College, abstracts of
speakers, dates of future conferences, and other information.

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

Karen Collins (Wesleyan University), (860) 685-2169,
kcollins(at-sign)wesleyan.edu

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


Date:           Tue, 15 Apr 1997 19:21:30 -0400 (EDT)
From:           Jim Propp <propp(at-sign)math.mit.edu>
To:             combinatorics(at-sign)math.mit.edu
Subject:        Web-friendly combinatorics(at-sign)mit archive


I have just used David Eppstein's handy m2html program to make
Web-friendly versions of the archive files.  You can access them
the way you would normally access one of the archive files; just
http://www-math.mit.edu/~propp/combinatorics-archive/96a.html

If you want a copy of m2html of your own, you can get it at
http://www.ics.uci.edu/~eppstein/m2html/

Jim


Date:           Tue, 15 Apr 1997 22:20:49 -0400 (EDT)
From:           Thomas Bohman <bohman(at-sign)math.mit.edu>
To:             combinatorics(at-sign)math.mit.edu
Subject:        Combinatorics Seminar on 4/18


The MIT Combinatorics seminar will resume its regular schedule
on Friday, April 18 at 4:15 in room 2-338 with the following
talk.

Speaker: Gabor Sarkozy

Title: On a new method in graph theory

We present a new method based on the Regularity Lemma and the
Blow-up Lemma for finding certain special spanning subgraphs of
dense graphs. Two typical applications of this method:

1. (Bollobas Conjecture, 1978) We show  that any constant
degree tree on sufficiently many vertices can be embedded into
any dense graph on the same number of vertices.

2. (Posa-Seymour Conjecture, 1962) We show  that a graph on
sufficiently many vertices and with minimum degree at least
2/3 n  (where n is the number of vertices) contains the square
of a Hamiltonian cycle.

Algorithmic implications of the method will also be discussed.


Date:           Thu, 17 Apr 1997 13:56:35 -0400 (EDT)
From:           Thomas Bohman <bohman(at-sign)math.mit.edu>
To:             combinatorics(at-sign)math.mit.edu
Subject:        MIT Cominatorics Seminar


                  MIT Combinatorics Seminar

Date: Friday April 25 at 4:15 PM in 2-338.

Speaker: Tibor Szabo, IAS

Title: Norm-graphs and the Zarankiewicz problem

The Turan number ex(n, G) of a fixed graph G is the greatest
integer m, such that there exists a graph on n vertices with m edges,
containing NO subgraph isomorphic to G. In the case when G is the complete
bipartite graph K_{t,s}, the determination of the
Turan number is called the Zarankiewicz problem. For 3 < t \le s,
the order of magnitude of ex(n, K_{t,s}) wasn't (partly isn't) known.

Using polynomials over finite fields, we give an explicit construction
of K_{t,(t-1)!+1}-free graphs with high edge-density. This improves upon
earlier probabilistic bounds. The validity of the construction
depends on elementary facts from commutative algebra. The result is
a joint work with J. Kollar and L. Ronyai.

Extending the result from s\ge (t-1)! to s\ge t or even to s\ge poly(t)
would represent major progress.


Date:           Mon, 28 Apr 1997 08:45:08 -0500
To:             kcollins(at-sign)mail.wesleyan.edu
From:           kcollins(at-sign)wesleyan.edu (Karen L. Collins)
Subject:        second announcement


               Come to the Twenty-fifth one day conference on

Combinatorics and Graph Theory

Saturday, May 3, 1997

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

Schedule

10:00  Stephen Wismath (Univ. of Lethbridge, McGill Univ.)
On Inducing Polygons of Arrangements

11:10  Hazel Everett (Universite de Quebec a Montreal)
The Homogeneous Set Sandwich Problem

12:30  Lunch

2:00  Katherine St. John (University of Pennsylvania)
Games, Logic, and Random Structures

3:10  Gabor Sarkozy (WPI)
On a New Method in Graph Theory

4:30  We invite you to celebrate the 25th CoNE meeting!
Come to a reception following the talks at Ileana Streinus
apartment on the Smith College Campus, 115 Elm Street #1.

The conferences are supported by an NSF grant which allows us
to provide a modest transportation allowance to those attendees
who are not local.  We also gratefully acknowledge support from
Smith College and Wesleyan University.

Our Web page site has directions to Smith College, abstracts of
speakers, dates of future conferences, and other information.

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

Karen Collins (Wesleyan University), (860) 685-2169,
kcollins(at-sign)wesleyan.edu

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


Date:           Tue, 29 Apr 1997 14:34:12 -0400 (EDT)
From:           Sara Billey <sara(at-sign)math.mit.edu>
To:             combinatorics(at-sign)math.mit.edu
Subject:        May seminars


Here is the schedule of combinatorics seminars for May.  Note, there
is no seminar this Friday, May 2.  Abstracts and more information will
be available on the web as it we receive it,
http://www-math.mit.edu/~rojas/Combinatorics/combi.html

date:  Wednesday, May 7, 1997
speaker: Marcelo Aguiar
title:  Braids, q-binomials and quantum groups

date: Friday, May 9, 1997
speaker: Irena Peeva
title: To be announced.

date: Wednesday, May 14, 1997
speaker: Hal Schenck
title:  Splines, Homological Algebra, and some interesting ideals

date: Friday, May 16, 1997
speaker: Vesselin Gasharov
title:  To be announced.

date: Friday, May 23, 1997
speaker: Miklos Bona
title:  Exact enumeration of 1342-avoiding permutations;
A close link with labeled trees and planar maps


Date:           Tue, 29 Apr 1997 15:21:03 -0400 (EDT)
From:           Sara Billey <sara(at-sign)math.mit.edu>
To:             combinatorics(at-sign)math.mit.edu
Subject:        Friday


Late breaking news..... We will have seminar this Friday, May 2 in
2-338 at 4:15pm as usual.

speaker: Lauren L. Rose
institution: Bunting Institute and MIT
title: Algebraic, Geometric, and Combinatorial Aspects of Multivariate
Splines

Multivariate splines are piecewise polynomial functions defined
on a polyhedral subdivision of R^d.  Splines have many
uses in applied math and engineering, e.g. approximating solutions to
partial differential equations and surface modeling for computer graphics.

dimensions for spline spaces by studying the combinatorial properties
of the subdivision.  Using these methods, we can explain how varying
the triangulation changes the types of splines that can occur.  We can
also use the technique of Groebner bases to compute bases for spline
spaces and to construct splines with a given set of constraints.

This talk will be accessible to a general mathematical audience.


Date:           Fri, 2 May 1997 09:34:59 -0400 (EDT)
From:           Sara Billey <sara(at-sign)math.mit.edu>
To:             combinatorics(at-sign)math.mit.edu
Subject:        seminar today


***********Combinatorics Seminar Today *************
4:15pm in 2-338

speaker: Lauren L. Rose
institution: Bunting Institute and MIT
title: Algebraic, Geometric, and Combinatorial Aspects of Multivariate
Splines

abstract:
Multivariate splines are piecewise polynomial functions defined
on a polyhedral subdivision of $R^d$.  Splines have many
uses in applied math and engineering, e.g. approximating solutions to
partial differential equations and surface modeling for computer graphics.

dimensions for spline spaces by studying the combinatorial properties
of the subdivision.  Using these methods, we can explain how varying
the triangulation changes the types of splines that can occur.  We can
also use the technique of Groebner bases to compute bases for spline
spaces and to construct splines with a given set of constraints.

This talk will be accessible to a general mathematical audience.

Upcoming Events:

date:  Wednesday, May 7, 1997
speaker: Marcelo Aguiar
title:  Braids, q-binomials and quantum groups

date: Friday, May 9, 1997
speaker: Irena Peeva
title:  Subspace Arrangements and Resolutions

http://www-math.mit.edu/~rojas/Combinatorics/combi.html


Date:           Wed, 7 May 1997 10:25:52 -0400 (EDT)
From:           Sara Billey <sara(at-sign)math.mit.edu>
To:             combinatorics(at-sign)math.mit.edu
Subject:        today


***********Combinatorics Seminar Today *************
4:15pm in 2-338

date:  Wednesday, May 7, 1997
speaker: Marcelo Aguiar
title:  Braids, q-binomials and quantum groups
abstract:
The classical identities between the $q$-binomial coefficients and
factorials can be generalized to a context where numbers are replaced
by braids. More precisely, for every pair $i$, $n$ of natural numbers
there is defined an element $b^{(n)}_i$ of the braid group algebra
$kB_n$, and these satisfy analogs of the classical identities for the
binomial coefficients.  By choosing representations of the braid
groups one obtains numerical or matrix realizations of these
identities, in particular one recovers the $q$-identities through the
simplest one dimensional representation.  These binomial braids
$b^{(n)}_i$ play a crucial role in the definition of the quantum group
$U_q^+(C)$ presented in the author's thesis. They are also closely
related to the Varchenko matrix'' associated to the hyperplane
arrangement of the root system $A_n$.

Upcoming events:

date: Friday, May 9, 1997
speaker: Irena Peeva
title:  Subspace Arrangements and Resolutions
abstract:
I will talk about two applications of free resolutions:
1) computing the cohomology of the complement of a
real diagonal subspace arrangement (joint work with
V. Reiner and V. Welker),
2) computing some invariants of the fundamental group
of the complement of a complex hyperplane arrangemant.

date: Wednesday, May 14, 1997
speaker: Hal Schenck
title:  Splines, Homological Algebra, and some interesting ideals

abstract on the web


Date:           Thu, 8 May 1997 14:43:27 -0400 (EDT)
From:           Sara Billey <sara(at-sign)math.mit.edu>
To:             combinatorics(at-sign)math.mit.edu
Subject:        seminar tomorrow


The combinatorics seminar for tomorrow will begin at ***4:30pm*** so
that people can briefly attend the the department party from 4:00 on.

Also, there will be a pretalk for anyone who is interested from
3:30-4:00 in 2-338.  As usual, the pretalk will cover background
material related to the talk for non-experts in the subject.

***********Combinatorics Seminar Tomorrow*************
**4:30** in 2-338

date: Friday, May 9, 1997
speaker: Irena Peeva
title:  Subspace Arrangements and Resolutions
abstract:
I will talk about two applications of free resolutions:
\begin{enumerate}
\item  Computing the cohomology of the complement of a
real diagonal subspace arrangement (joint work with
V. Reiner and V. Welker).
\item  Computing some invariants of the fundamental group
of the complement of a complex hyperplane arrangemant.
\end{enumerate}

********************************************************
Upcoming events:

date: Wednesday, May 14, 1997
speaker: Hal Schenck
title:  Splines, Homological Algebra, and some interesting ideals

date: Friday, May 16, 1997
speaker: Vesselin Gasharov
title:  Eulerian polynomials and the Neggers-Stanley conjecture


From:           "John Stembridge" <jrs(at-sign)math.lsa.umich.edu>
Date:           Mon, 12 May 1997 16:53:09 -0400 (EDT)
To:             combinatorics(at-sign)math.mit.edu
Subject:        Maple packages


I maintain a mailing list for sending out announcements about my Maple
packages SF, posets, and coxeter/weyl. If you didn't get a message about
these packages earlier today, it means you aren't on the mailing list.

If you want to be added to the list, let me know. And if your preferred
let me know.

By the way, the list is:
low-traffic (the last message was sent more than a year ago)
kept private (I send the messages via blind carbon copy).

John Stembridge


Date:           Wed, 14 May 1997 13:26:52 -0400 (EDT)
From:           Lauren Rose <rose(at-sign)math.mit.edu>
To:             combinatorics(at-sign)math.mit.edu
Subject:        Seminar Today!


********  Seminar Today  ***********************

4:15 pm,  Room 2-338

Title:  Splines, Homological Algebra, and Some Interesting Ideals

Speaker:  Hal Schenck, Cornell University

For a simplicial subdivison Delta of a region in R^n, we analyze the
dimension of the vector space C^r_k(Delta) of C^r piecewise polynomial
functions (splines) on Delta of degree at most k. This problem is
closely related to the structure of the graded R[x_0 \ldots
x_n]-module C^r(\hat{Delta}), where \hat{Delta} is the join of Delta
with the origin in R^{n+1}.

I will define a chain complex such that C^r(\hat{Delta}) appears as
the top homology module, and will prove that if n=2 (i.e., Delta is
planar), then C^r(\hat{\Delta}) is free if and only if the first
homology module of the complex vanishes. Finally, I will show that
there is a short exact sequence which relates the behavior of
C^r(\hat{Delta}) to the behavior of ideals of the form <(x+a_1
y)^{r+1},...,(x+a_k y)^{r+1}>, with a_i not equal to a_j if i is not
equal j, and will analyze the structure of these ideals.


Date:           Thu, 15 May 1997 17:47:56 -0400 (EDT)
From:           Sara Billey <sara(at-sign)math.mit.edu>
To:             combinatorics(at-sign)math.mit.edu
Subject:        seminar


            ****Combinatorics Seminar Tomorrow ****
4:15pm in 2-334

Eulerian polynomials and the Neggers-Stanley conjecture

Vesselin Gasharov{University of Michigan}

Abstract:

It is well known that the Eulerian polynomials are log-concave, but until
recently no combinatorial proof was known. In the first part of the talk we
will present such a proof and discuss some related results and open questions.

The W-polynomials of labeled posets generalize the Eulerian polynomials. It
was conjectured by Neggers and Stanley that the W-polynomials have only real
zeros. We will prove that the W-polynomials of naturally labeled graded posets
of small rank are unimodal which provides further evidence in support of the
Neggers-Stanley conjecture. In the process we will also obtain a combinatorial
proof of the fact that the W-polynomials of such posets are symmetric. (It is
known that the W-polynomial of any naturally labeled graded poset is symmetric,
but no combinatorial proof is known for the general case.)

Upcoming Event:

date: Friday, May 23, 1997
speaker: Miklos Bona
title:  Exact enumeration of 1342-avoiding permutations;
A close link with labeled trees and planar maps

http://www-math.mit.edu/~rojas/Combinatorics/combi.html


Date:           Fri, 23 May 1997 13:38:01 -0400 (EDT)
From:           Sara Billey <sara(at-sign)math.mit.edu>
To:             combinatorics(at-sign)math.mit.edu
Subject:        seminar tomorrow


Today we will have our final combinatorics seminar for the year.  We
will be holding an informal summer seminar meeting (tentatively) on
Tuesdays and Fridays at 2:00.  If you are interested in getting more
info, you can either write to me or Patricia Hersh
(hersh(at-sign)math.mit.edu).

If anyone would like to be removed from this mailing list, just let me
know.

***********Combinatorics Seminar Today *************
4:15pm in 2-338

speaker: Miklos Bona
title:  Exact enumeration of 1342-avoiding permutations;
A close link with labeled trees and planar maps

abstract:
Solving the first nonmonotonic, longer-than-three instance of a
classic enumeration problem, we obtain the generating function $H(x)$
of all 1342-avoiding permutations of length $n$ as well as an {\em
exact} formula for their number $S_n(1342)$.  While achieving this, we
bijectively prove that the number of indecomposable 1342-avoiding
permutations of length $n$ equals that of labeled plane trees of a
certain type on $n+1$ vertices recently enumerated by Cori, Jacquard
and Schaeffer, which is in turn known to be equal to the number of
rooted bicubic maps enumerated by Tutte in 1963. Moreover, $H(x)$
turns out to be algebraic, proving the first nonmonotonic,
longer-than-three instance of a conjecture of Zeilberger and Noonan.
We also prove that $\sqrt[n]{S_n(1342)}$ converges to 8, so in
particular, $lim_{n\rightarrow \infty}(S_n(1342)/S_n(1234))=0$.


To:             domino(at-sign)math.mit.edu, combinatorics(at-sign)math.mit.edu
Subject:        counting at MIT
Date:           Fri, 18 Jul 1997 07:43:42 -0400
From:           John Stembridge <jrs(at-sign)math.lsa.umich.edu>


There is an amusing article on the 2000 vs. 2001 debate in the latest
issue of the Atlantic monthly. See

http://www.theAtlantic.com/atlantic/issues/97jul/zero.htm

But especially amusing is the following excerpt, regarding the author's
attempt to establish whether it is "proper" to count starting from 0.
(Elsewhere, he makes a reasonable argument that it sometimes is.)

"I called the math department at the Massachusetts Institute of Technology
to find out the proper way to count and whether zero is a real number.
Apparently, counting is not MIT's forte. I was told that no one in the math
department would comment on that topic. As for zero, a department
administrator said, Our people are interested more in numbers invented after
1972.' He told me I needed a number theorist."

The author? He is Dick Teresi, "the editor of VQ, a magazine about
Harley-Davidson motorcycles. He is the co-author, with the physicist Leon
Lederman, of The God Particle (1993)."

John Stembridge
`