An official website of the United States government
Abstract Although both noncrossing partitions and nonnesting partitions are uniformly enumerated for Weyl groups, the exact relationship between these two sets of combinatorial objects remains frustratingly mysterious. In this paper, we give a precise combinatorial answer in the case of the symmetric group: for any standard Coxeter element, we construct an equivariant bijection between noncrossing partitions under theKreweras complementand nonnesting partitions under a Coxeter‐theoretically natural cyclic action we call theKroweras complement. Our equivariant bijection is the unique bijection that is both equivariant and support‐preserving, and is built using local rules depending on a new definition ofcharmed roots. Charmed roots are determined by the choice of Coxeter element — in the special case of the linear Coxeter element , we recover one of the standard bijections between noncrossing and nonnesting partitions.
more »
« less
What’s the difference? a functional pearl on subtracting bijections
It is a straightforward exercise to write a program to add two bijections---resulting in a bijection between two sum types, which runs the first bijection on elements from the left summand and the second bijection on the right. It is much less obvious how to subtract one bijection from another. This problem has been studied in the context of combinatorics, with several computational principles known for producing the difference of two bijections. We consider the problem from a computational and algebraic perspective, showing how to construct such bijections at a high level, avoiding pointwise reasoning or being forced to construct the forward and backward directions separately---without sacrificing performance.
more »
« less
- PAR ID:
- 10605766
- Publisher / Repository:
- Association for Computing Machinery (ACM)
- Date Published:
- Journal Name:
- Proceedings of the ACM on Programming Languages
- Volume:
- 2
- Issue:
- ICFP
- ISSN:
- 2475-1421
- Format(s):
- Medium: X Size: p. 1-21
- Size(s):
- p. 1-21
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
null (Ed.)Abstract We say two posets are doppelgängers if they have the same number of P-partitions of each height k. We give a uniform framework for bijective proofs that posets are doppelgängers by synthesizing K-theoretic Schubert calculus techniques of H. Thomas and A. Yong with M. Haiman’s rectification bijection and an observation of R. Proctor. Geometrically, these bijections reflect the rational equivalence of certain subvarieties of minuscule flag manifolds. As a special case, we provide the 1st bijective proof of a 1983 theorem of R. Proctor—that plane partitions of height k in a rectangle are equinumerous with plane partitions of height k in a shifted trapezoid.more » « less
-
Evil-avoiding permutations, introduced by Kim and Williams in 2022, arise in the study of the inhomogeneous totally asymmetric simple exclusion process. Rectangular permutations, introduced by Chirivì, Fang, and Fourier in 2021, arise in the study of Schubert varieties and Demazure modules. Taking a suggestion of Kim and Williams, we supply an explicit bijection between evil-avoiding and rectangular permutations in $$S_n$$ that preserves the number of recoils. We encode these classes of permutations as regular languages and construct a length-preserving bijection between words in these regular languages. We extend the bijection to another Wilf-equivalent class of permutations, namely the $$1$$-almost-increasing permutations, and exhibit a bijection between rectangular permutations and walks of length $2n-2$ in a path of seven vertices starting and ending at the middle vertex.more » « less
-
Colijn and Plazzotta (2018) [1] described a bijective scheme for associating the unlabeled bifurcating rooted trees with the positive integers. In mathematical and biological applications of unlabeled rooted trees, however, nodes of rooted trees are sometimes multifurcating rather than bifurcating. Building on the bijection between the unlabeled bifurcating rooted trees and the positive integers, we describe bijective schemes for associating the unlabeled multifurcating rooted trees with the positive integers. We devise bijections with the positive integers for a set of trees in which each non-leaf node has exactly k child nodes, and for a set of trees in which each non-leaf node has at most k child nodes. The calculations make use of Macaulay's binomial expansion formula. The generalization to multifurcating trees can assist with the use of unlabeled trees for applications in evolutionary biology, such as the measurement of phylogenetic patterns of genetic lineages in pathogens.more » « less
-
Abstract We construct a moduli space $$\textsf {LP}_{G}$$ of $$\operatorname {SL}_{2}$$-parameters over $${\mathbb {Q}}$$, and show that it has good geometric properties (e.g., explicitly parametrized geometric connected components and smoothness). We construct a Jacobson–Morozov morphism$$\textsf {JM}\colon \textsf {LP}_{G}\to \textsf {WDP}_{G}$$ (where $$\textsf {WDP}_{G}$$ is the moduli space of Weil–Deligne parameters considered by several other authors). We show that $$\textsf {JM}$$ is an isomorphism over a dense open of $$\textsf {WDP}_{G}$$, that it induces an isomorphism between the discrete loci $$\textsf {LP}^{\textrm {disc}}_{G}\to \textsf {WDP}_{G}^{\textrm {disc}}$$, and that for any $${\mathbb {Q}}$$-algebra $$A$$ it induces a bijection between Frobenius semi-simple equivalence classes in $$\textsf {LP}_{G}(A)$$ and Frobenius semi-simple equivalence classes in $$\textsf {WDP}_{G}(A)$$ with constant (up to conjugacy) monodromy operator.more » « less
