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: A Bijection Between Evil-Avoiding and Rectangular Permutations
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
Award ID(s):
2052036
PAR ID:
10470762
Author(s) / Creator(s):
Publisher / Repository:
Electronic Journal of Combinatorics
Date Published:
Journal Name:
The Electronic Journal of Combinatorics
Volume:
30
Issue:
4
ISSN:
1077-8926
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; (, The Electronic Journal of Combinatorics)
    We study relationships between permutation statistics and pattern-functions, counting the number of times particular patterns occur in a permutation. This allows us to write several familiar statistics as linear combinations of pattern counts, both in terms of a permutation and in terms of its image under the fundamental bijection. We use these enumerations to resolve the question of characterizing so-called "shallow" permutations, whose depth (equivalently, disarray/displacement) is minimal with respect to length and reflection length. We present this characterization in several ways, including vincular patterns, mesh patterns, and a new object that we call "arrow patterns." Furthermore, we specialize to characterizing and enumerating shallow involutions and shallow cycles, encountering the Motzkin and large Schröder numbers, respectively. 
    more » « less
  2. ; (, The Electronic Journal of Combinatorics)
    Pipe dreams and bumpless pipe dreams for vexillary permutations are each known to be in bijection with certain semistandard tableaux via maps due to Lenart and Weigandt, respectively. Recently, Gao and Huang have defined a bijection between the former two sets. In this note we show for vexillary permutations that the Gao-Huang bijection preserves the associated tableaux, giving a new proof of Lenart's result. Our methods extend to give a recording tableau for any bumpless pipe dream. 
    more » « less
  3. ; (, Forum of Mathematics, Sigma)
    Abstract We characterize totally symmetric self-complementary plane partitions (TSSCPP) as bounded compatible sequences satisfying a Yamanouchi-like condition. As such, they are in bijection with certain pipe dreams. Using this characterization and the recent bijection of Gao–Huang between reduced pipe dreams and reduced bumpless pipe dreams, we give a bijection between alternating sign matrices and TSSCPP in the reduced, 1432-avoiding case. We also give a different bijection in the 1432- and 2143-avoiding case that preserves natural poset structures on the associated pipe dreams and bumpless pipe dreams. 
    more » « less
  4. ; ; (, Discrete Mathematics & Theoretical Computer Science)
    We initiate a systematic study of key-avoidance on alternating sign matrices (ASMs) defined via pattern-avoidance on an associated permutation called the \emph{key} of an ASM. We enumerate alternating sign matrices whose key avoids a given set of permutation patterns in several instances. We show that ASMs whose key avoids $231$ are permutations, thus any known enumeration for a set of permutation patterns including $231$ extends to ASMs. We furthermore enumerate by the Catalan numbers ASMs whose key avoids both $312$ and $321$. We also show ASMs whose key avoids $312$ are in bijection with the gapless monotone triangles of [Ayyer, Cori, Gouyou-Beauchamps 2011]. Thus key-avoidance generalizes the notion of $312$-avoidance studied there. Finally, we enumerate ASMs with a given key avoiding $312$ and $321$ using a connection to Schubert polynomials, thereby deriving an interesting Catalan identity. Comment: 28 pages 
    more » « less
  5. ; (, Proceedings of the ACM on Programming Languages)
    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
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email