2024/08/09 by S. Hari Ganesh, Ganesh, Samanyu, Lanxuan Xia +3
Computer Science · Engineering · Mathematics · #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #FOS: Mathematics #graph theory and CDMA systems #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2408.05377
openalex publication_date 2024/08/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 ϕσ 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 ϕ_aba as a natural next step. We newly define two algorithms with time complexity O(n3) that determine if any given sock sequence is in the image of ϕaba or ϕ_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 ϕ_aba maps. Additionally, we prove results regarding fertility numbers (introduced by Defant) in the context of set partitions and multiple-pattern-avoiding stacks.