Search for: All records

Abstract The matching polytope of a graphGis the convex hull of the indicator vectors of the matchings onG. We characterize the graphs whose associated matching polytopes are Gorenstein, and then prove that all Gorenstein matching polytopes possess the integer decomposition property. As a special case study, we examine the matching polytopes of wheel graphs and show that they arenotGorenstein, butdopossess the integer decomposition property. 

Abstract A barcode is a finite multiset of intervals on the real line. Jaramillo-Rodriguez (2023) previously defined a map from the space of barcodes with a fixed number of bars to a set of multipermutations, which presented new combinatorial invariants on the space of barcodes. A partial order can be defined on these multipermutations, resulting in a class of posets known as combinatorial barcode lattices. In this paper, we provide a number of equivalent definitions for the combinatorial barcode lattice, show that its Möbius function is a restriction of the Möbius function of the symmetric group under the weak Bruhat order, and show its ground set is the Jordan-Hölder set of a labeled poset. Furthermore, we obtain formulas for the number of join-irreducible elements, the rank-generating function, and the number of maximal chains of combinatorial barcode lattices. Lastly, we make connections between intervals in the combinatorial barcode lattice and certain classes of matchings. 

Abstract We show that the base polytopeP_Mof any paving matroidMcan be systematically obtained from a hypersimplex by slicing off certain subpolytopes, namely base polytopes of lattice path matroids corresponding to panhandle-shaped Ferrers diagrams. We calculate the Ehrhart polynomials of these matroids and consequently write down the Ehrhart polynomial ofP_M, starting with Katzman’s formula for the Ehrhart polynomial of a hypersimplex. The method builds on and generalizes Ferroni’s work on sparse paving matroids. Combinatorially, our construction corresponds to constructing a uniform matroid from a paving matroid by iterating the operation ofstressed-hyperplane relaxationintroduced by Ferroni, Nasr and Vecchi, which generalizes the standard matroid-theoretic notion of circuit-hyperplane relaxation. We present evidence that panhandle matroids are Ehrhart positive and describe a conjectured combinatorial formula involving chain forests and Eulerian numbers from which Ehrhart positivity of panhandle matroids will follow. As an application of the main result, we calculate the Ehrhart polynomials of matroids associated with Steiner systems and finite projective planes, and show that they depend only on their design-theoretic parameters: for example, while projective planes of the same order need not have isomorphic matroids, their base polytopes must be Ehrhart equivalent. 

Abstract A classical parking function of lengthnis a list of positive integers$$(a_1, a_2, \ldots , a_n)$$ $(a_1,a_2,\dots ,a_n)$whose nondecreasing rearrangement$$b_1 \le b_2 \le \cdots \le b_n$$ $b_1\le b_2\le \cdots \le b_n$satisfies$$b_i \le i$$ $b_i\le i$. The convex hull of all parking functions of lengthnis ann-dimensional polytope in$${\mathbb {R}}^n$$ $R^n$, which we refer to as the classical parking function polytope. Its geometric properties have been explored in Amanbayeva and Wang (Enumer Combin Appl 2(2):Paper No. S2R10, 10, 2022) in response to a question posed by Stanley (Amer Math Mon 127(6):563–571, 2020). We generalize this family of polytopes by studying the geometric properties of the convex hull of$${\textbf{x}}$$ $x$-parking functions for$${\textbf{x}}=(a,b,\dots ,b)$$ $x=(a,b,\cdots ,b)$, which we refer to as$${\textbf{x}}$$ $x$-parking function polytopes. We explore connections between these$${\textbf{x}}$$ $x$-parking function polytopes, the Pitman–Stanley polytope, and the partial permutahedra of Heuer and Striker (SIAM J Discrete Math 36(4):2863–2888, 2022). In particular, we establish a closed-form expression for the volume of$${\textbf{x}}$$ $x$-parking function polytopes. This allows us to answer a conjecture of Behrend et al. (2022) and also obtain a new closed-form expression for the volume of the convex hull of classical parking functions as a corollary. 

We establish a tantalizing symmetry of certain numbers refining the Narayana numbers. In terms of Dyck paths, this symmetry is interpreted in the following way: if $$w_{n,k,m}$$ is the number of Dyck paths of semilength $$n$$ with $$k$$ occurrences of $UD$ and $$m$$ occurrences of $UUD$, then $$w_{2k+1,k,m}=w_{2k+1,k,k+1-m}$$. We give a combinatorial proof of this fact, relying on the cycle lemma, and showing that the numbers $$w_{2k+1,k,m}$$ are multiples of the Narayana numbers. We prove a more general fact establishing a relationship between the numbers $$w_{n,k,m}$$ and a family of generalized Narayana numbers due to Callan. A closed-form expression for the even more general numbers $$w_{n,k_{1},k_{2},\ldots, k_{r}}$$ counting the semilength-$$n$$ Dyck paths with $$k_{1}$$ $UD$-factors, $$k_{2}$$ $UUD$-factors, $$\ldots$$, and $$k_{r}$$ $$U^{r}D$$-factors is also obtained, as well as a more general form of the discussed symmetry for these numbers in the case when all rise runs are of certain minimal length. Finally, we investigate properties of the polynomials $$W_{n,k}(t)= \sum_{m=0}^k w_{n,k,m} t^m$$, including real-rootedness, $$\gamma$$-positivity, and a symmetric decomposition. 

Let $$G$$ be a graph with vertex set $$\{1,2,\ldots,n\}$$. Its bond lattice, $BL(G)$, is a sublattice of the set partition lattice. The elements of $BL(G)$ are the set partitions whose blocks induce connected subgraphs of $$G$$. In this article, we consider graphs $$G$$ whose bond lattice consists only of noncrossing partitions. We define a family of graphs, called triangulation graphs, with this property and show that any two produce isomorphic bond lattices. We then look at the enumeration of the maximal chains in the bond lattices of triangulation graphs. Stanley's map from maximal chains in the noncrossing partition lattice to parking functions was our motivation. We find the restriction of his map to the bond lattice of certain subgraphs of triangulation graphs. Finally, we show the number of maximal chains in the bond lattice of a triangulation graph is the number of ordered cycle decompositions.