Richard P. Stanley Seminar in Combinatorics

Different statistics on the set of integer partitions of n appeared in the various part of mathematics. The main question arises what is the asymptiotic behaviour of the typical partitions when n tends to infinity. This type of probelms appeared in representation theory, combinatorics, integrable systems, statistical physics and so on. Will give a survey of the recent results on the wide class of statistics - so called multiplicative statistics (numbers of summands which are equal to the given number are infdependent).

The goal of this work is to give a new unified axiomatic approach to the representation theory of Coxeter groups and their Hecke algebras. Building upon fundamental works by Young, Kazhdan-Lusztig and Vershik, we propose a direct combinatorial construction, avoiding a priori use of external concepts (such as standard Young tableaux). This is carried out by a natural assumption on the representation matrices. For simply laced Coxeter groups, this assumption yields explicit simple matrices, generalizing the Young forms. For the symmetric groups (and for Weyl groups of type $B$) the resulting representations are completely classified and contain the irreducible ones. Analysis involves generalized descent classes and convexity (a la Tits) within the Hasse diagram of the weak Bruhat poset.

This a joint work with Ron Adin and Francesco Brenti.

Let a(z) be a polynomial having nonnegative integer coefficients, a constant term of one, and only real zeros. We will discuss the open problem of showing that the coefficients of a(z) count faces in a simplicial complex. This problem generalizes the recent result that the coefficients of a(z) count monomials in a multicomplex.

This is joint work with Jason Bell.

Tutte conjectured that any cubic, bipartite, and 3-connected graph is Hamiltonian. It is also natural to consider Tutte's conjecture for cubic, bipartite, and cyclically 4-connected graphs.

We discribe different constructions of cubic, bipartite, and 3-connected graphs having no Hamiltonian cycle. Some of these constructions provide (infinitely many) graphs that are not only 3-connected but, moreover, cyclically 4-connected. The minimal such graph has 50 vertices and this graph is a minimal known counterexample to Tutte's conjecture. Moreover by means of these constructions we prove that if Barnette's conjecture (any cubic, bipartite, 3-connected and planar graph is Hamiltonian) is true, then a much stronger result is also true.

No preparation is needed to understand this talk.

The aim of this talk is to give an introduction to rigged configurations. Rigged configurations were first introduced by Kerov, Kirillov and Reshetikhin in the 1980's in their study of the XXX model: rigged configurations are combinatorial objects which label the eigenvectors and eigenvalues of the XXX Hamiltonian obtained from the Bethe Ansatz. From the representation theoretic point of view, the XXX model can be described as a tensor product of GL_n representations. The number of eigenvectors should hence be equal to the number of highest weight elements. From the combinatorial point of view this correspondence is given by a bijection between rigged configurations and highest weight crystal paths. This bijection has many astonishing properties which we will discuss.

If time permits I will also mention a new rigged configuration bijection for type D.

Littlewood-Richardson numbers have a wide variety of interpretations in many fields. They arise in multiplying symmetric functions, so for example

$$ (\sum_{j=1}^n x_i)^2 = 1 \times \sum_{1 \leq i \leq j \leq n} x_i x_j + 1 \times \sum_{1 \leq i < j \leq n} x_i x_j $$

is an illustration that two Littlewood-Richardson numbers are $1$. They also arise in the representation theory of the symmetric group and the general linear group. A third fundamental description is geometric, in terms of the topology of the Grassmannian (the space of $k$-dimensional subspaces of an $n$-dimensional vector space). A Littlewood-Richardson rule is a combinatorial interpretation of Littlewood-Richardson numbers.

I will describe how to interpret Littlewood-Richardson numbers in terms of the Grassmannian, and then sketch an explicit geometric Littlewood-Richardson rule. (The combinatorics of the rule will be described completely, but the geometric description will avoid any technical background.)

This rule has straightforward bijections to other rules, such as tableaux and Knutson and Tao's puzzles. This rule has useful geometric and non-geometric consequences, including extensions to more general Littlewood-Richardson situations.

This talk is intended to be accessible to all graduate students, and assumes no prerequisites.

