Richard P. Stanley Seminar in Combinatorics

For a graph, we construct two algebras, whose dimensions are both equal to the number of spanning trees of the graph. One of these algebras is the quotient of the polynomial ring modulo certain monomial ideal, while the other is the quotient of the polynomial ring modulo certain powers of linear forms. We describe a monomial basis of these two algebras. The basis elements correspond to G-parking functions that naturally came up in the abelian sandpile model. These ideals are instances of the general class of ideals associated with posets and their deformations. Hilbert series of such ideals are always bounded by the Hilbert series of their deformations. We prove several formulas for Hilbert series of these ideals and construct their minimal free resolutions in terms of the order complex of the poset.

This is a joint work with Boris Shapiro.

The f-vector enumerates the number of faces of a convex polytope according to dimension. The flag f-vector is a refinement of the f-vector since it enumerates face incidences of the polytope. To classify the set of flag f-vectors of polytopes is an open problem in discrete geometry. This was settled for 3-dimensional polytopes by Steinitz a century ago. However, already in dimension 4 the problem is open.

We will discuss the known linear inequalities for the flag f-vector of polytopes. These inequalities include the non-negativity of the toric g-vector, that the simplex minimizes the cd-index, and the Kalai convolution of inequalities.

We will introduce a method of lifting inequalities from lower dimensional polytopes to higher dimensions. As a result we obtain two new inequalities for 6-dimensional polytopes.

The talk will be accessible to a general audience.

Given a polytope $P\subset\mathbb{R}^d$ and a generic linear functional $f$, we can describe an orientation of the graph of $P$ by orienting each edge towards the vertex on which $f$ is larger. We will survey the known results on so-called LP-orientations. Chief among these is the Holt-Klee condition, which states that on every $k$-dimensional face of a polytope an LP-orientation contains at least $k$ vertex-disjoint paths from source to sink. We will investigate the case of cubes and cross-polytopes, showing that the percentage of Holt-Klee orientations of the $n$-cube which are LP goes to 0 as $n$ goes to infinity.

No prior knowledge of polytopes or LP-orientations will be assumed.

A family of polynomials {P_n} such that P_n has degree n is a basis for the polynomial ring. A product

P_{n_1} P_{n_2} ... P_{n_k}

can be expanded in this basis, and the coefficients in this expansion are called linearization coefficients. If the basis consists of orthogonal polynomials, these coefficients are generalizations of the moments of the measure of orthogonality. Just like moments, these coefficients have combinatorial significance for many classical families. For instance, for the Hermite polynomials they are the numbers of inhomogeneous matchings.

After giving a brief introduction to the general theory of orthogonal polynomials, I will describe some families for which the linearization coefficients are known. These include Hermite, Charlier, Laguerre, Meixner, Chebyshev, and some q-interpolated families. In the second half of the talk, I will describe one method that can be used to calculate many of these coefficients. The method is only slightly combinatorial; instead, it is based on the partition-dependent stochastic measures of Rota and Wallstrom.

No prior knowledge of the material will be assumed.

There is a rich and highly-developed combinatorial theory for for Schur functions (Young tableaux, the Littlewood-Richardson Rule, etc), but one can argue that it suffers from a few too many seemingly arbitrary choices and miracles.

On the other hand, Kashiwara's theory of crystal bases for quantum groups comes close to subsuming this theory, and at the same time is (a) canonical and (b) has a much greater range of applicability (namely, to the representations of semisimple Lie groups and algebras and their quantum analogues).

The main goal of our talk will be to explain that Kashiwara's theory can be developed at a purely combinatorial level, and need not rely on any of the representation theory of quantum groups. Even in type A, this leads to a more natural understanding of the combinatorics of Schur functions. Along the way, we hope to mention an open problem or two.

Buch and Fulton defined quiver polynomials in a geometric context, and proved that these polynomials can be expressed as integer sums of products of Schur functions in differences of alphabets. Motivated by the fact that Littlewood-Richardson numbers are (very) special cases of the integer 'quiver coefficients' appearing in these sums, Buch and Fulton conjectured that all quiver coefficients are positive, and moreover described certain 'factor sequenes' of Young tableaux that they should count.

