From propp(at-sign)math.mit.edu Mon Aug 22 17:58:41 1994 To: combinatorics(at-sign)math.mit.edu Subject: MIT Combinatorics Seminar Welcome back. I don't have a September schedule yet, but anyone interested in giving a talk in the MIT Combinatorics Seminar in the next month and a half should definitely contact me this week. The paper "Normal Cayley graphs and homomorphisms of cartesian powers of graphs," by Benoit Larose, Francois Laviolette, and Claude Tardif, is now available in ~propp/public. Anyone who wants a copy but doesn't have an account on the math machines can request a copy via email. Jim Propp From propp(at-sign)math.mit.edu Fri Sep 23 13:50:37 1994 To: combinatorics(at-sign)math.mit.edu Subject: Combinatorics Seminar: October schedule MIT COMBINATORICS SEMINAR Here is the list of talks scheduled for the month of October. Wednesday, October 5, 4:15 p.m.: Yuval Roichman, Upper bounds on characters of the symmetric groups and combinatorial applications Wednesday, October 12, 4:15 p.m.: Jay Goldman, Knots, tangles, and signed graphs Friday, October 14, 4:15 p.m.: Timothy Chow, The path-cycle symmetric function of a digraph Wednesday, October 19, 4:15 p.m.: Tim Wallstrom, Orthogonal polynomials on a random measure space Wednesday, October 26, 4:15 p.m.: Vic Reiner, Rhombic tilings and free hyperplane arrangements Friday, October 28, 4:15 p.m.: Mark Shimozono, Generalized exponents, column cyclage type, and tableaux of rectangular content All talks will meet in room 2-338. From propp(at-sign)math.mit.edu Fri Sep 23 17:15:29 1994 To: combinatorics(at-sign)math.mit.edu Subject: Combinatorics Seminar: October schedule (revised) MIT COMBINATORICS SEMINAR Here is a revised list of talks scheduled for the month of October. Wednesday, October 5, 4:15 p.m.: Yuval Roichman, Upper bounds on characters of the symmetric groups and combinatorial applications Friday, October 7, 4:15 p.m.: Ken Berman, On-line hypergraph algorithms, unique satisfiability of Horn clauses, and logic programming Wednesday, October 12, 4:15 p.m.: Jay Goldman, Knots, tangles, and signed graphs Friday, October 14, 4:15 p.m.: Timothy Chow, The path-cycle symmetric function of a digraph Wednesday, October 19, 4:15 p.m.: Tim Wallstrom, Orthogonal polynomials on a random measure space Wednesday, October 26, 4:15 p.m.: Vic Reiner, Rhombic tilings and free hyperplane arrangements Friday, October 28, 4:15 p.m.: Mark Shimozono, Generalized exponents, column cyclage type, and tableaux of rectangular content All talks will meet in room 2-338. From propp(at-sign)math.mit.edu Thu Sep 29 15:30:33 1994 To: combinatorics(at-sign)math.mit.edu Subject: Roichman, 10/5 Wednesday, October 5, 4:15 p.m.; MIT, room 2-338 Yuval Roichman (Hebrew University and Harvard) Upper bounds on characters of the symmetric groups and combinatorial applications The rate of convergence of a random walk on the Cayley graph of the alternating group A_n with respect to a conjugacy class C with support sup(C) \le (1-\delta)n is \Theta({n\cdot\log n\over sup(C)}) . This is a far reaching generalization of a famous result of Diaconis and Shahshahani. In particular it solves an open problem of Diaconis. The result is obtained by new upper bounds on characters of the symmetric groups, and estimations of the probability of a random standard tableau to satisfy certain conditions. The estimations on characters imply expansion properties of certain Cayley graphs of the symmetric groups, and results on the decomposition of the conjugacy representation of these groups. From propp(at-sign)math.mit.edu Thu Sep 29 15:34:06 1994 To: combinatorics(at-sign)math.mit.edu Subject: Berman, 10/7 Friday, October 7, 4:15 p.m.; MIT, room 2-338 Ken Berman (Cincinnati) On-line Hypergraph Algorithms, Unique Satisfiability of Horn Clauses, and Logic Programming A hypergraph H, where one vertex of each hyperedge e is designated the head and the remaining vertices of e form the tail, models a set of (pure) Horn clauses. We present a linear on-line algorithm for finding cycles in such a hypergraph when edges are added on-line, which we employ to obtain an optimal (linear time) algorithm for determining whether a set of (general) Horn clauses is uniquely satisfiable. We also present an efficient on-line algorithm for maintaining the distance from a particular vertex r to all the other vertices of the hypergraph when hyperedges are deleted on-line. We discuss several natural applications of the latter algorithm, including an application to well-founded semantics in logic programming. From propp(at-sign)math.mit.edu Wed Oct 5 15:44:54 1994 To: combinatorics(at-sign)math.mit.edu Subject: Combinatorics seminar postponements MIT COMBINATORICS SEMINAR Note: The talks of Jay Goldman and Timothy Chow, originally scheduled for the 12th and 14th of October, have been cancelled, as they conflict with talks being given as part of the Norbert Wiener Centennial Symposium. These talks will be re-scheduled for later dates. Here is the current list of talks scheduled for the month of October. Wednesday, October 5, 4:15 p.m.: Yuval Roichman, Upper bounds on characters of the symmetric groups and combinatorial applications Friday, October 7, 4:15 p.m.: Ken Berman, On-line hypergraph algorithms, unique satisfiability of Horn clauses, and logic programming Wednesday, October 19, 4:15 p.m.: Tim Wallstrom, Orthogonal polynomials on a random measure space Wednesday, October 26, 4:15 p.m.: Vic Reiner, Rhombic tilings and free hyperplane arrangements Friday, October 28, 4:15 p.m.: Mark Shimozono, Generalized exponents, column cyclage type, and tableaux of rectangular content All talks will meet in room 2-338. From propp(at-sign)math.mit.edu Tue Oct 11 18:01:49 1994 To: combinatorics(at-sign)math.mit.edu Subject: Discrete Dinner It's once again time to organize the semester's DISCRETE DINNER. The next Discrete Dinner will be held at the Cambridge Brewing Company in Kendall Square. I propose that the cost for graduate students and undergraduates 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, as well as on the amount of subsidized suds consumed, but the total per person should be less than $20.) Does this strike people as reasonable? If so, I'd like people's thoughts on the following proposed dates: Weds., October 19 Weds., October 26 Weds., November 2 Weds., November 9 Jim Propp (Send replies to propp(at-sign)math.mit.edu) From propp(at-sign)math.mit.edu Wed Oct 19 21:05:56 1994 To: combinatorics(at-sign)math.mit.edu Subject: Discrete Dinner This semester's DISCRETE DINNER will take place on Wednesday, November 9 at 6 p.m. at the Cambridge Brewing Company in Kendall Square. Graduate students are especially welcome to attend. 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 should be less than $20 per person. As the date approaches, I'll get the usual stochastic headcount. Jim Propp From propp(at-sign)math.mit.edu Tue Oct 25 11:50:24 1994 To: combinatorics(at-sign)math.mit.edu Subject: Combinatorics Seminar: November schedule MIT COMBINATORICS SEMINAR Here is the current list of talks scheduled for the month of November. Wednesday, November 2, 4:15 p.m.: Anders Bjorner, Face numbers of complexes whose Stanley-Reisner ring has bounded depth Wednesday, November 9, 4:15 p.m.: Sara Billey, An overview of Schubert polynomials Wednesday, November 16, 4:15 p.m.: Timothy Chow, The path-cycle symmetric function of a digraph Wednesday, November 30, 4:15 p.m.: Ezra Getzler, An analogue of the Fourier transform for symmetric functions All talks will meet in room 2-338. From propp(at-sign)math.mit.edu Tue Nov 1 00:43:25 1994 To: combinatorics(at-sign)math.mit.edu Subject: Discrete Dinner (headcount requested) This semester's DISCRETE DINNER will take place on Wednesday, November 9 at 6 p.m. at the Cambridge Brewing Company in Kendall Square. Graduate students in discrete mathematics are especially welcome to attend. 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 should be less than $20 per person. Please let me know BY THIS FRIDAY (November 4) the approximate probability of your attending. (Those with probability close to zero need not reply.) Jim Propp From propp(at-sign)math.mit.edu Thu Nov 17 13:43:58 1994 To: combinatorics(at-sign)math.mit.edu Subject: belated announcements of recent seminar talks I see I've been forgetting to send out electronic announcements of the abstracts for Combinatorics Seminar talks. The ones that have already taken place in the month of November follow. (Better late than never...) Jim Propp ****************************************************************** MIT COMBINATORICS SEMINAR Here is the current list of talks scheduled for the month of November. Wednesday, November 2, 4:15 p.m.: Anders Bjorner, Face numbers of complexes whose Stanley-Reisner ring has bounded depth Wednesday, November 9, 4:15 p.m.: Sara Billey, An overview of Schubert polynomials Wednesday, November 16, 4:15 p.m.: Timothy Chow, The path-cycle symmetric function of a digraph Wednesday, November 30, 4:15 p.m.: Ezra Getzler, An analogue of the Fourier transform for symmetric functions All talks will meet in room 2-338. ****************************************************************** Wednesday, November 2, 4:15 p.m.; MIT, room 2-338 Anders Bjorner (KTH) Face numbers of complexes whose Stanley-Reisner ring has bounded depth A characterization will be given of the possible numbers of faces of simplicial complexes whose Stanley-Reisner ring has depth k or greater. For k = 0 (no condition) this gives the Kruskal-Katona theorem and for maximal depth (the Cohen-Macaulay case) it specializes to Stanley's theorem. Intermediate cases include a characterization of f-vectors of connected complexes. In a more general version the general theorem also involves the Betti numbers of the complex. No previous knowledge of the area will be assumed - the old results will be reviewed. ****************************************************************** Wednesday, November 9, 4:15 p.m.; MIT, room 2-338 Sara Billey (M.I.T.) An overview of Schubert polynomials Schubert polynomials are a fascinating family of polynomials related to the geometry of flag manifolds. We present a unified theory of Schubert polynomials for the classical groups in the context of combinatorics and algebraic geometry. Historically, Schubert polynomials (for type A) were defined by Lascoux and Schutzenberger to simplify computations of intersection multiplicities of Schubert varieties and to provide explicit representatives of the Schubert classes defined by Bernstein, Gelfand and Gelfand. Recently, Schubert polynomials have been studied by algebraic combinatorialists because of their connections with the theory of symmetric functions, representation theory and reduced words. In this talk, we will present some of the background from algebraic geometry on flag manifolds and their cohomology rings. From the geometry there is a natural construction which defines the Schubert polynomials. Once we have a general definition of these polynomials we can give formulas for Schubert polynomials for each of the root systems of type A, B, C, and D. These formulas are defined in terms of Schur Q-functions, the Haiman correspondence of B_n and D_n reduced words, and Stanley symmetric functions. We conclude with some conjectures for expanding products of Schubert polynomials in special cases, these special cases correspond to analogs of the Pieri rules for Schur functions. ****************************************************************** Wednesday, November 16, 4:15 p.m.; MIT, room 2-338 Timothy Chow (M.I.T.) The path-cycle symmetric function of a digraph R. Stanley has generalized the chromatic polynomial of a graph to a symmetric function. Independently, F. Chung and R. Graham have defined a digraph polynomial called the cover polynomial, which has close connections with chromatic polynomials and also rook polynomials. In this paper we imitate Stanley's construction to define a symmetric function generalization of the cover polynomial. We obtain generalizations and analogues of several results of Stanley, Chung and Graham, and others. In addition, we prove a combinatorial reciprocity theorem that unexpectedly ties together a number of results scattered in the literature that previously seemed unrelated, and we define a new symmetric function basis that appears to be a natural counterpart of the polynomial basis ${x+n\choose d}_{n=0,\ldots,d}$. From propp(at-sign)math.mit.edu Thu Nov 17 13:44:30 1994 To: combinatorics(at-sign)math.mit.edu Subject: Getzler, 11/30 Wednesday, November 30, 4:15 p.m.; MIT, room 2-338 Ezra Getzler (M.I.T.) An analogue of the Fourier transform for symmetric functions Motivated by questions in mathematical physics (notably, the work of Kontsevich), Kapranov and I have studied the following problem. Given S_n-modules a(n), associate to a graph G the vector space a(G) given by tensoring together a copy of a(n) for each vertex of G of valence n, and then taking coinvariants under the automorphism group of G. Now sum a(G) over all graphs with given Euler characteristic. We derive a formula for the dimension of this vector space, using the theory of symmetric functions. This formula may be applied to calculate certain combinations of the Euler characteristics of moduli spaces of Riemann surfaces. From MAILER-DAEMON(at-sign)math.mit.edu Sat Nov 19 13:51:15 1994 Subject: Returned mail: Cannot send message for 2 days To: <propp(at-sign)math.mit.edu> ----- Transcript of session follows ----- 421 abel.lanl.gov: Host abel.lanl.gov is down

