Richard P. Stanley Seminar in Combinatorics

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.

In their seminal work which initiated random graph theory Erd\"os and R\'enyi discovered that many graph properties have sharp thresholds as the number of vertices tends to infinity. That is, if every edge of the graph is chosen with probability $p$, then when $p$ increases, the transition from a property being very unlikely to its being very likely is very swift.

We prove a conjecture of Linial that every monotone graph property has a sharp threshold. This result applies to random subgraphs of arbitrary symmetric graphs. We will discuss the relation between the symmetry group and the length of the transition interval.

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.