The first thing I'll do in this talk is present an elementary definition of quiver polynomials, with no reference to geometry, in terms of combinatorial permutation diagrams called 'pipe dreams' ('rc-graphs'). Then I'll talk about the algebraic combinatorics that goes into extracting sequences of Young tableaux from them. It would help to know what Schur functions and Young tableaux are, but everything else I'll define from scratch. This talk concerns joint work with Allen Knutson and Mark Shimozono.

Let $G=(V,E)$ be a graph. A {\em picture} of $G$ consists of a point for each vertex in $V$ and a line for each edge in $E$, subject to containment conditions given by incidence in $G$. The space of all pictures has some very interesting combinatorial properties. Using elementary techniques, we can show that the polynomial equations constraining the possible slopes of the lines are generating functions for certain kinds of trees in $G$. In the case that $G$ is the complete graph of $K_n$, we can translate the algebraic problem into a combinatorial one using the theory of Stanley-Reisner simplicial complexes (which we will explain). Our results include some unexpected connections between the geometry of pictures of $K_n$ and the combinatorics of matchings and rooted trees.

The talk will be as combinatorial as possible and accessible to graduate students

An infinite sequence of finite regular graphs of a fixed degree $k$ is called a family of {\it expanders} if the eigenvalue gap of every graph in the sequence is bounded away from $0$ by a constant which depends only on $k$. Explicit constructions of such families have found extensive use in efficient planning of networks and other applications.

The best possible exapnders are called {\it Ramanujan graphs}. The main open problem about Ramanujan graphs is the existence of infinite families of Ramanujan graphs of fixed degree $k$, for every $k\geq 3$.

An introduction into Ramanujan graphs will be given in the first part of the talk. In the second part of the talk I will report on a joint work with Alex Lubotzky in which we study the problem of existense of infinite families of Ramanujan graphs in the class of all finite (not necessarily regular) graphs.

I will also report on some results on random walks on infinite trees which allow to decide algorithmically whether a given finite graph is Ramanujan.

The talk should be accessible to a broad audience.

Characteristic polynomials of random unitary matrices have been intensively studied in recent years: by number theorists in connection with Riemann zeta-function, and by theoretical physicists in connection with Quantum Chaos. In particular, Haake and collaborators have computed the variance of the coefficients of these polynomials and raised the question of computing the higher moments. The answer, obtained in recent joint work with Persi Diaconis, turns out to be intimately related to counting integer stochastic matrices (magic squares).

The talk will be accessible to a general audience

Alternating-sign matrices form a well-known class of combinatorial objects that is worth enumerating. The matrices themselves and the conjecture for their number were discovered by Mills, Robbins and Rumsey; the conjecture was first proved by Doron Zeilberger. Shortly after Zeilberger's proof was confirmed, I found another proof based on the Yang-Baxter equation and the Izergin-Korepin determinant.

But this one conjecture is not the end of the story. Robbins (in one case, Mills) also studied symmetry classes of alternating-sign matrices, by analogy with symmetry classes of plane partitions. Many of these symmetry classes also have round (i.e. smooth) enumerations according to conjecture and computer experiments. I will describe my program to generalize the Izergin-Korepin determinant and its evaluation to these other symmetry classes. So far the method only enumerates some of the symmetry classes listed by Robbins, but it also leads to new classes of matrices that can also be enumerated. Moreover, alternating-sign matrices could be only the sl(2) case of constructions in quantum algebra that generalize to many complex simple Lie algebras.

In 2001, a purely combinatorial proof of the Schur positivity of the Stanley Symmetric functions was discovered. This proof appeared in the form of a bijection between reduced factorizations of permutations related by the Lascoux-Schutzenberger Tree. Subsequently, many remarkable properties of this bijection have been revealed. In this talk we will discuss the connection between our bijection and the classic bijections of Robinson-Schensted and Edelman-Greene. Throughout the talk, we will make use of an Applet which has proved to be invaluable in the discovery of many of these properties.

