2023/09/26 by Janabel Xia, Xia, Janabel
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Algorithms and Data Compression #Combinatorics (math.CO) #FOS: Mathematics #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2309.14644
openalex publication_date 2023/09/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A sock sequence is a sequence of elements, which we will refer to as socks, from a finite alphabet. A sock sequence is sorted if all occurrences of a sock appear consecutively. We define equivalence classes of sock sequences called sock patterns, which are in bijection with set partitions. The notion of stack-sorting for set partitions was originally introduced by Defant and Kravitz. In this paper, we define a new deterministic stack-sorting map ϕσ for sock sequences that uses a σ-avoiding stack, where pattern containment need not be consecutive. When σ= aba, we show that our stack-sorting map sorts any sock sequence with n distinct socks in at most n iterations, and that this bound is tight for n ≥ 3. We obtain a fine-grained enumeration of the number of sock patterns of length n on r distinct socks that are 1-stack-sortable under ϕaba, and we also obtain asymptotics for the number of sock patterns of length n that are 1-stack-sortable under ϕaba. Finally, we show that for all unsorted sock patterns σ≠ a⋯ a b a ⋯ a, the map ϕσ cannot eventually sort all sock sequences on any multiset M unless every sock sequence on M is already sorted.