Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2408.05377 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911983731736576 |
|---|---|
| author | Ganesh, Samanyu Xia, Lanxuan Ying, Bole |
| author_facet | Ganesh, Samanyu Xia, Lanxuan Ying, Bole |
| contents | Let a sock be an element of an ordered finite alphabet A and a sequence of these elements be a sock sequence. In 2023, Xia introduced a deterministic version of Defant and Kravitz's stack-sorting map by defining the $ϕ_σ$ and $ϕ_{\overlineσ}$ pattern-avoidance stack-sorting maps for sock sequences. Xia showed that the $ϕ_{aba}$ map is the only one that eventually sorts all set partitions; in this paper, we prove deeper results regarding $ϕ_{aba}$ and $ϕ_{\overline{aba}}$ as a natural next step. We newly define two algorithms with time complexity $O(n^3)$ that determine if any given sock sequence is in the image of $ϕ_{aba}$ or $ϕ_{\overline{aba}}$ respectively. We also show that the maximum number of preimages that a sock sequence of length $n$ has grows at least exponentially under both the $ϕ_{aba}$ and $ϕ_{\overline{aba}}$ maps. Additionally, we prove results regarding fertility numbers (introduced by Defant) in the context of set partitions and multiple-pattern-avoiding stacks. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_05377 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | More results on stack-sorting for set partitions Ganesh, Samanyu Xia, Lanxuan Ying, Bole Combinatorics Let a sock be an element of an ordered finite alphabet A and a sequence of these elements be a sock sequence. In 2023, Xia introduced a deterministic version of Defant and Kravitz's stack-sorting map by defining the $ϕ_σ$ and $ϕ_{\overlineσ}$ pattern-avoidance stack-sorting maps for sock sequences. Xia showed that the $ϕ_{aba}$ map is the only one that eventually sorts all set partitions; in this paper, we prove deeper results regarding $ϕ_{aba}$ and $ϕ_{\overline{aba}}$ as a natural next step. We newly define two algorithms with time complexity $O(n^3)$ that determine if any given sock sequence is in the image of $ϕ_{aba}$ or $ϕ_{\overline{aba}}$ respectively. We also show that the maximum number of preimages that a sock sequence of length $n$ has grows at least exponentially under both the $ϕ_{aba}$ and $ϕ_{\overline{aba}}$ maps. Additionally, we prove results regarding fertility numbers (introduced by Defant) in the context of set partitions and multiple-pattern-avoiding stacks. |
| title | More results on stack-sorting for set partitions |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2408.05377 |