Richard P. Stanley Seminar in Combinatorics

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.)

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.

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.

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.

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).

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.

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.

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.

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.

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.)

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

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.

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.

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.

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.

We are concerned with U(q), the class of matroids containing no minor isomorphic to the (q+2)-point line. This class is of interest in part because of its connections with representability questions and its role in extremal matroid theory, in particular, in connection with size functions.

For any prime power q, L(q) is a subset of U(q), where L(q) is the class of matroids representable over GF(q). In 1958, Tutte proved that L(2) = U(2). We will give a new proof of Tutte's theorem and sketch several other applications of the techniques used.

For prime powers q>2, the (q+2)-point line is not the only excluded minor for GF(q)-representability. However, we show that with enough points in a geometry, the (q+2)-point line is the only minor one must exclude to guarantee that the geometry is representable over GF(q). Indeed, such geometries are uniquely representable over GF(q). We will apply these ideas to bound the size function of U(q) and to obtain a simple counting characterization of affine space.

In earlier work it was shown that the Aztec diamond of order n has 2^{n(n+1)/2} domino-tilings, and connections were established with monotone triangles and alternating sign matrices. In this talk I will describe follow-up work that establishes formulas for the number of domino-tilings of a ``quarter'' of an Aztec diamond of order n, with different formulas depending on exactly how the quartering is done as well as on the residue of n mod 4.

This turns out to be a special case of a more general enumeration problem, where the number of domino-tilings of a certain kind of region is always equal to a power of 2 times the dimension of a particular representation of a Lie algebra. Our method of proof uses a weighted count of certain sorts of monotone triangles. Interestingly, if one considers other enumeration problems for these monotone triangles, one gets conjectural product-formulas that generalize earlier conjectures of Mills, Robbins and Rumsey.

This is joint work with Jim Propp.

A classic elementary problem with a surprise answer is the following: if a circular key ring holds n identically shaped keys, and in order to tell them apart, we plan to affix to each one a colored label, what is the minimum number of different colors needed to distinguish the keys? The surprise is that if n is at least 6, there need only be 2 different colors of labels; but if there are three, four, or five keys on the ring, there must be 3 different colors of labels. If we consider the keys as vertices in the n-cycle, then the effect of the labels on the vertices is to destroy every symmetry of the n-cycle.

Define a labeling of a graph G, l:V(G) --> {1,2,...,r}, to be _r-distinguishing_ if no automorphism of G preserves all of the vertex labels. Then a natural question is, for any graph G, what is the minimum r such that G is r-distinguished? For an n-cycle, the answer is 3 if n=3,4,5 and 2 if n is at least 6. For a complete graph on m vertices, the answer is m. We give a bound on the minimum distinguishing number of a graph in terms of the order of its automorphism group, as well as finding the distinguishing numbers of graphs whose automorphism groups are abelian, dihedral, S_3, or S_4.

This is joint work with Michael Albertson.

Dowling lattices arose in connection with the theory of linear codes and as q-analogs of partition lattices, and they were quickly seen to be of use for studying arrangements of hyperplanes. These geometric lattices also provided the motivation for biased graphs, and, like projective spaces and free matroids, they are the universal models for one of the five types of varieties of combinatorial geometries. This talk will provide an introduction to these lattices and will outline several recent advances in the theory.

The first class of results to be treated brings out similarities between Dowling lattices and projective spaces. This includes an axiom scheme for Dowling lattices, analogs of Desargues' and Pappus' theorems, and a coordinatization theory analogous to that for projective spaces. We will also present an application of the automorphism theory for Dowling lattices.

The second collection of results to be discussed involves the Tutte polynomial, the matroid counterpart of the dichromatic polynomial of graph theory. The Tutte polynomial of any matroid contains much information about the matroid, and this is especially true for Dowling lattices. We will explore exactly how much information about a Dowling lattice is reflected in its Tutte polynomial.

