Singleton mesh patterns in multidimensional permutations
| Autor: | Avgustinovich, Sergey, Kitaev, Sergey, Liese, Jeffrey, Potapov, Vladimir, Taranenko, Anna |
|---|---|
| Rok vydání: | 2022 |
| Předmět: | |
| Zdroj: | J. Combin. Th. A, V. 201, (2024) 105801 |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1016/j.jcta.2023.105801 |
| Popis: | This paper introduces the notion of mesh patterns in multidimensional permutations and initiates a systematic study of singleton mesh patterns (SMPs), which are multidimensional mesh patterns of length 1. A pattern is avoidable if there exist arbitrarily large permutations that do not contain it. As our main result, we give a complete characterization of avoidable SMPs using an invariant of a pattern that we call its rank. We show that determining avoidability for a $d$-dimensional SMP $P$ of cardinality $k$ is an $O(d\cdot k)$ problem, while determining rank of $P$ is an NP-complete problem. Additionally, using the notion of a minus-antipodal pattern, we characterize SMPs which occur at most once in any $d$-dimensional permutation. Lastly, we provide a number of enumerative results regarding the distributions of certain general projective, plus-antipodal, minus-antipodal and hyperplane SMPs. Comment: Theorem 12 and Conjecture 1 are replaced by a more general Theorem 12; the paper is to appear in JCTA |
| Databáze: | arXiv |
| Externí odkaz: |
|