Date:Fri, 17 Jan 1997 12:52:41 -0500To:combinatorics(at-sign)math.mit.eduFrom: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 -0500To:combinatorics(at-sign)math.mit.eduFrom: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 -0500To:combinatorics(at-sign)math.mit.eduFrom: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.eduSubject: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 -0500To:combinatorics(at-sign)math.mit.eduFrom: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.eduSubject: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 -0500To:combinatorics(at-sign)math.mit.eduFrom: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.eduSubject:LOVASZ --- ORC Seminar (fwd)

Date:Tue, 18 Feb 97 06:24:41 ESTFrom:"L. Beril Toktay" <toktay(at-sign)keiko.mit.edu>To:or_seminar(at-sign)MIT.EDUSubject: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.eduSubject: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.eduSubject: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 -0500To:combinatorics(at-sign)math.mit.eduFrom: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 -0500To:combinatorics(at-sign)math.mit.eduFrom: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.eduSubject: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 -0500To:kcollins(at-sign)mail.wesleyan.eduFrom: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 -0500To:kcollins(at-sign)mail.wesleyan.eduFrom: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.eduSubject:[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.orgSubject: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 -0500To:kcollins(at-sign)mail.wesleyan.eduFrom: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.eduSubject: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.eduSubject: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.eduSubject: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 -0500To:kcollins(at-sign)mail.wesleyan.eduFrom: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.eduSubject: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.eduSubject: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.eduSubject: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.eduSubject: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.eduSubject: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.eduSubject: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.eduSubject: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.eduSubject: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.eduSubject: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.eduSubject:counting at MITDate:Fri, 18 Jul 1997 07:43:42 -0400From: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