{
  "id": "2408.05377",
  "version": "v1",
  "published": "2024-08-09T22:59:36.000Z",
  "updated": "2024-08-09T22:59:36.000Z",
  "title": "More results on stack-sorting for set partitions",
  "authors": [
    "Samanyu Ganesh",
    "Lanxuan Xia",
    "Bole Ying"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "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 $\\phi_{\\sigma}$ and $\\phi_{\\overline{\\sigma}}$ pattern-avoidance stack-sorting maps for sock sequences. Xia showed that the $\\phi_{aba}$ map is the only one that eventually sorts all set partitions; in this paper, we prove deeper results regarding $\\phi_{aba}$ and $\\phi_{\\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 $\\phi_{aba}$ or $\\phi_{\\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 $\\phi_{aba}$ and $\\phi_{\\overline{aba}}$ maps. Additionally, we prove results regarding fertility numbers (introduced by Defant) in the context of set partitions and multiple-pattern-avoiding stacks.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-08-09T22:59:36.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "set partitions",
      "sock sequence",
      "results regarding fertility numbers",
      "deterministic version",
      "ordered finite alphabet"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}