{
  "id": "2309.14644",
  "version": "v1",
  "published": "2023-09-26T03:53:58.000Z",
  "updated": "2023-09-26T03:53:58.000Z",
  "title": "Deterministic stack-sorting for set partitions",
  "authors": [
    "Janabel Xia"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "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 $\\phi_{\\sigma}$ for sock sequences that uses a $\\sigma$-avoiding stack, where pattern containment need not be consecutive. When $\\sigma = 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 \\geq 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 $\\phi_{aba}$, and we also obtain asymptotics for the number of sock patterns of length $n$ that are $1$-stack-sortable under $\\phi_{aba}$. Finally, we show that for all unsorted sock patterns $\\sigma \\neq a\\cdots a b a \\cdots a$, the map $\\phi_{\\sigma}$ cannot eventually sort all sock sequences on any multiset $M$ unless every sock sequence on $M$ is already sorted.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-09-26T03:53:58.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "sock sequence",
      "set partitions",
      "sock patterns",
      "distinct socks",
      "define equivalence classes"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}