Richard P. Stanley Seminar in Combinatorics

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.

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.

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.

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.

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}$.

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.

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.

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.

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.

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.

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.