{
"id": "1809.09158",
"version": "v1",
"published": "2018-09-24T18:40:41.000Z",
"updated": "2018-09-24T18:40:41.000Z",
"title": "Stack-sorting for Words",
"authors": [
"Colin Defant",
"Noah Kravitz"
],
"comment": "23 pages, 8 figures",
"categories": [
"math.CO"
],
"abstract": "We introduce operators $\\mathsf{hare}$ and $\\mathsf{tortoise}$, which act on words as natural generalizations of West's stack-sorting map. We show that the heuristically slower algorithm $\\mathsf{tortoise}$ can sort words arbitrarily faster than its counterpart $\\mathsf{hare}$. We then generalize the combinatorial objects known as valid hook configurations in order to find a method for computing the number of preimages of any word under these two operators. We relate the question of determining which words are sortable by $\\mathsf{hare}$ and $\\mathsf{tortoise}$ to more classical problems in pattern avoidance, and we derive a recurrence for the number of words with a fixed number of copies of each letter (permutations of a multiset) that are sortable by each map. We conclude with several open problems and conjectures. In particular, our investigation of $\\mathsf{tortoise}$-sortable words leads us to conjecture that there are $\\frac{1}{\\ell n+1}{(\\ell+1)n\\choose n}$ $\\ell$-uniform (normalized) words of length $\\ell n$ that avoid the patterns $231$ and $221$; we prove this conjecture in the case $\\ell=2$.",
"revisions": [
{
"version": "v1",
"updated": "2018-09-24T18:40:41.000Z"
}
],
"analyses": {
"subjects": [
"05A05",
"05A15",
"05A19"
],
"keywords": [
"conjecture",
"valid hook configurations",
"sort words arbitrarily faster",
"wests stack-sorting map",
"open problems"
],
"note": {
"typesetting": "TeX",
"pages": 23,
"language": "en",
"license": "arXiv",
"status": "editable"
}
}
}