From propp(at-sign)math.mit.edu Tue Jan 17 17:40:40 1995 To: combinatorics(at-sign)math.mit.edu Subject: Combinatorics and Graph Theory day at Smith Posted on behalf of Karen Collins: Come to the fourteenth one day conference on Combinatorics and Graph Theory Saturday, February 18, 1994 10 a.m. to 4:30 p.m. at Smith College Northampton MA 01063 Schedule 10:00 Neil Calkin Random Birthdays, Random Walks and Random Vectors 11:10 Nate Dean Interactive and Incomprehensible Graphs 12:10 Lunch 2:00 Kathleen Romanik A Three Dimensional Visibility Representation for Graphs 3:10 Jay Goldman Knots, Tangles, and Electrical Networks Directions to Burton Hall, Smith College (Updated 8/3/94) 1. Take I-91 to exit 18. Make a left off the ramp. 2. You are now on Pleasant Street (Rte. 5) heading towards Northampton Center. Go about 1 mile to the first light. 3. Make a left here onto Main Street (Rte. 9). 4. Go to the second light and make a left onto West Street (Rte. 66). 5. Make the next right onto Green Street. 6. Take the second right into the parking lot. This will lead you into the Dickenson parking lot. You can park here. If this lot is full, go back onto Green Street the same way you were going until the road forks at College Lane. Turn left down the hill. The Ainsworth Gym parking lot entrance is the second left. 7. To get to Burton from the Dickenson lot, walk back out to Green Street and continue down it to the end. Make a right onto College Lane. To get to Burton from the Ainsworth lot, walk up the hill along College Lane and enter Burton from the courtyard area, see 8 below. 8. Burton is the third building on your right. Just before Burton is a small courtyard area with a skyway between buildings. Enter Burton from this courtyard area. The only door open on Saturday is the first one you will come to (it has a handicap accessible ramp). 9. Enter the building and go straight until you see a circular stairway on your right. Take the stairway (or elevator in the middle of it) to the third floor of Burton (not Sabin Reed). (If you take the elevator this will mean that you exit on the opposite side than you entered.) Once on the third floor go left to the Math forum area. We have received an NSF grant to support these conferences. This will allow us to provide a modest transportation allowance to those attendees who are not local. For more information contact: Mike Albertson (Smith College), (413) 585-3865, albertson(at-sign)smith.smith.edu Karen Collins (Wesleyan Univ.), (203) 685-2169, kcollins(at-sign)eagle.wesleyan.edu Ruth Haas (Smith College), (413) 585-3872, rhaas(at-sign)smith.smith.edu From propp(at-sign)math.mit.edu Sun Jan 29 19:55:41 1995 To: combinatorics(at-sign)math.mit.edu Subject: MIT Combinatorics: February schedule MIT COMBINATORICS SEMINAR Here is the current list of talks scheduled for the month of February. Wednesday, February 8, 4:15 p.m.: Christos Athanasiadis, Spectra of graphs and the branching operation Friday, February 10, 4:15 p.m.: Dan Ullman, Multicolorings of graphs Wednesday, February 15, 4:15 p.m.: Michael Albertson, The normalized chromatic difference sequence of a graph Friday, February 17, 4:15 p.m.: Julian West, Recent forbidden-subsequenciana Wednesday, February 22, 4:15 p.m.: David Wagner, Toric varieties associated with finite distributive lattices All talks will meet in room 2-338. From propp(at-sign)math.mit.edu Wed Feb 1 19:34:22 1995 To: combinatorics(at-sign)math.mit.edu Subject: Athanasiadis, 2/8 (at 4:30 p.m.) Wednesday, February 8, 4:30 p.m.; MIT, room 2-338 ^^^^ (note changed starting time!) Christos Athanasiadis (M.I.T) Spectra of graphs and the branching operation The "branching" operation, defined by J. Propp, assigns to a given digraph G another digraph D(G), whose vertices are the oriented spanning rooted trees of G. Using an elementary counting argument, we describe explicitly the adjacency eigenvalues of D(G) in terms of the adjacency eigenvalues of the induced subgraphs and the Laplacian of G. A conjecture of Propp follows as a special case. We also attempt a brief introduction to the theory of spectra of graphs. Please note that the starting time for this lecture has been changed from the time originally announced. From propp(at-sign)math.mit.edu Thu Feb 2 12:01:50 1995 To: combinatorics(at-sign)math.mit.edu Subject: Talk by Michel Brion The following talk may be of interest to subscribers to this list: Harvard-Brandeis-MIT-Northeastern Colloquium at Northeastern U, Feb. 9 Michel Brion (U. Grenoble) "Convex Polytopes, Piecewise Polynomial Functions, and Enumerative Geometry" 4:30 PM at 200 Richards Hall, Thursday Feb. 9 (Tea at 4 PM, Churchill Hall Faculty Dining Room) Abstract: The talk will be about recent results of McMullen concerning the polytope algebra, and of Morelli, Fulton, Sturmfels, and others concerning its connections with the Chow rings of toric varieties. For further info or directions, see posted announcements, or phone (617)-373-2450, e-mail iarrobin(at-sign)neu.edu. Parking vouchers available. From propp(at-sign)math.mit.edu Mon Feb 6 15:17:08 1995 To: combinatorics(at-sign)math.mit.edu Subject: Ullman, 2/10 Friday, February 10, 4:15 p.m.; MIT, room 2-338 Dan Ullman (George Washington) Multicolorings of graphs The n-chromatic number \chi_n (G) of a graph G is the smallest number of colors needed to color the vertices, putting n colors on each vertex, subject to the constraint that adjacent vertices get disjoint sets of colors. Recently, Saul Stahl showed that the 11-chromatic number of the so-called Grotzsch graph is 32. In this talk, we survey results about sequences of the form \chi (G) , \chi_2 (G) , \chi_3 (G) , ... and explain the importance of Stahl's discovery. From propp(at-sign)math.mit.edu Mon Feb 6 20:48:01 1995 To: combinatorics(at-sign)math.mit.edu Subject: travel to Northampton on the 18th If anyone is planning to travel to the Smith one-day conference on the 18th and is looking for drivers/passengers, please contact propp(at-sign)math.mit.edu. Jim Propp From propp(at-sign)math.mit.edu Wed Feb 8 15:50:08 1995 To: combinatorics(at-sign)math.mit.edu Subject: Albertson, 2/15 Wednesday, February 15, 4:15 p.m.; MIT, room 2-338 Michael Albertson (Smith) The normalized chromatic difference sequence of a graph Almost twenty years ago Greene and Kleitman showed that the chain and antichain partition sequences of a poset are conjugate. Partially in response to that result David Berman and I began investigations into what we called the chromatic difference sequence of a graph. This talk will introduce the natural generalization of the antichain partition sequence, highlight the results that have been obtained, propose several open (dare I say intriguing) questions, and describe recent progress (mostly joint work with Ruth Haas) on edge versions. From propp(at-sign)math.mit.edu Wed Feb 8 16:08:09 1995 To: combinatorics(at-sign)math.mit.edu Subject: West, 2/17 Friday, February 17, 4:15 p.m.; MIT, room 2-338 Julian West (CECM, SFU, Vancouver) Recent forbidden-subsequenciana A survey of papers and preprints, by myself and others, which have appeared in the 28 months since my last address to this seminar. The general theme remains the enumeration of permutations under certain forbidden-subsequence restrictions, a problem which continues to sustain a small cottage industry. As usual, there will be a number of open problems cited, and an effort will be made to suggest directions for future research. From propp(at-sign)math.mit.edu Wed Feb 15 11:12:27 1995 To: combinatorics(at-sign)math.mit.edu Subject: Wagner, 2/22 Wednesday, February 22, 4:15 p.m.; MIT, room 2-338 David Wagner (Waterloo) Toric varieties associated with finite distributive lattices With each finite lattice L one associates a projectively embedded scheme V(L) in a natural way. As Hibi has observed, the lattice D is distributive if and only if V(D) is irreducible, in which case it is a toric variety. We will review this result and investigate further connections between the combinatorics of D and the geometry of V(D), including its orbit decomposition, locus of singularities, and structure of the normal cones of orbit closures. The methods employed are primarily combinatorial, relying on the Birkhoff structure theorem for finite distributive lattices, Mobius inversion, the matrix-tree theorem, and combinatorial/topological properties of the Hasse graph of the poset P of join-irreducibles of D. We will sketch a proof that each orbit closure of V(D) has an irreducible normal cone if and only if P is a dismantlable poset. This result indicates that for dismantlable posets P (in particular, for planar posets) intersection theory on V(D) may be more easily described than in the general case. From propp(at-sign)math.mit.edu Fri Feb 17 15:25:16 1995 To: combinatorics(at-sign)math.mit.edu Subject: MIT Combinatorics: March schedule MIT COMBINATORICS SEMINAR Here is the list of talks currently scheduled for the month of March. Wednesday, March 1, 4:15 p.m.: Ivan Cherednik, Products of symmetric polynomials through Hecke algebras Friday, March 3, 4:15 p.m.: Anatol Kirillov, Combinatorics of the Kostka-Foulkes polynomials Wednesday, March 8, 4:15 p.m.: Richard Ehrenborg, Sheffer posets and $r$-signed permutations Friday, March 10, 4:15 p.m.: Egon Schulte, The combinatorics and geometry of chiral polytopes Wednesday, March 15, 4:15 p.m.: Francesco Brenti, The combinatorics of Kazhdan-Lusztig polynomials Friday, March 17, 4:15 p.m.: Sergey Fomin, Parametrizing canonical bases and totally positive matrices Wednesday, March 22, 4:15 p.m.: Dan Klain, A short proof of Hadwiger's characterization theorem On Wednesday, April 5, there will be an ``open mike'' (a combinatorial free-for-all). We all know that some of the most important exchanges of ideas take place at conferences -- not during talks, but between them. Why not try to create some of that atmosphere while we're here in our own town? Bring short explanations of nice recent results of yours (whether they're cute lemmas you needed in your work or solutions to problems you saw in the Monthly), or bring questions about the combinatorial literature, or bring a list of good open problems you want to advertise, or just come to listen. If you're planning on presenting something, let Jim Propp know ahead of time (call 253-6544 or write to propp(at-sign)math.mit.edu). All talks will meet in room 2-338. From propp(at-sign)math.mit.edu Tue Feb 21 21:45:45 1995 To: combinatorics(at-sign)math.mit.edu Subject: Cherednik, 3/1 Wednesday, March 1, 4:15 p.m.; MIT, room 2-338 Ivan Cherednik (North Carolina, Harvard) Products of symmetric polynomials through Hecke algebras As it was found recently, double affine Hecke algebras arise naturally when we multiply the monomial symmetric functions x^{n}+x^{-n} by Schur functions (x^{m+1}-x^{-m-1})/(x^{1}-x^{-1}) and "uniformly" express the products in terms of the latter. This observation can be extended to arbitrary Macdonald's polynomials. From propp(at-sign)math.mit.edu Tue Feb 21 22:01:57 1995 To: combinatorics(at-sign)math.mit.edu Subject: Kirillov, 3/3 Friday, March 3, 4:15 p.m.; MIT, room 2-338 Anatol Kirillov (Steklov and Madison) Combinatorics of the Kostka-Foulkes polynomials We describe a bijection between the set of semi-standard Young tableaux and the set of rigged configurations. Applications to the combinatorics of Kostka-Foulkes-Lusztig polynomials will be discussed. From propp(at-sign)math.mit.edu Tue Feb 28 15:35:57 1995 To: combinatorics(at-sign)math.mit.edu Subject: MIT Combinatorics: March schedule (REVISED) MIT COMBINATORICS SEMINAR Here is the revised list of talks currently scheduled for the month of March. Note the added talks by Kauffman on the 9th and Rota on the 24th. Wednesday, March 1, 4:15 p.m.: Ivan Cherednik, Products of symmetric polynomials through Hecke algebras Friday, March 3, 4:15 p.m.: Anatol Kirillov, Combinatorics of the Kostka-Foulkes polynomials Wednesday, March 8, 4:15 p.m.: Richard Ehrenborg, Sheffer posets and $r$-signed permutations Thursday, March 9, 1:00 p.m.: Louis Kauffman, Quantum groups, Hopf algebras and knots Friday, March 10, 4:15 p.m.: Egon Schulte, The combinatorics and geometry of chiral polytopes Wednesday, March 15, 4:15 p.m.: Francesco Brenti, The combinatorics of Kazhdan-Lusztig polynomials Friday, March 17, 4:15 p.m.: Sergey Fomin, Parametrizing canonical bases and totally positive matrices Wednesday, March 22, 4:15 p.m.: Dan Klain, A short proof of Hadwiger's characterization theorem Friday, March 24, 4:15 p.m.: Gian-Carlo Rota, Combinatorial methods in homological algebra And don't forget: Wednesday, April 5, 4:15 p.m.: Combinatorial free-for-all (for more info, contact Jim Propp, 253-6544, propp(at-sign)math.mit.edu) All talks will meet in room 2-338. From propp(at-sign)math.mit.edu Wed Mar 1 09:53:50 1995 To: combinatorics(at-sign)math.mit.edu Subject: Talk at Northeastern by Kirillov on March 6 Of possible interest to subscribers to this mailing-list: Anatol Kirillov will speak at the Northeastern University Geometry-Algebra- Singularities Seminar on Monday, March 6, at 1:30 PM, in 509 Lake Hall. His topic will be "Dilogarithm Identities". From propp(at-sign)math.mit.edu Wed Mar 1 10:04:18 1995 To: combinatorics(at-sign)math.mit.edu Subject: Ehrenborg, 3/8 Wednesday, March 8, 4:15 p.m.; MIT, room 2-338 Richard Ehrenborg (UQAM) Sheffer posets and r-signed permutations We study a class of posets, which we call Sheffer posets. These posets were also studied by Vic Reiner. Sheffer posets are a generalization of binomial posets. Their incidence algebra has two interesting subspaces. These spaces behave like a ring and a module, and are isomorphic to certain generating functions. We also generalize the concept of R-labelings to linear edge-labelings, and prove a result analogous to a theorem of Bjorner and Stanley about R-labelings. This, together with the theory of rank-selections from a Sheffer poset, enables us to study augmented r-signed permutations. This is joint work with Margaret Readdy. From propp(at-sign)math.mit.edu Wed Mar 1 10:22:20 1995 To: combinatorics(at-sign)math.mit.edu Subject: Kauffman, 3/9 Thursday, March 9, 1:00 p.m.; MIT, room 2-338 ^^^^^^^^ (note unusual time) Special meeting: Louis Kauffman (University of Chicago at Illinois) Quantum groups, Hopf algebras and knots This is an introductory talk about the relationships of the subjects in the title. We discuss how Hopf algebras give rise to knot invariants and to invariants of 3-manifolds and raise questions about how these approaches are related to combinatorics and state sums. From propp(at-sign)math.mit.edu Wed Mar 1 11:54:51 1995 To: combinatorics(at-sign)math.mit.edu Subject: Schulte, 3/10 Friday, March 10, 4:15 p.m.; MIT, room 2-338 Egon Schulte (Northeastern) The combinatorics and geometry of chiral polytopes Abstract polytopes are discrete geometric structures which generalize the traditional notion of a convex polytope. These objects usually have a quite sophisticated combinatorics and topology. Chirality in abstract polytopes is a fascinating phenomenon which competes with the more well-behaving regularity. Chiral polytopes are those abstract polytopes which have maximal symmetry by (combinatorial) rotation, in contrast to the abstract regular polytopes which have maximal symmetry by (combinatorial) reflection. The geometric structure of chiral polytopes is currently best understood in ranks 3 and 4. We discuss some of the main problems in this area including the classification of polytopes by topological type, the phenomenon of enantiomorphism, and certain extension problems for chiral polytopes and their groups. From propp(at-sign)math.mit.edu Fri Mar 3 20:06:50 1995 To: combinatorics(at-sign)math.mit.edu Subject: Garsia, 3/9 Thursday, March 9, 4:15 p.m.; room to be announced Special meeting: Adriano Garsia (San Diego) Science fiction and Macdonald polynomials The talk will give a science-fiction explanation to some patterns that have been observed in the table of the q,t-Kostka coefficients. This work is joint with Francois Bergeron and Mark Haiman. From propp(at-sign)math.mit.edu Wed Mar 8 15:51:13 1995 To: combinatorics(at-sign)math.mit.edu Subject: MIT Combinatorics Seminar This is just a reminder that there are FOUR talks this week: Wednesday, March 8, 4:15 p.m.; MIT, room 2-338 Richard Ehrenborg (UQAM) Sheffer posets and r-signed permutations Thursday, March 9, 1:00 p.m.; MIT, room 2-338 Louis Kauffman (University of Chicago at Illinois) Quantum groups, Hopf algebras and knots Thursday, March 9, 4:15 p.m.; MIT, room 2-338 Adriano Garsia (San Diego) Science fiction and Macdonald polynomials Friday, March 10, 4:15 p.m.; MIT, room 2-338 Egon Schulte (Northeastern) The combinatorics and geometry of chiral polytopes From propp(at-sign)math.mit.edu Thu Mar 9 22:32:47 1995 To: combinatorics(at-sign)math.mit.edu Subject: Brenti, 3/15 Wednesday, March 15, 4:15 p.m.; MIT, room 2-338 Frencesco Brenti (IAS) The combinatorics of Kazhdan-Lusztig polynomials In 1979 Kazhdan and Lusztig defined, for every Coxeter group W, a family of polynomials, indexed by pairs of elements of W, which have become known as the Kazhdan-Lusztig polynomials of W. These polynomials are intimately related to the Bruhat order of W and to the algebraic geometry and topology of Schubert varieties, and have proved to be of fundamental importance in representation theory. While Kazhdan-Lusztig polynomials are usually defined algebraically in terms of Hecke algebras, in recent years purely combinatorial rules to compute them have been found. These rules not only make these objects more concrete, and accessible to a wider audience, but also enable combinatorial reasoning and techniques to be applied to them. Since these polynomials are still not very well understood, and several conjectures and open problems exist about them, many of a combinatorial nature, we feel that these combinatorial rules are worthy of further investigation. In this talk we survey and illustrate one of these rules as well as the main combinatorial properties which are known for the Kazhdan-Lusztig polynomials, and we present some intriguing conjectures and open problems (some old and some new) together with the evidence that exists for them. From propp(at-sign)math.mit.edu Thu Mar 9 22:35:39 1995 To: combinatorics(at-sign)math.mit.edu Subject: Fomin, 3/17 Friday, March 17, 4:15 p.m.; MIT, room 2-338 Sergey Fomin (MIT) Parametrizing canonical bases and totally positive matrices Let N be the group of n by n unipotent upper-triangular matrices. G. Lusztig discovered a close connection between the following two problems: (i) studying the piecewise-linear maps that relate different labelings of the canonical basis in the quantized enveloping algebra of the Lie algebra of N; (ii) studying the variety of totally positive elements of N. (Lusztig's theory holds in greater generality, when N is a maximal unipotent subgroup of a semisimple group of simply-laced type; for the moment, we only treat the A case.) Jointly with A. Berenstein and A. Zelevinsky, we obtained: (i) explicit closed formulas for these piecewise-linear maps; (ii) formulas for decomposing an upper-triangular matrix into a product of elementary Jacobi matrices, and related total positivity criteria. Our methods employ a combinatorial Ansatz based on representing commutation classes of reduced words by pseudoline arrangements. No background in quantum groups will be required for understanding. From propp(at-sign)math.mit.edu Tue Mar 14 17:44:27 1995 To: combinatorics(at-sign)math.mit.edu Subject: Klain, 3/22 Wednesday, March 22, 4:15 p.m.; MIT, room 2-338 Dan Klain (Georgia Tech) A characterization theorem for volume One of the most beautiful and important results in geometric convexity is Hadwiger's characterization theorem for the elementary mixed volumes (quermassintegrals). Hadwiger's theorem classifies all convex-continuous valuations that are invariant under rotations and translations as consisting of the linear span of the elementary mixed volumes (or, equivalently, of the intrinsic volumes of McMullen). This characterization theorem leads to effortless proofs of numerous results in integral geometry (including various kinematic formulas and the mean projection formulas for convex bodies) and also provides a connection between rigid motion invariant set functions and symmetric polynomials. Hadwiger's theorem is easily shown to be equivalent to a characterization theorem for the volume as a valuation on compact convex subsets of Euclidean space. Unfortunately the original proof of this volume characterization (the only known proof until now) is the product of a long and arduous sequence of cut and paste arguments scattered through over 100 pages of text. The purpose of this talk is to present a new and more general characterization of volume in Euclidean space, whose proof is digestible within a few minutes. (Note: This supersedes an earlier announcement that gave a different title and abstract.) From propp(at-sign)math.mit.edu Tue Mar 14 17:56:43 1995 To: combinatorics(at-sign)math.mit.edu Subject: Rota, 3/24 Friday, March 24, 4:15 p.m.; MIT, room 2-338 Gian-Carlo Rota (M.I.T.) Combinatorial methods in homological algebra This is a survey of the work done so far in collaboration with David Buchsbaum obtaining a characteristic-free resolution of Schur and Weyl functors. Some of the general techniques that we were led to in the course of working on this problem will be described. From propp(at-sign)math.mit.edu Tue Mar 28 16:10:21 1995 To: combinatorics(at-sign)math.mit.edu Subject: MIT Combinatorics: April schedule MIT COMBINATORICS SEMINAR Here is a revised list of talks scheduled for the month of April. Note the new talks scheduled for April 5, April 19, and April 28. Also note that the open mike originally scheduled for April 5 has been moved to April 12. Wednesday, April 5, 4:15 p.m.: Kimmo Eriksson, Combinatorial aspects of Fulton's essential set Friday, April 7, 4:15 p.m.: Jim Haglund, Colored rook placements Wednesday, April 12, 4:15 p.m.: Jim Propp, Richard Stanley, and others, Open mike Wednesday, April 19, 4:15 p.m.: Lenore Cowen, Defective colorings revisited Friday, April 21, 4:15 p.m.: Susanna Fishel, Canonical bases for the Birman-Wenzl algebra Wednesday, April 26, 4:15 p.m.: Margaret Readdy, The r-cubical lattice and a generalization of cd-index Friday, April 28, 4:15 p.m.: Dana Randall, Generating random surfaces, tilings and Eulerian orientations At the combinatorial open mike day to be held on April 12, Richard Stanley will speak about a particular determinant that counts paths in acyclic digraphs, and Jim Propp will give a quasi-combinatorial interpretation of the relation 2^{-1} = 1/2 via the ``Euler characteristic'' of an infinite- dimensional polytope. Others wishing to give short presentations should contact Jim Propp (propp(at-sign)math.mit.edu; 253-6544). All talks will meet in room 2-338. From propp(at-sign)math.mit.edu Tue Mar 28 16:13:32 1995 To: combinatorics(at-sign)math.mit.edu Subject: Eriksson, 4/5 Wednesday, April 5, 4:15 p.m.; MIT, room 2-338 Kimmo Eriksson (KTH) Combinatorial aspects of Fulton's essential set A square matrix with one "dot" in each row and column defines a permutation. The "diagram" of this permutation is obtained by deleting the squares in each row from the dot and eastwards, and deleting the squares in each column from the dot and southwards. The _essential_set_ of a permutation was defined by Fulton as the set of southeast corners of the diagram. I will discuss some combinatorial aspects: characterization, enumeration, and application, of the essential set. For example, how big is the essential set on average? Some nice formulas appear! For the nicest formula, one needs to know the number of "extendably 321-avoiding dotted matrices". Pursuing my old interest in chips games, I will show how this problem can be solved by considering a game of moving around chips. This is joint work with Svante Linusson. From propp(at-sign)math.mit.edu Tue Mar 28 16:17:15 1995 To: combinatorics(at-sign)math.mit.edu Subject: Haglund, 4/7 Friday, April 7, 4:15 p.m.; MIT, room 2-338 Jim Haglund (Kennesaw) Colored rook placements Recent work in rook theory by Chung, Graham and others has centered around enumerating permutations by number of cycles. In this talk we introduce a number of parameters which generalize the cycle parameter, and show that for Ferrers boards the rook factorial polynomial factors as in the classical case. Applications include an interpretation in terms of rook polynomials of certain types of hypergeometric series which arise in physics. This is joint work with Richard Ehrenborg and Margaret Readdy. From propp(at-sign)math.mit.edu Tue Mar 28 17:36:58 1995 To: combinatorics(at-sign)math.mit.edu Subject: MIT Combinatorics: April schedule (NOTE CANCELLATION!) MIT COMBINATORICS SEMINAR Here is a re-revised list of talks scheduled for the month of April. Kimmo Eriksson's talk, announced for April 5 earlier today, will be moved to another date (to be announced) so as not to conflict with John Harbison's Killian lecture. Friday, April 7, 4:15 p.m.: Jim Haglund, Colored rook placements Wednesday, April 12, 4:15 p.m.: Jim Propp, Richard Stanley, and others, Open mike Wednesday, April 19, 4:15 p.m.: Lenore Cowen, Defective colorings revisited Friday, April 21, 4:15 p.m.: Susanna Fishel, Canonical bases for the Birman-Wenzl algebra Wednesday, April 26, 4:15 p.m.: Margaret Readdy, The r-cubical lattice and a generalization of cd-index Friday, April 28, 4:15 p.m.: Dana Randall, Generating random surfaces, tilings and Eulerian orientations At the combinatorial open mike day to be held on April 12, Richard Stanley will speak about a particular determinant that counts paths in acyclic digraphs, and Jim Propp will give a quasi-combinatorial interpretation of the relation 2^{-1} = 1/2 via the "Euler characteristic" of an infinite- dimensional polytope. Others wishing to give short presentations should contact Jim Propp (propp(at-sign)math.mit.edu; 253-6544). All talks will meet in room 2-338. From propp(at-sign)math.mit.edu Tue Apr 4 10:22:51 1995 To: combinatorics(at-sign)math.mit.edu Subject: Haglund, 4/7 Friday, April 7, 4:15 p.m.; MIT, room 2-338 Jim Haglund (Kennesaw) Colored rook placements Recent work in rook theory by Chung, Graham and others has centered around enumerating permutations by number of cycles. In this talk we introduce a number of parameters which generalize the cycle parameter, and show that for Ferrers boards the rook factorial polynomial factors as in the classical case. Applications include an interpretation in terms of rook polynomials of certain types of hypergeometric series which arise in physics. This is joint work with Richard Ehrenborg and Margaret Readdy. From propp(at-sign)math.mit.edu Tue Apr 4 10:22:51 1995 To: combinatorics(at-sign)math.mit.edu Subject: MIT Combinatorics: April schedule (new talk added) MIT COMBINATORICS SEMINAR Here is a final list of talks scheduled for the month of April. Note that Kimmo Eriksson's talk has been re-scheduled for April 14. Friday, April 7, 4:15 p.m.: Jim Haglund, Colored rook placements Wednesday, April 12, 4:15 p.m.: M. Albertson, J. Propp, R. Stanley et al., Open mike Friday, April 14, 4:15 p.m.: Kimmo Eriksson, Combinatorial aspects of Fulton's essential set Wednesday, April 19, 4:15 p.m.: Lenore Cowen, Defective colorings revisited Friday, April 21, 4:15 p.m.: Susanna Fishel, Canonical bases for the Birman-Wenzl algebra Wednesday, April 26, 4:15 p.m.: Margaret Readdy, The r-cubical lattice and a generalization of cd-index Friday, April 28, 4:15 p.m.: Dana Randall, Generating random surfaces, tilings and Eulerian orientations At the combinatorial open mike day to be held on April 12, Richard Stanley will speak about a particular determinant that counts paths in acyclic digraphs, Jim Propp will give a quasi-combinatorial interpretation of the relation 2^{-1} = 1/2 via the ``Euler characteristic'' of an infinite-dimensional polytope, and Mike Albertson will present on a problem on automorphism groups acting on graphs. Others wishing to give short presentations should contact Jim Propp (propp(at-sign)math.mit.edu; 253-6544). All talks will meet in room 2-338. From propp(at-sign)math.mit.edu Thu Apr 6 12:40:50 1995 To: combinatorics(at-sign)math.mit.edu Subject: Discrete Dinner The next Discrete Dinner will be held at newly re-opened Mary Chung's near MIT. The cost for graduate students and undergraduates will be held down to $7 (drinks included), with the rest of us making up the difference. (The cost for the rest of us will of course depend on the ratio between the two classes of diners, but the total paid by each non-student should be less than $20.) Please let me know the relative convenience of the following proposed dates: Weds., April 26 Fri., April 28 Weds., May 3 Fri., May 5 Weds., May 10 Fri., May 12 Jim Propp (Send replies to propp(at-sign)math.mit.edu) From propp(at-sign)math.mit.edu Thu Apr 6 13:28:21 1995 To: combinatorics(at-sign)math.mit.edu Subject: Free-for-all, 4/12 Wednesday, April 12, 4:15 p.m.; MIT, room 2-338 All of Us (from All Over the Boston Area) Open Mike Session / Combinatorial Free-for-All We all know that some of the most important exchanges of ideas take place at conferences -- not during talks, but between them. Why not try to create some of that atmosphere while we're here in our own town? Bring short explanations of nice recent results of yours (whether they're cute lemmas you needed in your work or solutions to problems you saw in the Monthly), or bring questions about the combinatorial literature (``What should I read to learn about oriented matroids?''), or bring a list of good open problems you want to advertise. Or whatever. Let me know ahead of time what you're bringing, if you plan on presenting something that will take longer than five minutes. Currently scheduled presenters are Richard Stanley, who will talk about a particular determinant that counts paths in acyclic digraphs, and Jim Propp, who will give a quasi-combinatorial interpretation of the relation 2^{-1} = 1/2 via the ``Euler characteristic'' of an infinite- dimensional polytope; and Mike Albertson, who will present a problem on automorphism groups acting on graphs. Others wishing to give short presentations should contact Jim Propp (propp(at-sign)math.mit.edu; 253-6544). From propp(at-sign)math.mit.edu Thu Apr 6 14:02:59 1995 To: combinatorics(at-sign)math.mit.edu Subject: Eriksson, 4/14 Friday, April 14, 4:15 p.m.; MIT, room 2-338 Kimmo Eriksson (KTH) Combinatorial aspects of Fulton's essential set A square matrix with one "dot" in each row and column defines a permutation. The "diagram" of this permutation is obtained by deleting the squares in each row from the dot and eastwards, and deleting the squares in each column from the dot and southwards. The _essential_set_ of a permutation was defined by Fulton as the set of southeast corners of the diagram. I will discuss some combinatorial aspects: characterization, enumeration, and application, of the essential set. For example, how big is the essential set on average? Some nice formulas appear! For the nicest formula, one needs to know the number of "extendably 321-avoiding dotted matrices". Pursuing my old interest in chips games, I will show how this problem can be solved by considering a game of moving around chips. This is joint work with Svante Linusson. From propp(at-sign)math.mit.edu Tue Apr 11 19:46:04 1995 To: combinatorics(at-sign)math.mit.edu Subject: Reminder Today's combinatorics seminar (Wednesday, April 12) will be an Open Mike. Currently scheduled "mini-speakers" are Mike Albertson, Tim Chow, Kimmo Eriksson, Igor Pak, Alexander Postnikov, Jim Propp, Richard Stanley, Herb Wilf, and Andrei Zelevinsky. (This doesn't leave much room for spontaneous mini-talks by others, but if we run out of time, we can schedule another Open Mike in May.) From propp(at-sign)math.mit.edu Tue Apr 11 20:03:22 1995 To: combinatorics(at-sign)math.mit.edu Subject: Cowen, 4/19 Wednesday, April 19, 4:15 p.m.; MIT, room 2-338 Lenore Cowen (Johns Hopkins) Defective colorings revisited A graph is said to be (n,k) colorable, if its vertices can be colored with n colors, so that any vertex has at most k self-colored neighbors. Cowen, Cowen and Woodall gave in 1986 a complete characterization of for which n and k is every planar graph (n,k) colorable. We extend to the torus, and show that every graph on the torus is (3,2) colorable (solving an 8-year old conjecture), and (5,1) colorable. It is still open if every torodial graph is (4,1) colorable. We also improve some bounds for defective chromatic number of general graphs. We also consider the complexity of finding defective colorings. We show (n,k) coloring is NP-complete for n >= 2 and k >= 1. We show (2,1) and (3,1) coloring remain NP-complete, even for planar graphs. We present polynomial-time approximation schemes and discuss open questions. This is joint work with W. Goddard and E. Jesurum. From propp(at-sign)math.mit.edu Tue Apr 11 20:07:51 1995 To: combinatorics(at-sign)math.mit.edu Subject: Fishel, 4/21 Friday, April 21, 4:15 p.m.; MIT, room 2-338 Susanna Fishel (Southern Connecticut State) Canonical bases for the Birman-Wenzl algebra In this talk, which is a summary of joint work with I. Grojnowski, we construct Kahzdan-Lusztig bases for the Birman-Wenzl algebra BW_n, and so define left, right, and two-sided cells. We describe these objects combinatorially, using a generalization of the Robinson-Schensted algorithm for the symmetric group, and show that each left cell carries an irreducible representation of BW_n. In particular, we obtain canonical bases for each representation, defined over Z. From CCHEN(at-sign)WELLESLEY.EDU Wed Apr 19 14:05:32 1995 Subject: Are you going to Smith on 4/22? 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" X-VMS-Cc: CCHEN MIME-version: 1.0 Content-type: TEXT/PLAIN; CHARSET=US-ASCII Content-transfer-encoding: 7BIT Hi, I am math major at Wellesley and I would like to go to the Combinatorics and Graph Theory conference at Smith this Saturday. I have a ride there, but I don't have one back. If you are attending and coming back to MIT/ Cambridge/Boston that evening, could you give me a ride back? I'd have no problem getting from the MIT area back to Wellesley on my own. Thank you for your help. Christina Chen From propp(at-sign)math.mit.edu Wed Apr 19 21:36:36 1995 To: combinatorics(at-sign)math.mit.edu Subject: Readdy, 4/26 Wednesday, April 26, 4:15 p.m.; MIT, room 2-338 Margaret Readdy (LACIM) The r-cubical lattice and a generalization of the cd-index We define a natural extension of the cubical lattice, called the r-cubical lattice. Recall that the cd-index is a convenient way to encode the flag f-vector of an Eulerian poset. We generalize the cd-index of the cubical lattice to an r-cd-index for the r-cubical lattice. The coefficients of this index enumerate augmented Andre r-signed permutations, generalizing Purtill's work relating the cd-index of the cubical lattice and signed Andre permutations. As an application of the r-cd-index, we find that the extremal configuration which maximizes the Mobius function over arbitrary rank selections from the r-cubical lattice is the odd alternating ranks, {1,3,5,...}. This is joint work with Richard Ehrenborg. From propp(at-sign)math.mit.edu Wed Apr 19 21:47:16 1995 To: combinatorics(at-sign)math.mit.edu Subject: Randall, 4/28 Friday, April 28, 4:15 p.m.; MIT, room 2-338 Dana Randall (Institute for Advanced Study) Generating random surfaces, tilings and Eulerian orientations We present a technique for generating random configurations on any finite region of a two-dimensional lattice and show it is efficient for several important combinatorial problems arising in statistical mechanics. The dimer problem asks for a random tiling of the region, where each tile covers two adjacent cells of the lattice. Thurston, Conway and Lagarias show that the set of tilings map bijectively to a set of piecewise linear surfaces with a fixed boundary. Similarly, the set of Eulerian orientations with fixed boundary conditions (or configurations of the ice model in statistical mechanics) are known to correspond bijectively with ``solid-on-solid'' surfaces where the difference in height between nearest neighbors is always exactly one. Finally, the set of 3-colorings of regions of the Cartesian lattice (or the dominant coefficient of the q=3 Pott's model) correspond to the union, over all boundary conditions, of the set of Eulerian orientations. We define a Markov chain for each family of surfaces and show that each will converge quickly to the uniform distribution over configurations. The proofs of the convergence rates rely on simple coupling arguments. (This is joint work with Michael Luby and Alistair Sinclair.) From propp(at-sign)math.mit.edu Tue Apr 25 17:32:28 1995 To: combinatorics(at-sign)math.mit.edu Subject: Discrete Dinner Spring 1995 Cambridge Discrete Mathematics Dinner This semester's Discrete Dinner will be held on Friday, May 12 at 6 p.m. at the recently re-opened Mary Chung's (at 464 Massachusetts Avenue in Cambridge, just a few blocks from MIT). The cost will be $7 for grad students and undergraduates, with the rest of us making up the difference. I hope that the closeness to campus and the low cost of the meal will encourage graduate students and undergraduates to attend. Please let me know by May 1 (preferably electronically) your probability of attendance. (The sum of these probabilities has proved to be a reliable indicator of the number of people who actually attend.) Send e-mail to propp(at-sign)math.mit.edu or call 253-6544. From propp(at-sign)math.mit.edu Tue Apr 25 17:33:23 1995 To: combinatorics(at-sign)math.mit.edu Subject: MIT Combinatorics: preliminary May schedule MIT COMBINATORICS SEMINAR Here is a preliminary list of talks scheduled for the month of May. The talk on May 12 will be followed by this semester's Discrete Dinner, which is open to all members of the Boston combinatorial community. Details are given in a separate announcement. Wednesday, May 3, 4:15 p.m.: Dan Kleitman, A surprisingly simple proof of the box conjecture Wednesday, May 10, 4:15 p.m.: David Jackson, Maps in locally orientable surfaces, an integral representation, zonal polynomials, and the monopole series Friday, May 12, 4:15 p.m.: Jim Propp and David Wilson, Random generation of combinatorial objects Wednesday, May 31, 4:15 p.m.: Amin Shokrollahi, Coding theory and Bernoulli numbers From propp(at-sign)math.mit.edu Tue Apr 25 17:36:37 1995 To: combinatorics(at-sign)math.mit.edu Subject: Kleitman, 5/3 Wednesday, May 3, 4:15 p.m.; MIT, room 2-338 Dan Kleitman (M.I.T.) A surprisingly simple proof of the box conjecture Recently Dave Reimer, a graduate student at Rutgers, settled the Van den Berg - Kesten "box conjecture", a long-standing problem in probability theory. I shall describe the proof, which is quite simple. Restated combinatorially, the problem is as follows. Given two collections A and B of 0,1-vectors of length n, we define "A box B" to be the set of vectors x for which there is a y(x) such that every z on a direct line between x and y is in A and such that every z' on a direct line between x and the complement of y is in B. Reimer's theorem asserts that |A box B| 2^n is at most |A| |B|. From propp(at-sign)math.mit.edu Wed May 3 13:06:41 1995 To: combinatorics(at-sign)math.mit.edu Subject: Jackson, 5/10 Wednesday, May 10, 4:15 p.m.; MIT, room 2-338 David Jackson (Waterloo) Maps in locally orientable surfaces, an integral representation, zonal polynomials, and the monopole series The genus series for maps is the generating series for the number of rooted maps with a given number of vertices and faces of each degree, and a given number of edges. It captures topological information about surfaces, and appears in questions arising in statistical mechanics, topology, group rings, and certain aspects of free probability theory. An expression has been given previously for the genus series for maps in locally orientable surfaces in terms of zonal polynomials. The purpose of this talk is to derive an integral representation for the genus series. We then show how this can be used in conjunction with integration techniques to determine the genus series for monopoles in locally orientable surfaces. The latter result can be interpreted in terms of the Euler characteristic for the moduli spaces of real curves, and therefore complements the analogous result for monopoles in orientable surfaces previously obtained by Harer and Zagier. From propp(at-sign)math.mit.edu Wed May 3 13:26:27 1995 To: combinatorics(at-sign)math.mit.edu Subject: Propp and Wilson, 5/12 Friday, May 12, 4:15 p.m.; MIT, room 2-338 Jim Propp and David Wilson (M.I.T.) Random generation of combinatorial objects We'll discuss our recent work on generating random combinatorial objects, including some that arise in statistical mechanics, via the method of coupled simulation from the past. We will first illustrate this method by showing how one can sample exactly from the steady-state distribution of any (ergodic) Markov chain which one can simulate. Next we extend these ideas to sampling from the uniform distribution on the set of order-ideals of a finite poset. Surprisingly, work of Winkler and others shows that this allows one to randomly sample the independent sets of a bipartite graph. Finally, we will apply this approach to sample from the Gibbs distribution for the Ising model in two different ways: a naive way that suffers from exponential slowdown below the critical temperature, and a more sophisticated approach that allows one to sample efficiently at any temperature. No prior knowledge of statistical mechanics will be required, though some knowledge of basic Markov chain theory (e.g., the concept of a steady state) will be helpful. From gptesler(at-sign)math.mit.edu Mon May 15 12:59:02 1995 To: combinatorics(at-sign)math.mit.edu Subject: Tesler, 5/24 (ADDED TALK) Wednesday, May 24, 4:15 p.m.; MIT, room 2-338 Glenn Tesler (MIT) Semi-primary Lattices and Schutzenberger's Evacuation Algorithm We consider lattices, such as the subgroups of a finite abelian p-group, in which an integer partition is assigned to every element and every interval. Chains in these lattices give rise to chains of partitions, which may be encoded as tableaux. In one class of these lattices, Hesselink and van Leeuwen showed that, given the types of the elements in a chain, the generic cotype, which is a certain description of the configuration of the elements in the chain, is computed by the well-known evacuation algorithm on standard tableaux. We explore extensions of this to a larger class of lattices called semi-primary lattices, consider the non-generic configurations, and consider enumeration of the number of chains achieving each configuration. From propp(at-sign)math.mit.edu Thu May 25 12:26:15 1995 To: combinatorics(at-sign)math.mit.edu Subject: Shokrollahi, 5/31 Wednesday, May 31, 4:15 p.m.; MIT, room 2-338 Amin Shokrollahi (Bonn) Coding theory and Bernoulli numbers A prime p is called regular if it does not divide the numerators of the Bernoulli numbers B_k, k=2,4,...,p-3. Otherwise it is called irregular; in that case, a pair (p,2i) such that p divides B_{2i} is called an irregular pair and the number of such pairs is called the index of irregularity of p. Many interesting data of the cyclotomic field K_p generated over the field of rational numbers by a primitive p-th root of unity are encoded in the irregular pairs corresponding to a prime. We show a relationship between these data and certain cyclic codes in the following way: let p>2, let G_p be the Galois group of K_p over the field of rational numbers, and let Gamma_p = Z[G_p] be the integral group ring of G_p. We study the reduction of a certain ideal of Gamma_p modulo p. This is a cyclic code over the finite field GF(p). We show a relationship between the dimension and minimum distance of this code and the index of irregularity of p. The results might indicate that there is a deeper connection between the minimum distance of cyclic codes and certain arithmetic invariants of cyclotomic fields.