An official website of the United States government
We give a new operator formula for Grothendieck polynomials that generalizes Magyar’s Demazure operator formula for Schubert polynomials. Our proofs are purely combinatorial, contrasting with the geometric and representation theoretic tools used by Magyar. We apply our formula to prove a necessary divisibility condition for a monomial to appear in a given Grothendieck polynomial.
more »
« less
Mixed Dimer Configuration Model in Type D Cluster Algebras
We define a combinatorial model for $$F$$-polynomials and $$g$$-vectors for type $$D_n$$ cluster algebras where the associated quiver is acyclic. Our model utilizes a combination of dimer configurations and double dimer configurations which we refer to as mixed dimer configurations. In particular, we give a graph theoretic recipe that describes which monomials appear in such $$F$$-polynomials, as well as a graph theoretic way to determine the coefficients of each of these monomials. In addition, we prove that a weighting on our mixed dimer configuration model yields the associated $$g$$-vector. To prove this formula, we use a combinatorial formula due to Thao Tran (arXiv:0911.4462, 2009) and provide explicit bijections between her combinatorial model and our own.
more »
« less
- PAR ID:
- 10417796
- Date Published:
- Journal Name:
- The Electronic Journal of Combinatorics
- Volume:
- 30
- Issue:
- 2
- ISSN:
- 1077-8926
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
null (Ed.)Abstract We investigate the long-standing problem of finding a combinatorial rule for the Schubert structure constants in the $$K$$-theory of flag varieties (in type $$A$$). The Grothendieck polynomials of A. Lascoux–M.-P. Schützenberger (1982) serve as polynomial representatives for $$K$$-theoretic Schubert classes; however no positive rule for their multiplication is known in general. We contribute a new basis for polynomials (in $$n$$ variables) which we call glide polynomials, and give a positive combinatorial formula for the expansion of a Grothendieck polynomial in this basis. We then provide a positive combinatorial Littlewood–Richardson rule for expanding a product of Grothendieck polynomials in the glide basis. Our techniques easily extend to the $$\beta$$-Grothendieck polynomials of S. Fomin–A. Kirillov (1994), representing classes in connective $$K$$-theory, and we state our results in this more general context.more » « less
-
A 2D rigidity circuit is a minimal graph G = (V , E) supporting a non-trivial stress in any generic placement of its vertices in the Euclidean plane. All 2D rigidity circuits can be constructed from K4 graphs using combinatorial resultant (CR) operations. A combinatorial resultant tree (CR-tree) is a rooted binary tree capturing the structure of such a construction. The CR operation has a specific algebraic interpretation, where an essentially unique circuit polynomial is associated to each circuit graph. Performing Sylvester resultant operations on these polynomials is in one-to-one correspondence with CR operations on circuit graphs. This mixed combinatorial/algebraic approach led recently to an effective algorithm for computing circuit polynomials. Its complexity analysis remains an open problem, but it is known to be influenced by the depth and shape of CR-trees in ways that have only partially been investigated. In this paper, we present an effective algorithm for enumerating all the CR-trees of a given circuit with n vertices. Our algorithm has been fully implemented in Mathematica and allows for computational experimentation with various optimality criteria in the resulting, potentially exponentially large collections of CR-trees.more » « less
-
Let f: {0, 1}n → {0, 1} be a boolean function, and let f∧(x, y) = f(x ∧ y) denote the AND-function of f, where x ∧ y denotes bit-wise AND. We study the deterministic communication complexity of f∧ and show that, up to a logn factor, it is bounded by a polynomial in the logarithm of the real rank of the communication matrix of f∧. This comes within a logn factor of establishing the log-rank conjecture for AND-functions with no assumptions on f. Our result stands in contrast with previous results on special cases of the log-rank conjecture, which needed significant restrictions on f such as monotonicity or low F2-degree. Our techniques can also be used to prove (within a logn factor) a lifting theorem for AND-functions, stating that the deterministic communication complexity of f∧ is polynomially related to the AND-decision tree complexity of f. The results rely on a new structural result regarding boolean functions f: {0, 1}n → {0, 1} with a sparse polynomial representation, which may be of independent interest. We show that if the polynomial computing f has few monomials then the set system of the monomials has a small hitting set, of size poly-logarithmic in its sparsity. We also establish extensions of this result to multi-linear polynomials f: {0, 1}n → with a larger range.more » « less
-
NA (Ed.)The quantum alcove model associated to a dominant weight plays an important role in many branches of mathematics, such as combinatorial representation theory, the theory of Macdonald polynomials, and Schubert calculus. For a dominant weight, it is proved by Lenart–Lubovsky that the quantum alcove model does not depend on the choice of a reduced alcove path, which is a shortest path of alcoves from the fundamental one to its translation by the given dominant weight. This is established through quantum Yang–Baxter moves, which biject the objects of the models associated to two such alcove paths, and can be viewed as a generalization of jeu de taquin slides to arbitrary root systems. The purpose of this paper is to give a generalization of quantum Yang–Baxter moves to the quantum alcove model corresponding to an arbitrary weight, which was used to express a general Chevalley formula for the equivariantK-group of semi-infinite flag manifolds. The generalized quantum Yang–Baxter moves give rise to a “sijection” (bijection between signed sets), and are shown to preserve certain important statistics, including weights and heights. As an application, we prove that the generating function of these statistics does not depend on the choice of a reduced alcove path. Also, we obtain an identity for the graded characters of Demazure submodules of level-zero extremal weight modules over a quantum affine algebra, which can be thought of as a representation-theoretic analogue of the mentioned Chevalley formula.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.37236/10437
