Singleton mesh patterns in multidimensional permutations
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917603981656064 |
|---|---|
| author | Avgustinovich, Sergey Kitaev, Sergey Liese, Jeffrey Potapov, Vladimir Taranenko, Anna |
| author_facet | Avgustinovich, Sergey Kitaev, Sergey Liese, Jeffrey Potapov, Vladimir Taranenko, Anna |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2208_12845 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Singleton mesh patterns in multidimensional permutations Avgustinovich, Sergey Kitaev, Sergey Liese, Jeffrey Potapov, Vladimir Taranenko, Anna Combinatorics 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. |
| title | Singleton mesh patterns in multidimensional permutations |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2208.12845 |