Lauren K. Williams - Papers


These articles are available here in pdf or postscript format, and most of them are also on the ArXiv.

  1. Polyhedral and tropical geometry of flag positroids (with Jon Boretsky and Chris Eur).

    We explore the polyhedral and tropical geometry of flag positroids, particularly flag positroids whose set of ranks is a sequence of consecutive numbers. In this case we show that the nonnegative tropical flag variety equals the nonnegative flag Dressian, and that points of these spaces give rise to coherent subdivisions of flag positroid polytopes into flag positroid polytopes. Our results have applications to Bruhat interval polytopes and to realizability questions. In particular, we prove that every positively oriented flag matroid of consecutive ranks is realizable.

  2. The combinatorics of hopping particles and positivity in Markov chains, London Math Society Newsletter (anniversary issue) No. 500 (2022), 50--59.

    The asymmetric simple exclusion process (ASEP) is a model for translation in protein synthesis and traffic flow; it can be defined as a Markov chain describing particles hopping on a one-dimensional lattice. In this article I give an overview of some of the connections of the stationary distribution of the ASEP to combinatorics (tableaux and multiline queues) and special functions (Askey-Wilson polynomials, Macdonald polynomials, and Schubert polynomials); this is based on previous joint works with Sylvie Corteel, as well as Olya Mandelshtam and Donghyun Kim. I also make some general observations about positivity in Markov chains.

  3. Grass trees and forests: enumeration of Grassmannian trees and forests, with applications to the momentum amplituhedron (with Robert Moerman).

    The Exponential Formula allows one to enumerate any class of combinatorial objects built by choosing a set of connected components and placing a structure on each connected component which depends only on its size. There are multiple variants of this result, including Speicher's result for noncrossing partitions, as well as analogues of the Exponential Formula for series-reduced planar trees and forests. In this paper we use these formulae to give generating functions for contracted Grassmannian trees and forests. Along the way we enumerate bipartite planar trees and forests, and give applications to enumeration of permutations: for example, bipartite planar trees are in bijection with separable permutations. Our generating function for Grassmannian forests can be interpreted as the rank generating function for the boundary strata of the momentum amplituhedron, an object which encodes the tree-level S-matrix of maximally supersymmetric Yang-Mills theory. This allows us to verify that its Euler characteristic is 1.

  4. The positive Grassmannian, the amplituhedron, and cluster algebras, to appear in the Proceedings of the 2022 ICM.

    The positive Grassmannian is the subset of the real Grassmannian where all Plucker coordinates are nonnegative. It has a beautiful combinatorial structure as well as connections to statistical physics, integrable systems, and scattering amplitudes. The amplituhedron is the image of the positive Grassmannian under a positive linear map. We will explain how ideas from oriented matroids, tropical geometry, and cluster algebras shed light on the structure of the positive Grassmannian and the amplituhedron.

  5. Schubert polynomials, the inhomogeneous TASEP, and evil-avoiding permutations (with Donghyun Kim), to appear in International Mathematics Research Notices.

    The inhomogeneous TASEP on a ring is a Markov chain on permutations whose stationary distribution is conjecturally Schubert positive. We show that the steady state probability of each evil-avoiding permutation w (a permutation avoiding the patterns 2413, 4132, 4213, and 3214) is proportional to a product of k Schubert polynomials, where k is the number of descents of w-1. We also give a multiline queues formula for Cantini's z-deformed steady state probabilities.

  6. The m=2 amplituhedron and the hypersimplex: signs, clusters, triangulations, Eulerian numbers (with Matteo Parisi and Melissa Sherman-Bennett).

    We prove various conjectures about the m=2 amplituhedron, including the sign-flip characterization of Arkani-Hamed--Thomas--Trnka, the cluster adjacency conjecture of Lukowski--Parisi--Spradlin--Volovich, and one direction of the conjecture of Lukowski--Parisi--Williams relating triangulations of the amplituhedron to triangulations of the hypersimplex. We also discuss new cluster structures in the amplituhedron. Finally, we discuss the amplituhedron sign-stratification of the amplituhedron, and show that when m=2, the number of sign chambers is the Eulerian number.

  7. Compact formulas for Macdonald polynomials and quasisymmetric Macdonald polynomials (with Sylvie Corteel, Jim Haglund, Olya Mandelshtam, and Sarah Mason), Selecta Mathematica 28 (2022).

    We present several new and compact formulas for the modified and integral form of the Macdonald polynomials, building on the compact "multiline queue" formula for Macdonald polynomials due to Corteel, Mandelshtam and Williams. We also introduce a new quasisymmetric analogue of Macdonald polynomials. These quasisymmetric Macdonald polynomials refine the (symmetric) Macdonald polynomials and specialize at q=t=0 to the quasisymmetric Schur polynomials defined by Haglund, Luoto, Mason, and van Willigenburg.

  8. The positive Dressian equals the positive tropical Grassmannian (with David Speyer), Transactions of the American Mathematical Society 8 (2021), 330--353.

    The Dressian and the tropical Grassmannian parameterize abstract and realizable tropical linear spaces; but in general, the Dressian is much larger than the tropical Grassmannian. There are natural positive notions of both of these spaces -- the positive Dressian, and the positive tropical Grassmannian (which we introduced in a 2005 paper) -- so it is natural to ask how these two positive spaces compare. In this paper we show that the positive Dressian equals the positive tropical Grassmannian. Using the connection between the positive Dressian and regular positroidal subdivisions of the hypersimplex, we use our result to give a new "tropical" proof of da Silva's 1987 conjecture (first proved in 2017 by Ardila-Rincon-Williams) that all positively oriented matroids are realizable. We also show that the finest regular positroidal subdivisions of the hypersimplex consist of series-parallel matroid polytopes, and achieve equality in Speyer's f-vector theorem. Finally we give an example of a positroidal subdivision of the hypersimplex which is not regular, and make a connection to the theory of tropical hyperplane arrangements.

  9. The positive tropical Grassmannian, the hypersimplex, and the m=2 amplituhedron (with Tomasz Lukowski and Matteo Parisi).

    We illustrate a very strange duality between positroidal subdivisions of the (n-1)-dimensional hypersimplex Δk+1,n and the 2k-dimensional amplituhedron An,k,2. We provide evidence that the positive tropical Grassmannian Trop+Grk+1,n should be thought of as the secondary fan for the amplituhedron An,k,2. We also give a new characterization of positroid polytopes, prove new results on positroidal subdivisions of the hypersimplex, and introduce a generalized momentum amplituhedron.

  10. Higher secondary polytopes and regular plabic graphs (with Pavel Galashin and Alex Postnikov), to appear in Advances in Mathematics.

    Given a configuration A of n points in Rd−1, we introduce the higher secondary polytopes ΣA,1,…,ΣA,n−d, which have the property that ΣA,1 agrees with the secondary polytope of Gelfand--Kapranov--Zelevinsky, while the Minkowski sum of these polytopes agrees with Billera--Sturmfels' fiber zonotope associated with (a lift of) A. In a special case when d=3, we refer to our polytopes as higher associahedra. They turn out to be related to the theory of total positivity, specifically, to certain combinatorial objects called plabic graphs, introduced by the second author in his study of the totally positive Grassmannian. We define a subclass of regular plabic graphs and show that they correspond to the vertices of the higher associahedron ΣA,k, while square moves connecting them correspond to the edges of ΣA,k. Finally we connect our polytopes to soliton graphs, the contour plots of soliton solutions to the KP equation, which were recently studied by Kodama and the third author. In particular, we confirm their conjecture that when the higher times evolve, soliton graphs change according to the moves for plabic graphs.

  11. Cluster structures in Schubert varieties in the Grassmannian (with Khrystyna Serhiyenko and Melissa Sherman-Bennett), Proceedings of the London Mathematical Society (3) 119 (2019), no 6, 1694--1744.

    We explain how the coordinate ring of each (open) Schubert variety in the Grassmannian can be identified with a cluster algebra, whose combinatorial structure is encoded using (target labelings of) Postnikov's plabic graphs. This result generalizes a theorem of Scott from 2006 for the Grassmannian, and proves a folklore conjecture for Schubert varieties that has been believed by experts since Scott's work, though the statement was not formally written down until a 2016 paper of Muller-Speyer. To prove this conjecture we use a result of Leclerc, who used the module category of the preprojective algebra to prove that coordinate rings of many Richardson varieties in the complete flag variety can be identified with cluster algebras. Our proof also uses a construction of Karpman to build plabic graphs associated to reduced expressions. We additionally generalize our result to the setting of skew Schubert varieties; the latter result uses generalized plabic graphs, i.e. plabic graphs whose boundary vertices need not be labeled in cyclic order.

  12. From multiline queues to Macdonald polynomials via the exclusion process (with Sylvie Corteel and Olya Mandelshtam), American Journal of Mathematics, 144 (2022), 395--436.

    Recently James Martin introduced multiline queues and used them to give a combinatorial formulas for the stationary distribution of the multispecies asymmetric simple exclusion process (ASEP) on a ring. Here we give an independent proof of Martin's result and show that by introducing additional statistics on multiline queues, we can give a new combinatorial formula for both the symmetric Macdonald polynomials Pλ and the nonsymmetric Macdonald polynomials Eλ where λ is a partition. This formula is rather different from others that have appeared in the literature. Our proof uses results of Cantini-deGier-Wheeler, who recently linked the multispecies ASEP on a ring to Macdonald polynomials.

    This paper generalizes the results of the cylindric rhombic tableaux paper below, although the combinatorics used in the two papers is rather different.

  13. Cylindric rhombic tableaux and the two-species ASEP on a ring (with Sylvie Corteel and Olya Mandelshtam), to appear in Progress in Mathematics (birthday volume for Kolya Reshetikhin).

    We use some new tableaux on a cylinder called cylindric rhombic tableaux (CRT) to give a formula for the stationary distribution of the two-species ASEP on a circle. We also use them to give a formula for Macdonald polynomials associated to partitions where all parts are 0, 1, or 2.

  14. Newton-Okounkov bodies, cluster duality and mirror symmetry for Grassmannians (with Konstanze Rietsch), Duke Mathematical Journal, 168 (2019), no 18, 3437--3527.

    In this article we use the A and X-cluster structure on the Grassmannian to exhibit a new aspect of mirror symmetry for Grassmannians in terms of polytopes. From a given cluster seed we have both an X-cluster chart and an A-cluster chart for the Grassmannian. We use the X-cluster chart to associate a corresponding Newton-Okounkov polytope. Meanwhile we use the corresponding A-cluster to express the superpotential as a Laurent polynomial, and by tropicalizing this expression, we obtain another polytope. Our first main result is that these two polytopes coincide. When our cluster seed arises from a plabic graph, we also give an explicit formula for each lattice point of these polytopes, which has an interpretation in terms of quantum cohomology.

  15. Decompositions of amplituhedra (with Steven Karp and Yan Zhang), Annales de l'Institut Henri Poincare D 7 (2020), no. 3, 303--363.

    The amplituhedron A(n,k,m) is the image in the Grassmannian Gr(k,k+m) of the totally nonnegative part of Gr(k,n), under a (map induced by a) linear map which is totally positive. It was introduced by Arkani-Hamed and Trnka in connection with scattering amplitudes in N=4 supersymmetric Yang-Mills theory. In the case relevant to physics (m=4), there is a collection of recursively-defined 4k-dimensional BCFW cells in the totally nonnegative part of Gr(k,n), whose images conjecturally "triangulate" the amplituhedron. In this paper, we approach this problem by first giving an explicit (as opposed to recursive) description of the BCFW cells. We then develop sign-variational tools which we use to prove that when k=2, the images of these cells are disjoint in A(n,k,4). We also conjecture that for arbitrary even m, there is a decomposition of the amplituhedron A(n,k,m) involving precisely M(k, n-k-m, m/2) top-dimensional cells (of dimension km), where M(a,b,c) is the number of plane partitions contained in an a x b x c box.

  16. The m=1 amplituhedron and cyclic hyperplane arrangements (with Steven Karp), International Mathematics Research Notices, 2019, no. 5, 1401--1462.

    The amplituhedron A(n,k,m) is the image in the Grassmannian Gr(k,k+m) of the totally nonnegative part of Gr(k,n), under a (map induced by a) linear map which is totally positive. It was introduced by Arkani-Hamed and Trnka in 2013 in order to give a geometric basis for the computation of scattering amplitudes in N=4 supersymmetric Yang-Mills theory. While the case m=4 is most relevant to physics, the amplituhedron is an interesting mathematical object for any m. In this paper we study it in the case m=1. We start by taking an orthogonal point of view and define a related "B-amplituhedron" B(n,k,m), which we show is isomorphic to A(n,k,m). We use this reformulation to describe the amplituhedron in terms of sign variation. We then show that A(n,k,1) can be identified with the complex of bounded faces of a cyclic hyperplane arrangement, and describe how its cells fit together. We deduce that A(n,k,1) is homeomorphic to a ball.

  17. Symmetric matrices, Catalan paths, and correlations (with Bernd Sturmfels and Emmanuel Tsukerman), Journal of Combinatorial Theory, Series A, 144 (2016), 496--510.

    Kenyon and Pemantle (2014) gave a formula for the entries of a square matrix in terms of connected principal and almost-principal minors. Each entry is an explicit Laurent polynomial whose terms are the weights of domino tilings of a half Aztec diamond. They conjectured an analogue of this parametrization for symmetric matrices, where the Laurent monomials are indexed by Catalan paths. In this paper we prove the Kenyon-Pemantle conjecture, and apply this to a statistics problem pioneered by Joe (2006). Correlation matrices are represented by an explicit bijection from the cube to the elliptope.

  18. Combinatorics of the two-species ASEP and Koornwinder moments (with Sylvie Corteel and Olya Mandelshtam), Advances in Mathematics, 321 (2017), 160--204.

    In an earlier work, Corteel and I introduced staircase tableaux, and used them to give combinatorial formulas for steady state probabilities of the ASEP and also for Askey-Wilson moments. It is well-known that Askey-Wilson polynomials can be viewed as the one-variable case of Koornwinder polynomials (also known as Macdonald polynomials of type BC). In this article we introduce rhombic staircase tableaux, and, building on our previous paper, we use them to give combinatorial formulas for steady state probabilities of the two-species ASEP and also for homogeneous Koornwinder moments. (Homogeneous Koornwinder moments are integrals of homogeneous symmetric polynomials with respect to the Koornwinder measure.) Note that rhombic staircase tableaux simultaneusly generalize staircase tableaux and also the rhombic alternative tableaux of Mandelshtam-Viennot.

  19. Macdonald-Koornwinder moments and the two-species exclusion process (with Sylvie Corteel), Selecta Mathematica, 24 (2018), no. 3, 2275--2317.

    Introduced in the late 1960's, the asymmetric exclusion process (ASEP) is an important model from statistical mechanics which describes a system of interacting particles hopping left and right on a one-dimensional lattice with open boundaries. It has been known for awhile that there is a tight connection between the partition function of the ASEP and moments of Askey-Wilson polynomials, a family of orthogonal polynomials which are at the top of the hierarchy of classical orthogonal polynomials in one variable. On the other hand, Askey-Wilson polynomials can be viewed as a specialization of the multivariate Macdonald-Koornwinder polynomials (also known as Koornwinder polynomials), which in turn give rise to the Macdonald polynomials associated to any classical root system via a limit or specialization. In light of the fact that Koornwinder polynomials generalize the Askey-Wilson polynomials, it is natural to ask whether one can find a particle model whose partition function is related to Koornwinder polynomials. In this article we answer this question affirmatively, by showing that Koornwinder moments at q=t are closely connected to the partition function for the two-species exclusion process.

  20. A positive Grassmannian analogue of the permutohedron, Proceedings of the AMS, 144 (2016), 2419--2436.

    The classical permutohedron Perm has many beautiful properties. For example, the paths from e to w_0 along the edges of Perm are in bijection with the reduced decompositions of w_0. Moreover, the two-dimensional faces of the permutohedron correspond to braid and commuting moves, which by the Tits Lemma, connect any two reduced expressions of w_0. In this note we introduce some ``bridge polytopes" Br(k,n) which provide a positive Grassmannian analogue of the permutohedron. In this setting, BCFW bridge decompositions of reduced plabic graphs play the role of reduced decompositions. We show that paths along the edges of Br(k,n) encode BCFW bridge decompositions of the longest element pi(k,n) in the circular Bruhat order. We also show that two-dimensional faces of Br(k,n) correspond to certain local moves for plabic graphs, which by a result of Postnikov, connect any two reduced plabic graphs associated to pi(k,n). A useful tool in our proofs is the fact that our polytopes are isomorphic to certain Bruhat interval polytopes.

  21. Bruhat interval polytopes (with Emmanuel Tsukerman), Advances in Mathematics 285 (2015), 766--810.

    Let u and v be permutations on n letters, with u <= v in Bruhat order. A Bruhat interval polytope Qu,v is the convex hull of all permutation vectors z = (z(1), z(2),...,z(n)) with u <= z <= v. Bruhat interval polytopes were studied recently by Kodama and the second author, in the context of the Toda lattice and the moment map on the flag variety. In this paper we study combinatorial aspects of Bruhat interval polytopes. For example, we give an inequality description and a dimension formula for Bruhat interval polytopes, and prove that every face of a Bruhat interval polytope is a Bruhat interval polytope. A key tool in the proof of the latter statement is a generalization of the well-known lifting property for Coxeter groups. This leads to a generalization of the standard recurrence for R-polynomials. Finally, we define and study a more general class of polytopes called Bruhat interval polytopes for G/P.

  22. On Landau-Ginzburg models for quadrics and flat sections of Dubrovin connections (with Clelia Pech and Konstanze Rietsch), Advances in Mathematics (Zelevinsky issue), 300 (2016), 275--319.

    This paper proves a version of mirror symmetry expressing the (small) Dubrovin connection for even-dimensional quadrics in terms of a mirror-dual Landau-Ginzburg model on the complement of an anticanonical divisor in a dual quadric. The cluster algebra structure on the coordinate ring of the mirror plays a key role in the proof. We then go into greater depth for all quadrics, even and odd, treating them as a series starting with Q3 and Q4=Gr2(4). This leads to a combinatorial model for the Laurent polynomial superpotential in terms of a quiver. We use this quiver description to compute explicitly a particular flat section of the Dubrovin connection, and recover the constant term of Givental's J-function by a variety of methods.

  23. Positively oriented matroids are realizable (with Federico Ardila and Felipe Rincon), Journal of the European Mathematical Society, 19 (2017), 815--833.

    We prove da Silva's 1987 conjecture that any positively oriented matroid is a positroid; that is, it can be realized by a set of vectors in a real vector space. It follows from this result and the main result of my paper ``Shelling totally nonnegative flag varieties" that the positive matroid Grassmannian (or positive MacPhersonian) is homeomorphic to a closed ball.

  24. Positroids and non-crossing partitions (with Federico Ardila and Felipe Rincon), Transactions of the American Mathematical Society 368 (2016), 337--363.

    We investigate the role that non-crossing partitions play in the study of positroids, a class of matroids introduced by Postnikov. We prove that every positroid can be constructed uniquely by choosing a non-crossing partition on the ground set, and then freely placing the structure of a connected positroid on each of the blocks of the partition. This structural result yields several combinatorial facts about positroids. We show that the face poset of a positroid polytope embeds in a poset of weighted non-crossing partitions. We enumerate connected positroids, and show how they arise naturally in free probability. Finally, we prove that the probability that a positroid on [n] is connected equals 1/e^2 asymptotically.

  25. The full Kostant-Toda hierarchy on the positive flag variety (with Yuji Kodama), Communications in Mathematical Physics, 335 (2015), 247--283.

    We study combinatorial aspects of the solution to the full Kostant-Toda (f-KT) hierarchy, when the initial data is given by an arbitrary point on the totally non-negative (tnn) flag variety. The f-KT flows on the tnn flag variety are complete, and their asymptotics are completely determined by Rietsch's cell decomposition of the tnn flag variety. We define the f-KT flow on the weight space via the moment map, and show that the closure of each f-KT flow forms an interesting convex polytope generalizing the permutohedron which we call a Bruhat interval polytope. Bruhat interval polytopes are generalized permutohedra, in the sense of Postnikov, and their edges correspond to cover relations in the Bruhat order.

  26. Cluster algebras: an introduction, Bulletin of the AMS 51 (2014), 1--26.

    In this expository paper we give a gentle introduction to cluster algebras. We also explain how cluster algebras naturally appear in Teichmuller theory, and how they were used to reformulate and prove the Zamolodchikov periodicity conjecture in mathematical physics.

  27. Network parameterizations for the Grassmannian (with Kelli Talaska), Algebra and Number Theory, 7 (2013), 2275--2311.

    Deodhar introduced his decomposition of partial flag varieties as a tool for understanding Kazhdan-Lusztig polynomials. The Deodhar decomposition of the Grassmannian is also useful in the context of soliton solutions to the KP equation. Deodhar components of the Grassmannian are in bijection with certain tableaux called Go-diagrams, and each component is isomorphic to (K *)a × Kb for some non-negative integers a and b. Our main result is an explicit parameterization of each Deodhar component in the Grassmannian in terms of networks. More specifically, from a Go-diagram we construct a weighted network and its weight matrix, whose entries enumerate directed paths in the network. By letting the weights in the network vary over K or K* as appropriate, one gets a parameterization of the corresponding Deodhar component. We also give a (minimal) characterization of each Deodhar component in terms of Plucker coordinates. Note that in his study of the totally non-negative part of the Grassmannian, Postnikov constructed parameterizations of positroid cells that used planar networks associated to Le-diagrams. Our construction generalizes his.

  28. Combinatorics of KP solitons from the real Grassmannian (with Yuji Kodama), Algebras, quivers and representations, 155--193, Abel Symposium, 8, Springer, Heidelberg, 2013.

    This paper is an exposition of our results from ``The Deodhar decomposition of the Grassmannian and the regularity of KP solitons," and ``KP solitons and total positivity on the Grassmannian."

  29. The Deodhar decomposition of the Grassmannian and the regularity of KP solitons (with Yuji Kodama), Advances in Mathematics, 244 (2013), 979--1032.

    Given a point A in the real Grassmannian, one may construct a soliton solution u_A(x,y,t) to the KP equation. The contour plot of such a solution provides a tropical approximation to the solution when the variables x, y, and t are considered on a large scale and t is fixed. In this paper we use several decompositions of the Grassmannian in order to understand the contour plots of the corresponding soliton solutions. First we use the positroid stratification of the real Grassmannian in order to characterize the unbounded line-solitons in the contour plots at y>>0 and y<<0. Next we use Deodhar's decomposition of the Grassmannian (a refinement of the positroid stratification) to study contour plots at t<<0. More specifically, we index the components of the Deodhar decomposition of the Grassmannian by certain tableaux which we call Go-diagrams, and then use these Go-diagrams to characterize the contour plots of solitons solutions when t<<0. Finally we use these results to show that a soliton solution u_A(x,y,t) is regular for all times t if and only if A comes from the totally non-negative part of the Grassmannian.

  30. Combinatorics of the asymmetric exclusion process on a semi-infinite lattice (with Tomohiro Sasamoto), Journal of Combinatorics, 5 (2014).

    We study an asymmetric exclusion process (ASEP) on a semi-infinite lattice with an open left boundary, and an ASEP on a finite lattice with open left and right boundaries -- and we demonstrate a surprising relationship between their stationary measures. We show that the finite correlation functions involving the leftmost L sites on the semi-infinite ASEP can be obtained as a nonphysical specialization of the stationary distribution of the finite ASEP on a lattice of L sites. Namely, if the output and input rates of particles at the right boundary of the finite ASEP are β and δ, respectively, and we set δ = -β, then this specialization corresponds to sending the right boundary of the lattice to infinity. Combining this observation with work of the second author and Corteel, we obtain a combinatorial formula for the finite correlation functions of the semi-infinite ASEP.

  31. Bases for cluster algebras from surfaces (with Gregg Musiker and Ralf Schiffler), Compositio Mathematica, 149 (2013), 217--263.

    Because of the conjectural connection between cluster algebras and dual canonical bases, it is natural to ask whether one may construct a "good" (vector-space) basis of each cluster algebra. In this paper we construct two bases for each cluster algebra coming from a triangulated surface without punctures. We work in the context of a coefficient system coming from a full-rank exchange matrix, for example, principal coefficients. The elements of our bases have positive Laurent expansions with respect to every cluster.

  32. Matrix formulae and skein relations for cluster algebras from surfaces (with Gregg Musiker), International Mathematics Research Notices, 2012, article ID rns118v2.

    This paper concerns cluster algebras with principal coefficients A(S,M) associated to bordered surfaces (S,M). Given any arc or loop in the surface -- with or without self-intersections -- we associate an element of A(S,M), using products of elements of PSL_2(R). We give a direct proof that our matrix formulas for arcs and loops agree with the combinatorial formulas for arcs and loops in terms of matchings, which were given in [MSW, MSW2]. Finally, we use our matrix formulas to prove skein relations for the cluster algebra elements associated to arcs and loops. This generalizes prior work of Fock and Goncharov, who worked in the coefficient-free case. The results of this paper will be used in [MSW2] in order to construct vector-space bases for A(S,M).

  33. KP solitons and total positivity on the Grassmannian (with Yuji Kodama), Inventiones Mathematicae, Volume 198, Issue 3, December 2014, 637--699.

    Soliton solutions of the KP equation have been studied since 1970, when Kadomtsev and Petviashvili proposed a two-dimensional nonlinear dispersive wave equation now known as the KP equation. It is well-known that one can use the Wronskian method to construct a soliton solution to the KP equation from each point of the real Grassmannian. The regular soliton solutions that one obtains in this way come from points of the totally nonnegative part of the Grassmannian. In this paper we exhibit a surprising connection between the theory of total positivity for the Grassmannian, and the structure of regular soliton solutions to the KP equation. This gives new insights into the structure of KP solitons as well as new interpretations of the combinatorial objects indexing positroid cells. In particular, we use this framework to: give an explicit construction of certain soliton contour graphs; demonstrate an intriguing connection between soliton graphs and cluster algebras; and solve the inverse problem for soliton solutions coming from the totally positive Grassmannian.

    Regular KP soliton solutions provide a good model for shallow water waves. Coincidentally, my sister Eleanor also studies waves.

  34. KP solitons, total positivity, and cluster algebras (with Yuji Kodama), Proceedings of the National Academy of Sciences, published online ahead of print May 11, 2011, doi:10.1073/pnas.1102627108.

    This is an announcement of the results of the paper above.

  35. Formulae for Askey-Wilson moments and enumeration of staircase tableaux (with Sylvie Corteel, Richard Stanley, and Dennis Stanton), Transactions of the American Mathematical Society 364 (2012), 6009--6037.

    We give explicit formulas for Askey-Wilson moments and the (enhanced) partition function of the ASEP. At various specializations of the parameters, the partition function factors. We also explore combinatorial properties of staircase tableaux, elucidating connections to trees, matchings, permutations, etc. We conclude with a number of open problems.

  36. The Matrix Ansatz, orthogonal polynomials, and permutations (with Sylvie Corteel and Matthieu Josuat-Verges), Advances in Applied Mathematics, special issue in honor of Dennis Stanton, Volume 46, January 2011, 209--225.

    In this paper we outline a ``Matrix Ansatz" approach to some problems of combinatorial enumeration. The idea is that many interesting quantities can be expressed in terms of products of matrices, where the matrices obey certain relations. We illustrate this approach with applications to moments of orthogonal polynomials, permutations, signed permutations, and tableaux.

  37. A Markov chain on the symmetric group which is Schubert positive? (with Thomas Lam), Experimental Mathematics, Volume 21, Issue 2, 2012, 189--192.

    We define a multivariate Markov chain on the symmetric group with remarkable enumerative properties. We conjecture that the components of its stationary distribution can be written as positive combinations of Schubert polynomials.

  38. Tableaux combinatorics for the asymmetric exclusion process and Askey-Wilson polynomials (with Sylvie Corteel), Duke Mathematical Journal, Volume 159, Number 3, September 2011, 385--415.

    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.

  39. Staircase tableaux, the asymmetric exclusion process, and Askey-Wilson polynomials (with Sylvie Corteel), Proceedings of the National Academy of Sciences, published online ahead of print March 26, 2010, doi:10.1073/pnas.0909915107.

    This is an announcement of the results of the paper above.

  40. Positivity for cluster algebras from surfaces (with Gregg Musiker and Ralf Schiffler), Advances in Mathematics, Volume 227, Issue 6, August 2011, 2241--2308.

    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.

  41. Discrete Morse theory for totally nonnegative flag varieties (with Konstanze Rietsch), Advances in Mathematics, Volume 223, Issue 6, April 2010, 1855--1884.

    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. Subsequently the second author made the concrete conjecture that this cell decomposed space is the next best thing to a polyhedron, by conjecturing it to be a regular CW complex that is homeomorphic to a closed ball (see the paper "Shelling ..." below). In this article we use discrete Morse theory to prove this conjecture up to homotopy-equivalence. Explicitly, we prove that the boundaries of the cells are homotopic to spheres, and the closures of cells are contractible. The latter part generalizes a result of Lusztig's that (G/P)_{\geq 0} -- the closure of the top-dimensional cell -- is contractible. Concerning our result on the boundaries of cells, even the special case that the boundary of the top-dimensional cell (G/P)_{> 0} is homotopic to a sphere, is new for all G/P other than projective space.

  42. Combinatorial Hopf algebras, noncommutative Hall-Littlewood functions, and permutation tableaux (with Jean-Christophe Novelli and Jean-Yves Thibon), Advances in Mathematics, Volume 224, Issue 4, July 2010, 1311--1348.

    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.

  43. The totally nonnegative part of G/P is a CW complex (with Konstanze Rietsch), Transformation Groups (special issue for Kostant's birthday), Volume 13, 2008, 839--853.

    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.

  44. Total positivity for cominuscule Grassmannians (with Thomas Lam), New York Journal of Mathematics, Volume 14, 2008, 53--99.

    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.

  45. Matching polytopes, toric geometry, and the non-negative part of the Grassmannian (with Alex Postnikov and David Speyer), Journal of Algebraic Combinatorics, Volume 30, Issue 2 (2009), 173--191.

    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.

  46. Faces of generalized permutohedra (with Alex Postnikov and Vic Reiner), Documenta Mathematica, Volume 13 (2008), 207--273.

    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.

  47. A conjecture of Stanley on alternating permutations (with Robin Chapman) Electronic Journal of Combinatorics, Volume 14 (1), 2007.

    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.

  48. A Markov chain on permutations which projects to the PASEP (partially asymmetric exclusion process) (with Sylvie Corteel), International Mathematics Research Notices, 2007, article ID mm055.

    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.

  49. Tableaux combinatorics for the asymmetric exclusion process (with Sylvie Corteel), Advances in Applied Math, Volume 39, Issue 3, Sept. 2007, 293--310.

    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.

  50. Shelling totally nonnegative flag varieties, Journal fur die reine und angewandte Mathematik (Crelle's Journal), Volume 2007, Issue 609, Aug. 2007, pages 1-22.

    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.

  51. Permutation tableaux and permutation patterns (with Einar Steingrimsson), Journal of Combinatorial Theory, Series A, Volume 114, Issue 2, February 2007, pages 211-234.

    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.

  52. Combinatorial aspects of total positivity (my thesis).

    My thesis comprises the four papers below. The main difference is an appendix with pictures of some posets of Le-diagrams and decorated permutations.

  53. Bergman complexes, Coxeter arrangements, graph associahedra (with Federico Ardila and Vic Reiner), Seminaire Lotharingien de Combinatoire (electronic), Volume 54A, 2006, B54Aj.

    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.

  54. The positive Bergman complex of an oriented matroid (with Federico Ardila and Carly Klivans), European Journal of Combinatorics, Volume 27, Issue 4, May 2006, pages 577-591.

    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.

  55. The tropical totally positive Grassmannian (with David Speyer), Journal of Algebraic Combinatorics, Volume 22, Number 2, September 2005, pages 189-210.

    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.

  56. Enumeration of totally positive Grassmann cells, Advances in Mathematics, Volume 190, Issue 2, January 2005, pages 319-342.

    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.)

  57. On exact n-step domination, Ars Combinatoria, Volume LVIII, January, 2001.

    This was written when I attended the Duluth REU.

  58. Enumerating up-side self-avoiding walks, Electronic Journal of Combinatorics, Volume 3 (1), 1996.

    This was written when I was a high school student at RSI.

  59. Collaborators

    I've had the pleasure of collaborating with: Federico Ardila, Jonathan Boretsky, Robin Chapman, Sylvie Corteel, Chris Eur, Sergey Fomin, Pasha Galashin, Jim Haglund, Matthieu Josuat-Verges, Steven Karp, Donghyun Kim, Carly Klivans, Yuji Kodama, Thomas Lam, Tomasz Lukowski, Olya Mandelshtam, Sarah Mason, Robert Moerman, Gregg Musiker, Jean-Christophe Novelli, Matteo Parisi, Clelia Pech, Alex Postnikov, Vic Reiner, Konstanze Rietsch, Felipe Rincon, Tomohiro Sasamoto, Ralf Schiffler, Khrystyna Serhiyenko, Melissa Sherman-Bennett, David Speyer, Richard Stanley, Dennis Stanton, Einar Steingrimsson, Bernd Sturmfels, Kelli Talaska, Jean-Yves Thibon, Emmanuel Tsukerman, Andrei Zelevinsky, Yan X. Zhang.