{
  "id": "1303.3776",
  "version": "v3",
  "published": "2013-03-15T14:01:22.000Z",
  "updated": "2015-06-05T13:24:05.000Z",
  "title": "Factorization of permutations",
  "authors": [
    "Zejun Huang",
    "Chi-Kwong Li",
    "Sharon H. Li",
    "Nung-Sing Sze"
  ],
  "comment": "16 pages, a substantially revised version",
  "categories": [
    "math.CO"
  ],
  "abstract": "We consider the problem of factoring permutations as a product of special types of transpositions, namely, those transpositions involving two positions with bounded distances. In particular, we investigate the minimum number, $\\delta$, such that every permutation can be factored into no more than $\\delta$ special transpositions. This study is related to sorting algorithms, Cayley graphs, and genomics.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2013-05-11T04:02:18.000Z",
      "abstract": "We consider the problem of factorization of permutations. We begin with a discussion of some simple mathematical ideas behind a matching game known as Amidakuji concerning the assignment of $n$ jobs to $n$ people. It is shown that the ideas are related to the study of other topics including sorting algorithms in computer science, permutations in abstract algebra, and research in genomics. We then extend the ideas to obtain new results and discuss new problems on factorization of permutations into special type of transpositions.",
      "comment": "12 pages, 1 figure, a substantially revised version",
      "journal": null,
      "doi": null
    },
    {
      "version": "v3",
      "updated": "2015-06-05T13:24:05.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05A05",
      "05C25"
    ],
    "keywords": [
      "permutations",
      "factorization",
      "simple mathematical ideas",
      "computer science",
      "abstract algebra"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 16,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1303.3776H"
    }
  }
}