Permutation polytopes and indecomposable elements in permutation groups

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:113

Article

Guralnick, Robert M. ; Perkinson, David

关键词: permutation polytopes;    permutation groups;    diameter;    mixing times;   

DOI  :  10.1016/j.jcta.2005.11.004

来源: Elsevier

【 摘 要 】

Each group G of n x n permutation matrices has a corresponding permutation polytope, P(G) := conv(G) subset of 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, [n/2]} is a sharp upper bound on the diameter of the graph of P(G). We also show that P(G) achieves its maximal dimension of (n - 1)(2) precisely when G is 2-transitive. We then extend the results of Pak [I. Pak, Four questions on Birkhoff polytope, Ann. Comb. 4 (1) (2000) 83-90] 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. (c) 2005 Elsevier Inc. All rights reserved.

【 授权许可】

Free