Richard P. Stanley Seminar in Combinatorics

In Richard P. Stanley's 1986 text, {\sl Enumerative Combinatorics\/}, the following problem is posed: Fix a natural number $k$. Consider the posets $P$ of cardinality $n$ such that, for $0<i<n$, $P$ has exactly $k$ order ideals (down-sets) of cardinality $i$. Let $f_k(n)$ be the number of such posets. What is the generating function $\sum f_k(n) x^n$?

We solve this problem. (Joint work with Ryan Klippenstine.)

Coordinate rings of some natural geometrical objects (for example, Grassmannians) possess distinguished sets of generators (Plucker coordinates). Cluster algebras are generalizations of such coordinate rings. Sets of generators of a cluster algebra are organized in a tree-like structure with simple transformation rules between neighboring sets of generators.

Fomin and Zelevinsky obtained a complete classification for cluster algebras of finite type (i.e., with finite number of generators). This classification coincides with the Cartan-Killing classification of simple Lie algebras. We try to describe cluster algebras with finitely many transformation rules, so called cluster algebras of finite mutation type. We prove that a special class of cluster algebras originating from triangulation of Riemann surfaces is of finite mutation type.

This is joint work with Sergey Fomin.

Schubert varieties are classical objects of study in algebraic geometry; their study often reduces to easy-to-state combinatorial questions.

Gorensteinness is a well-known measure of the "pathology" of the singularities of an algebraic variety. Gorensteinness is a condition that is logically weaker than smoothness but stronger than Cohen-Macaulayness.

We present a non-recursive, combinatorial characterization of which Schubert varieties in the flag variety are Gorenstein. Our answer is in terms of generalized permutation pattern avoidance conditions.

I'll explain the algebraic geometric and representation (Borel-Weil) theoretic applications of this work. I will also describe further combinatorial questions.

This is a joint project with Alexander Woo, see math.AG/0409490.

The number of left to right minima of a permutation is generalized to Coxeter (and closely related) groups, via an interpretation as the number of "long factors" in canonical expressions of elements in the group.

This statistic is used to determine a covering map, which 'lifts' identities on the symmetric group $S_n$ to the alternating group $A_{n+1}$. The covering map is then extended to 'lift' known identities on $S_n$ to new identities on $S_{n+q-1}$ for every positive integer $q$, thus yielding $q$-analogues of the known $S_n$ identities.

Equi-distribution identities on certain families of pattern avoiding permutations follow. The cardinalities of subsets of permutations avoiding these patterns are given by extended Stirling and Bell numbers. The dual systems (determined by matrix inversion) have combinatorial realizations via statistics on colored permutations.

Joint with Amitai Regev.

Any Coxeter group G with string diagram is the automorphism group of an abstract regular polytope (typically infinite). When G is crystallographic, its standard real representation is easily reduced modulo an odd prime p, thus giving a finite representation in some finite orthogonal space V over $\Bbb F_p$. The finite group need not be polytopal; and whether or not it is depends in an intricate way on the geometry of V. The talk presents recent work with Barry Monson, in which we describe this construction in considerable generality and study in depth the interplay between the geometric properties of the polytope (if it exist) and the algebraic structure of the overlying finite orthogonal group. As a byproduct, we obtain many new maps on surfaces and even more interesting polytopes of higher rank.

In this talk, we'll give a simple combinatorial explanation of a formula of A. Postnikov relating bicolored rooted trees to bicolored binary trees. We'll also present generalized formula for the number of labeled k-ary trees, rooted labeled trees, and labeled plane trees. Combinatorial explanations of these formulas will be discussed too.

This is joint work with Ira Gessel.

The Probabilistic Method is a powerful tool in tackling many problems in Combinatorics and it belongs to those areas of mathematical research that have experienced a most impressive growth in recent years. One of the parts of discrete mathematics where this approach has proved to be especially useful is Extremal Combinatorics. In fact, many of the strongest results in this area in the last few decades are examples of this method.

