From propp(at-sign)math.mit.edu Mon Feb 1 14:03:07 1993 To: combinatorics(at-sign)math.mit.edu Subject: Combinatorics seminar, 2/10 Wednesday, February 10, 4:15 p.m.; MIT, room 2-338 Xavier Gerard Viennot (Bordeaux I) Heaps of segments and q-enumeration of convex polyominoes [Abstract not yet available.] From propp(at-sign)math.mit.edu Mon Feb 1 14:03:28 1993 To: combinatorics(at-sign)math.mit.edu Subject: Combinatorics seminar, 2/12 Friday, February 12, 4:15 p.m.; MIT, room 2-338 Andrei Gabrielov (visiting Cornell) Avalanches, sandpiles and Tutte decompositions Abstract of Gabrielov's talk: Sandpile and avalanche models of failure were introduced recently (Bak et al., 1987, and an avalanche of publications with references to this paper) to simulate processes of different nature (earthquakes, charge density waves, forest fires, etc., including economics) characterized by self-organized critical behavior. Statistical properties of an important class of these models, abelian sandpiles (Dhar, 1990) and abelian avalanches (Gabrielov, 1992), can be investigated analytically due to an abelian group acting on the phase space. It is shown that the distribution of avalanches in a discrete, stochastic abelian sandpile model is identical to the distribution of avalanches in a continuous, deterministic abelian avalanche model with the same redistribution matrix and loading rate vector. For a symmetric redistribution matrix, recurrent formulas for the distribution of avalanches in the abelian avalanche model lead to explicit expressions containing invariants of graphs known as Tutte polynomials. In the general case, an analog of the Tutte decomposition is suggested for matrices and directed graphs, and the corresponding expressions for the distribution of avalanches in terms of directed tree numbers of a directed graph are found. New combinatorial identities for graphs and directed graphs are derived from these formulas. From propp(at-sign)math.mit.edu Wed Feb 3 14:57:59 1993 To: combinatorics(at-sign)math.mit.edu Subject: Viennot's talk on 2/10 Wednesday, February 10, 4:15 p.m.; MIT, room 2-338 Xavier Gerard Viennot (Bordeaux I) Heaps of segments and q-enumeration of convex polyominoes Heaps of pieces provide a geometrical interpretation to the so-called Cartier-Foata monoids defined with partial commutation rules. Polyominoes (or animals) are connected unions of cells drawn on a planar lattice and related to statistical physics. In this talk (joint work with Mireille Bousquet-Melou), we show the use of heap theory in the enumeration of certain families of polyominoes: skew Ferrers diagrams and directed convex polyominoes. Related topics are Mobius inversion, q-Bessel functions, Ehrhart polytope theory and braids. From propp(at-sign)math.mit.edu Fri Feb 5 22:39:51 1993 To: combinatorics(at-sign)math.mit.edu Subject: Gabrielov's talk(s) Although Andrei Gabrielov's two talks next week (Feb. 10 at Northeastern and Feb. 12 at MIT) have the same title and abstract, they will not be identical and will stress different aspects of his theory (although they will definitely have some repetitions to make them formally independent). From propp(at-sign)math.mit.edu Mon Feb 8 14:32:52 1993 To: combinatorics(at-sign)math.mit.edu Subject: *** "NEWSFLASH" *** [Apologies for sending out this announcement so close to the wire.] The following talk may be of interest: APPLIED MATH COLLOQUIUM, FEBRUARY 8, 1993 MIT, ROOM 2-105 Xavier Gerard Viennot Nonlinear controlled systems and combinatorics In this talk, I will present a combinatorial approach to nonlinear systems of differential equations in control theory. A typical example is the following equation associated to a simple nonlinear circuit: 2 y'(t) = a y(t) + b y (t) + u(t). The function u(t) is the input, or forcing term, y(t) is the output. Usually solutions of such systems with forcing terms are represented by Volterra type expansions. The use of functional expansions has been energetically studied in the last forty years in engineering as well as in physics. With Pierre Leroux (LACIM, UQAM, Montreal), we propose a combinatorial approach. To each system, we associate certain families of combinatorial objects called "increasing weighted colored trees", "weighted paths" and "histories". The determination of the coefficients of the functional expansion becomes a combinatorial problem: compute the sum of the weights of certain families of trees or paths. This approach gives very efficient computation algorithms. Another interest is theoretical, by giving "combinatorial" proof of some general facts and formulae, or by leading to the introduction of certain approximants of the solutions of general systems by solutions of bilinear systems. From propp(at-sign)math.mit.edu Mon Feb 8 14:49:59 1993 To: combinatorics(at-sign)math.mit.edu Subject: Re: previous announcement Viennot's talk is scheduled for 4:15 p.m. From propp(at-sign)math.mit.edu Mon Feb 15 20:55:23 1993 To: combinatorics(at-sign)math.mit.edu Subject: Anders Bjorner, 2/17 Wednesday, February 17, 4:15 p.m.; MIT, room 2-338 Anders Bjorner (KTH) Subspace arrangements, linear decision trees and Mobius functions From propp(at-sign)math.mit.edu Thu Feb 18 18:20:32 1993 To: combinatorics(at-sign)math.mit.edu Subject: Rota, 2/26 Friday, February 26, 4:15 p.m.; MIT, room 2-338 Gian-Carlo Rota (MIT) A probabilistic interpretation of the Riemann zeta function A probabilistic interpretation of the Riemann zeta function has been given by Golomb, but his interpretation of zeta(s) has the disatvantage that one needs a different sample space for each s > 1. We give another stochastic process, which gives a stochastic model for zeta(s) simultaneously for all integer s > 1. The idea is to develop a suitable concept of infinite Mobius inversion. From propp(at-sign)math.mit.edu Thu Mar 4 15:43:34 1993 To: combinatorics(at-sign)math.mit.edu Subject: MIT Combinatorics Seminar There are still a half-dozen open slots in the combinatorics seminar for the spring semester. Anyone who is interested in presenting a talk should contact me in the next few weeks. Jim Propp (propp(at-sign)math.mit.edu) From propp(at-sign)math.mit.edu Thu Mar 4 15:52:42 1993 To: combinatorics(at-sign)math.mit.edu Subject: Ray Hill, 3/8 Monday, March 8, 4:00 p.m.; MIT LCS, building NE43, room 518 (LCS) ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ (note unusual location of talk!) Ray Hill (University of Salford) Searching with Lies: The Ulam Problem Ulam's searching problem is to determine the minimal number of yes-no queries to find an unknown integer between 1 and 2^20 if at most some given number e of the answers may be lies. Recently published papers have solved the problem for the cases e = 1,2,3 and 4. By relying more heavily on a reference published in 1968 we solve the problem for all values of e. (Joint work with ER Berlekamp and JP Karim) (This announcement overrides an earlier announcement, sent by snail-mail, that announced the date of the talk as Tuesday, March 9.) From propp(at-sign)math.mit.edu Thu Mar 4 15:53:42 1993 To: combinatorics(at-sign)math.mit.edu Subject: Persi Diaconis, 3/12 Friday, March 12, 4:15 p.m.; MIT, room 2-338 Persi Diaconis (Harvard) The combinatorics of Haar measure A variety of applied problems, from telephone encryption, through the study of the energies of nuclear collisions, through study of the zeroes of the zeta function, lead to the study of the eigenvalues of random unitary, orthogonal, or symplectic matrices. These can be understood using Schur functions and the Brauer algebra. This is joint work with Mehrdad Shahshahani. From propp(at-sign)math.mit.edu Thu Mar 4 15:54:39 1993 To: combinatorics(at-sign)math.mit.edu Subject: Aviezri Fraenkel, 3/10 Wednesday, March 10, 4:15 p.m.; MIT, room 2-338 Aviezri Fraenkel (Weizmann Institute, visiting U.\ of Penn.) Some of my favorite problems in combinatorial game theory Poset games, Wythoff games, ... Why are combinatorial games hard? The Divide & Conquer approach for bridging the complexity gap between Nim and chess. What's an efficient strategy? Spectra of inefficiencies... Open problems. From propp(at-sign)math.mit.edu Mon Mar 15 18:45:22 1993 To: combinatorics(at-sign)math.mit.edu Subject: Trenk, 3/17 Wednesday, March 17, 4:15 p.m.; MIT, room 2-338 Ann Trenk (Wellesley) Bipartite Bitolerance Orders Tolerance orders and tolerance graphs arise as a generalization of interval orders and interval graphs in which some overlap of intervals is tolerated. They can be used to model scheduling problems where some overlap between scheduled events is permitted. The classes of bounded, proper and unit tolerance orders and graphs have been studied by other authors. Here we introduce two-sided versions of these classes. We show that {\em all} the classes are identical for bipartite ordered sets and give some examples to show that the classes differ in the nonbipartite case. We also give an algorithm for determining whether a bipartite ordered set is in these classes, and if so finding a representation of it. This is joint work with Ken Bogart at Dartmouth College. From propp(at-sign)math.mit.edu Wed Mar 17 21:48:40 1993 To: combinatorics(at-sign)math.mit.edu Subject: Schedule of combinatorics talks for April M.I.T. COMBINATORICS SEMINAR There will be no meetings of the seminar until April 7. Here is a list of upcoming talks: * Wednesday, April 7: Gian-Carlo Rota, ``The theory of Baxter algebras'' * Friday, April 9: Andrew Gleason, ``Hadamard matrices and the Matthieu groups'' * Wednesday, April 14: Erwin Lutwak, ``Larger bodies that cast smaller shadows'' * Wednesday, April 21: Rachel Rue, ``On covering an independent set in a grid with another one'' * Friday, April 23: Bruce Sagan, ``Why the characteristic polynomial factors'' * Wednesday, April 28: Ivan Cherednik, ``The Macdonald constant term conjecture'' All talks will meet in room 2-338 at 4:15 p.m. From propp(at-sign)math.mit.edu Fri Mar 19 11:38:55 1993 To: combinatorics(at-sign)math.mit.edu Subject: CORRECTION M.I.T. COMBINATORICS SEMINAR There will be no meetings of the seminar until April 7. Here is a list of upcoming talks. ** NOTE ** : This supersedes an erroneous version that was sent out earlier this week. * Wednesday, April 7: Gian-Carlo Rota, ``The theory of Baxter algebras'' * Friday, April 9: Andrew Gleason, ``Hadamard matrices and the Matthieu groups'' * Wednesday, April 14: Erwin Lutwak, ``Larger bodies that cast smaller shadows'' * Friday, April 16: Michael Albertson, ``Some degree-constrained extremal graph problems'' * Wednesday, April 21: Rachel Rue, ``On covering an independent set in a grid with another one'' * Friday, April 23: Bruce Sagan, ``Why the characteristic polynomial factors'' * Wednesday, April 28: Ivan Cherednik, ``The Macdonald constant term conjecture'' All talks will meet in room 2-338 at 4:15 p.m. From propp(at-sign)math.mit.edu Wed Mar 24 14:05:39 1993 To: combinatorics(at-sign)math.mit.edu Subject: Another correction M.I.T. COMBINATORICS SEMINAR There will be no meetings of the seminar until April 7. Here is a list of the next seven talks in the MIT Combinatorics Seminar. ** NOTE ** : This supersedes two earlier versions of this announcement that were sent out earlier this month. * Wednesday, April 7: Gian-Carlo Rota, ``The theory of Baxter algebras'' * Wednesday, April 14: Erwin Lutwak, ``Larger bodies that cast smaller shadows'' * Friday, April 16: Michael Albertson, ``Some degree-constrained extremal graph problems'' * Wednesday, April 21: Rachel Rue, ``On covering an independent set in a grid with another one'' * Friday, April 23: Bruce Sagan, ``Why the characteristic polynomial factors'' * Wednesday, April 28: Ivan Cherednik, ``The Macdonald constant term conjecture'' * Friday, April 30: Andrew Gleason, ``Hadamard matrices and the Matthieu groups'' (note new date of talk) All talks will meet in room 2-338 at 4:15 p.m. From propp(at-sign)math.mit.edu Wed Mar 31 11:57:40 1993 To: combinatorics(at-sign)math.mit.edu Subject: Rota, 4/7 Wednesday, April 7, 4:15 p.m.; MIT, room 2-338 Gian-Carlo Rota (MIT) The theory of Baxter algebras Baxter operators are operators that satisfy an identity which is roughly the q-analogue of integration by parts. We shall develop the combinatorial properties of these operators and give some combinatorial and probabilistic applications. From propp(at-sign)math.mit.edu Mon Apr 12 15:32:16 1993 To: combinatorics(at-sign)math.mit.edu Subject: Lutwak, 4/14 Wednesday, April 14, 4:15 p.m.; MIT, room 2-338 Erwin Lutwak (Brooklyn Polytechnic) Larger bodies that cast smaller shadows Consider two solid objects (convex bodies, to be precise) in ordinary Euclidean 3-space. Suppose we are told that one of these bodies always (in all directions) casts larger (in area) shadows than the other. Does it follow that the body which casts the larger shadow is larger in volume? The answer here is an easy NO. There are numerous similar counter intuitive results concerning ordinary bodies in Euclidean 3-space. Some of these will be presented. A number of long standing open problems will also be presented. These problems (while apparently not easy) can all be explained to the `man in the street'. From propp(at-sign)math.mit.edu Mon Apr 12 15:41:51 1993 To: combinatorics(at-sign)math.mit.edu Subject: Albertson, 4/16 Friday, April 16, 4:15 p.m.; MIT, room 2-338 Michael Albertson (Smith) Some degree-constrained extremal graph problems If G is any graph with at least six vertices, then either G or its complement must contain a triangle in which two vertices have the same degree. We say that a triangle has the Ramsey repeat degree property. This talk will describe how this result generalizes. For instance: One might naively expect that every graph must have the Ramsey repeat degree property - all bipartite graphs do, but the 4-clique does not. There are natural Turan bounds, theorems about independent sets, results about the total edge discrepancy of a graph, and questions. From propp(at-sign)math.mit.edu Wed Apr 14 13:09:04 1993 To: combinatorics(at-sign)math.mit.edu Subject: Rue, 4/21 Wednesday, April 21, 4:15 p.m.; MIT, room 2-338 Rachel Rue (Williams) On covering an independent set in a grid with another one I will prove the following conjecture by Winkler and Arasmith: For any independent set O in a grid, there is a second independent set X such that there is at least one point in X adjacent to every point in O. Or equivalently, for every maximal independent set in a grid, there is a second, disjoint maximal independent set. From propp(at-sign)math.mit.edu Fri Apr 16 11:18:11 1993 To: combinatorics(at-sign)math.mit.edu Subject: Sagan, 4/23 Friday, April 23, 4:15 p.m.; MIT, room 2-338 Bruce Sagan (Michigan State) Why the characteristic polynomial factors Let L be a finite ranked lattice with minimal element 0, maximal element 1, rank function rho(x), and Mobius function mu(x)=mu(0,x) for x in L. The characteristic polynomial of L is chi(L,t) = sum_{x in L} mu(x) t^{rho(1)-rho(x)}. For many interesting lattices, chi(L,t) factors over the non-negative integers. We will survey various ways of proving such results, using lattices connected with Coxeter hyperplane arrangments as examples. (These arrangments are obtained by using hyperplanes perpendicular to root systems generating Coxeter groups.) Techniques may include using broken circuit complexes, supersolvability, atom decision trees, signed graph colorings, Earhart polynomials of polytopes, free modules of derivations, and results about the all-reflections length function on a Coxeter group. From propp(at-sign)math.mit.edu Fri Apr 16 13:38:42 1993 To: combinatorics(at-sign)math.mit.edu Subject: Sagan, 4/23 [We're having mailer-troubles; my apologies for any duplications.] Friday, April 23, 4:15 p.m.; MIT, room 2-338 Bruce Sagan (Michigan State) Why the characteristic polynomial factors Let L be a finite ranked lattice with minimal element 0, maximal element 1, rank function rho(x), and Mobius function mu(x)=mu(0,x) for x in L. The characteristic polynomial of L is chi(L,t) = sum_{x in L} mu(x) t^{rho(1)-rho(x)}. For many interesting lattices, chi(L,t) factors over the non-negative integers. We will survey various ways of proving such results, using lattices connected with Coxeter hyperplane arrangments as examples. (These arrangments are obtained by using hyperplanes perpendicular to root systems generating Coxeter groups.) Techniques may include using broken circuit complexes, supersolvability, atom decision trees, signed graph colorings, Earhart polynomials of polytopes, free modules of derivations, and results about the all-reflections length function on a Coxeter group. From propp(at-sign)math.mit.edu Thu Apr 22 12:30:10 1993 To: combinatorics(at-sign)math.mit.edu Subject: This Friday After the talk on Friday, some people will be going out to dinner with the speaker, Bruce Sagan. All are welcome. From propp(at-sign)math.mit.edu Fri Apr 23 17:30:08 1993 To: combinatorics(at-sign)math.mit.edu Subject: Gleason, 4/30 Friday, April 9, 4:15 p.m.; MIT, room 2-338 Andrew Gleason (Harvard) Hadamard matrices and the Matthieu groups Hadamard matrices offer a short route to the Matthieu groups M_12 and M_24. From propp(at-sign)math.mit.edu Fri Apr 23 17:31:29 1993 To: combinatorics(at-sign)math.mit.edu Subject: Cherednik, 4/28 Wednesday, April 28, 3:30 p.m.; MIT, room 2-338 ^^^^ (note unusual time of talk!) Ivan Cherednik (U.N.C. at Chapel Hill) The Macdonald constant term conjecture The talk will be about the general (with q) Macdonald constant term conjecture which was proved recently (for reduced root systems) by means of a new approach to the harmonic analysis on symmetric spaces based on the affine Hecke algebras. From propp(at-sign)math.mit.edu Fri Apr 23 18:04:12 1993 To: combinatorics(at-sign)math.mit.edu Subject: Gleason, 4/30 (yes, 4/30!) Correction: Friday, April 30, 4:15 p.m.; MIT, room 2-338 Andrew Gleason (Harvard) Hadamard matrices and the Matthieu groups Hadamard matrices offer a short route to the Matthieu groups M_12 and M_24. From propp(at-sign)math.mit.edu Fri Apr 30 13:26:33 1993 To: combinatorics(at-sign)math.mit.edu Subject: Discrete Mathematics Dinner This semester's Discrete Mathematics Dinner will be held at Taj India at 6 p.m. on May 19. Undergraduates will pay $9 a head and graduate students will pay $12 a head (beverages not included); the rest of us will make up the difference. In a week or two I will send out a second announcement and ask people who wish to attend to let me know, so that I can give the restaurant an estimate of how many people will be there. If you will be out of town in early May (e.g., if you are going to be attending the Jerusalem Combinatorics Conference), and you do plan to attend the dinner on the 19th, * please let me know now *. There will be no meetings of the MIT Combinatorics Seminar next week, but there will be five talks later in May. A complete schedule follows. Jim Propp From propp(at-sign)math.mit.edu Fri Apr 30 13:28:01 1993 To: combinatorics(at-sign)math.mit.edu Subject: Schedule for May M.I.T. COMBINATORICS SEMINAR There will be no meetings of the seminar until May 10. Here is a list of the last five talks in the MIT Combinatorics Seminar. * Monday, May 10: David Grabiner, ``Random walks and Lie groups'' * Wednesday, May 12: Larry Harper, ``Discrete isoperimetric problems and Steiner operations'' * Friday, May 14: Ira Gessel, ``Counting 2-stack-sortable multipermutations'' * Wednesday, May 19: Barbara Nostrand, ``Chiral polytopes from hyperbolic honeycombs'' * Wednesday, May 26: Paul Erdos, ``Some of my favorite combinatorial problems'' All talks will meet in room 2-338 at 4:15 p.m. From propp(at-sign)math.mit.edu Fri Apr 30 18:03:34 1993 To: combinatorics(at-sign)math.mit.edu Subject: Discrete Math Dinner It's been pointed out to me that April 19 is also the evening of a dinner being held in honor of Prof. Kostant, and that at least one of the local combinatorialists will not be able to attend for that reason. So I will retract my announcement and ask instead, how many people (among those who want to come to the Discrete Math Dinner) would be able to attend on the 19th but not on the 12th? And how many would be able to attend on the 12th but not on the 19th? I will let simple majority vote decide which of the two days is more suitable. Please reply by Wednesday, May 5. Jim Propp From propp(at-sign)math.mit.edu Fri Apr 30 18:55:46 1993 To: combinatorics(at-sign)math.mit.edu Subject: Discrete Math Dinner (correction) For "April", read "May" (in the preceding message). Jim Propp From propp(at-sign)math.mit.edu Tue May 4 19:57:05 1993 To: combinatorics(at-sign)math.mit.edu Subject: Grabiner, 5/10 Monday, May 10, 4:15 p.m.; MIT, room 2-338 David Grabiner (Harvard) Random walks and Lie groups The formula for the Catalan numbers is usually obtained by a reflection argument. We consider a class of random walks on a lattice, introduced by Gessel and Zeilberger, for which the same reflection principle can be used to count the number of k-step walks between two points which stay within a Weyl chamber. For many such ``reflectable'' walks, we compute determinant formulas for walk-numbers and their generating functions. We also show that many of these walk-numbers correspond to the multiplicities of irreducibles in the kth tensor power of certain Lie group representations associated to the walk-types, including the defining representations of the classical groups. This is joint work with Peter Magyar. From propp(at-sign)math.mit.edu Wed May 5 14:58:13 1993 To: combinatorics(at-sign)math.mit.edu Subject: Harper, 5/12 Wednesday, May 12, 4:15 p.m.; MIT, room 2-338 Larry Harper (U.N.C. at Chapel Hill) Discrete isoperimetric problems and Steiner operations Certain optimization problems on graphs are analagous to the isoperimetric problem of Greek geometry. Discrete (as well as continuous) isoperimetric theorems are notoriously difficult to prove, but we will show how a standard method, called compression, can be developed so as to give transparent proofs of many results. Compression, it turns out, is a discrete analog of Steiner symmetrization. From propp(at-sign)math.mit.edu Thu May 6 11:56:34 1993 To: combinatorics(at-sign)math.mit.edu Subject: Dinner This semester's Discrete Mathematics Dinner will be held at Taj India at 6 p.m. on May *12* (not 19, as previously announced). Undergraduates will pay $9 a head and graduate students will pay $12 a head (beverages not included); the rest of us will make up the difference. If you wish to attend, please let me know by next Tuesday, May 11, so that I can advise the restaurant how many people to expect. If you're not sure, submit your best estimate of the probability that you'll attend. A new talk is being scheduled for May; Serge Kerov will be speaking on May 28th. Further details will be posted when they become available. Jim Propp From propp(at-sign)math.mit.edu Thu May 6 11:58:05 1993 To: combinatorics(at-sign)math.mit.edu Subject: Gessel, 5/14 Friday, May 14, 4:15 p.m.; MIT, room 2-338 Ira Gessel (Brandeis) Counting 2-stack-sortable multipermutations Julian West conjectured that the number of permutations of {1,2,...,n} that can be reduced to the identity permutation by two applications of the ``stack-sorting'' operation is 2(3n)!/(n+1)!(2n+1)!. West's conjecture was proved by Doron Zeilberger. Zeilberger used a combinatorial decomposition to find a recurrence for counting West's permutations by an additional parameter. The recurrence is easily converted into a functional equation for a generating function, but unfortunately the functional equation is of a type that no one knows how to solve. Zeilberger guessed that the solution was algebraic and with 10 hours of computer time found empirically a polynomial equation that the generating function satisfied. He then verified that the solution of this polynomial equation did indeed satisfy the functional equation. I will describe a simplified version of Zeilberger's approach that does not require a computer, and that also yields a generalization of West's formula for certain multiset permutations. From propp(at-sign)math.mit.edu Mon May 10 14:16:05 1993 To: combinatorics(at-sign)math.mit.edu Subject: Discrete Mathematics Dinner The Taj India Restaurant (for those who won't be walking there together after Larry Harper's talk) is located at 781 Main Street in Cambridge, about 100 yards from Massachusetts Avenue (on the left side of Main Street if you're walking from Mass. Ave.). Remember to let me know by Tuesday if you want to attend the dinner. Jim From propp(at-sign)math.mit.edu Wed May 12 15:54:04 1993 To: combinatorics(at-sign)math.mit.edu Subject: Nostrand, 5/19 Wednesday, May 19, 4:15 p.m.; MIT, room 2-338 Barbara Nostrand (Northeastern) Chiral Polytopes from Hyperbolic Honeycombs Abstract-polytopes are partially ordered structures which generalize the notion of polyhedra in a combinatorial sense. This concept includes all of the classical regular polytopes as well as many well-known configurations. Chiral polytopes are abstract polytopes with rotational symmetry which lack reflexive symmetry. We use a technique developed by Schulte and Weiss which employs hyperbolic geometry to derive abstract polytopes with cells isomorphic to maps of type {6,3,4} and {6,3,5} to complete the classification of toroidal polytopes of rank 4 which can be realized by this construction. Of particular interest is a newly discovered flat polytope of type {6,3,4}. From propp(at-sign)math.mit.edu Wed May 19 18:44:08 1993 To: combinatorics(at-sign)math.mit.edu Subject: Erdos, 4/26 Wednesday, May 26, 4:15 p.m.; MIT, room 2-338 Paul Erdos (Hungarian Academy of Sciences) Some of my favorite combinatorial problems From propp(at-sign)math.mit.edu Mon May 24 10:55:27 1993 To: combinatorics(at-sign)math.mit.edu Subject: Kerov, 5/28 Friday, May 28, 4:15 p.m.; MIT, room 2-338 Serge Kerov (St. Petersburg University and the University of Iowa) Combinatorial problems in asymptotic representation theory Let the group G = union G_n be the union of a sequence of its finite or compact subgroups G_n . The infinite symmetric group S_infinity and the unitary group U(infinity) are important examples. Representation theory of such groups can be effectively studied in terms of the Bratteli diagram D = union D_n which is a countable ranked poset describing the restrictions of irreps of approximating groups. The main problem is to find factor - representations of G (irreducible representations are far less interesting). It reduces to that of counting the number of saturated chains for any interval in D . A number of examples related to Young lattice and to Young - Fibonacci lattice will be discussed in the talk. In particular, the remarkable Robinson - Schensted - Knuth algorithm and Hook Walk procedure arise in the character theory of the group S_infinity . From propp(at-sign)math.mit.edu Mon May 24 16:36:30 1993 To: combinatorics(at-sign)math.mit.edu Subject: Roby, 6/2 (added talk) Wednesday, June 2, 4:15 p.m.; MIT, room 2-338 Tom Roby (University of Tokyo) A two-dimensional pictorial presentation of Berele's insertion algorithm for symplectic tableaux The usual Robinson-Schensted correspondence gives a bijection from permutations of a certain alphabet to pairs of same-shape standard Young tableaux. A generalization of Schensted gives a bijection from permutations with repetitions to pairs of tableaux of the same shape, one column-strict, one standard. The latter may be viewed from the standpoint of representation theory as giving the decomposition of the action of the group GL(n) \times S(n) on the k-fold tensor power of the natural representation \otimes ^{k} \square_{GL(n)} . Berele's correspondence, originally conceived to explain a similar representation theoretic phenomenon for the symplectic group, gives a bijective map from the set of words on a certain alphabet of size 2n to pairs of tableaux, one ``symplectic'', the other ``up-down''. S.\ Fomin gave a two-dimensional pictorial presentation of the usual Robinson-Schensted correspondence. This presentation enhances the understanding of certain properties of R-S, and also allows it to be naturally generalized in a number of different ways. Our aim is to give a similar presentation of Berele's algorithm. The eventual goal (which has yet to be fully realized) is to explain more clearly the combinatorics of up-down tableaux. From propp(at-sign)math.mit.edu Mon May 24 18:43:44 1993 To: combinatorics(at-sign)math.mit.edu Subject: Erdos Paul Erdos will be in New England between now (Monday night) and his Wednesday afternoon talk. His itinerary has not been established yet, but I imagine there are a number of people reading this message who will want to see him while he's here. Contact me on Tuesday and I'll let you know where he'll be, when. From propp(at-sign)math.mit.edu Wed May 26 11:40:08 1993 To: combinatorics(at-sign)math.mit.edu Subject: Dinner After Prof. Erdos' lecture this afternoon, I will be taking him out to dinner (probably at Shilla, a Japanese/Korean restaurant in Harvard Square, but plans haven't been made final yet). Anyone who wants to join us is welcome to come along. From propp(at-sign)math.mit.edu Fri Jun 25 15:44:37 1993 To: combinatorics(at-sign)math.mit.edu Subject: Danzer, 7/7 Wednesday, July 7, 4:15 p.m.; MIT, room 2-338 Ludwig Danzer (University of Dortmund, Germany) How to define quasiperiodicity especially with respect to quasicrystals