Permutation polytopes and indecomposable elements in permutation groups
| dc.creator | Guralnick, Robert | |
| dc.creator | Perkinson, David | |
| dc.date | 2005-03-01 | |
| dc.date | 2005-11-24 | |
| dc.date.accessioned | 2026-07-07T06:39:30Z | |
| dc.date.available | 2026-07-07T06:39:30Z | |
| dc.description | 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. | |
| dc.description | 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 | |
| dc.identifier | https://arxiv.org/abs/math/0503015 | |
| dc.identifier | http://arxiv.org/abs/math/0503015 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/101102 | |
| dc.subject | Combinatorics | |
| dc.subject | Group Theory | |
| dc.title | Permutation polytopes and indecomposable elements in permutation groups | |
| dc.type | text |