We will discuss the Rogers-Ramanujan identities, their origin and some new developments in partition identities of Rogers-Ramanujan type.

We will survey some past work upper bounding the number of cuts in a graph whose value (number of edges) is close to the minimum cut value. We describe two distinct techniques that give an upper bound, tight to within a constant factor, on this quantity as a function of the number of graph vertices and the value of the cut.

With this bound in hand, we generalize a classical result of Erdos and Renyi, that a random graph on n vertices is connected with high probability once it has n log n edges. We show that a similar result holds for random edge-subgraphs of any graph: if the expected number of edges crossing each cut exceeds log n, then the subgraph will be connected with high probability. These results generalize to yield tight approximations to the Tutte Polynomial on a large region of the Tutte Plane.

We describe a general setup for inverse problems on directed graphs. The inspiration comes from work in Optical Tomography, where the graphs that arise are very complicated (nonplanar with lots of cycles) but nevertheless the inverse problem can be solved. This is joint work (in progress) with Alberto Grunbaum.

This talk is about combinatorial aspects of the theory of cluster algebras initiated by Sergey Fomin and myself three years ago. We shall discuss a family of piecewise-linear transformations (called mutations) of integer matrices. The classification of matrices with certain finiteness property preserved under mutations turns out to provide a new instance of the famous Cartan-Killing classification.

Let $L$ be a finite distributive lattice. (One could think of $L$ as the family of order ideals---or downward-closed subsets---of a finite partially ordered set, ordered by set-inclusion.) Let $f_i$ be the number of $i+1$-element chains (totally ordered subsets) of $L$.

One of the main implications of the Stanley--Neggers Conjecture is that the $f$-vector---the sequence $f_{-1}$, $f_0$, $f_1$, \dots, $f_h$---is unimodal, where $h$ is the ``rank" or height of the lattice $L$.

