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, certain graphs whose vertices are decorated with a helicity. Along the way we enumerate bipartite planar trees and forests, and we apply our results to enumerate various families of permutations: for example, bipartite planar trees are in bijection with separable permutations. It is postulated by Livia Ferro, Tomasz Łukowski and Robert Moerman (2020) that contracted Grassmannian forests are in bijection with boundary strata of the momentum amplituhedron, an object encoding the tree-level S-matrix of maximally supersymmetric Yang-Mills theory. With this assumption, our results give a rank generating function for the boundary strata of the momentum amplituhedron, and imply that the Euler characteristic of the momentum amplituhedron is \(1\).

Mathematics Subject Classifications: 05A05, 05A15, 05C10

Keywords: Generating functions, permutations, planar forests

This thesis is a compendium of three studies on which matroids and convex geometry play a central role and show their connections to Catalan combinatorics, tiling theory, and factorization theory. First, we study positroids in connection with rational Dyck paths. Then, we study certain matroids on the lattice points of a regular triangle in connection with lozenge tilings. Finally, we explore the connection between the atomic structure of submonoids of (N^d,+) and the geometric properties of the cones they generate.

Positroids, first studied by Postnikov in 2006, are matroids that parameterize the cells of the totally nonnegative part of a Grassmannian variety. The first part of this thesis concerns with the study of a family of positroids that can be parameterized by (rational) Dyck paths. We call such positroids (rational) Dyck positroids. Using work of Reed and Skandera, we show that Dyck positroids on the ground set [2n] are in natural bijection with unit interval orders of size n. We also offer recipes to read the decorated permutation of a Dyck positroid directly from either the antiadjacency matrix representation or the interval representation of the corresponding unit interval order. Finally, for the family of rational Dyck positroids, we provide combinatorial descriptions for some of the most relevant combinatorial objects that are in bijection with positroids.

The second part of this thesis pertains to the study of certain class of matroids which naturally appear in the set of one-dimensional intersections of complete complex flag arrangements. More specifically, these matroids encode the dependency relations among the lines of such flag arrangements. The bases of such matroids can be thought of as certain n-subsets of lattice points of a regular n-simplex. For dimension 2, we provide various cryptomorphic characterizations of these matroids in connection with lozenge tilings of a regular triangle. We also study the connectivity of members of this family of matroids in any dimension.

Finitely generated submonoids of (N^d,+), also known as affine monoids, are crucial in the study of combinatorial commutative algebra and, in particular, toric geometry. Let C denote the class consisting of all submonoids of (N^d,+) (not necessarily finitely generated). The last part of this thesis is devoted to explore how atomic properties of a monoid M in C (and the monoid algebras M induces) are connected with the geometry of its conic hull cone(M) and with the combinatorial structure of the face lattice of cone(M). For monoids in C, we investigate two of the most important arithmetic invariants in factorization theory: the system of sets of lengths and the elasticity. We conclude this thesis studying the atomicity of monoid algebras, including the algebras induced by monoids in C. We shall provide a partial answer to a fundamental question about the atomicity of monoid algebras that Robert Gilmer asked back in the 1980's.

Cluster algebras are a class of commutative rings with a remarkable combinatorial structure, introduced by Fomin and Zelevinsky. A cluster algebra has a distinguished set of generators, called cluster variables, which are grouped together into overlapping subsets called seeds. This dissertation is concerned with the cluster algebra structure of coordinate rings of open positroid varieties in the Grassmannian. Open positroid varieties are projections of open Richardson varieties from the full flag variety to the Grassmannian. They were studied first by Lusztig and Rietsch in the context of total positivity, and then by Knutson--Lam--Speyer, who connected them to the combinatorics of the totally nonnegative Grassmannian developed by Postnikov. Open positroid varieties are smooth, irreducible, and stratify the Grassmannian; open Schubert varieties are a special case.

Seminal work of Scott established that the homogeneous coordinate ring of the Grassmannian is a cluster algebra, and moreover that Postnikov's plabic graphs for the Grassmannian give seeds for this cluster algebra. Postnikov defined plabic graphs not just for the Grassmannian but for all positroid varieties. Accordingly, experts long believed that the coordinate ring of any open positroid variety is also a cluster algebra, with seeds given by plabic graphs. In Chapter 3, which is joint work with Khrystyna Serhiyenko and Lauren Williams, we prove this in the case of open Schubert varieties in the Grassmannian. Work of Leclerc on Richardson varieties in the full flag variety implies that the coordinate rings of these varieties are cluster algebras, but does not give any explicit descriptions of seeds. We show that Postnikov's plabic graphs give seeds in this cluster algebra. For skew Schubert varieties, we show that Leclerc's cluster algebra is given by relabeled plabic graphs, whose boundary vertices are permuted.

Shortly following my work with Serhiyenko and Williams, Galashin--Lam showed that Postnikov's graphs give a cluster algebra structure on coordinate rings of arbitrary positroid varieties using similar methods. In Chapter 4, which is joint work with Chris Fraser, we expand on this result to show that positroid varieties admit a number of different cluster structures, with seeds given by relabeled plabic graphs. Along the way, we show that many positroid varieties are isomorphic, using a permuted version of the Muller--Speyer twist map. We conjecture that all of these distinct cluster structures differ only by rescaling, and prove this conjecture for open Schubert varieties. This enlarges the class of combinatorially well-understood seeds for positroid varieties, which provides additional tools to further study the cluster structure on positroid varieties.

