From propp(at-sign)math.mit.edu Mon Aug 30 12:55:06 1993 To: combinatorics(at-sign)math.mit.edu Subject: MIT Combinatorics Seminar [It seems that mailer problems prevented this from getting circulated, so I'm trying once more. Apologies to those who have already received this message.] There are still many slots available for the coming semester; anyone who is interested in giving a talk (or who knows of someone who might be) should send me e-mail. Also, let me know if there are new faculty or grad students who should be put on the distribution list. Jim Propp (propp(at-sign)math.mit.edu) From propp(at-sign)math.mit.edu Thu Sep 2 11:57:45 1993 To: combinatorics(at-sign)math.mit.edu I've been asked to shift the Wednesday seminar so that it runs from 4:30 to 5:30 (instead of 4:15 to 5:15). *N.B.: The Fridays meetings would remain in the 4:15-5:15 slot.* Before I make a decision on this, I'd like to know whether anyone has strong feelings on the matter, one way or the other. Jim From grabiner(at-sign)math.harvard.edu Thu Sep 2 12:08:54 1993 To: propp(at-sign)math.mit.edu Reply-To: grabiner(at-sign)math.harvard.edu You write: > I've been asked to shift the Wednesday seminar so that it runs from 4:30 to 5:30 > (instead of 4:15 to 5:15). *N.B.: The Fridays meetings would remain in the > 4:15-5:15 slot.* Before I make a decision on this, I'd like to know whether > anyone has strong feelings on the matter, one way or the other. I don't care this semester, but I will have a slight preference for 4:15 next semester, since this is immediately after Kleitman's 3:00-4:00 seminar. It isn't that important. David Grabiner From rota(at-sign)math.mit.edu Thu Sep 2 19:00:23 1993 To: propp(at-sign)math.mit.edu I have no feelings on the matter, please let me know your decision. Best regards, Gian-Carlo. From ira(at-sign)cs.brandeis.edu Fri Sep 3 16:53:29 1993 To: propp(at-sign)math.mit.edu I don't have strong feelings either way. On the one hand, making the seminar later allows me to get more done here first. On the other hand, making it later means getting home later. But 15 minutes isn't a big deal either way. Ira From propp(at-sign)math.mit.edu Wed Sep 8 14:16:06 1993 To: combinatorics(at-sign)math.mit.edu This semester, the combinatorics seminar will meet from 4:15 to 5:15 on Wednesdays (as before), but on Fridays it will meet from 4:30 to 5:30. Jim Propp From propp(at-sign)math.mit.edu Wed Sep 8 14:17:48 1993 To: combinatorics(at-sign)math.mit.edu Subject: MIT Combinatorics Seminar: Correction Oops! I got that backwards. This semester, *Wednesday* meetings will be from 4:30 to 5:30; *Friday* meetings will continue to be held from 4:15 to 5:15. Sorry for the confusion! Jim Propp From propp(at-sign)math.mit.edu Wed Sep 8 14:18:21 1993 To: combinatorics(at-sign)math.mit.edu Subject: Krattenthaler, 9/15 Wednesday, September 15, 4:30 p.m.; MIT, room 2-338 (note new time!) ^^^^ Christian Krattenthaler (Vienna) The Major Counting of Nonintersecting Lattice Paths and Generating Functions for Tableaux We develop a theory of counting nonintersecting lattice paths by the major index and generalizations of it. As application we prove refinements of two theorems in plane partition theory, the Bender-Knuth and MacMahon (Ex-)Conjectures, respectively. From propp(at-sign)math.mit.edu Sat Sep 18 14:40:14 1993 To: combinatorics(at-sign)math.mit.edu Subject: Wild, 9/22 Wednesday, September 22, 4:30 p.m.; MIT, room 2-338 (note new time!) ^^^^ Marcel Wild (M.I.T.) An enumerative principle of exclusion Let M be a finite set and P a ``property'' enjoyed by some subsets X of M. With N(P) we denote the number of X in 2^M with property P. For any properties P_1,...,P_n let C=C(P_1,...,P_n) be the family of those X in 2^M which enjoy {\it all} properties P_i. According to the well known principle of "inclusion-exclusion" one has |C| = N(P_1 wedge ... wedge P_n) = sum_{1 <= i <= n} N(P_i) - sum_{1 <= i < j <= n} N(P_i vee P_j) + ... Unfortunately 2^n-1 many terms N(P_i vee P_j vee ... vee P_k) need to be added and substracted from each other on the righthand side. Moreover, sometimes there is no easy way to compute the terms themselves. We shall present an often better method for determining |C|, which is based on a principle of ``exclusion''. It is demonstrated for arbitrary _closure_systems_ C (which fit a lot of applications in Algebra and Combinatorics), but we believe that variations would apply to other counting problems as well. From propp(at-sign)math.mit.edu Sat Sep 18 15:12:32 1993 To: combinatorics(at-sign)math.mit.edu Subject: Stanley, 9/24 Friday, September 24, 4:15 p.m.; MIT, room 2-338 Richard Stanley (M.I.T.) A symmetric function generalization of the chromatic polynomial of a graph Let G be a finite graph. We will define a symmetric function X_G = X_G(x_1,x_2,...) which generalizes the chromatic polynomial of G. Classical results on chromatic polynomials dealing with Mobius functions and acyclic orientations can be extended to X_G. For certain graphs G, the expansion of X_G in terms of elementary symmetric functions is related to the theory of Hecke algebras and Kazhdan-Lusztig polynomials. From propp(at-sign)math.mit.edu Wed Sep 22 21:14:34 1993 To: combinatorics(at-sign)math.mit.edu Subject: MIT Combinatorics Seminar: time change One final change in this semester's schedule (hopefully the last): the Wednesday talks will start at 4:35, not 4:30. I hope this doesn't inconvenience anyone too much. Jim From propp(at-sign)math.mit.edu Wed Sep 22 21:59:45 1993 To: combinatorics(at-sign)math.mit.edu Subject: MIT Combinatorics Seminar The semester is filling up fast. Here's the current tentative schedule (a more detailed schedule will follow, once the question-marks get removed): Month W F 9: 15 Krattenthaler 17 9: 22 Wild 24 Stanley 9: 29 Arnold 1 Fishel 10: 6 Almkvist 8 Larose 10: 13 Goemans 15 Thomas 10: 20 Landau? 22 Collins 10: 27 29 Schulte 11: 3 Brenti 5 Reeves 11: 10 12 Okada? 11: 17 Hanlon 19 11: * * 11: 1 3 12: 8 10 12: 15 17 Those who are interested in speaking this semester should definitely contact me during the next week or two. Jim From propp(at-sign)math.mit.edu Thu Sep 23 11:47:09 1993 To: combinatorics(at-sign)math.mit.edu Subject: Arnold, 9/29 Wednesday, September 29, 4:35 p.m.; MIT, room 2-338 (note REALLY new time! ^^^^ ) Vladimir Arnold (Moscow) Euler, Bernoulli and Springer numbers of Coxeter groups and of Morsification spaces The classical sequence 1,1,1,2,5,16,61,272,1385,... occurs in many combinatorial problems. It has recently been discovered that the same sequence governs the topological classification of Morsifications of simplest degenerate critical points of smooth functions. This observation leads to the generalizations of the Euler and tangent numbers which can be associated with any simple Lie algebra or even to any Coxeter group. This gives new information even in the classical case (corresponding to the sl(n) algebras and to the symmetries of simplices), for instance new congruences for the classical Euler and Bernoulli numbers, generalising those found by Kummer, von Staudt and Knuth. From propp(at-sign)math.mit.edu Thu Sep 23 11:47:32 1993 To: combinatorics(at-sign)math.mit.edu Subject: Fishel, 10/1 Friday, October 1, 4:15 p.m.; MIT, room 2-338 Susanna Fishel (Southern Connecticut State) The combinatorics of certain entries in the two-parameter Kostka matrix Kirillov and Reshetikhin introduced rigged configurations as a new way to calculate the entries K_{\lambda\mu}(t) of the Kostka matrix. Macdonald defined the two-parameter Kostka matrix whose entries K_{\lambda\mu}(q,t) generalize K_{\lambda\mu}(t) . I use rigged configurations and a formula of Stembridge to provide a combinatorial interpretation of K_{\lambda\mu}(q,t) in the case where \mu is a partition with no more than two columns. In particular, I show that in this case, K_{\lambda\mu}(q,t) has nonnegative coefficients. From yuzvinsk(at-sign)math.wisc.edu Sat Sep 25 18:52:28 1993 Subject: accomodations To: combinatorics(at-sign)math.mit.edu X-Mailer: ELM [version 2.4 PL21] Content-Type: text Content-Length: 343 Dear Colleague, I am going to visit the Boston area for about two months in January - February with Tony Iarrobino (NEU) as the principal host. If you know any available accomodation for 2 adults and a 13-year old for this period please let me know. A decent high school in the area is important. TIA, Sergey Yuzvinsky (yuz(at-sign)math.uoregon.edu) From SCHULTE(at-sign)neu.edu Tue Sep 28 15:11:11 1993 Subject: Northeastern Combinatorics Seminar To: combinatorics(at-sign)math.mit.edu X-Envelope-To: combinatorics(at-sign)math.mit.edu X-Vms-To: IN%"combinatorics(at-sign)math.mit.edu" Mime-Version: 1.0 Content-Transfer-Encoding: 7BIT COMBINATORICS SEMINAR NORTHEASTERN UNIVERSITY Schedule for Fall 1993 ______________________________ The seminars are usually Wednesday at 1:30 p.m. in 509 Lake Hall. Sept. 22 Roy Meshulam, Technion, Haifa On subsets of abelian groups with no 3-term arithmetic progression Any questions? Call 373-5511. From SCHULTE(at-sign)neu.edu Tue Sep 28 15:11:40 1993 Subject: Northeastern Combinatorics Seminar To: combinatorics(at-sign)math.mit.edu X-Envelope-To: combinatorics(at-sign)math.mit.edu X-Vms-To: IN%"combinatorics(at-sign)math.mit.edu" Mime-Version: 1.0 Content-Transfer-Encoding: 7BIT COMBINATORICS SEMINAR NORTHEASTERN UNIVERSITY Schedule for Fall 1993 ______________________________ The seminars are usually Wednesday at 1:30 p.m. in 509 Lake Hall. Sept. 29 Vladimir Retakh (visiting Harvard) Non-commutative determinants and their combinatorics Oct. 6 Klaus Altmann (M.I.T.) Deformation theory of toric varieties Any questions? Call 373-5511. From SCHULTE(at-sign)neu.edu Tue Sep 28 15:11:45 1993 Subject: Northeastern Combinatorics Seminar To: combinatorics(at-sign)math.mit.edu X-Envelope-To: combinatorics(at-sign)math.mit.edu X-Vms-To: IN%"combinatorics(at-sign)math.mit.edu" Mime-Version: 1.0 Content-Transfer-Encoding: 7BIT COMBINATORICS SEMINAR NORTHEASTERN UNIVERSITY Schedule for Fall 1993 ______________________________ The seminars are usually Wednesday at 1:30 p.m. in 509 Lake Hall. Sept. 29 Vladimir Retakh (visiting Harvard) Non-commutative determinants and their combinatorics Oct. 6 Klaus Altmann (M.I.T.) Deformation theory of toric varieties Any questions? Call 373-5511. From SCHULTE(at-sign)neu.edu Tue Sep 28 15:18:56 1993 Subject: Northeastern Combinatorics Seminar To: combinatorics(at-sign)math.mit.edu X-Envelope-To: combinatorics(at-sign)math.mit.edu X-Vms-To: IN%"combinatorics(at-sign)math.mit.edu" Mime-Version: 1.0 Content-Transfer-Encoding: 7BIT COMBINATORICS SEMINAR NORTHEASTERN UNIVERSITY Schedule for Fall 1993 ______________________________ The seminars are usually Wednesday at 1:30 p.m. in 509 Lake Hall. Sept. 29 Vladimir Retakh (visiting Harvard) Non-commutative determinants and their combinatorics Oct. 6 Klaus Altmann (M.I.T.) Deformation theory of toric varieties Any questions? Call 373-5511. From propp(at-sign)math.mit.edu Wed Sep 29 16:11:41 1993 To: combinatorics(at-sign)math.mit.edu Subject: Almkvist, 10/6 Wednesday, October 6, 4:35 p.m.; MIT, room 2-338 Gert Almkvist (KTH) (Title not yet known) (Abstract not yet available) From propp(at-sign)math.mit.edu Wed Sep 29 16:18:03 1993 To: combinatorics(at-sign)math.mit.edu Subject: Larose, 10/8 Friday, October 8, 4:15 p.m.; MIT, room 2-338 Benoit Larose (Universite de Montreal) Products of finite posets and the fixed point property If P and Q are finite posets with the fixed point property, does the product PxQ also have this property? In 1985, E. Corominas introduced the notion of "projective" (idempotent trivial) poset to attack this problem: the fixed point property is preserved under products if the so-called "minimal automorphic" posets are projective. We prove that the projection property is equivalent to quasiprojectivity (tightness) for posets of arbitrary cardinality; universal algebraic methods can then be used to determine if a poset is projective. We relate Corominas' conjecture to the notion of representability by irreducibles in varieties of ordered sets. From propp(at-sign)math.mit.edu Wed Sep 29 21:37:52 1993 To: combinatorics(at-sign)math.mit.edu Subject: Almkvist, 10/6 (more info now available) Wednesday, October 6, 4:35 p.m.; MIT, room 2-338 Gert Almkvist (KTH) From plane partitions to Fermat's last theorem: some excerpts from the notebook of a Maple-user Attempting to find "exact" asymptotic formulas for the number of plane partitions various byproducts are obtained: generalized Dedekind sums, values of Bernoulli polynomials at rational points. Wilf's conjecture is proved. From propp(at-sign)math.mit.edu Fri Oct 1 21:09:52 1993 To: combinatorics(at-sign)math.mit.edu Subject: Combinatorics Seminar: on-line preprints People who speak in the seminar are invited to send me electronic preprints, which I will keep in the publically-readable directory ~propp/public. (Subscribers to this mailing list who do not have accounts on the MIT math department machines cannot obtain these via anonymous ftp, but I will be happy to e-mail a preprint to anyone who asks me.) Jim From propp(at-sign)math.mit.edu Tue Oct 5 08:53:07 1993 To: combinatorics(at-sign)math.mit.edu Subject: Combinatorics Seminar: October Schedule COMBINATORICS SEMINAR Here is a list of all talks currently scheduled for the month of October. Friday, October 1, 4:15 p.m.: Susanna Fishel, The combinatorics of certain entries in the two-parameter Kostka matrix Wednesday, October 6, 4:35 p.m.: Gert Almkvist, From plane partitions to Fermat's last theorem: some excerpts from the notebook of a Maple-user Friday, October 8, 4:15 p.m.: Benoit Larose, Products of finite posets and the fixed point property Wednesday, October 13, 4:35 p.m.: Michel Goemans, Minimizing submodular functions over families of sets Friday, October 15, 4:15 p.m.: Rekha Thomas, Grobner basis methods for integer programming Wednesday, October 20, 4:35 p.m.: Susan Landau, Embedding linkages on an integer lattice Friday, October 22, 4:15 p.m.: Karen Collins, Chromatic difference sequences Wednesday, October 27, 4:35 p.m.: Luis Verde-Star, Solution of linear matrix difference and differential equations by operator methods Friday, October 29, 4:15 p.m.: Egon Schulte, Toroidal regular polytopes and their groups All talks will meet in room 2-338. From propp(at-sign)math.mit.edu Tue Oct 12 14:34:38 1993 To: combinatorics(at-sign)math.mit.edu Subject: Goemans, 10/13 Wednesday, October 13, 4:35 p.m.; MIT, room 2-338 Michel Goemans (M.I.T.) Minimizing submodular functions over families of sets Submodular set-functions arise in a variety of fields, including combinatorics, probability and geometry. Classical examples include the rank function of a matroid, the cuts in a directed or undirected graph, the probability that a subset of events do not simultaneously occur, or the logarithm of the volume of the parallelepiped spanned by a subset of linearly independent vectors. We consider the problem of characterizing the minimum of a submodular function when the minimization is restricted to a family of subsets. We show that, for many interesting families, the problem can be reduced to a sequence of submodular function minimizations over all subsets. Our results apply, for example, to the families of odd cardinality subsets or even cardinality subsets, leading to a characterization of the minimum even cut in a graph. These results generalize and unify many classical results in combinatorial optimization. This is joint work with V.S. Ramakrishnan. From propp(at-sign)math.mit.edu Tue Oct 12 15:26:46 1993 To: combinatorics(at-sign)math.mit.edu Subject: Thomas, 10/15 Friday, October 15, 4:15 p.m.; MIT, room 2-338 Rekha Thomas (Cornell) Grobner basis methods for integer programming Consider the family of integer programs of the form Min cx : Ax = b, x in N^n obtained by varying the right hand side vector b but keeping A and c fixed. We describe a unique minimal test set for this family, called the reduced Grobner basis. Algebraically, this test set arises as the reduced Grobner basis of the toric ideal associated with A. We present a combinatorial version of Buchberger's Grobner basis algorithm for this class of problems. As a special case we discuss the perfect f-matching problem on the complete graph K_n. An explicit description is given of test sets for all graphs with eight vertices or less. We briefly indicate the role of the above test sets in studying triangulations of the second hypersimplex, that is, the convex hull of columns of the vertex-edge incidence matrix of K_n. From propp(at-sign)math.mit.edu Thu Oct 14 12:41:50 1993 To: combinatorics(at-sign)math.mit.edu Subject: Landau, 10/20 Wednesday, October 20, 4:35 p.m.; MIT, room 2-338 Susan Landau (U. Mass. Amherst) Embedding linkages on an integer lattice Using links and joints, one can build an "erector set" type linkage in which angles are free to change, but lengths and collinearity properties are fixed. A problem in computer-aided design raised the question of when such a linkage can be embedded in an integer lattice, assuming one is allowed to shift lengths by epsilon, but collinearity properties must be preserved. What is the minimal epsilon that will allow an embedding where each of the edges has its endpoints on integer vertices in the lattice? We show here that the question of whether a linkage can be embedded on the integer lattice is NP-complete, an unhappy situation. But all is not lost: for applications, it is quite reasonable to assume that lengths are bounded, as are the number of "co-incident" polygons. With these caveats, we show there is a polynomial time solution to the problem. We note that the problem has some nice ties to number theory: the linkage can be embedded only if each of its links can, and this can happen if and only if each of the links has a length whose square can be written as the sum of two squares. We explore these connections further in the paper. From propp(at-sign)math.mit.edu Thu Oct 14 12:52:34 1993 To: combinatorics(at-sign)math.mit.edu Subject: Collins, 10/22 Friday, October 22, 4:15 p.m.; MIT, room 2-338 Karen Collins (Wesleyan) Chromatic difference sequences Define G to be stable if the normalized chromatic difference sequence of G is equal to the normalized chromatic difference sequence of G times G, the Cartesian product of G with itself. Zhou has shown that circulants and Cayley graphs are stable. The chromatic difference sequence of a stable graph G begins with omega terms equal to alpha where omega is the clique number and alpha is the independence number of the graph. If G contains partitionable graph H with the same clique size, then the omega+1st term is at least alpha(G)/alpha(H). For stable graphs of large odd girth, this gives upper bounds on the independence ratio of the graph which agree with previously known lower bounds. We also prove nice bounds on the independence ratios of circulants. From propp(at-sign)math.mit.edu Mon Oct 18 18:18:39 1993 To: combinatorics(at-sign)math.mit.edu Subject: Discrete Mathematics Dinner I propose that this semester's Discrete Dinner be held at Sol Azteca in Boston on Wednesday, November 10. The cost would be about $20 per person (not counting drinks). I suggest that graduate students could pay $15 a head (excluding drinks) and the rest of us would pick up the difference. Comments on this suggestion are welcome from all. Jim From propp(at-sign)math.mit.edu Mon Oct 25 19:24:57 1993 To: combinatorics(at-sign)math.mit.edu Subject: Combinatorics Seminar: November Schedule COMBINATORICS SEMINAR Here is a list of all talks currently scheduled for the month of November. Wednesday, November 3, 4:35 p.m.: Francesco Brenti, Some combinatorial properties of Kazhdan-Lusztig polynomials Friday, November 5, 4:15 p.m.: Alyson Reeves, On the radius of the Hilbert scheme Wednesday, November 10, 4:35 p.m.: Soichi Okada, Algebraic structures associated to the Young-Fibonacci lattice Friday, November 12, 4:15 p.m.: Margaret Readdy, Extremal problems for the Mobius function Wednesday, November 17, 4:35 p.m.: Phil Hanlon, Partitions with restricted block size, Lie k-algebras and the Lie(k) operad Friday, November 19, 4:15 p.m.: Laurent Habsieger, Lower bounds for q-ary coverings by spheres of radius one All talks will meet in room 2-338. From propp(at-sign)math.mit.edu Mon Oct 25 19:34:19 1993 To: combinatorics(at-sign)math.mit.edu Subject: Discrete Dinner This semester's Discrete Dinner will be held at Sol Azteca (one of the best Mexican restaurants in Boston) on Wednesday, November 10. The cost will be about $20 per person (not counting drinks). Graduate students will pay $15 a head (excluding drinks) and the rest of us will pick up the difference (aside from drinks). I need to give the restaurant a preliminary estimate of the number of people in our party, so if there's a positive probability that you'll attend, please let me know what this probability is sometime this week. I will give the restaurant the sum of these probabilities as my estimate for the size of our group. Jim Propp From propp(at-sign)math.mit.edu Wed Oct 27 16:56:59 1993 To: combinatorics(at-sign)math.mit.edu The following talk may be of interest to you. APPLIED MATHEMATICS COLLOQUIUM MONDAY, November 1, 1993, 4:15 p.m., Room 2-105 TRIANGULATIONS Professor C. Itzykson Service de Physique Theorique, Saclay, France and Department of Physics, MIT Abstract: Finite cell decompositions of surfaces (or ``fat graphs'') appear in the perturbative expansion of matrix models. The latter yield tau-functions for discrete or continuous integrable systems. Suitable specializations solve combinatorial problems on the moduli space of algebraic curves of given genus such as virtual characteristic (Harer, Zagier, Penner) or intersection numbers of stable characteristic classes (Witten, Kontsevich). The same data record unramified arithmetic coverings of P_1/{0,1,infinity}. This gives an action of Gal(Qbar / Q) on fat graphs (Belyi, Grothendieck, Voevodsky, Shabat). We shall attempt to give an overview of the (few) results and (many) open problems in this area. Refreshments will be served from 3:45 p.m. in Room 2-349 DEPARTMENT OF MATHEMATICS MASSACHUSETTS INSTITUTE OF TECHNOLOGY CAMBRIDGE, MASSACHUSETTS 02139 From MAILER-DAEMON(at-sign)math.mit.edu Wed Oct 27 19:44:54 1993 Subject: Returned mail: Cannot send message for 2 days To: <propp(at-sign)math.mit.edu> ----- Transcript of session follows ----- 421 iris1.math.nctu.edu.tw: Host iris1.math.nctu.edu.tw is down
Date: Mon, 25 Oct 93 19:13:00 EDT From: propp(at-sign)math.mit.edu To: GRADSTU(at-sign)math.mit.edu Subject: Discrete Mathematics Dinner
This semester's Discrete Dinner will be held at Sol Azteca (one of the best Mexican restaurants in Boston) on Wednesday, November 10. The cost will be about $20 per person (not counting drinks). Graduate students will pay $15 a head (excluding drinks) and the rest of us will pick up the difference (aside from drinks). I need to give the restaurant a preliminary estimate of the number of people in our party, so if there's a positive probability that you'll attend, please let me know what this probability is sometime this week. I will give the restaurant the sum of these probabilities as my estimate for the size of our group. Jim Propp From propp(at-sign)math.mit.edu Thu Oct 28 14:49:06 1993 To: combinatorics(at-sign)math.mit.edu Subject: preprint Karen Collins' article "Chromatic Difference Sequences" is now available on-line as ~propp/public/chromatic.tex. From propp(at-sign)math.mit.edu Mon Nov 1 13:30:27 1993 To: combinatorics(at-sign)math.mit.edu Subject: Reeves, 11/5 Friday, November 5, 4:15 p.m.; MIT, room 2-338 Alyson Reeves (Brandeis) On the radius of the Hilbert scheme Though the Hilbert scheme parametrizing subschemes of projective n-space has been the object of much investigation, its structure remains largely a mystery. This talk will combine elements from combinatorics, Grobner basis theory, and algebraic geometry to bound the component-wise radius of the Hilbert Scheme. From propp(at-sign)math.mit.edu Mon Nov 1 13:31:05 1993 To: combinatorics(at-sign)math.mit.edu Subject: Brenti, 11/3 Wednesday, November 3, 4:35 p.m.; MIT, room 2-338 Francesco Brenti (Universita di Perugia) Some combinatorial properties of Kazhdan-Lusztig polynomials Our aim in this talk is to give a simple, nonrecursive, combinatorial formula for any Kazhdan-Lusztig polynomial of any Coxeter group W, and to study some consequences of it. The main idea involved in the proof and statement of this formula is that of extending the concept of the R-polynomial to any (finite) multichain of W (so that, for multichains of length 1, one obtains, apart from sign, the usual R-polynomials). Our main result expresses the Kazhdan-Lusztig polynomial of any Bruhat interval as the sum of the R-polynomials of its multichains. We then use our main result to obtain combinatorial formulas for each coefficient of any Kazhdan-Lusztig polynomial. We use one of the special cases to characterize in purely combinatorial terms those Bruhat intervals whose Kazhdan-Lusztig polynomial equals the g-polynomial (as defined by R. Stanley) of the dual interval. As a consequence of it we obtain explicit formulas for the Kazhdan-Lusztig polynomials of intervals which are lattices. We also use our main result to obtain upper and lower bounds for the coefficients of Kazhdan-Lusztig polynomials. In particular, we verify a conjecture of Lascoux- Schutzenberger for all sufficiently long intervals. Finally, we briefly sketch how it is possible to obtain analogues of all the results in the talk for inverse Kazhdan-Lusztig polynomials. From propp(at-sign)math.mit.edu Mon Nov 8 13:36:27 1993 To: combinatorics(at-sign)math.mit.edu Subject: Dinner this Wednesday This semester's Discrete Dinner will be held at Sol Azteca (one of the best Mexican restaurants in Boston) on Wednesday, November 10. I have told the restaurant to expect us at 6:15. Given Boston traffic and Boston parking, people should leave MIT at 5:45 in order to arrive on time. The adddress is 914A Beacon Street, in Boston; as you drive on Beacon away from Boston, the restaurant is on the right, a block or two before Brookline begins. We will be ordering and paying for dinners individually; graduate students will get a 20% discount (the cost of which will be shared by the rest of us). Jim Propp From propp(at-sign)math.mit.edu Mon Nov 8 16:16:01 1993 To: combinatorics(at-sign)math.mit.edu Subject: Getting to Sol Azteca For those of you who will be coming to the restaurant by T: Take the Red Line to Park Street in Boston. Then take the Green Line (C branch) to St. Mary's Street, the first above-ground stop. Cross the street and start walking back towards Boston. The restaurant will be half a block down Beacon on the left side (number 914). Jim Propp From propp(at-sign)math.mit.edu Mon Nov 8 18:58:03 1993 To: combinatorics(at-sign)math.mit.edu Subject: Okada, 11/10 Wednesday, November 10, 4:35 p.m.; MIT, room 2-338 Soichi Okada (Nagoya) Algebraic structures associated to the Young-Fibonacci lattice The Young-Fibonacci lattice is an interesting example of a differential poset, of which another fundamental example is Young's lattice of partitions ordered by inclusion of Young diagrams. With Young's lattice are naturally associated the symmetric groups and the ring of symmetric functions. In this talk, I construct a Young-Fibonacci analogue of (1) the group algebra of the symmetric group, (2) the ring of symmetric functions, and (3) the character ring of the symmetric group. From propp(at-sign)math.mit.edu Mon Nov 8 19:24:21 1993 To: combinatorics(at-sign)math.mit.edu Subject: Readdy, 11/12 Friday, November 12, 4:15 p.m.; MIT, room 2-338 Margaret Readdy (LACIM, Montreal) Extremal problems for the Mobius function In the vein of recent work of Sagan, Yeh and Ziegler, we study extremal problems connected with the Mobius function of three families of subsets from O_n, the lattice of faces of the n-dimensional octahedron: lower order ideals, intervals of rank-selections, and arbitrary rank-selections. In each case, we illustrate the techniques used to determine the extremal configurations. Also, we briefly describe other results and present/future research. From propp(at-sign)math.mit.edu Fri Nov 12 10:40:35 1993 To: combinatorics(at-sign)math.mit.edu Subject: Hanlon, 11/17 Wednesday, November 17, 4:35 p.m.; MIT, room 2-338 Phil Hanlon (Michigan) Partitions with restricted block size, Lie k-algebras and the Lie(k) operad In this lecture we will combine three very different bodies of recent work, one combinatorial and two algebraic. The first is the study of the posets of partitions where every block size is congruent to 1 mod k+1. The second is the study of certain algebraic structures called Lie k-algebras and Liebnitz k-algebras. The third is the theory of Koszul duality for operads. Although we will not assume any background knowledge in these subject areas we will try to give enough of an idea about them to demonstrate some of their close connections. From propp(at-sign)math.mit.edu Fri Nov 12 11:03:28 1993 To: combinatorics(at-sign)math.mit.edu Subject: Habsieger, 11/19 Friday, Nov. 19, 4:15 p.m.; MIT, room 2-338 Laurent Habsieger (Bordeaux and UQAM) Lower bounds for q-ary coverings by spheres of radius one Let C be a q-ary covering code with covering radius one. We give lower and upper bounds for the number of elements of C that lie in a fixed subspace of {0,...,q-1}^n. These inequalities lead to lower bounds for the cardinality of C that improve on the sphere covering bound. More precisely we show that, if (q-1)n+1 does not divide q^n and if (q,n) is not in {(2,2),(2,4)}, the sphere covering bound is never reached. This enables us to characterize the cases where the sphere covering bound is attained, when q is a prime power. We also present some improvements of the already known lower bounds for binary and ternary codes. From propp(at-sign)math.mit.edu Mon Nov 22 16:25:09 1993 To: combinatorics(at-sign)math.mit.edu Subject: Terada, 12/1 Wednesday, December 1, 4:35 p.m.; MIT, room 2-338 Itaru Terada (University of Tokyo and M.I.T.) An identity generalizing the length-MAJ symmetry and the variety of N-stable flags D. Foata and M.-P. Schutzenberger showed that the number of permutations in S_n with length i and major index j is equal to the number of those with length j and major index i. The two-variable generating function of this distribution is expressed as a sum of K_{lambda,(1^n)}(q) . K_{lambda,(1^n)}(t) for all partitions lambda of n. Generalizing this identity, we give a combinatorial interpretation of the sum of K_{lambda,mu}(q) . K_{lambda,(1^n)}(t), for any fixed partition mu of n. This interpretation is different from that in terms of Lascoux-Schutzenberger's charge and the major index. In showing the generalized identity, we look at the variety of flags in C^n that are stable under a nilpotent matrix N. We note that Staltenstein's partition of this variety into affine spaces is explicitly achieved by taking the N-stable parts of Schubert cells. From propp(at-sign)math.mit.edu Mon Nov 22 16:25:22 1993 To: combinatorics(at-sign)math.mit.edu Subject: Combinatorics Seminar: December Schedule COMBINATORICS SEMINAR Here is a list of all talks currently scheduled for the month of December. Wednesday, December 1, 4:35 p.m.: Itaru Terada, An identity generalizing the length-MAJ symmetry and the variety of N-stable flags Friday, December 3, 4:15 p.m.: Sergey Fomin, Lattice paths, braids, and reduced decompositions Wednesday, December 8, 4:35 p.m.: Andrei Zelevinsky, title to be announced Friday, December 10, 4:15 p.m.: Mark McConnell, Convex polytopes and intersection cohomology of toric varieties All talks, as usual, will meet in room 2-338. I have already begun to schedule talks for next semester, so if you're interested in speaking, let me know. From propp(at-sign)math.mit.edu Tue Nov 23 16:30:30 1993 To: combinatorics(at-sign)math.mit.edu Subject: Sturmfels, 12/2 The following talk (not part of the MIT Combinatorics Seminar) may be of interest to local combinatorialists: The talk, "Applications of Toric Ideals", by Bernd Sturmfels, will be in the Brandeis-Harvard-MIT colloquium at 4:30, in Goldsmith Rm 317, at Brandeis, on Thursday December 2. Tea is a 4:00. There will be a dinner afterwards. From propp(at-sign)math.mit.edu Tue Nov 23 18:58:11 1993 To: combinatorics(at-sign)math.mit.edu Subject: Combinatorics Seminar: December Schedule (updated) COMBINATORICS SEMINAR Here is a list of all talks currently scheduled for the month of December. Wednesday, December 1, 4:35 p.m.: Itaru Terada, An identity generalizing the length-MAJ symmetry and the variety of N-stable flags Friday, December 3, 4:15 p.m.: Sergey Fomin, Lattice paths, braids, and reduced decompositions Wednesday, December 8, 4:35 p.m.: Andrei Zelevinsky, A piecewise-linear involution arising in representation theory Friday, December 10, 4:15 p.m.: Mark McConnell, Convex polytopes and intersection cohomology of toric varieties All talks, as usual, will meet in room 2-338. From propp(at-sign)math.mit.edu Mon Nov 29 15:47:24 1993 To: combinatorics(at-sign)math.mit.edu Subject: Terada, 12/1 Wednesday, December 1, 4:35 p.m.; MIT, room 2-338 Itaru Terada (University of Tokyo and M.I.T.) An identity generalizing the length-MAJ symmetry and the variety of N-stable flags D. Foata and M.-P. Schutzenberger showed that the number of permutations in S_n with length i and major index j is equal to the number of those with length j and major index i. The two-variable generating function of this distribution is expressed as a sum of K_{lambda,(1^n)}(q) . K_{lambda,(1^n)}(t) for all partitions lambda of n. Generalizing this identity, we give a combinatorial interpretation of the sum of K_{lambda,mu}(q) . K_{lambda,(1^n)}(t), for any fixed partition mu of n. This interpretation is different from that in terms of Lascoux-Schutzenberger's charge and the major index. In showing the generalized identity, we look at the variety of flags in C^n that are stable under a nilpotent matrix N. We note that Staltenstein's partition of this variety into affine spaces is explicitly achieved by taking the N-stable parts of Schubert cells. From propp(at-sign)math.mit.edu Mon Nov 29 16:34:49 1993 To: combinatorics(at-sign)math.mit.edu Subject: Fomin, 12/3 Friday, December 3, 4:15 p.m.; MIT, room 2-338 Sergey Fomin (M.I.T.) Lattice paths, braids, and reduced decompositions Recently, a combinatorial interpretation of stable Schubert polynomials in terms of braid configurations was found, based on a well-known geometric interpretation of the Yang-Baxter equation. In the particular case of 321-avoiding permutations, these polynomials are the skew Schur functions. Each of corresponding braid configurations breaks up into two families of paths which are exactly the Gessel-Viennot paths for the two Jacobi-Trudi determinants. An alternative description of this construction relates skew Schur functions to reduced decompositions in the Temperley-Lieb algebra. Generalizations and applications include super-Schur functions, binomial determinants, and the $P$- and $Q$-Schur functions. This is a joint work with X. G. Viennot. From propp(at-sign)math.mit.edu Wed Dec 1 13:33:18 1993 To: combinatorics(at-sign)math.mit.edu Subject: Zelevinsky talk cancelled CANCELLATION! Andrei Zelevinsky's talk (originally scheduled for Wednesday, December 8) has been cancelled, on account of a conflict with the MIT math department's holiday party, which has been scheduled at the last minute for the same afternoon. My apologies to all. Prof. Zelevinsky will give a lecture on his originally-announced topic ("A piecewise-linear involution arising in representation theory") in February. From propp(at-sign)math.mit.edu Fri Dec 3 18:00:53 1993 To: combinatorics(at-sign)math.mit.edu Subject: McConnell, 12/10 Friday, December 10, 4:15 p.m.; MIT, room 2-338 Mark McConnell (M.I.T.) Convex polytopes and intersection cohomology of toric varieties McMullen's conjecture characterized the f-vectors of simplicial convex polytopes Delta. Stanley's proof of (one direction of) this conjecture used the cohomology H^*(X, C) of the toric variety X associated to Delta. Let omega in H^2(X, C) be the Lefschetz hyperplane class. Key facts for Stanley's proof were that the quotient H^*(X, C)/(omega) is a graded ring generated by H^2. When Delta is an arbitrary rational convex polytope, one can ask about the analogues in intersection cohomology: is IH^*(X, C)/(omega) a ring, and is it generated by IH^2 ? I will discuss preliminary results on these questions, as well as approaches for computing the intersection cohomology.