skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Cyclic Sieving for Plane Partitions and Symmetry
The cyclic sieving phenomenon of Reiner, Stanton, and White says that we can often count the fixed points of elements of a cyclic group acting on a combinatorial set by plugging roots of unity into a polynomial related to this set. One of the most impressive instances of the cyclic sieving phenomenon is a theorem of Rhoades asserting that the set of plane partitions in a rectangular box under the action of promotion exhibits cyclic sieving. In Rhoades's result the sieving polynomial is the size generating function for these plane partitions, which has a well-known product formula due to MacMahon. We extend Rhoades's result by also considering symmetries of plane partitions: specifically, complementation and transposition. The relevant polynomial here is the size generating function for symmetric plane partitions, whose product formula was conjectured by MacMahon and proved by Andrews and Macdonald. Finally, we explain how these symmetry results also apply to the rowmotion operator on plane partitions, which is closely related to promotion.  more » « less
Award ID(s):
1802920
PAR ID:
10353963
Author(s) / Creator(s):
Date Published:
Journal Name:
Symmetry, Integrability and Geometry: Methods and Applications
ISSN:
1815-0659
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ; (, Seminaire Lotharingien de Combinatoire)
    We construct an injection from the set of r-fans of Dyck paths of length n into the set of chord diagrams on [n] that intertwines promotion and rotation. This is done in two different ways, namely as fillings of promotion matrices and in terms of Fomin growth diagrams. Our analysis uses the fact that r-fans of Dyck paths can be viewed as highest weight elements of weight zero in crystals of type Br, which in turn can be analyzed using virtual crystals. On the level of Fomin growth diagrams, the virtualization process corresponds to the Roby–Krattenthaler blow up construction. Our construction generalizes to vacillating tableaux as well. We give a cyclic sieving phenomenon on r-fans of Dyck paths using the promotion action. 
    more » « less
  2. ; (, Selecta Mathematica)
    Abstract Kreweras words are words consisting of n $$\mathrm {A}$$ A ’s, n $$\mathrm {B}$$ B ’s, and n $$\mathrm {C}$$ C ’s in which every prefix has at least as many $$\mathrm {A}$$ A ’s as $$\mathrm {B}$$ B ’s and at least as many $$\mathrm {A}$$ A ’s as  $$\mathrm {C}$$ C ’s. Equivalently, a Kreweras word is a linear extension of the poset $$\mathsf{V}\times [n]$$ V × [ n ] . Kreweras words were introduced in 1965 by Kreweras, who gave a remarkable product formula for their enumeration. Subsequently they became a fundamental example in the theory of lattice walks in the quarter plane. We study Schützenberger’s promotion operator on the set of Kreweras words. In particular, we show that 3 n applications of promotion on a Kreweras word merely swaps the $$\mathrm {B}$$ B ’s and $$\mathrm {C}$$ C ’s. Doing so, we provide the first answer to a question of Stanley from 2009, asking for posets with ‘good’ behavior under promotion, other than the four families of shapes classified by Haiman in 1992. We also uncover a strikingly simple description of Kreweras words in terms of Kuperberg’s $$\mathfrak {sl}_3$$ sl 3 -webs, and Postnikov’s trip permutation associated with any plabic graph. In this description, Schützenberger’s promotion corresponds to rotation of the web. 
    more » « less
  3. ; (, Séminaire lotharingien de combinatoire)
    The classical hook-length formula counts the number of standard tableaux of straight shapes, but there is no known product formula for skew shapes. Okounkov– Olshanski (1996) and Naruse (2014) found new positive formulas for the number of standard Young tableaux of a skew shape. We prove various properties of the Okounkov– Olshanski formula: a reformulation similar to the Naruse formula, determinantal formulas for the number of terms, and a q-analogue extending the formula to reverse plane partitions, which complements work by Chen and Stanley for semistandard tableaux. 
    more » « less
  4. ; ; ; ; (, Transactions of the American Mathematical Society)
    We introduce a new basis of quasisymmetric functions, the row-strict dual immaculate functions. We construct a cyclic, indecomposable 0-Hecke algebra module for these functions. Our row-strict immaculate functions are related to the dual immaculate functions of Berg-Bergeron-Saliola-Serrano-Zabrocki (2014-15) by the involution ψ<#comment/> \psi on the ring QSym \operatorname {QSym} of quasisymmetric functions. We give an explicit description of the effect of ψ<#comment/> \psi on the associated 0-Hecke modules, via the poset induced by the 0-Hecke action on standard immaculate tableaux. This remarkable poset reveals other 0-Hecke submodules and quotient modules, often cyclic and indecomposable, notably for a row-strict analogue of the extended Schur functions studied in Assaf-Searles (2019). Like the dual immaculate function, the row-strict dual immaculate function is the generating function of a suitable set of tableaux, corresponding to a specific descent set. We give a complete combinatorial and representation-theoretic picture by constructing 0-Hecke modules for the remaining variations on descent sets, and showing thatallthe possible variations for generating functions of tableaux occur as characteristics of the 0-Hecke modules determined by these descent sets. 
    more » « less
  5. ; ; ; (, Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing)
    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
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email