Let "Fred" be a finite partially ordered set, labelled by the numbers 1, 2, 3, up to $n$ so that, whenever an element $p$ is below an element $q$ in the poset, the label of $p$ (a natural number) is less than the label of $q$. (The permutation $123...n$ is a ``linear extension" of the poset Fred.)

For example, consider the zig-zag-shaped poset with four elements $1,2,3,4$, whose partial ordering is given by $1<3>2<4$.

Look at the linear extensions, that is, the permutations in $S_n$ that respect the partial ordering of Fred, by which we mean the following: If the element labelled $i$ in Fred is below the element labelled $j$ in Fred, then the number $i$ must come before the number $j$ in the permutation. In our example, there are 5 linear extensions: $1234$, $2134$, $1243$, $2143$, and $2413$.

Now take your favourite linear extension and count the number of descents, the number of places where a bigger number comes immediately before a smaller number. In our example, the number of descents in the linear extensions is given by 0, 1, 1, 2, and 1, respectively. Let $H_k$ be the set of linear extensions with $k$ descents and let $h_k$ be the number of such extensions. The zig-zag has $h_0=1$, $h_1=3$, and $h_2=1$.

The $h$-vector in this case---(1,3,1)---is symmetric. Around 1971 Stanley proved that the $h$-vector of a ranked poset is symmetric. At the 1981 Banff Conference on Ordered Sets, Stanley asked for a bijective proof of this fact. To wit, if a naturally-labelled poset of size $n$ is ranked (all maximal chains have the same number of elements $r+1$), Stanley wanted to find a bijection between the set of linear extensions with $k$ descents and the set of linear extensions with $n-1-r-k$ descents.

We establish such a bijection, thus solving Stanley's problem.

Abstract: For every Ferrers diagram one can construct a bipartite graph in a natural way. In this talk we introduce these graphs and calculate the number of spanning trees, the number of Hamiltonian paths, and the chromatic polynomial of such a graph. In particular, it transpires that formulas for the former two have simple combinatorial descriptions, whilst the latter is related to a set of permutations that satisfy certain criteria.

This is joint work with Richard Ehrenborg.

This is a survey talk on the noncommutative version of the classical theory of invariants and covariants of the symmetric group. We will present some recent results and list some open problems.

A brief review of the clasical theory of invariants and covariants of the symmetric group will be included in this talk.

Join work with Bruce Sagan, Christophe Reutenauer, and Michael Zabrocki.

The top to random shuffle is a method of shuffling cards which proceeds at each step by removing the top card and inserting it into a random position. We survey applications of the top to random shuffle to representation theory and combinatorics. Along the way we give an introduction to Stein's method (a remarkable technique for proving probabilistic limit theorems in situtations where exact enumeration fails). Finally, we give a new result on character ratios of symmetric groups. This talk should be accessible to a general audience.

Semistandard Young tableaux count characters of irreducible representations of SL_n. Littelmann paths count characters of irreducible representations of an arbitrary semi-simple Lie group. However, Littelmann paths are hard to work with. They have much more complicated characterization than, say, Young tableaux.

In this talk we present a general simple combinatorial formula for characters of irreducible representations. We also give a Chevalley-type formula for equivariant K-theory of generalized flag manifolds. Our combinatorial counterpart of a Littelmann path is an alcove path, which a sequence of adjacent alcoves for the affine Weyl group. The construction is given in terms of saturated chains in the Bruhat order. The Yang-Baxter equation also plays an important role in the construction.

This construction is just a tip on an iceberg. Alcoves for the affine Weyl group seem to have very interesting and rich combinatorial structure that is yet to be explored.

The talk in based on a joint work with Cristian Lenart. The preprint can be found at arXiv:math.RT/0309207. We will also mention some other results related to combinatorics of alcoves, including joint results with Thomas Lam.

The talk should be accessible for graduate students.

Geometric group theorists and geometric combinatorialists have long studied the same types of objects with the same types of tools -- most importantly for this talk posets, their order complexes and the topology of the results. In recent years geometric group theorists have also started putting metrics on these complexes and using the curvature and geometry which result in order to investigate their structure. In this talk I will briefly introduce the notions of a Gromov hyperbolic group and a non-positively curved group and report on some results connecting these concepts to the combinatorics of posets. Finally, if time permits I will also comment about where this line of research seems to be heading.

Many interesting sets can be expressed as the projection of the set integer points in a polyhedron. The Frobenius semigroup is a good example: let S be the set of all numbers representable as a nonnegative integer combination of given coprime positive integers a_1,...,a_d. What is the largest integer not in S? How many positive integers are not in S? For any fixed d, these questions and others admit polynomial time algorithms. Our main tool is the following theorem: for fixed d, the generating function of the projection of the set of integer points in a d-dimensional polytope is computable in polynomial time. We use this to find the generating function of S, as well as of other interesting sets of lattice points, such as minimal Hilbert bases and test sets for integer programming.

The Kostka numbers $K_{\lambda\mu}$ appear in combinatorics when expressing the Schur functions in terms of the monomial symmetric functions, as $K_{\lambda\mu}$ counts the number of semistandard Young tableaux of shape $\lambda$ and content $\mu$. They also appear in representation theory as the multiplicities of weights in the irreducible representations of type $A$.

Using a variety of tools from representation theory (Gelfand-Tsetlin diagrams), convex geometry (vector partition functions), symplectic geometry (Duistermaat-Heckman measure) and combinatorics (hyperplane arrangements), we show that the Kostka numbers are given by polynomials in the cells of a complex of cones. For fixed $\lambda$, the nonzero $K_{\lambda\mu}$ consist of the lattice points inside a permutahedron. By relating the complex of cones to a family of hyperplane arrangements, we provide an explanation for why the polynomials giving the Kostka numbers exhibit interesting factorization patterns in the boundary regions of the permutahedron. We will consider $A_2$ and $A_3$ (partitions with at most three and four parts) as running examples, with lots of pictures.

I will also say a few words as to how some of the techniques used generalize to the case of Littlewood-Richardson coefficients.

This is joint work with Sara Billey and Victor Guillemin.

Within the last few years there has been an interest in the literature on spaces which generalize and are analogous to the algebra of symmetric functions. We will give a survey that will be of interest to a general audience of some of these spaces: the non-commmutative symmetric functions of Gelfand/Krob/Lascoux/Leclerc/Retakh/Thibon/et al., the non-commutative symmetric functions of Rosas/Sagan, the quasi-symmetric functions of Gessel, the Malvenuto-Reutenauer algebra of permutations and a new space which we call the non-commutative quasi-symmetric functions.

The purpose of this talk will be to show how these spaces relate to each other and to describe how posets on the indexing set are used to define bases of these spaces with interesting algebraic properties.

This is joint work with Nantel Bergeron

A graph is distance transitive if given two pairs of vertices at the same distance, there exists an automorphism taking the first pair to the second. There are many interesting examples. There is an ongoing project to classify finite distance transitive graphs. A closely related problem is concerned with permutation representations of groups in which all the irreducible constituents are distinct (also known as Gelfand pairs). The talk will report on some of the steps in these projects.

A T-tetromino is the figure formed by attaching four unit squares together in the shape of a T. In this talk we consider the problem of tiling a region with T-tetrominoes. We show that for a particular class of regions, the number of T-tetromino tilings is an evaluation of the Tutte polynomial of a graph related to the region. Furthermore, using a height-function approach, we show that the set of all T-tetromino tilings of such a region forms a distributive lattice, and that any two tilings of such a region are connected by local moves. Along the way we observe connections to the square-ice model of statistical mechanics, domino tilings, and alternating-sign matrices. Joint work with Igor Pak.

Although firmly rooted in analysis on infinite dimensional Hilbert space, planar algebras present a huge variety of combinatorial problems, including counting planar and less planar configurations, solving large systems of linear equations, generating functions, the structure of associative algebras and the asymptotics of random walks on graphs. I will give the definition of a planar algebra and indicate how each of the above problems is encountered.

The first part of the talk will give a survey of some of the main results and conjectures in the subject of restricted (or pattern-avoiding) permutations. Next, recent developments and new directions will be discussed, including simultaneous avoidance of several patterns, enumeration of occurrences of a particular pattern in permutations, and generalized patterns (i.e., with the requirement that some elements occur in adjacent positions). The last part of the talk will focus on the study of statistics in restricted permutations, in which bijections to Dyck paths play an important role. We will discuss recent work with Emeric Deutsch, Toufik Mansour and Igor Pak.

We will start with a definition of a group generated by a finite automaton. A few interesting examples will be given including torsion groups of intermediate growth, Basilica group and the lamplighter group.

Then we will focus on the last example and describe the spectrum of discrete Laplace operator on Cayley grap of this group. The information about spectrum will be used to solve one question of M.Atiayh on range of L^2-Betti numbers.

We do not assume any knowledge of the L^-cohomology. The talk should be accessible to a general audience.

The classical Iwahori-Hecke algebra for $G=GL_n(F_q)$ can be thought of as a $q$-analog of the symmetric group $S_n$. It has generators indexed by simple reflections, relations that generalize the symmetric group's braid relations, and a representation theory with a strong connection to Young tableaux. Unipotent Hecke algebras are a family of Hecke algebras that generalize the Iwahori-Hecke algebra by substituting the unipotent subgroup $U$ (upper-triangular matrices with ones on the diagonal) for the Borel subgroup $B$ (upper-triangular matrices) in the Hecke algebra construction.

This talk defines unipotent Hecke algebras and analyzes some combinatorial implications of their construction. In particular, I construct an explicit basis, and describe a skein model for multiplying these basis elements (analogous to the braid relations above). Finally, the representation theory of unipotent Hecke algebras leads to a generalization of the RSK-insertion correspondence that associates monomial matrices to pairs of column strict multi-tableaux. While a large portion of this talk addresses the $G=GL_n(F_q)$ case, the unipotent Hecke algebra construction and skein model generalize to arbitrary finite groups of Lie type.

We study the Bergman complex B(M) of a matroid M: a polyhedral complex which arises in algebraic geometry, but which we describe purely combinatorially. We prove that a natural subdivision of the Bergman complex of M is a geometric realization of the order complex of its lattice of flats. In addition, we show that the Bergman fan B'(K_n) of the graphical matroid of the complete graph K_n is homeomorphic to the space of phylogenetic trees T_n.

The talk will be self-contained and accesible to a general audience.

This is joint work with Carly Klivans.

A geometric (topological) graph is a graph drawn in the plane so that its vertices are represented by points and its edges by segments (curves) connecting the corresponding points. It follows from Euler's formula that every geometric (topological) graph with no two crossing edges has at most $3n-6$ edges. How far can we relax this simple condition so that it still implies that we have at most a linear number of edges?

I will survey some known results and open problems on this subject. Among others, I will estimate the maximum number of edges of a geometric (topological) graph if there is no edge crossed by 2, 3, 4, and in general, by $k$ edges. I will also sketch the proof that if we do not have three pairwise crossing edges, then we still have a linear number of edges.

As an application, I show how this is connected, through the well known Crossing Lemma of Ajtai, Chvatal, Newborn, Szemeredi, and Leighton, to many problems in discrete and computational geometry.

If the time allows, I will also sketch the proof that any topological graph on $n$ vertices and $\Omega (n^{8/5})$ edges contains a self-crossing cycle of length four, with further applications.

Joint work with subsets of {J. Pach, R. Pinchasi, G. Tardos and G. Toth}.

I will talk about convex polytopes which are unions of alcoves of an affine Coxeter arrangement. The motivating examples are two triangulations of the hypersimplex given by Stanley and Sturmfels respectively. The volume of the hypersimplex is an Eulerian number and this allows us to define generalised `descents' and Eulerian numbers for all Weyl groups. Other aspects of these polytopes I will talk about are formulae for their volumes, Groebner bases which lead to these triangulations, and connections with matroids and with geometry.

This is joint work with Alex Postnikov.