These articles are available here in postscript format, and most of them are on the ArXiv.
Introduced in the late 1960's, the asymmetric exclusion process (ASEP) is a model from statistical mechanics which describes a system of interacting particles hopping left and right on a one-dimensional lattice of n sites. In its most general form, particles may enter and exit at the left with probabilities α and γ, and they may exit and enter at the right with probabilities β and δ. In the bulk, the probability of hopping left is q times that of hopping right. The first result of this paper is a combinatorial formula for the stationary distribution of the ASEP with all parameters general, in terms of some new staircase tableaux. This generalizes our previous work for the ASEP with parameters γ=δ=0. Combining our first result with results of Uchiyama-Sasamoto-Wadati, we derive our second result: a combinatorial formula for the moments of Askey-Wilson polynomials. Since the early 1980's there has been a great deal of work giving combinatorial formulas for moments of various other classical orthogonal polynomials. However, this is the first such formula for the Askey-Wilson polynomials, which are at the top of the hierarchy of classical orthogonal polynomials.
This is an announcement of the results of the paper above.
The class of cluster algebras coming from triangulated surfaces was systematically studied by Fomin-Shapiro-Thurston, and it was later shown by Felikson-Shapiro-Tumarkin that this class is very large: it includes all but finitely many (= eleven) of the skew-symmetric cluster algebras of finite mutation type. In this paper we give combinatorial formulas for the Laurent expansion of any cluster variable in any cluster algebra coming from a triangulated surface (with or without punctures), with respect to an arbitrary seed. Moreover, we work in the generality of principal coefficients. An immediate corollary of our formulas is a proof of the positivity conjecture of Fomin and Zelevinsky for cluster algebras from surfaces, in geometric type.
In a seminal 1994 paper, Lusztig extended the theory of total positivity by introducing the totally non-negative part (G/P)_{\geq 0} of an arbitrary (generalized, partial) flag variety G/P. He referred to this space as a "remarkable polyhedral subspace", and conjectured a decomposition into cells, which was subsequently proven by the first author. In this article we use discrete Morse theory to show that the cell decomposition of (G/P)_{\geq 0} is polyhedral in the following sense: closures of cells are collapsible and hence contractible. This answers a question of Lusztig and generalizes his result that (G/P)_{\geq 0} -- the closure of the top-dimensional cell -- is contractible. Furthermore, we show that the boundary of each cell, hence in particular the boundary of (G/P)_{\geq 0}, is homotopy equivalent to a sphere. This proves the conjecture that (G/P)_{\geq 0} is a regular CW complex (see the paper "Shelling totally nonnegative flag varieties" below) up to homotopy-equivalence.
We introduce a new family of noncommutative analogs of the Hall-Littlewood symmetric functions. Our construction relies upon Tevlin's bases and simple q-deformations of the classical combinatorial Hopf algebras. We connect our new Hall-Littlewood functions to permutation tableaux, which gives an exact formula for the q-enumeration of permutation tableaux of a fixed shape. By a result in the paper ``Permutation tableaux and permutation patterns" below, this is also an exact formula for the number of permutations with a fixed set of weak excedances, enumerated according to crossings. And by the main result of the paper ``Tableaux Combinatorics for the asymmetric exclusion process" below, this gives an explicit formula for the steady state probability of each state in the partially asymmetric exclusion process.
The totally nonnegative part of a partial flag variety G/P has been shown by Rietsch to be a union of semi-algebraic cells. In this note we provide glueing maps for each of the cells to prove that the totally nonnegative part of G/P is a CW complex. This generalizes a previous result found in collaboration with Postnikov and Speyer for Grassmannians. We again use a technique of associating an auxiliary toric variety to each parameterization of a cell; but this time we need to use the canonical basis to prove that the parameterizations are given by positive polynomials.
In this paper we explore the combinatorics of the non-negative part of a cominuscule Grassmannian (G/P)+. For each such Grassmannian we define Le-diagrams -- certain fillings of generalized Young diagrams which are in bijection with the cells of (G/P)+. In the classical cases, we describe Le-diagrams explicitly in terms of pattern avoidance. We also define a game on diagrams, by which one can reduce an arbitrary diagram to a Le-diagram. We give enumerative results and relate our Le-diagrams to other combinatorial objects. Surprisingly, the totally non-negative cells in the open Schubert cell of the even and odd orthogonal Grassmannians are (essentially) in bijection with preference functions and atomic preference functions respectively.
In this paper we use toric geometry to investigate the topology of the totally non-negative part of the Grassmannian, a cell complex whose cells can be parameterized in terms of the combinatorics of plane-bipartite graphs. To each cell we associate a related toric variety, whose moment polytope is related to a matroid polytope, and whose combinatorial structure is similar to a Birkhoff polytope and can be completely described in terms of plane-bipartite graphs. We use our technology to prove that the cell decomposition of the non-negative part of the Grassmannian is a CW complex and that the Euler characteristic of the closure of each cell is 1.
The aim of this paper is to calculate face numbers of simple generalized permutohedra and study their f, h, and gamma-vectors. Generalized permutohedra include many famous families of polytopes, including permutohedra, assocahedra, graph-associahedra, and graphical zonotopes. We give several explicit formulas involving descent statistics, and calculate generating functions. In particular, we give a combinatorial interpretation for gamma-vectors of a wide class of simple generalized permutohedra (the chordal nestohedra), proving Gal's conjecture on the nonnegativity of gamma-vectors in this case.
In this paper we give two short proofs of a conjecture of Richard Stanley concerning the equidistribution of derangements and alternating permutations with the maximal number of fixed points.
In this paper we strengthen the connection between permutation tableaux and the PASEP found in our previous paper "Tableaux combinatorics ..." by showing that the PASEP can be "lifted" to a Markov chain on permutation tableaux of a fixed semiperimeter. Because of the bijection between permutation tableaux and permutations, this can also be thought of as a Markov chain on permutations in S_n.
The (partially) asymmetric exclusion process (PASEP) is an important model from statistical mechanics which involves particles hopping on a one-dimensional lattice. It has been cited as a model for traffic flow and protein synthesis. In this paper we use the matrix ansatz to prove a combinatorial interpretation for the steady state probability of being in any configuration of the PASEP. Surprisingly, our formula is in terms of permutation tableaux, certain combinatorial objects indexing cells in the non-negative part of the Grassmannian.
It is conjectured that the non-negative part of a real flag variety (as defined by Lusztig) is homeomorphic to a ball. A stronger conjecture says that its Lusztig-Rietsch cell decomposition is a regular CW complex homeomorphic to a ball. Here we use tools from poset topology to prove the combinatorial analog of this statement: that the poset (partially ordered set) of Lusztig-Rietsch cells is the face poset of a regular CW complex homeomorphic to a ball. This result holds in complete generality -- for any partial flag variety of any type.
Permutation tableaux are a distinguished subset of Postnikov's "Le-diagrams," which index cells in the non-negative part of the Grassmannian. In this paper we show that the bijection from the set of permutation tableaux to permutations translates many natural tableaux statistics into natural permutation statistics. One application is an additional combinatorial interpretation for the q-Eulerian polynomials introduced in my paper "Enumeration of totally positive Grassmann cells": this polynomial enumerates permutations according to descents and occurrences of certain generalized permutation patterns.
My thesis comprises the four papers below. The main difference is an appendix with pictures of some posets of Le-diagrams and decorated permutations.
We consider oriented matroids coming from Coxeter arrangements, and study their Bergman complexes and positive Bergman complexes. We relate these objects to nested set complexes and graph associahedra. Additionally, we prove that for an arbitrary orientable matroid, its Bergman complex is covered in a nice way by the various positive Bergman complexes one gets by considering different orientations.
The Bergman complex can be thought of as a generalization for matroids of the notion of a tropical variety. There is a natural notion of the "totally positive" part of the Bergman complex of an oriented matroid. We relate this object to the Las Vergnas face lattice, thereby proving that it is homeomorphic to a ball.
We introduce the totally positive part of a tropical variety -- an object which has the structure of a polyhedral fan -- and study this object in the case of the Grassmannian. For the Grassmannians G(2,n), G(3,6), G(3,7), and G(3,8), the polyhedral fans in question turn out to be (essentially) the generalized associahedra of types A, D_4, E_6, and E_8, respectively. These results are reminiscent of the fact that the Grassmannian's coordinate ring has a cluster algebra structure which in these cases has types A, D_4, E_6, E_8. We formulate a conjecture generalizing these results.
The nonnegative part of the Grassmannian is the subset of the real Grassmannian where all Plucker coordinates are non-negative (this definition was given by Postnikov; it turns out to agree with Lusztig's definition). We prove an explicit formula for the rank-generating function for its Lusztig-Postnikov-Rietsch cell decomposition. This leads us to introduce a new q-analog of the Eulerian numbers, which enumerates permutations according to weak excedences and "crossings." (Subsequently Corteel showed that this polynomial also has an interpretation in terms of the PASEP, which led to our joint work on the PASEP.)
This was written when I attended the Duluth REU.
This was written when I was a high school student at RSI.