Sequences obeying a(n) = a(a(n-1))+a(n-a(n-1)) have been explored by Conway, Hofstadter, Mallows, Kleitman and others. They have beautiful and intricate properties: combinatorial (symmetry, self-similarity), analytic (asymptotics related to the Gaussian distribution), and arithmetic (e.g., a(2^n)=2^{n-1}). We will show that a(n) can be viewed not as a complicated sequence, but as a simple compression operation on finite sets. Combinatorial structures including trees, Fibonacci and Catalan numbers, refinements of Pascal's triangle, and a mysterious appearance of Nim-like games, are encountered on the way. (These results were obtained in collaboration with R. Vakil.)

The classical theory of Elliptic Functions gives rise to many interesting theta function identities such as P(b+e) P(b-e) P(c+d) P(c-d) - P(b+d) P(b-d) P(c+e) P(c-e) + q^(c-d) P(b+c) P(b-c) P(d+e) P(d-e) = 0, where P is a rescaled version of Jacobi's third theta function. The proofs of these identities typically are analytic, or rely on invoking standard facts about the finite dimensional space of modular forms of a given weight. Other theta function identities, like Jacobi's Triple Product which factors a theta function into three infinite products, have nice combinatorial interpretations and proofs. In this talk I will discuss a simple "symmetric function theory" proof of a generalization of the former identity. The technique involves expressing the combination of theta functions as the Pfaffian of a 4 by 4 skew-symmetric matrix, and then expanding the Pfaffian as a (vanishing) sum of alternants. Finally, we generalize the proof to give interesting expansions for Pfaffians of other "theta-like" functions.

The original characterization for when a graph can be decomposed into k spanning forests was given by Nash-Williams in 1964. In this talk we give several old and new characterizations for the following two classes of graphs: (i) graphs for which adding _some_ m edges produces a graph which is decomposable into k spanning trees, i.e., the graph has arboricity k; and (ii) graphs for which adding _any_ m edges produces a graph which is decomposable into k spanning trees.

The study of the second of these is motivated by some results in combinatorial rigidity. In particular, a graph is rigid in the plane if it can be "constructed" using rigid bars for the edges and rotatable joints for the vertices so that the only possible motions in the plane are translation and rotation. Lovasz and Yemini showed that a graph is minimally rigid in the plane (removal of any edge would make it not rigid) if and only if adding any edge to the graph, including a multiple edge results in a graph which is decomposable into 2 spanning trees. A recent paper of Crapo gives another characterization of this class and it is this characterization that we extend to other cases.

Let V be a q-dimensional vector space. Fix a set B of q(q-1) monomials in S^p(V) of the form x^I where i_k>0 for all k. The generic element of S^p(V) is conjugate under a suitable linear transformation to an element with support off of B. We prove this by showing the existence of a perfect matching with a unique weight in a certain weighted bipartite graph. Such a perfect matching corresponds to the non-vanishing of an appropriate determinant.

This is joint work with Jozsef Losonczy.

Robbins conjectured, and Zeilberger recently proved, that there are

             1!4!7!...(3n-2)!
            ------------------
            n!(n+1)!...(2n-1)!
        

alternating sign matrices of order n. We will discuss a new proof of this result using an analysis of the six-vertex state model (also called square ice) based on the Yang-Baxter equation.

Abstract: A (real) hyperplane arrangement is a finite set of affine hyperplanes in R^n. A central problem in the theory of hyperplane arrangements is to count the number of regions into which the hyperplanes subdivide R^n. For instance, the number of regions of the arrangement (known as the _braid_arrangement_) consisting of all hyperplanes x_i = x_j, i<j, is easily seen to be n!. We will consider some modifications (deformations) of the braid arrangement and show some surprising connections with such topics as interval orders and the enumeration of trees. In particular, there is an explicit conjecture for the number of regions of the arrangement x_i - x_j=1, i<j. Much of this work was done in collaboration with Nati Linial, Igor Pak, Alexander Postnikov, and Schmulik Ravid.

