Discrete Mathematics & Theoretical Computer Science |
The notion of (3+1)-avoidance appears in many places in enumerative combinatorics, but the natural goal of enumerating all (3+1)-avoiding posets remains open. In this paper, we enumerate \emphgraded (3+1)-avoiding posets. Our proof consists of a number of structural theorems followed by some generating function magic.
The degree chromatic polynomial $P_m(G,k)$ of a graph $G$ counts the number of $k$ -colorings in which no vertex has m adjacent vertices of its same color. We prove Humpert and Martin's conjecture on the leading terms of the degree chromatic polynomial of a tree.
We generalize the brick polytope of V. Pilaud and F. Santos to spherical subword complexes for finite Coxeter groups. This construction provides polytopal realizations for a certain class of subword complexes containing all cluster complexes of finite types. For the latter, the brick polytopes turn out to coincide with the known realizations of generalized associahedra, thus opening new perspectives on these constructions. This new approach yields in particular the vertex description and a relevant Minkowski sum decomposition of generalized associahedra.
We study integral ratios of hook products of quotient partitions. This question is motivated by an analogous question in number theory concerning integral factorial ratios. We prove an analogue of a theorem of Landau that already applied in the factorial case. Under the additional condition that the ratio has one more factor on the denominator than the numerator, we provide a complete classification. Ultimately this relies on Kneser's theorem in additive combinatorics.
We generalize the symmetry on Young's lattice, found by Suter, to a symmetry on the $k$-bounded partition lattice of Lapointe, Lascoux and Morse.
In a 2010 paper Haglund, Morse, and Zabrocki studied the family of polynomials $\nabla C_{p1}\dots C_{pk}1$ , where $p=(p_1,\ldots,p_k)$ is a composition, $\nabla$ is the Bergeron-Garsia Macdonald operator and the $C_\alpha$ are certain slightly modified Hall-Littlewood vertex operators. They conjecture that these polynomials enumerate a composition indexed family of parking functions by area, dinv and an appropriate quasi-symmetric function. This refinement of the nearly decade old ``Shuffle Conjecture,'' when combined with properties of the Hall-Littlewood operators can be shown to imply the existence of certain bijections between these families of parking functions. In previous work to appear in her PhD thesis, the author has shown that the existence of these bijections follows from some relatively simple properties of a certain family of polynomials in one variable x with coefficients in $\mathbb{N}[q]$. In this paper we introduce those polynomials, explain their connection to the conjecture of Haglund, Morse, and Zabrocki, and explore some of their surprising properties, both proven and conjectured.
This paper is devoted to the explicit computation of generating series for the connection coefficients of two commutative subalgebras of the group algebra of the symmetric group, the class algebra and the double coset algebra. As shown by Hanlon, Stanley and Stembridge (1992), these series gives the spectral distribution of some random matrices that are of interest to statisticians. Morales and Vassilieva (2009, 2011) found explicit formulas for these generating series in terms of monomial symmetric functions by introducing a bijection between partitioned hypermaps on (locally) orientable surfaces and some decorated forests and trees. Thanks to purely algebraic means, we recover the formula for the class algebra and provide a new simpler formula for the double coset algebra. As a salient ingredient, we compute an explicit formulation for zonal polynomials indexed by partitions of type $[a,b,1^{n-a-b}]$.
Tropical oriented matroids were defined by Ardila and Develin in 2007. They are a tropical analogue of classical oriented matroids in the sense that they encode the properties of the types of points in an arrangement of tropical hyperplanes – in much the same way as the covectors of (classical) oriented matroids describe the types in arrangements of linear hyperplanes. Not every oriented matroid can be realised by an arrangement of linear hyperplanes though. The famous Topological Representation Theorem by Folkman and Lawrence, however, states that every oriented matroid can be represented as an arrangement of $\textit{pseudo}$hyperplanes. Ardila and Develin proved that tropical oriented matroids can be represented as mixed subdivisions of dilated simplices. In this paper I prove that this correspondence is a bijection. Moreover, I present a tropical analogue for the Topological Representation Theorem.
In a recent paper, Duane, Garsia, and Zabrocki introduced a new statistic, "ndinv'', on a family of parking functions. The definition was guided by a recursion satisfied by the polynomial $\langle\Delta_{h_m}C_p1C_p2...C_{pk}1,e_n\rangle$, for $\Delta_{h_m}$ a Macdonald eigenoperator, $C_{p_i}$ a modified Hall-Littlewood operator and $(p_1,p_2,\dots ,p_k)$ a composition of n. Using their new statistics, they are able to give a new interpretation for the polynomial $\langle\nabla e_n, h_j h_n-j\rangle$ as a q,t numerator of parking functions by area and ndinv. We recall that in the shuffle conjecture, parking functions are q,t enumerated by area and diagonal inversion number (dinv). Since their definition is recursive, they pose the problem of obtaining a non recursive definition. We solved this problem by giving an explicit formula for ndinv similar to the classical definition of dinv. In this paper, we describe the work we did to construct this formula and to prove that the resulting ndinv is the same as the one recursively defined by Duane, Garsia, and Zabrocki.
We introduce a certain class of algebras associated to matroids. We prove the Lefschetz property of the algebras for some special cases. Our result implies the Sperner property for the Boolean lattice and the vector space lattice.
Based on the notion of colored and absolute excedances introduced by Bagno and Garber we give an analogue of the derangement polynomials. We obtain some basic properties of these polynomials. Moreover, we define an excedance statistic for the affine Weyl groups of type $\widetilde{B}_n, \widetilde {C}_n$ and $\widetilde {D}_n$ and determine the generating functions of their distributions. This paper is inspired by one of Clark and Ehrenborg (2011) in which the authors introduce the excedance statistic for the group of affine permutations and ask if this statistic can be defined for other affine groups.
Bergman complexes are polyhedral complexes associated to matroids. Faces of these complexes are certain matroids, called matroid types, too. In order to understand the structure of these faces we decompose matroid types into direct summands. Ardila/Klivans proved that the Bergman Complex of a matroid can be subdivided into the order complex of the proper part of its lattice of flats. Beyond that Feichtner/Sturmfels showed that the Bergman complex can even be subdivided to the even coarser nested set complex. We will give a much shorter and more general proof of this fact. Generalizing formulas proposed by Ardila/Klivans and Feichtner/Sturmfels for special cases, we present a decomposition into direct sums working for faces of any of these complexes. Additionally we show that it is the finest possible decomposition for faces of the Bergman complex.
We present a family of simplicial complexes called \emphmulti-cluster complexes. These complexes generalize the concept of cluster complexes, and extend the notion of multi-associahedra of types ${A}$ and ${B}$ to general finite Coxeter groups. We study combinatorial and geometric properties of these objects and, in particular, provide a simple combinatorial description of the compatibility relation among the set of almost positive roots in the cluster complex.
The Ram–Yip formula for Macdonald polynomials (at t=0) provides a statistic which we call charge. In types ${A}$ and ${C}$ it can be defined on tensor products of Kashiwara–Nakashima single column crystals. In this paper we show that the charge is equal to the (negative of the) energy function on affine crystals. The algorithm for computing charge is much simpler than the recursive definition of energy in terms of the combinatorial ${R}$-matrix.
Let $P$ be a poset and let $P^*$ be the set of all finite length words over $P$. Generalized subword order is the partial order on $P^*$ obtained by letting $u≤ w$ if and only if there is a subword $u'$ of $w$ having the same length as $u$ such that each element of $u$ is less than or equal to the corresponding element of $u'$ in the partial order on $P$. Classical subword order arises when $P$ is an antichain, while letting $P$ be a chain gives an order on compositions. For any finite poset $P$, we give a simple formula for the Möbius function of $P^*$ in terms of the Möbius function of $P$. This permits us to rederive in an easy and uniform manner previous results of Björner, Sagan and Vatter, and Tomie. We are also able to determine the homotopy type of all intervals in $P^*$ for any finite $P$ of rank at most 1.
We provide a Hopf algebra structure on the supercharacter theory for the unipotent upper triangular group of type {D} over a finite field. Also, we make further comments with respect to types {B} and {C}. Type {A} was explored by M. Aguiar et. al (2010), thus this extended abstract is a contribution to understand combinatorially the supercharacter theory of the other classical Lie types.
In their paper on Wilf-equivalence for singleton classes, Backelin, West, and Xin introduced a transformation $\phi^*$, defined by an iterative process and operating on (all) full rook placements on Ferrers boards. Bousquet-Mélou and Steingrimsson proved the analogue of the main result of Backelin, West, and Xin in the context of involutions, and in so doing they needed to prove that $\phi^*$ commutes with the operation of taking inverses. The proof of this commutation result was long and difficult, and Bousquet-Mélou and Steingrimsson asked if $\phi^*$ might be reformulated in such a way as to make this result obvious. In the present paper we provide such a reformulation of $\phi^*$, by modifying the growth diagram algorithm of Fomin. This also answers a question of Krattenthaler, who noted that a bijection defined by the unmodified Fomin algorithm obviously commutes with inverses, and asked what the connection is between this bijection and $\phi^*$.
We produce skew Pieri Rules for Hall–Littlewood functions in the spirit of Assaf and McNamara (FPSAC, 2010). The first two were conjectured by the first author (FPSAC, 2011). The key ingredients in the proofs are a q-binomial identity for skew partitions that are horizontal strips and a Hopf algebraic identity that expands products of skew elements in terms of the coproduct and antipode.
Cayley polytopes were defined recently as convex hulls of Cayley compositions introduced by Cayley in 1857. In this paper we resolve Braun's conjecture, which expresses the volume of Cayley polytopes in terms of the number of connected graphs. We extend this result to a two-variable deformations, which we call Tutte polytopes. The volume of the latter is given via an evaluation of the Tutte polynomial of the complete graph. Our approach is based on an explicit triangulation of the Cayley and Tutte polytope. We prove that simplices in the triangulations correspond to labeled trees and forests. The heart of the proof is a direct bijection based on the neighbors-first search graph traversal algorithm.
Let $G=(V,E)$ be a finite acyclic directed graph. Being motivated by a study of certain aspects of cluster algebras, we are interested in a class of triangulations of the cone of non-negative flows in $G, \mathcal F_+(G)$. To construct a triangulation, we fix a raming at each inner vertex $v$ of $G$, which consists of two linear orders: one on the set of incoming edges, and the other on the set of outgoing edges of $v$. A digraph $G$ endowed with a framing at each inner vertex is called $framed$. Given a framing on $G$, we define a reflexive and symmetric binary relation on the set of extreme rays of $\mathcal F_+ (G)$. We prove that that the complex of cliques formed by this binary relation is a pure simplicial complex, and that the cones spanned by cliques constitute a unimodular simplicial regular fan $Σ (G)$ covering the entire $\mathcal F_+(G)$.
Motivated by a result of Fiebig (2007), we categorify some properties of Kazhdan-Lusztig polynomials via sheaves on Bruhat moment graphs. In order to do this, we develop new techniques and apply them to the combinatorial data encoded in these moment graphs.
We will discuss some recent theorems relating the space of weighted phylogenetic trees to the tropical varieties of each flag variety of type A. We will also discuss the tropicalizations of the functions corresponding to semi-standard tableaux, in particular we relate them to familiar functions from phylogenetics. We close with some remarks on the generalization of these results to the tropical geometry of arbitrary flag varieties. This involves the family of Bergman complexes derived from the hyperplane arrangements associated to simple Dynkin diagrams.
We define new families of noncommutative symmetric functions and quasi-symmetric functions depending on two matrices of parameters, and more generally on parameters associated with paths in a binary tree. Appropriate specializations of both matrices then give back the two-vector families of Hivert, Lascoux, and Thibon and the noncommutative Macdonald functions of Bergeron and Zabrocki.
In this article we prove that the poset of m-divisible noncrossing partitions is EL-shellable for every well-generated complex reflection group. This was an open problem for type G(d,d,n) and for the exceptional types, for which a proof is given case-by-case.
A chromatic root is a zero of the chromatic polynomial of a graph. At a Newton Institute workshop on Combinatorics and Statistical Mechanics in 2008, two conjectures were proposed on the subject of which algebraic integers can be chromatic roots, known as the ``$α +n$ conjecture'' and the ``$nα$ conjecture''. These say, respectively, that given any algebraic integer α there is a natural number $n$ such that $α +n$ is a chromatic root, and that any positive integer multiple of a chromatic root is also a chromatic root. By computing the chromatic polynomials of two large families of graphs, we prove the $α +n$ conjecture for quadratic and cubic integers, and show that the set of chromatic roots satisfying the nα conjecture is dense in the complex plane.
We evaluate induced sign characters of $H_n(q)$ at certain elements of $H_n(q)$ and conjecture an interpretation for the resulting polynomials as generating functions for $P$-tableaux by a certain statistic. Our conjecture relates the quantum chromatic symmetric functions of Shareshian and Wachs to $H_n(q)$ characters.
We discuss some properties of a subposet of the Tamari lattice introduced by Pallo (1986), which we call the comb poset. We show that three binary functions that are not well-behaved in the Tamari lattice are remarkably well-behaved within an interval of the comb poset: rotation distance, meets and joins, and the common parse words function for a pair of trees. We relate this poset to a partial order on the symmetric group studied by Edelman (1989).
We study the problem of expanding the product of two Stanley symmetric functions $F_w·F_u$ into Stanley symmetric functions in some natural way. Our approach is to consider a Stanley symmetric function as a stabilized Schubert polynomial $F_w=\lim _n→∞\mathfrak{S}_{1^n×w}$, and study the behavior of the expansion of $\mathfrak{S} _{1^n×w}·\mathfrak{S} _{1^n×u}$ into Schubert polynomials, as $n$ increases. We prove that this expansion stabilizes and thus we get a natural expansion for the product of two Stanley symmetric functions. In the case when one permutation is Grassmannian, we have a better understanding of this stability.
Let $δ (\mathcal{P} )=(δ _0,δ _1,\ldots,δ _d)$ be the $δ$ -vector of an integral convex polytope $\mathcal{P}$ of dimension $d$. First, by using two well-known inequalities on $δ$ -vectors, we classify the possible $δ$ -vectors with $\sum_{i=0}^d δ _i ≤3$. Moreover, by means of Hermite normal forms of square matrices, we also classify the possible $δ$ -vectors with $\sum_{i=0}^d δ _i = 4$. In addition, for $\sum_{i=0}^d δ _i ≥5$, we characterize the $δ$ -vectors of integral simplices when $\sum_{i=0}^d δ _i$ is prime.
We introduce an algorithm to determine when a sorting operation, such as stack-sort or bubble-sort, outputs a given pattern. The algorithm provides a new proof of the description of West-2-stack-sortable permutations, that is permutations that are completely sorted when passed twice through a stack, in terms of patterns. We also solve the long-standing problem of describing West-3-stack-sortable permutations. This requires a new type of generalized permutation pattern we call a decorated pattern.
We obtain a very simple formula for the generating function of bipartite (resp. quasi-bipartite) planar maps with boundaries (holes) of prescribed lengths, which generalizes certain expressions obtained by Eynard in a book to appear. The formula is derived from a bijection due to Bouttier, Di Francesco and Guitter combined with a process (reminiscent of a construction of Pitman) of aggregating connected components of a forest into a single tree.
We give a new description of the combinatorics of triangulations of even-dimensional cyclic polytopes, and of their bistellar flips. We show that the tropical exchange relation governing the number of intersections between diagonals of a polygon and a lamination (which generalizes to arbitrary surfaces) can also be generalized in a different way, to the setting of higher dimensional cyclic polytopes.
We obtain several properties of extremal statistics in non-crossing configurations with n vertices. We prove that the maximum degree and the largest component are of logarithmic order, and the diameter is of order $\sqrt{n}$. The proofs are based on singularity analysis, an application of the first and second moment method and on the analysis of iterated functions.
We study random lozenge tilings of a certain shape in the plane called the Novak half-hexagon, and compute the correlation functions for this process. This model was introduced by Nordenstam and Young (2011) and has many intriguing similarities with a more well-studied model, domino tilings of the Aztec diamond. The most difficult step in the present paper is to compute the inverse of the matrix whose (i,j)-entry is the binomial coefficient $C(A, B_j-i)$ for indeterminate variables $A$ and $B_1, \dots , B_n.$
\textbfAbstract. The purpose of this paper is to present an algorithm which generates linear extensions for a non-simply-laced d-complete poset with uniform probability. ≠wline
We introduce an arithmetic version of the multivariate Tutte polynomial recently studied by Sokal, and a quasi-polynomial that interpolates between the two. We provide a generalized Fortuin-Kasteleyn representation for representable arithmetic matroids, with applications to arithmetic colorings and flows. We give a new proof of the positivity of the coefficients of the arithmetic Tutte polynomial in the more general framework of pseudo-arithmetic matroids. In the case of a representable arithmetic matroid, we provide a geometric interpretation of the coefficients of the arithmetic Tutte polynomial.
We give a combinatorial proof of Goulden and Jackson's formula for the number of minimal transitive factorizations of a permutation when the permutation has two cycles. We use the recent result of Goulden, Nica, and Oancea on the number of maximal chains of annular noncrossing partitions of type B.
The q-semicircular law as introduced by Bożejko and Speicher interpolates between the Gaussian law and the semicircular law, and its moments have a combinatorial interpretation in terms of matchings and crossings. We prove that the cumulants of this law are, up to some factor, polynomials in q with nonnegative coefficients. This is done by showing that they are obtained by an enumeration of connected matchings, weighted by the evaluation at (1,q) of a Tutte polynomial. The two particular cases q=0 and q=2 have also alternative proofs, related with the fact that these particular evaluation of the Tutte polynomials count some orientations on graphs. Our methods also give a combinatorial model for the cumulants of the free Poisson law.
The Hilbert series of the Garsia-Haiman module can be written as a generating function of standard fillings of Ferrers diagrams. It is conjectured by Haglund and Loehr that the Hilbert series of the diagonal harmonics can be written as a generating function of parking functions. In this paper we present a weight-preserving injection from standard fillings to parking functions for certain cases.
Given a fan $\Delta$ and a cone $\sigma \in \Delta$ let $star^1(\sigma )$ be the set of cones that contain $\sigma$ and are one dimension bigger than $\sigma$ . In this paper we study two cones of piecewise linear functions defined on $\delta$ : the cone of functions which are convex on $star^1(σ\sigma)$ for all cones, and the cone of functions which are convex on $star^1(σ\sigma)$ for all cones of codimension 1. We give nice combinatorial descriptions for these two cones given two different fan structures on the tropical linear space of complete graphs. For the complete graph $K_5$, we prove that with the finer fan subdivision the two cones are not equal, but with the coarser subdivision they are the same. This gives a negative answer to a question of Gibney-Maclagan that for the finer subdivision the two cones are the same.
Baxter numbers are known to count several families of combinatorial objects, all of which come equipped with natural involutions. In this paper, we add a combinatorial family to the list, and show that the known bijections between these objects respect these involutions. We also give a formula for the number of objects fixed under this involution, showing that it is an instance of Stembridge's "$q=-1$ phenomenon''.
Using the expansion of the inverse of the Kostka matrix in terms of tabloids as presented by Eğecioğlu and Remmel, we show that the fusion coefficients can be expressed as an alternating sum over cylindric tableaux. Cylindric tableaux are skew tableaux with a certain cyclic symmetry. When the skew shape of the tableau has a cutting point, meaning that the cylindric skew shape is not connected, or if its weight has at most two parts, we give a positive combinatorial formula for the fusion coefficients. The proof uses a slight modification of a sign-reversing involution introduced by Remmel and Shimozono. We discuss how this approach may work in general.
We characterize by pattern avoidance the Schubert varieties for $\mathrm{GL}_n$ which are local complete intersections (lci). For those Schubert varieties which are local complete intersections, we give an explicit minimal set of equations cutting out their neighbourhoods at the identity. Although the statement of our characterization only requires ordinary pattern avoidance, showing that the Schubert varieties not satisfying our conditions are not lci appears to require working with more general notions of pattern avoidance. The Schubert varieties defined by inclusions, originally introduced by Gasharov and Reiner, turn out to be an important subclass, and we further develop some of their combinatorics. One application is a new formula for certain specializations of Schubert polynomials.
We examine the sets of permutations that are sorted by two passes through a stack with a $D_8$ operation performed in between. From a characterization of these in terms of generalized excluded patterns, we prove two conjectures on their enumeration, that can be refined with the distribution of some statistics. The results are obtained by generating trees.
Dyck tilings were introduced by Kenyon and Wilson in their study of double-dimer pairings. They are certain kinds of tilings of skew Young diagrams with ribbon tiles shaped like Dyck paths. We give two bijections between "cover-inclusive'' Dyck tilings and linear extensions of tree posets. The first bijection maps the statistic (area + tiles)/2 to inversions of the linear extension, and the second bijection maps the "discrepancy'' between the upper and lower boundary of the tiling to descents of the linear extension.
This article presents a methodology that automatically derives a combinatorial specification for the permutation class $\mathcal{C} = Av(B)$, given its basis $B$ of excluded patterns and the set of simple permutations in $\mathcal{C}$, when these sets are both finite. This is achieved considering both pattern avoidance and pattern containment constraints in permutations.The obtained specification yields a system of equations satisfied by the generating function of $\mathcal{C}$, this system being always positive and algebraic. It also yields a uniform random sampler of permutations in $\mathcal{C}$. The method presented is fully algorithmic.
Cylindric plane partitions may be thought of as a natural generalization of reverse plane partitions. A generating series for the enumeration of cylindric plane partitions was recently given by Borodin. As in the reverse plane partition case, the right hand side of this identity admits a simple factorization form in terms of the "hook lengths'' of the individual boxes in the underlying shape. The first result of this paper is a new bijective proof of Borodin's identity which makes use of Fomin's growth diagram framework for generalized RSK correspondences. The second result of this paper is a $(q,t)$-analog of Borodin's identity which extends previous work by Okada in the reverse plane partition case. The third result of this paper is an explicit combinatorial interpretation of the Macdonald weight occurring in the $(q,t)$-analog in terms of the non-intersecting lattice path model for cylindric plane partitions.
We consider the problem of enumerating planar constellations with two points at a prescribed distance. Our approach relies on a combinatorial correspondence between this family of constellations and the simpler family of rooted constellations, which we may formulate algebraically in terms of multicontinued fractions and generalized Hankel determinants. As an application, we provide a combinatorial derivation of the generating function of Eulerian triangulations with two points at a prescribed distance.
Given a graph $G$, the number of nowhere-zero $\mathbb{Z}_q$-flows $\phi _G(q)$ is known to be a polynomial in $q$. We extend the definition of nowhere-zero $\mathbb{Z} _q$-flows to simplicial complexes $\Delta$ of dimension greater than one, and prove the polynomiality of the corresponding function $\phi_{\Delta}(q)$ for certain $q$ and certain subclasses of simplicial complexes.
We prove that on the set of lattice paths with steps $N=(0,1)$ and $E=(1,0)$ that lie between two boundaries $B$ and $T$, the two statistics `number of $E$ steps shared with $B$' and `number of $E$ steps shared with $T$' have a symmetric joint distribution. We give an involution that switches these statistics, preserves additional parameters, and generalizes to paths that contain steps $S=(0,-1)$ at prescribed $x$-coordinates. We also show that a similar equidistribution result for other path statistics follows from the fact that the Tutte polynomial of a matroid is independent of the order of its ground set. Finally, we extend the two theorems to $k$-tuples of paths between two boundaries, and we give some applications to Dyck paths, generalizing a result of Deutsch, and to pattern-avoiding permutations.
We present a new edge selection heuristic and vertex ordering heuristic that together enable one to compute the Tutte polynomial of much larger sparse graphs than was previously doable. As a specific example, we are able to compute the Tutte polynomial of the truncated icosahedron graph using our Maple implementation in under 4 minutes on a single CPU. This compares with a recent result of Haggard, Pearce and Royle whose special purpose C++ software took one week on 150 computers.
Let $W$ be an infinite Coxeter group, and $\Phi$ be the root system constructed from its geometric representation. We study the set $E$ of limit points of "normalized'' roots (representing the directions of the roots). We show that $E$ is contained in the isotropic cone $Q$ of the bilinear form associated to $W$, and illustrate this property with numerous examples and pictures in rank $3$ and $4$. We also define a natural geometric action of $W$ on $E$, for which $E$ is stable. Then we exhibit a countable subset $E_2$ of $E$, formed by limit points for the dihedral reflection subgroups of $W$; we explain how $E_2$ can be built from the intersection with $Q$ of the lines passing through two roots, and we establish that $E_2$ is dense in $E$.
We establish the relationship between volumes of flow polytopes associated to signed graphs and the Kostant partition function. A special case of this relationship, namely, when the graphs are signless, has been studied in detail by Baldoni and Vergne using techniques of residues. In contrast with their approach, we provide combinatorial proofs inspired by the work of Postnikov and Stanley on flow polytopes. As an application of our results we study a distinguished family of flow polytopes: the Chan-Robbins-Yuen polytopes. Inspired by their beautiful volume formula $\prod_{k=0}^{n-2} Cat(k)$ for the type $A_n$ case, where $Cat(k)$ is the $k^{th}$ Catalan number, we introduce type $C_{n+1}$ and $D_{n+1}$ Chan-Robbins-Yuen polytopes along with intriguing conjectures about their volumes.
We describe a perturbation method that can be used to compute the multivariate generating function (MGF) of a non-simple polyhedron, and then construct a perturbation that works for any transportation polytope. Applying this perturbation to the family of central transportation polytopes of order $kn \times n$, we obtain formulas for the MGF of the polytope. The formulas we obtain are enumerated by combinatorial objects. A special case of the formulas recovers the results on Birkhoff polytopes given by the author and De Loera and Yoshida. We also recover the formula for the number of maximum vertices of transportation polytopes of order $kn \times n$.
We consider two recent open problems stating that certain statistics on various sets of combinatorial objects are equidistributed. The first, posed by Anders Claesson and Svante Linusson, relates nestings in matchings on $\{1,2,\ldots,2n\}$ to occurrences of a certain pattern in permutations in $S_n$. The second, posed by Miles Jones and Jeffrey Remmel, relates occurrences of a large class of consecutive permutation patterns to occurrences of the same pattern in the cycles of permutations. We develop a general method that solves both of these problems and many more. We further employ the Garsia-Milne involution principle to obtain purely bijective proofs of these results.
We show that the Galois group of any Schubert problem involving lines in projective space contains the alternating group. Using a criterion of Vakil and a special position argument due to Schubert, this follows from a particular inequality among Kostka numbers of two-rowed tableaux. In most cases, an easy combinatorial injection proves the inequality. For the remaining cases, we use that these Kostka numbers appear in tensor product decompositions of $\mathfrak{sl}_2\mathbb{C}$ -modules. Interpreting the tensor product as the action of certain commuting Toeplitz matrices and using a spectral analysis and Fourier series rewrites the inequality as the positivity of an integral. We establish the inequality by estimating this integral.
We investigate the combinatorial Hopf algebra based on uniform block permutations and we realize this algebra in terms of noncommutative polynomials in inﬁnitely many bi-letters.
A $d$-polytope $P$ is neighborly if every subset of $\lfloor\frac{d}{2}\rfloor $vertices is a face of $P$. In 1982, Shemer introduced a sewing construction that allows to add a vertex to a neighborly polytope in such a way as to obtain a new neighborly polytope. With this, he constructed superexponentially many different neighborly polytopes. The concept of neighborliness extends naturally to oriented matroids. Duals of neighborly oriented matroids also have a nice characterization: balanced oriented matroids. In this paper, we generalize Shemer's sewing construction to oriented matroids, providing a simpler proof. Moreover we provide a new technique that allows to construct balanced oriented matroids. In the dual setting, it constructs a neighborly oriented matroid whose contraction at a particular vertex is a prescribed neighborly oriented matroid. We compare the families of polytopes that can be constructed with both methods, and show that the new construction allows to construct many new polytopes.
We consider unicellular maps, or polygon gluings, of fixed genus. In FPSAC '09 the first author gave a recursive bijection transforming unicellular maps into trees, explaining the presence of Catalan numbers in counting formulas for these objects. In this paper, we give another bijection that explicitly describes the ``recursive part'' of the first bijection. As a result we obtain a very simple description of unicellular maps as pairs made by a plane tree and a permutation-like structure. All the previously known formulas follow as an immediate corollary or easy exercise, thus giving a bijective proof for each of them, in a unified way. For some of these formulas, this is the first bijective proof, e.g. the Harer-Zagier recurrence formula, or the Lehman-Walsh/Goupil-Schaeffer formulas. Thanks to previous work of the second author this also leads us to a new expression for Stanley character polynomials, which evaluate irreducible characters of the symmetric group.
We introduce a functorial construction which, from a monoid, produces a set-operad. We obtain new (symmetric or not) operads as suboperads or quotients of the operad obtained from the additive monoid. These involve various familiar combinatorial objects: parking functions, packed words, planar rooted trees, generalized Dyck paths, Schröder trees, Motzkin paths, integer compositions, directed animals, etc. We also retrieve some known operads: the magmatic operad, the commutative associative operad, and the diassociative operad.
We give in a particular case a combinatorial proof of a recent algebraicity result of Kontsevich; the proof uses generalized one-sided and two-sided Dyck words, or equivalently, excursions and bridges. We indicate a noncommutative version of these notions, which could lead to a full proof. We show also a relation with pointed planar maps.
We use the cluster method in order to enumerate permutations avoiding consecutive patterns. We reprove and generalize in a unified way several known results and obtain new ones, including some patterns of length 4 and 5, as well as some infinite families of patterns of a given shape. Our main tool is the cluster method of Goulden and Jackson. We also prove some that, for a large class of patterns, the inverse of the exponential generating function counting occurrences is an entire function, but we conjecture that it is not D-finite in general.
Arc permutations and unimodal permutations were introduced in the study of triangulations and characters. In this paper we describe combinatorial properties of these permutations, including characterizations in terms of pattern avoidance, connections to Young tableaux, and an affine Weyl group action on them.
We present an equivariant bijection between two actions—promotion and rowmotion—on order ideals in certain posets. This bijection simultaneously generalizes a result of R. Stanley concerning promotion on the linear extensions of two disjoint chains and certain cases of recent work of D. Armstrong, C. Stump, and H. Thomas on noncrossing and nonnesting partitions. We apply this bijection to several classes of posets, obtaining equivariant bijections to various known objects under rotation. We extend the same idea to give an equivariant bijection between alternating sign matrices under rowmotion and under B. Wieland's gyration. Lastly, we define two actions with related orders on alternating sign matrices and totally symmetric self-complementary plane partitions.
We investigate the Zariski closure of the projective equivalence class of a matrix. New results are presented regarding the matrices in this variety and their matroids, and we give equations for the variety. We also discuss the K-polynomial of the closure of a projective equivalence class, and two other geometric invariants that can be obtained from this.
We give a multivariate analog of the type B Eulerian polynomial introduced by Brenti. We prove that this multivariate polynomial is stable generalizing Brenti's result that every root of the type B Eulerian polynomial is real. Our proof combines a refinement of the descent statistic for signed permutations with the notion of real stability—a generalization of real-rootedness to polynomials in multiple variables. The key is that our refined multivariate Eulerian polynomials satisfy a recurrence given by a stability-preserving linear operator.
The symmetric edge polytopes of odd cycles (del Pezzo polytopes) are known as smooth Fano polytopes. In this extended abstract, we show that if the length of the cycle is 127, then the Ehrhart polynomial has a root whose real part is greater than the dimension. As a result, we have a smooth Fano polytope that is a counterexample to the two conjectures on the roots of Ehrhart polynomials.
The number of Monotone Triangles with bottom row $k_1 < k_2 < ⋯< k_n$ is given by a polynomial $\alpha (n; k_1,\ldots,k_n)$ in $n$ variables. The evaluation of this polynomial at weakly decreasing sequences $k_1 ≥k_2 ≥⋯≥k_n $turns out to be interpretable as signed enumeration of new combinatorial objects called Decreasing Monotone Triangles. There exist surprising connections between the two classes of objects – in particular it is shown that $\alpha (n;1,2,\ldots,n) = \alpha (2n; n,n,n-1,n-1,\ldots,1,1)$. In perfect analogy to the correspondence between Monotone Triangles and Alternating Sign Matrices, the set of Decreasing Monotone Triangles with bottom row $(n,n,n-1,n-1,\ldots,1,1)$ is in one-to-one correspondence with a certain set of ASM-like matrices, which also play an important role in proving the claimed identity algebraically. Finding a bijective proof remains an open problem.
We introduce the notion of arithmetic matroid, whose main example is provided by a list of elements in a finitely generated abelian group. We study the representability of its dual, and, guided by the geometry of toric arrangements, we give a combinatorial interpretation of the associated arithmetic Tutte polynomial, which can be seen as a generalization of Crapo's formula.
The Severi variety parametrizes plane curves of degree $d$ with $\delta$ nodes. Its degree is called the Severi degree. For large enough $d$, the Severi degrees coincide with the Gromov-Witten invariants of $\mathbb{CP}^2$. Fomin and Mikhalkin (2009) proved the 1995 conjecture that for fixed $\delta$, Severi degrees are eventually polynomial in $d$. In this paper, we study the Severi varieties corresponding to a large family of toric surfaces. We prove the analogous result that the Severi degrees are eventually polynomial as a function of the multidegree. More surprisingly, we show that the Severi degrees are also eventually polynomial "as a function of the surface". Our strategy is to use tropical geometry to express Severi degrees in terms of Brugallé and Mikhalkin's floor diagrams, and study those combinatorial objects in detail. An important ingredient in the proof is the polynomiality of the discrete volume of a variable facet-unimodular polytope.
The alcove model of the first author and Postnikov describes highest weight crystals of semisimple Lie algebras. We present a generalization, called the quantum alcove model, and conjecture that it uniformly describes tensor products of column shape Kirillov-Reshetikhin crystals, for all untwisted affine types. We prove the conjecture in types $A$ and $C$. We also present evidence for the fact that a related statistic computes the energy function.
Let $M$ be a finite monoid. In this paper we describe how the Cartan invariant matrix of the monoid algebra of $M$ over a field $\mathbb{K}$ of characteristic zero can be expressed using characters and some simple combinatorial statistic. In particular, it can be computed efficiently from the composition factors of the left and right class modules of $M$. When $M$ is aperiodic, this approach works in any characteristic, and generalizes to $\mathbb{K}$ a principal ideal domain like $\mathbb{Z}$. When $M$ is $\mathcal{R}$-trivial, we retrieve the formerly known purely combinatorial description of the Cartan matrix.
This paper discusses a surprising relationship between the quantum cohomology of the variety of complete flags and the partially ordered set of Newton polygons associated to an element in the affine Weyl group. One primary key to establishing this connection is the fact that paths in the quantum Bruhat graph, which is a weighted directed graph with vertices indexed by elements in the finite Weyl group, encode saturated chains in the strong Bruhat order on the affine Weyl group. This correspondence is also fundamental in the work of Lam and Shimozono establishing Peterson's isomorphism between the quantum cohomology of the finite flag variety and the homology of the affine Grassmannian. In addition, using some geometry associated to the poset of Newton polygons, one obtains independent proofs for several combinatorial statements about paths in the quantum Bruhat graph and its symmetries, which were originally proved by Postnikov using the tilted Bruhat order. An important geometric application of this work is an inequality which provides a necessary condition for non-emptiness of certain affine Deligne-Lusztig varieties in the affine flag variety.
The Severi degree is the degree of the Severi variety parametrizing plane curves of degree $d$ with $\delta$ nodes. Recently, Göttsche and Shende gave two refinements of Severi degrees, polynomials in a variable $q$, which are conjecturally equal, for large $d$. At $q=1$, one of the refinements, the relative Severi degree, specializes to the (non-relative) Severi degree. We give a combinatorial description of the refined Severi degrees, in terms of a $q$-analog count of Brugallé and Mikhalkin's floor diagrams. Our description implies that, for fixed $\delta$, the refined Severi degrees are polynomials in $d$ and $q$, for large $d$. As a consequence, we show that, for $\delta \leq 4$ and all $d$, both refinements of Göttsche and Shende agree and equal our $q$-count of floor diagrams.
We introduce a "lifting'' construction for generalized permutohedra, which turns an $n$-dimensional generalized permutahedron into an $(n+1)$-dimensional one. We prove that this construction gives rise to Stasheff's multiplihedron from homotopy theory, and to the more general "nestomultiplihedra,'' answering two questions of Devadoss and Forcey. We construct a subdivision of any lifted generalized permutahedron whose pieces are indexed by compositions. The volume of each piece is given by a polynomial whose combinatorial properties we investigate. We show how this "composition polynomial'' arises naturally in the polynomial interpolation of an exponential function. We prove that its coefficients are positive integers, and conjecture that they are unimodal.
We give a new description of the Pieri rule for $k$-Schur functions using the Bruhat order on the affine type-$A$ Weyl group. In doing so, we prove a new combinatorial formula for representatives of the Schubert classes for the cohomology of affine Grassmannians. We show how new combinatorics involved in our formulas gives the Kostka-Foulkes polynomials and discuss how this can be applied to study the transition matrices between Hall-Littlewood and $k$-Schur functions.
We study the fluctuations of models of random partitions $(\mathbb{P}_n,ω )_n ∈\mathbb{N}$ stemming from the representation theory of the infinite symmetric group. Using the theory of polynomial functions on Young diagrams, we establish a central limit theorem for the values of the irreducible characters $χ ^λ$ of the symmetric groups, with $λ$ taken randomly according to the laws $\mathbb{P}_n,ω$ . This implies a central limit theorem for the rows and columns of the random partitions, and these ``geometric'' fluctuations of our models can be recovered by relating central measures on partitions, generalized riffle shuffles, and Brownian motions conditioned to stay in a Weyl chamber.
The pentagram map, introduced by R. Schwartz, is a birational map on the configuration space of polygons in the projective plane. We study the singularities of the iterates of the pentagram map. We show that a ``typical'' singularity disappears after a finite number of iterations, a confinement phenomenon first discovered by Schwartz. We provide a method to bypass such a singular patch by directly constructing the first subsequent iterate that is well-defined on the singular locus under consideration. The key ingredient of this construction is the notion of a decorated (twisted) polygon, and the extension of the pentagram map to the corresponding decorated configuration space.
We describe a generating tree approach to the enumeration and exhaustive generation of k-nonnesting set partitions and permutations. Unlike previous work in the literature using the connections of these objects to Young tableaux and restricted lattice walks, our approach deals directly with partition and permutation diagrams. We provide explicit functional equations for the generating functions, with k as a parameter.
We investigate the combinatorics and geometry of permutation polytopes associated to cyclic permutation groups, i.e., the convex hulls of cyclic groups of permutation matrices. In the situation that the generator of the group consists of at most two orbits, we can give a complete combinatorial description of the associated permutation polytope. In the case of three orbits the facet structure is already quite complex. For a large class of examples we show that there exist exponentially many facets.
We prove that the Lam-Shimozono ``down operator'' on the affine Weyl group induces a derivation of the affine Fomin-Stanley subalgebra of the affine nilCoxeter algebra. We use this to verify a conjecture of Berg, Bergeron, Pon and Zabrocki describing the expansion of k-Schur functions of ``near rectangles'' in the affine nilCoxeter algebra. Consequently, we obtain a combinatorial interpretation of the corresponding k-Littlewood–Richardson coefficients.
The well-known Gilbert-Shannon-Reeds model for riffle shuffles assumes that the cards are initially cut `about in half' and then riffled together. We analyze a natural variant where the initial cut is biased. Extending results of Fulman (1998), we show a sharp cutoff in separation and L-infinity distances. This analysis is possible due to the close connection between shuffling and quasisymmetric functions along with some complex analysis of a generating function.
We give a polyomino characterisation of recurrent configurations of the sandpile model on the complete bipartite graph $K_{m,n}$ in which one designated vertex is the sink. We present a bijection from these recurrent configurations to decorated parallelogram polyominoes whose bounding box is a $m×n$ rectangle. Other combinatorial structures appear in special cases of this correspondence: for example bicomposition matrices (a matrix analogue of set partitions), and (2+2)-free posets. A canonical toppling process for recurrent configurations gives rise to a path within the associated parallelogram polyominoes. We define a collection of polynomials that we call $q,t$-Narayana polynomials, the generating functions of the bistatistic $(\mathsf{area ,parabounce} )$ on the set of parallelogram polyominoes, akin to Haglund's $(\mathsf{area ,hagbounce} )$ bistatistic on Dyck paths. In doing so, we have extended a bistatistic of Egge et al. to the set of parallelogram polyominoes. This is one answer to their question concerning extensions to other combinatorial objects. We conjecture the $q,t$-Narayana polynomials to be symmetric and discuss the proofs for numerous special cases. We also show a relationship between the $q,t$-Catalan polynomials and our bistatistic $(\mathsf{area ,parabounce}) $on a subset of parallelogram polyominoes.
An $m$-ballot path of size $n$ is a path on the square grid consisting of north and east unit steps, starting at (0,0), ending at $(mn,n)$, and never going below the line $\{x=my\}$. The set of these paths can be equipped with a lattice structure, called the $m$-Tamari lattice and denoted by $\mathcal{T}{_n}^{(m)}$, which generalizes the usual Tamari lattice $\mathcal{T}n$ obtained when $m=1$. This lattice was introduced by F. Bergeron in connection with the study of diagonally coinvariant spaces in three sets of $n$ variables. The representation of the symmetric group $\mathfrak{S}_n$ on these spaces is conjectured to be closely related to the natural representation of $\mathfrak{S}_n$ on (labelled) intervals of the $m$-Tamari lattice studied in this paper. An interval $[P,Q$] of $\mathcal{T}{_n}^{(m)}$ is labelled if the north steps of $Q$ are labelled from 1 to $n$ in such a way the labels increase along any sequence of consecutive north steps. The symmetric group $\mathfrak{S}_n$ acts on labelled intervals of $\mathcal{T}{_n}^{(m)}$by permutation of the labels. We prove an explicit formula, conjectured by F. Bergeron and the third author, for the character of the associated representation of $\mathfrak{S}_n$. In particular, the dimension of the representation, that is, the number of labelled $m$-Tamari intervals of size $n$, is found to be $(m+1)^n(mn+1)^{n-2}$. These results are new, even when $m=1$. The form of these numbers suggests a connection with parking […]
Recently, Kenyon and Wilson introduced a certain matrix M in order to compute pairing probabilities of what they call the double-dimer model. They showed that the absolute value of each entry of the inverse matrix $M^-1$ is equal to the number of certain Dyck tilings of a skew shape. They conjectured two formulas on the sum of the absolute values of the entries in a row or a column of $M^-1$. In this paper we prove the two conjectures. As a consequence we obtain that the sum of the absolute values of all entries of $M^-1$ is equal to the number of complete matchings. We also find a bijection between Dyck tilings and complete matchings.
It is well-known that the derivation modules of Coxeter arrangements are free. Holm began to study the freeness of modules of differential operators on hyperplane arrangements. In this paper, we study the cases of the Coxter arrangements of type A, B and D. In this case, we prove that the modules of differential operators of order 2 are free. We give examples of all the 3-dimensional classical Coxeter arrangements. Two keys for the proof are ``Cauchy–Sylvester's theorem on compound determinants'' and ``Saito–Holm's criterion''.