{
  "id": "math/0503015",
  "version": "v2",
  "published": "2005-03-01T15:07:19.000Z",
  "updated": "2005-11-24T17:03:32.000Z",
  "title": "Permutation polytopes and indecomposable elements in permutation groups",
  "authors": [
    "Robert Guralnick",
    "David Perkinson"
  ],
  "comment": "18 pages. To appear in the Journal of Combinatorial Theory, Series A. A corollary about solvable primitive permutation groups has been added. We have fixed some typos and made revisions according to referees' comments",
  "categories": [
    "math.CO",
    "math.GR"
  ],
  "abstract": "Each group G of nxn permutation matrices has a corresponding permutation polytope, P(G):=conv(G) in R^{nxn}. We relate the structure of P(G) to the transitivity of G. In particular, we show that if G has t nontrivial orbits, then min{2t,floor(n/2)} is a sharp upper bound on the diameter of the graph of P(G); so if G is transitive, the diameter is at most 2. We also show that P(G) achieves its maximal dimension of (n-1)^2 precisely when G is 2-transitive. We then extend results of I. Pak on mixing times for a random walk on P(G). Our work depends on a new result for permutation groups involving writing permutations as products of indecomposable permutations.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2005-11-24T17:03:32.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "permutation groups",
      "indecomposable elements",
      "nxn permutation matrices",
      "sharp upper bound",
      "work depends"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 18,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2005math......3015G"
    }
  }
}