The Plücker relations which define the Grassmann manifolds as projective varieties are well known. Grass-mann manifolds are examples of minuscule flag manifolds. We study the generalized Plücker relations for minuscule flag manifolds independent of Lie type. To do this we combinatorially model the Plücker coordinates based on Wild-berger’s construction of minuscule Lie algebra representations; it uses the colored partially ordered sets known asminuscule posets. We obtain, uniformly across Lie type, descriptions of the Plücker relations of “extreme weight”. We show that these are “supported” by “double-tailed diamond” sublattices of minuscule lattices. From this, we obtain a complete set of Plücker relations for the exceptional minuscule flag manifolds. These Plücker relations are straightening laws for their coordinate rings.
The main objects of noncrossing Catalan combinatorics associated to a finite Coxeter system are noncross- ing partitions, sortable elements, and cluster complexes. The first and the third of these have known Fuss–Catalan generalizations. We provide new viewpoints for these, introduce a corresponding generalization of sortable elements as elements in the positive Artin monoid, and show how this perspective ties together all three generalizations.
A q-integral over an order polytope coming from a poset is interpreted as a generating function of linear extensions of the poset. As an application, theq-beta integral and aq-analog of Dirichlet’s integral are computed. A combinatorial interpretation of aq-Selberg integral is also obtained.
In general, the existence of a maximal green sequence is not mutation invariant. In this paper we show that it is in fact mutation invariant for cluster quivers associated to most marked surfaces. We develop a procedure to find maximal green sequences for cluster quivers associated to an arbitrary triangulation of closed higher genus marked surfaces with at least two punctures. As a corollary, it follows that any triangulation of a marked surface with at least one boundary component has a maximal green sequence.
Jean-Christophe Aval, Valentin Féray, Jean-Christophe Novelli
et al.
We consider the multivariate generating series $F_P$ of $P-$partitions in infinitely many variables $x_1, x_2, \ldots$ . For some family of ranked posets $P$, it is natural to consider an analog $N_P$ with two infinite alphabets. When we collapse these two alphabets, we trivially recover $F_P$. Our main result is the converse, that is, the explicit construction of a map sending back $F_P$ onto $N_P$. We also give a noncommutative analog of the latter. An application is the construction of a basis of $\mathbf{WQSym}$ with a non-negative multiplication table, which lifts a basis of $\textit{QSym}$ introduced by K. Luoto.
End-vertices of a given graph search may have some nice properties, as for example it is well known that the last vertex of Lexicographic Breadth First Search (LBFS) in a chordal graph is simplicial, see Rose, Tarjan and Lueker 1976. Therefore it is interesting to consider if these vertices can be recognized in polynomial time or not, as first studied in Corneil, Köhler and Lanlignel 2010. A graph search is a mechanism for systematically visiting the vertices of a graph. At each step of a graph search, the key point is the choice of the next vertex to be explored. Graph searches only differ by this selection mechanism during which a tie-break rule is used. In this paper we study how the choice of the tie-break in case of equality during the search, for a given graph search including the classic ones such as BFS and DFS, can determine the complexity of the end-vertex problem. In particular we prove a counterintuitive NP-completeness result for Breadth First Search solving a problem raised in Corneil, Köhler and Lanlignel 2010.
A driving question in (quantum) cohomology of flag varieties is to find non-recursive, positive combinatorial formulas for expressing the quantum product in a particularly nice basis, called the Schubert basis. Bertram, Ciocan-Fontanine and Fulton provide a way to compute quantum products of Schubert classes in the Grassmannian of $k$-planes in complex $n$-space by doing classical multiplication and then applying a combinatorial rimhook rule which yields the quantum parameter. In this paper, we provide a generalization of this rim hook rule to the setting in which there is also an action of the complex torus. Combining this result with Knutson and Tao's puzzle rule provides an effective algorithm for computing the equivariant quantum Littlewood-Richardson coefficients. Interestingly, this rule requires a specialization of torus weights that is tantalizingly similar to maps in affine Schubert calculus.
Given an odd prime p, we give an explicit factorization over the ring of formal power series with integer coefficients for certain reducible polynomials whose constant term is of the form $p^w$ with $w>1$. Our formulas are given in terms of partial Bell polynomials and rely on the inversion formula of Lagrange.
In this paper we present a work in progress on a conjectural new combinatorial model for the Genocchi numbers. This new model called irreducible k-shapes has a strong algebraic background in the theory of symmetric functions and leads to seemingly new features on the theory of Genocchi numbers. In particular, the natural q-analogue coming from the degree of symmetric functions seems to be unknown so far.
We show that the # product of binary trees introduced by Aval and Viennot (2008) is in fact defined at the level of the free associative algebra, and can be extended to most of the classical combinatorial Hopf algebras.
It is well known that a planar map is bipartite if and only if all its faces have even degree (what we call an even map). In this paper, we show that rooted even maps of positive genus $g$ chosen uniformly at random are bipartite with probability tending to $4^{−g}$ when their size goes to infinity. Loosely speaking, we show that each of the $2g$ fundamental cycles of the surface of genus $g$ contributes a factor $\frac{1}{2}$ to this probability.We actually do more than that: we obtain the explicit asymptotic behaviour of the number of even maps and bipartite maps of given genus with any finite set of allowed face degrees. This uses a generalisation of the Bouttier-Di Francesco-Guitter bijection to the case of positive genus, a decomposition inspired by previous works of Marcus, Schaeffer and the author, and some involved manipulations of generating series counting paths. A special case of our results implies former conjectures of Gao.
We characterize the asymptotics of heights of the trees of de la Briandais and the ternary search trees (TST) of Bentley and Sedgewick. Our proof is based on a new analysis of the structure of tries that distinguishes the bulk of the tree, called the $\textit{core}$, and the long trees hanging down the core, called the $\textit{spaghettis}$.