In this talk we discuss a few recent applications of this methodology. In particular, we present simple but yet surprisingly powerful probabilistic arguments which were used recently to make progress on some long-standing Ramsey and Turan type problems.

The Bergman complex B(M) and the positive Bergman complex B+(M) of an oriented matroid M generalize to matroids the notions of tropical varieties and positive tropical varieties. Our main result is that if M is the oriented matroid of a Coxeter arrangement, then B(M) equals the nested set complex of that arrangement, and B+(M) is dual to the corresponding graph associahedron. This recovers Carr and Devadoss' tiling of the minimal blowup of a Coxeter complex by graph associahedra.

This is joint work with Federico Ardila and Vic Reiner.

Tropical geometry is the geometry of the tropical semiring $(\mathbb{R}, \min, +)$. Tropical varieties are polyhedral cell complexes which behave like complex algebraic varieties. The link between classical complex geometry and tropical geometry is provided by amoebas, which are logarithmic images of complex varieties.

In this talk, we begin with a combinatorially oriented review of some fundamental concepts in tropical geometry (aimed at a general audience), and then we turn towards some algorithmic problems concerning the intersection of tropical hypersurfaces in general dimension: deciding whether this intersection is nonempty, whether it is a tropical variety, and whether it is connected, as well as counting the number of connected components. We characterize the borderline between tractable and hard computations by proving NP-hardness and #P-hardness results even under various strong restrictions of the input data, as well as providing polynomial time

1. Ramsey Theory: Motivation, Results and Challenges
2. The Structure of Graphs and Grothendieck Type Inequalities
3. Property Testing and Approximation Algorithms

Many counting problems for graphs, codes, etc. are solved by appropriate specialisations of the Tutte polynomial. Suppose that we have a group of automorphisms of the structure in question, and we want to count orbits of this group acting on the appropriate objects. Is there a polynomial which does this? Two such polynomials have been proposed; the first combines the cycle index of the group with the Tutte polynomial, the second directly generalises the Tutte polynomial itself. The second example works only for matroids representable over a principal ideal domain, and is a multivariate generating function for the invariant factors of certain matrices.

This broadly-accessible talk will introduce certain finite collections of vectors in $2n$-dimensional Euclidean space with combinatorial and geometrical properties that are useful in the study of quantum logic. These configurations generalize the $4$-dimensional configurations employed by Peres (1993), Navara and Pt\'{a}k (2004), and others in various treatments of the Kochen-Specker theorem. We will discuss applications, including the characterization of certain group-valued measures on the closed subspaces of Hilbert space, and we will conclude with several open problems.

This work is joint with John Harding and Ekaterina Jager.

Local Weak Convergence method (LWC) exploits local structure (typically a tree) of a large random combinatorial object and leads to a complete asymptotic solutions to several optimization problems on random graphs. The method reduces the original problem into the problem of finding fixed points of a certain distributional operator. We show that when the fixed point of the second iterate of the distributional operator is unique, it determines the value of the underlying combinatorial optimization problem.

A finite graphs with large spectral gap are called expanders. These graphs have many nice properties and have many applications. It is easy to see that a random graph is an expander but constructing an explicit examples is very difficult. All known explicit constructions are based on the group theory --- if an infinite group G has property T (or its variants) then the Cayley graphs of its finite quotients form an expander family.

This leads to the following question: For which infinite families of groups G_i, it is possible to find generating sets S_i which makes the Cayley graphs expanders?

The answer of the question is known only in few case. It seems that if G_i are far enough from being abelian then the answer is YES. However if one takes 'standard' generating sets the resulting Cayley graphs are not expanders (in many cases).

I will describe a recent construction which answers the above question in the case of the family of all symmetric/alternating groups. It is possible to construct explicit generating sets S_n of Alt_n, such that the Cayley graphs C(Alt_n,S_n) are expanders, and the expanding constant can be estimated.

Unlike the usually constructions of expanders, the proof does not use an infinite group with property T (although such group exists) but uses the representation theory of the symmetric groups directly.