From:Jim Propp <propp(at-sign)math.mit.edu>Date:Thu, 17 Nov 94 13:29:56 ESTTo:combinatorics(at-sign)math.mit.eduSubject:belated announcements of recent seminar talks

I see I've been forgetting to send out electronic announcements of the abstracts for Combinatorics Seminar talks. The ones that have already taken place in the month of November follow. (Better late than never...) Jim Propp ****************************************************************** MIT COMBINATORICS SEMINAR Here is the current list of talks scheduled for the month of November. Wednesday, November 2, 4:15 p.m.: Anders Bjorner, Face numbers of complexes whose Stanley-Reisner ring has bounded depth Wednesday, November 9, 4:15 p.m.: Sara Billey, An overview of Schubert polynomials Wednesday, November 16, 4:15 p.m.: Timothy Chow, The path-cycle symmetric function of a digraph Wednesday, November 30, 4:15 p.m.: Ezra Getzler, An analogue of the Fourier transform for symmetric functions All talks will meet in room 2-338. ****************************************************************** Wednesday, November 2, 4:15 p.m.; MIT, room 2-338 Anders Bjorner (KTH) Face numbers of complexes whose Stanley-Reisner ring has bounded depth A characterization will be given of the possible numbers of faces of simplicial complexes whose Stanley-Reisner ring has depth k or greater. For k = 0 (no condition) this gives the Kruskal-Katona theorem and for maximal depth (the Cohen-Macaulay case) it specializes to Stanley's theorem. Intermediate cases include a characterization of f-vectors of connected complexes. In a more general version the general theorem also involves the Betti numbers of the complex. No previous knowledge of the area will be assumed - the old results will be reviewed. ****************************************************************** Wednesday, November 9, 4:15 p.m.; MIT, room 2-338 Sara Billey (M.I.T.) An overview of Schubert polynomials Schubert polynomials are a fascinating family of polynomials related to the geometry of flag manifolds. We present a unified theory of Schubert polynomials for the classical groups in the context of combinatorics and algebraic geometry. Historically, Schubert polynomials (for type A) were defined by Lascoux and Schutzenberger to simplify computations of intersection multiplicities of Schubert varieties and to provide explicit representatives of the Schubert classes defined by Bernstein, Gelfand and Gelfand. Recently, Schubert polynomials have been studied by algebraic combinatorialists because of their connections with the theory of symmetric functions, representation theory and reduced words. In this talk, we will present some of the background from algebraic geometry on flag manifolds and their cohomology rings. From the geometry there is a natural construction which defines the Schubert polynomials. Once we have a general definition of these polynomials we can give formulas for Schubert polynomials for each of the root systems of type A, B, C, and D. These formulas are defined in terms of Schur Q-functions, the Haiman correspondence of B_n and D_n reduced words, and Stanley symmetric functions. We conclude with some conjectures for expanding products of Schubert polynomials in special cases, these special cases correspond to analogs of the Pieri rules for Schur functions. ****************************************************************** Wednesday, November 16, 4:15 p.m.; MIT, room 2-338 Timothy Chow (M.I.T.) The path-cycle symmetric function of a digraph R. Stanley has generalized the chromatic polynomial of a graph to a symmetric function. Independently, F. Chung and R. Graham have defined a digraph polynomial called the cover polynomial, which has close connections with chromatic polynomials and also rook polynomials. In this paper we imitate Stanley's construction to define a symmetric function generalization of the cover polynomial. We obtain generalizations and analogues of several results of Stanley, Chung and Graham, and others. In addition, we prove a combinatorial reciprocity theorem that unexpectedly ties together a number of results scattered in the literature that previously seemed unrelated, and we define a new symmetric function basis that appears to be a natural counterpart of the polynomial basis ${x+n\choose d}_{n=0,\ldots,d}$. From propp(at-sign)math.mit.edu Sun Nov 27 09:03:18 1994 To: combinatorics(at-sign)math.mit.edu Subject: Getzler, 11/30 (reminder) Wednesday, November 30, 4:15 p.m.; MIT, room 2-338 Ezra Getzler (M.I.T.) An analogue of the Fourier transform for symmetric functions Motivated by questions in mathematical physics (notably, the work of Kontsevich), Kapranov and I have studied the following problem. Given S_n-modules a(n), associate to a graph G the vector space a(G) given by tensoring together a copy of a(n) for each vertex of G of valence n, and then taking coinvariants under the automorphism group of G. Now sum a(G) over all graphs with given Euler characteristic. We derive a formula for the dimension of this vector space, using the theory of symmetric functions. This formula may be applied to calculate certain combinations of the Euler characteristics of moduli spaces of Riemann surfaces. From propp(at-sign)math.mit.edu Sun Nov 27 09:07:25 1994 To: combinatorics(at-sign)math.mit.edu Subject: Combinatorics seminar: December schedule MIT COMBINATORICS SEMINAR Here is the current, corrected list of talks scheduled for the month of December. Friday, December 2, 4:15 p.m.: Frank Sottile, Structure constants for Schubert polynomials Wednesday, December 7, 4:15 p.m.: Jay Goldman, Knots, tangles, and signed graphs Friday, December 9, 4:15 p.m.: Sergey Fomin, On the Littlewood-Richardson and Murnaghan-Nakayama Rules Wednesday, December 14, 4:15 p.m.: Herb Wilf, The problem of the kings Friday, December 16, 4:15 p.m.: William Jockusch, Some mysterious matrix factorizations All talks will meet in room 2-338. From propp(at-sign)math.mit.edu Sun Nov 27 09:13:26 1994 To: combinatorics(at-sign)math.mit.edu Subject: Sottile, 12/2 Friday, December 2, 4:15 p.m.; MIT, room 2-338 Frank Sottile (Toronto) Structure constants for Schubert polynomials Schubert polynomials originated from the study of flag varieties in algebraic geometry. Recently, many of their properties have been elucidated using combinatorics and algebra. A basic open problem is to give a rule for multiplying two Schubert polynomials, that is give a `Littlewood-Richardson'-type rule for their structure constants. In this talk, we will establish a formula that is the analog of Pieri's rule for Schubert polynomials. This had previously been conjectured by Bergeron and Billey. While our methods come from algebraic geometry, the proof we present involves only elementary (albeit complicated!) linear algebra. From propp(at-sign)math.mit.edu Thu Dec 1 To: combinatorics(at-sign)math.mit.edu Subject: Reminder This is just a reminder that the announcements for the talks of Jay Goldman and Frank Sottile got switched when they were first released. * Frank Sottile will be talking THIS WEEK (Friday). * Jay Goldman will be talking NEXT WEEK (Wednesday). Sorry for any confusion. Jim P.S. It's not too soon to request a slot in the combinatorics seminar this spring. We've already got a couple of speakers lined up. From propp(at-sign)math.mit.edu Thu Dec 1 18:52:11 1994 To: combinatorics(at-sign)math.mit.edu Subject: Goldman, 12/7 Wednesday, December 7, 4:15 p.m.; MIT, room 2-338 Jay Goldman (Minnesota and M.I.T.) Knots, tangles, and signed graphs The signed graphs of tangles or of tunnel links are two-terminal signed networks. The latter contain the two-terminal passive electrical networks. The conductance across the two terminals of such a signed network is defined, generalizing the classical electrical notion. The conductance is a topological invariant of the corresponding tangle or tunnel link. Series, parallel, and star triangle methods generalized from the electrical context yield the first natural interpretation of the graphical Reidemeister moves. The conductance is sensitive to detecting mirror images and linking. Conway's continued fraction of a rational tangle is a conductance and this leads to an elementary proof of Conway's classification of rational tangles. The conductance is related to evaluations of the Jones and Conway polynomials. From propp(at-sign)math.mit.edu Thu Dec 1 18:57:09 1994 To: combinatorics(at-sign)math.mit.edu Subject: Fomin, 12/9 Friday, December 9, 4:15 p.m.; MIT, room 2-338 Sergey Fomin (M.I.T.) On the Littlewood-Richardson and Murnaghan-Nakayama Rules The Murnaghan-Nakayama Rule is an explicit combinatorial rule for computing a value of an irreducible character of the symmetric group S_n on a given conjugacy class. The similar Littlewood- Richardson Rule describes the coefficients of an expansion of a skew representation of S_n into irreducibles. We use noncommutative Schur functions to generalize these rules to a large class of representations of S_n, including those related to stable Schubert/Grothendieck polynomials. Alternative versions of the classical L-R and M-N rules will also be given. Most of the new results are joint with Curtis Greene. From propp(at-sign)math.mit.edu Wed Dec 7 18:51:26 1994 To: combinatorics(at-sign)math.mit.edu Subject: Proposal: combinatorial free-for-all I am thinking of having a special "open mike" meeting of the combinatorics seminar this spring, in which people could give short presentations ("Is the following identity new?"; "Is there a technique for attacking the following kind of problem?"; "I'm looking for collaborators on the following project"; etc.). If someone wants to give a twenty-minute or half-hour talk to start things off, that might work too. Would such a meeting satisfy an unmet need? Jim From propp(at-sign)math.mit.edu Thu Dec 8 18:16:10 1994 To: combinatorics(at-sign)math.mit.edu Subject: Wilf, 12/14 Wednesday, December 14, 4:15 p.m.; MIT, room 2-338 Herb Wilf (Pennsylvania) The problem of the kings On a 2m by 2n chessboard, the maximum number of nonattacking kings that can be placed is mn. The question here is to determine f(m,n), which is the number of such placements. This question was raised by D. E. Knuth in the case m=n. Using the transfer matrix method, we first express the generating function of f(m,n) as the sum of the entries of x(I-x\Lambda)^{-1}, where the transfer matrix \Lambda is (m+1) 2^m by (m+1) 2^m$. Then we introduce a partial order on the configurations in such a way that the transfer matrix \Lambda becomes upper block triangular, and we discuss the spectra of the diagonal blocks. The result is that for each fixed m, we have f(m,n)=(c_mn+d_m)(m+1)^n+O(\theta_m^n) (as n goes to infinity), where |\theta_m| < m+1. Finally, we discuss also some related work on the problem by other researchers and some open questions. From propp(at-sign)math.mit.edu Thu Dec 8 18:25:11 1994 To: combinatorics(at-sign)math.mit.edu Subject: Jockusch, 12/16 Friday, December 16, 4:15 p.m.; MIT, room 2-338 William Jockusch (Michigan) Some mysterious matrix factorizations I will be presenting some mysterious matrix factorizations which arise in the study of Brauer's Centralizer Algebras and which I would like to better understand. I am hoping that someone in the audience will have seen something like them before or will have some ideas about what is going on. I hope this will be more of a dialogue than a talk.