We prove that the unimodality conjecture is "three-quarters true" (joint work with Anders Bj\"orner): that is, the first half of the sequence is increasing, and the last quarter of the sequence is decreasing.

We use the fact that the symmetric group $S_h$ with the weak Bruhat order is a bounded-homomorphic image of a finitely-generated free lattice, a so-called "bounded" lattice in the sense of McKenzie.

We present some vague ideas for constructing a counter-example to the Stanley--Neggers conjecture.

Polytopes, simplicial complexes, and matchings arise.

The talk contains interesting open problems for graduate students and will be accessible to a general audience.

In 1998, Watts and Strogatz observed that many large-scale real-world networks, including neural networks, power grids, collaboration graphs, and the internet, have numerous common features that resemble properties of random graphs. It was also realized that the standard mean-field and lattice-based random graphs are not appropriate models of these large-scale networks, so we should look for other classes of random graphs. One of the main features demanded of these new random graphs is that they should be scale-free. The first such model was introduced by Barabasi and Albert in 1999; by now, numerous models of scale-free random graphs have been proposed and studied, mostly by computer simulations and heuristic analysis.

In the talk we shall review a number of these models, and present several recent rigorous results obtained jointly with Oliver Riordan, and some other results proved with Noam Berger, Christian Borgs, Jennifer Chayes and Oliver Riordan.

Littlewood-Richardson coefficients are fundamental numbers in algebraic combinatorics. They appear in the theory of symmetric functions, in the representation theory of symmetric and general linear groups, in Schubert calculus, and other areas.

In this talk we will review three mayor combinatorial interpretations of Littlewood-Richardson coefficients, namely LR tableaux, hives, and Berenstein-Zelevinsky triangles. We view the three of them as integer points in certain cones, and present simple linear maps between them, which produce explicit bijections for all triples of partitions involved in the Littlewood-Richardson rule.

The goal of the talk is to explain few basic algebraic facts underlying representation theory of symmetric groups (the ideas are the same in characteristic 0 and p, for linear and projective representations, for Hecke algebras and affine Hecke algebras, etc. but we will concentrate on symmetric groups for simplicity).

The key object is a maximal commutative subalgebra of the group algebra of the symmetric group which plays a role of a "maximal torus". Considering the corresponding "weight spaces" and "formal characters" leads to familiar combinatorial objects (partitions, Young tableaux, cores, etc.) However, these notions are nothing more than just one of several convenient combinatorial languages and the theory can be constructed from scratch using "Lie theoretic approach".

The talk is bases on the work of Ariki, Grojnovski, Okounkov-Vershik, the speaker and the others.

At least half of the talk requires nothing more than elemntary facts on representations of groups.

The Wronski map associates to a $p$-tuple $Q=(q_1(x),\dots,q_p(x))$ of polynomials of degree at most $m+p-1$ their Wronski determinant $W(Q)$. If the polynomials are linearly independent, they define a $p$-dimensional subspace in the space of all polynomials, i.e., a point in the Grassmannian $G(p,m+p)$. Basic properties of the Wronskian imply that the Wronski map can be considered as a map from $G(p,m+p)$ to the projective space ${\bf P}^{mp}$. It respects the Schubert cell decomposition of $G(p,m+p)$, sending each cell $S$ to a projective subspace of the same dimension as $S$. The map is finite, and one can define its degree.

In the complex case, the degree of the Wronski map equals the number of standard tableaux for the Young diagram of a Schubert cell. In the real case, standard tableax should be counted with the signs depending on the number of inversions. For a rectangular Young diagram of the Grassmannian $G(p,m+p)$, the real degree is zero when $m+p$ is even, and equals the number of standard shifted Young tableaux for an appropriately defined shifted Young diagram when $m+p$ is odd. For $p=2$, the complex degree for the Grassmannian is $m$-th Catalan number, and the real degree is $\frac{m-1}{2}$-th Catalan number for odd $m$ and zero otherwise.

For a general Schubert cell, a closed form for the real degree is unknown. In particular, a question when this degree is not zero remains open. The answer to this question is important in applications to real Schubert calculus and to the pole placement problem in control theory.

Joint work with Alex Eremenko.

P.S. Most of the talk is linear algebra and manipulations with polynomials, and should be understandable by students.

The decomposition of tensor products of an irreducible representation with the standard representation of a classical Lie group can be easily described via Young tableau combinatorics. In particular, this induces a partial order on the representations of classical Lie groups. It is fairly straightforward to define similar partial orders via other representations or for other Lie groups. We present examples for which this can be done again via some tableau combinatorics. This includes an example coming from exceptional Lie algebras which is related to Deligne's conjectured exceptional series.

Most of the talk does not assume any knowledge of Lie theory and should be accessible to students.

Let $G$ be a group, $d_G(G)$ the minimal number of generators of $G$ as a normal subgroup, $k \geq d_G(G)$, and $N_k(G)$ the set of all $k$-tuples of elements in $G$ which generate $G$ as a normal subgroup. Then the Andrews--Curtis graph $\Delta_k(G)$ of the group $G$ is the graph whose vertices are tuples from $N_k(G)$ and such that two tuples are connected by an edge if one of them is obtained from another by an elementary Nielsen transformation or by a conjugation of one of the components of the tuple.

Famous Andrews-Curtis Conjecture from algebraic topology states that $\Delta_k(F)$ is connected for a free group $F$ of rank $k$. I am going to discuss the following result which can be viewed as Finitary Andrews-Curtis Conjecture:

Theorem. Let $G$ be a finite group and $k \ge max{d_G(G),2}$. Then the connected components of the AC-graph $\Delta_k(G)$ are precisely the preimages of the connected components of the AC-graph of the abelianization $\Delta_k(G/[G,G])$.

This is joint work with Alexandre Borovik and Alex Lubotzky.

It is a classical result dating back to Jordan that any finite transitive permutation group contains derangements (permutations without fixed points). Rather remarkably, it was not until 1993 that it was shown that if the degree is n > 1, then the proportion of derangements is at least 1/n. We will discuss variations on this theme in the context of algebraic groups and finite simple and almost simple groups. In particular, we will discuss our recent result with Fulman about derangements in simple groups. Also, we will consider the problem of finding derangements in a given coset of a normal subgroup and applications to covers of curves over finite fields.