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

                Quadratic Integers and Coxeter Groups

               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.
For more information, see
	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)
        The Weakness of an Ordered Set:  advice to your dean
         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.
The address is:  http://math.smith.edu/~rhaas/coneweb.html

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)
        The Weakness of an Ordered Set: advice to your dean
         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.
The address is:  http://math.smith.edu/~rhaas/coneweb.html

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.  
The deadline  for  submission is 
                {\bf May 15, 1997}. 
Please  send   your  abstract to the above address or by e-mail 
(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
connected with your attendance please place it on this form.
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 
After  acceptance of your registration, you will  receive  a
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%%%%%

     Family name (please print)=
%%
\hskip3cm    
     First name=
%%
\par\smallskip  
     Sex= Male Female  %% delete one
%%
\par\smallskip 
     Affiliation=
%%
\par\vskip1truecm  
     Mailing address (if different)=  
%%
\par\vskip1truecm
     E-mail address=
%%
\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
to translate facts about commutative rings into facts about  more general 
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 
quietly left aside,  and invariably I received evasive answers. Most likely,  
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 Streinu`s
       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.
The address is:  http://math.smith.edu/~rhaas/coneweb.html

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
add the suffix .html, e.g.:
    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 Streinu`s
       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.
The address is:  http://math.smith.edu/~rhaas/coneweb.html

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.

We address a problem in approximation theory about finding bases and
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.

We address a problem in approximation theory about finding bases and
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

More info available on 
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
e-mail address is something other than the address you are replying from,
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

More info available on 
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