Patterns in multi-dimensional permutations

Tools

Chen, Shaoshi and Fang, Hanqian and Kitaev, Sergey and Zhang, Candice X.T. (2025) Patterns in multi-dimensional permutations. European Journal of Combinatorics, 130. 104203. ISSN 0195-6698 (https://doi.org/10.1016/j.ejc.2025.104203)

[thumbnail of Chen-etal-EJC-2025-Patterns-in-multi-dimensional-permutations]
Preview
 Text. Filename: Chen-etal-EJC-2025-Patterns-in-multi-dimensional-permutations.pdf
Accepted Author Manuscript
License: Creative Commons Attribution 4.0 logo
Download (867kB)| Preview

Abstract

In this paper, we propose a general framework that extends the theory of permutation patterns to higher dimensions and unifies several combinatorial objects studied in the literature. Our approach involves introducing the concept of a “level” for an element in a multi-dimensional permutation, which can be defined in multiple ways. We consider two natural definitions of a level, each establishing connections to other combinatorial sequences found in the Online Encyclopedia of Integer Sequences (OEIS). Our framework allows us to offer combinatorial interpretations for various sequences found in the OEIS, many of which previously lacked such interpretations. As a notable example, we introduce an elegant combinatorial interpretation for the Springer numbers: they count weakly increasing 3-dimensional permutations under the definition of levels determined by maximal entries.

ORCID iDs

Chen, Shaoshi, Fang, Hanqian, Kitaev, Sergey ORCID logoORCID: https://orcid.org/0000-0003-3324-1647 and Zhang, Candice X.T.;
CORE (COnnecting REpositories)