The number of unlabeled binary trees on n vertices is the Catalan number C_n={1 \over n+1}{2n \choose n}, so the number of labeled binary trees is n! C_n. We call a vertex of a labeled binary tree (with totally ordered vertices) a _left_ascent_ if it is a left child and is greater than its parent, and we define right ascents and left and right descents similarly.

In this talk I will count labeled binary trees by left and right ascents and descents. Special cases yield Eulerian numbers and the number (n+1)^{n-1} of labeled rooted forests. There are also some non-obvious symmetries: There is a symmetry that switches left ascents with right descents, and by allowing repeated labels we obtain symmetric functions which I conjecture to be Schur-positive.

It is a long-studied, hard problem to determine how many permutations in S_n avoid a certain pattern q. The general conjecture claims that less than K^n, where K is a constant. Efforts to prove this have been unsuccessful for most patterns. (For two permutations a and b, it is NP-complete to decide whether a is a pattern of b; the problem of counting permutations in S_n avoiding q is #P-complete. Thus in general all we can expect is an upper bound or an asymptotical formula, not an exact formula). The only important cases in which the conjecture is known to be true were when k = 3 or when the pattern is monotonic. We improve these results showing that the_conjecture_on_the_exponential_ upper_bound_is_true_for_all_patterns_of_length_4.

A conjecture states that if S_n(q_1) < S_n(q_2) for some n, then this inequality holds for all N > n. We prove this conjecture for patterns of length 4. These are the first results proving that one pattern is more likely to occur in a random permutation than another one. (Even in the asymptotical sense). Finally, we prove a lemma which allows us to extend our results to some longer patterns.

This question was solved for the complex case in 1986 by Harer and Zagier. A later argument was given by Penner. The real case, however, has remained open. In this talk I will give two arguments, that are combinatorial ones, which appeal 2-cell embeddings of graphs.

The first argument is based on determining the genus series for monopoles (these are maps with one vertex) in locally orientable surfaces. This is of interest in its own right.

The moduli space question can be expressed as a particular monopole problem (joint work with Goulden and Harer). This second problem can be treated by a classical theorem about multivariate integrals, to give a very simple explicit expression for the Euler characteristic.

The integral representation for the case of orientable surfaces can also be given, and this gives a proof of the original result of Harer and Zagier that is direct.

Here's another chance to share partial results, open questions, and nice ideas that aren't suited to the 50-minute talk format. Presenters will include Gian-Carlo Rota, Dan Kleitman, and Christos Athanasiadis. Let Jim Propp know ahead of time what you're bringing, if you plan on presenting something that will take longer than five minutes.

Part I: The Cliffordization of Hopf algebras

Part II: Explicit formulas for resultants

A formula for the resultant of n homogoneous polynomials will be given. This formula can be used to derive all known properties of resultants without recourse to elimination theory.

Those who attend are expected to know basic notation of Hopf algebras.

The label "regular polytope" can be applied to objects ranging from Platonic solids to simplicial complexes. The object of this talk is to describe methods of taking regular maps --- regularly tiled 2-manifolds --- and embedding the vertices of the tilings in Euclidean space to form objects called regular skew polyhedra. These polyhedra have all the symmetries dictated by the automorphism group of the underlying manifold, but may not have planar faces. They need not even lie in three dimensional space!

For example, a sphere can be regularly tiled with pentagons. One realization of this map is the dodecahedron. More interestingly, a torus can be tiled with squares. As Coxeter and Petrie discovered in 1926, this map can be realized in four dimensions as a polyhedral surface with square faces and "skew square" vertex figures.

In my talk I will describe more skew polyhedra, and review the methods I used to discover them. These methods, involving association schemes and representation theory, can be extended to provide symmetric realizations of any graph or polytope whose automorphism group is vertex-transitive.