Total positivity is the mathematical study of spaces and their positive parts, which can have interesting combinatorial properties as well as applications in areas such as analysis, representation theory, and theoretical physics. In this dissertation, I study total positivity in the Grassmannian Gr(k,n), which is the space of k-dimensional subspaces of R^n. The totally nonnegative Grassmannian is the subset of Gr(k,n) where all Plücker coordinates are nonnegative. In Chapter 2, I generalize a result of Gantmakher and Krein, who showed that an element V of Gr(k,n) is totally nonnegative if and only if every vector in V, when viewed as a sequence of n numbers and ignoring any zeros, changes sign at most k-1 times. I characterize when the vectors in V change sign at most k-1+m times for any m, in terms of the Plücker coordinates of V. I then apply this result to solve the problem of determining when Grassmann polytopes, generalizations of polytopes into the Grassmannian studied by Lam, are well defined. In Chapter 3, which is joint work with Lauren Williams, we study the (tree) amplituhedron A(n,k,m), the image in 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 computing scattering amplitudes in N=4 supersymmetric Yang-Mills theory. We take 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), and use the results of Chapter 2 to describe the amplituhedron in terms of sign variation. Then we use this reformulation to give a cell decomposition of the amplituhedron in the case m=1, using the images of a collection of distinguished cells of the totally nonnegative Grassmannian. We also identify A(n,k,1) with the complex of bounded faces of a cyclic hyperplane arrangement, and deduce that A(n,k,1) is homeomorphic to a ball. In Chapter 4, I study the action of the cyclic group of order n on the totally nonnegative part of Gr(k,n). I show that the cyclic action has a unique fixed point, given by taking n equally spaced points on the trigonometric moment curve (if k is odd) or the symmetric moment curve (if k is even). More generally, I show that the cyclic action on the entire complex Grassmannian has exactly n choose k fixed points, corresponding to k-subsets of nth roots of (-1)^(k-1). I explain how these fixed points also appear in the study of the quantum cohomology ring of the Grassmannian.

We study Newton polytopes of cluster variables in type A cluster algebras, whose cluster and coefficient variables are indexed by the diagonals and boundary segments of a polygon. Our main results include an explicit description of the affine hull and facets of the Newton polytope of the Laurent expansion of any cluster variable, with respect to any cluster. In particular, we show that every Laurent monomial in a Laurent expansion of a type A cluster variable corresponds to a vertex of the Newton polytope. We also describe the face lattice of each Newton polytope via an isomorphism with the lattice of elementary subgraphs of the associated snake graph. Other results include a geometric interpretation of the proper Laurent property in type A based on Newton polytopes, and a proof that the Newton polytope of a type A cluster variable has no relative interior lattice points. We also consider extensions of these ideas, results, and methods to other cluster algebras.

This dissertation explores questions about posets and polytopes through the lenses of positroids and geometry. The introduction and study of positroids, a special class of matroids, was pioneered by Postnikov in his study of the totally nonnegative Grassmannian and has subsequently been applied to various fields such as cluster algebras, physics, and free probability. Postnikov showed that positroids, the matroids realized by full rank $k\times n$ real matrices whose maximal minors are nonnegative, are in bijection with several combinatorial objects: Grassmann necklaces, decorated permutations, Le-diagrams and plabic graphs.

In the first chapter, following work of Skandera and Reed, we define the unit interval positroid arising from a unit interval order poset via its associated antiadjacency matrix. We give a simple description of the decorated permutation representation of a unit interval positroid, and show it can be recovered from the Dyck path drawn on the associated antiadjacency matrix. We also describe the unit interval positroid cells in the totally nonnegative Grassmannian and their adjacencies. Finally, we provide a new description of the $f$-vector of posets.

The second chapter concerns the $f$-vector of a $d$-dimensional polytope $P$, which stores the number of faces of each dimension. When $P$ is a simplicial polytope the Dehn--Sommerville relations condense the $f$-vector into the $g$-vector, which has length $\lceil{\frac{d+1}{2}}\rceil$. Thus, to determine the $f$-vector of $P$, we only need to know approximately half of its entries. This raises the question: Which $\left(\lceil{\frac{d+1}{2}}\rceil\right)$-subsets of the $f$-vector of a general simplicial polytope are sufficient to determine the whole $f$-vector? We prove that the answer is given by the bases of the Catalan matroid.

In the final chapter, we explore the combinatorial structure of Knuth equivalence graphs $G_{\lambda}$. The vertices of $G_{\lambda}$ are the permutations whose insertion tableau is a fixed tableau of shape $\lambda$, and the edges are given by local Knuth moves on the permutations. The graph $G_{\lambda}$ is the $1$-skeleton of a cubical complex $C_{\lambda}$, and one can ask whether it is CAT(0); this is a desirable metric property that allows us to describe the combinatorial structure of $G_{\lambda}$ very explicitly. We prove that $C_{\lambda}$ is CAT(0) if and only if $\lambda$ is a hook.