{
  "id": "0911.3604",
  "version": "v1",
  "published": "2009-11-18T17:16:01.000Z",
  "updated": "2009-11-18T17:16:01.000Z",
  "title": "The cycle structure of compositions of random involutions",
  "authors": [
    "Michael Lugo"
  ],
  "comment": "17 pages",
  "categories": [
    "math.CO",
    "math.PR"
  ],
  "abstract": "In this article we consider the cycle structure of compositions of pairs of involutions in the symmetric group S_n chosen uniformly at random. These can be modeled as modified 2-regular graphs, giving rise to exponential generating functions. A composition of two random involutions in S_n typically has about n^(1/2) cycles, and the cycles are characteristically of length n^(1/2). Compositions of two random fixed-point-free involutions, on the other hand, typically have about log n cycles and are closely related to permutations with all cycle lengths even. The number of factorizations of a random permutation into two involutions appears to be asymptotically lognormally distributed, which we prove for a closely related probabilistic model. This study is motivated by the observation that the number of involutions in [n] is (n!)^(1/2) times a subexponential factor; more generally the number of permutations with all cycle lengths in a finite set S is n!^(1-1/m) times a subexponential factor, and the typical number of k-cycles is nearly n^(k/m)/k. Connections to pattern avoidance in involutions are also considered.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2009-11-18T17:16:01.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05A16",
      "05A15",
      "05A05",
      "60C05",
      "20B30"
    ],
    "keywords": [
      "random involutions",
      "cycle structure",
      "composition",
      "cycle lengths",
      "subexponential factor"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 17,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2009arXiv0911.3604L"
    }
  }
}