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

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 EST
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 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.
`