Permutation Polytope Resource Page
joint work with Barbara
Baumeister (RG Group Theory and Applications)
This page contains lists and resources refered to in the paper
On permutation polytopes.
We remark that all permutation polytopes and their faces are 0/1polytopes.
 In the [gap] column you find explicit GAPcode for a permutation group G.
 In the [poly] column you find the permutation polytope P(G) associated to the group G, given in the
polymake format,
which also contains the information, how this polytope was generated from the GAP file.
 In the [face] column you find the face of P(G) that realizes the desribed combinatorial type.
 In the [0/1] column you find a combinatorially equivalent 0/1polytope from the list of
Aichholzer, given
in the polymake format.
2dimensional faces of permutation polytopes
There are only two possible combinatorial types of
2dimensional faces, a triangle and a square. Both appear already as permutation polytopes.
Combin. type 
fvector 
Isom. type 
Eff. equiv type 
Resources 
triangle 
(3,3) 
Z/3Z 
〈(123)〉 
[gap]
[poly]

square 
(4,4) 
(Z/2Z)^{2} 
〈(12),(34)〉 
[gap]
[poly]

3dimensional permutation polytopes
Combin. type 
fvector 
Isom. type 
Eff. equiv type 
Resources 
tetrahedron 
(4,6,4) 
Z/4Z 
〈(1234)〉 
[gap]
[poly]

tetrahedron 
(4,6,4) 
(Z/2Z)^{2} 
〈(12)(34),(13)(24)〉 
[gap]
[poly]

triangular prism 
(6,9,5) 
Z/6Z 
〈(12),(345)〉 
[gap]
[poly]

cube 
(8,12,6) 
(Z/2Z)^{3} 
〈(12),(34),(56)〉 
[gap]
[poly]

3dimensional faces of permutation polytopes
Faces of the Birkhoff polytope
These combinatorial types appear as faces of the Birkhoff polytope
B_{6}.
fvector 
Type 
Resources 
(4,6,4) 
simplex 
[face]

(5,8,5) 
square pyramid 
[face]

(6,8,5) 
triangle prism 
[face]

(8,12,6) 
cube 
[face]

Other Faces
The octahedron is the smallest face of a permutation polytope that does not appear as the
face of a Birkhoff polytope.
4dimensional permutation polytopes
Combin. type 
fvector 
Isom. type 
Eff. equiv type 
Resources 
simplex 
(5,10,10,5) 
Z/5Z 
〈(12345)〉 
[gap]
[poly]

Birkhoff polytope 
(6,15,18,9) 
S_{3} 
〈(12),(123)〉 
[gap]
[poly]

prism over tetrahedron 
(8,16,14,6)) 
(Z/2Z)X(z/4z) 
〈(1234),(56)〉 
[gap]
[poly]

prism over tetrahedron 
(8,16,14,6) 
(Z/2Z)^{3} 
〈(12)(34),(13)(24),(56)〉 
[gap]
[poly]

crosspolytope 
(8,24,32,16) 
(Z/2Z)^{3} 
〈(12)(34),(34)(78),(56)(78)〉 
[gap]
[poly]

product of triangles (dual birkhoff) 
(9,18,15,6) 
(Z/3Z)^{2} 
〈(123),(456)〉 
[gap]
[poly]

prism over triangle prism 
(12,24,19,7) 
(Z/6Z)x(Z/2Z) 
〈(12),(345),(67)〉 
[gap]
[poly]

cube 
(16,32,24,8) 
(Z/2Z)^{4} 
〈(12),(34),(56),(78)〉 
[gap]
[poly]

4dimensional faces of permutation polytopes
Any 4dimensional face of a permutation polytope
is a fourdimensional 0/1polytope, possibly living in a higher
dimensional ambient space. However, any such polytope can be
represented as a 4dimensional 0/1polytope. Except for two polytopes, we
could determine, whether such a 0/1polytope appears as the combinatorial type of a
4dimensional face of a permutation polytope.
Faces of the Birkhoff polytope
fvector 
Type 
Resources 
(5,10,10,5) 
simplex 
[0/1]

(6,13,13,6) 
join of segment and square 
[0/1]

(6,15,18,9) 
Birkhoff polytope 
[0/1]

(7,15,14,6) 
pyramid over a prism over a triangle 
[0/1]

(8,16,14,6) 
prism over tetrahedron 
[0/1]

(8,18,17,7) 
Wedge W over base edge of square pyramid 
[0/1]

(9,18,15,6) 
Dual Birkhoff polytope 
[0/1]

(9,20,18,7) 
pyramid over cube 
[0/1]

(10,21,18,7) 
prism over square pyramid 
[0/1]

(12,24,19,7) 
product of triangle and square 
[0/1]

(16,32,24,8) 
cube 
[0/1]

Other Faces
fvector 
Type 
Resources 
(7,17,18,8) 
Dual of W (see above in the list of Birkhoff 4dim. faces) 
[gap]
[poly]
[face]
[0/1]

(7,18,20,9) 
pyramid over octahedron (for explanation of files, please read gapfile) 
[gap]
[poly]
[face]
[0/1]

(8,21,22,9) 
special 0/1 polytope called P in Table 2 of the
paper 
[gap]
[poly]
[face]
[0/1]

(8,24,32,16) 
4crosspolytope (already a permutation polytope) 
[gap]
[poly]
[0/1]

(9,24,24,9) 
wedge over facet of octahedron 
[gap]
[poly]
[face]
[0/1]

(10,28,30,12) 
bipyramid over cube 
[gap]
[poly]
[face]
[0/1]

(10,30,30,10) 
hypersimplex (for explanation of files, please read gapfile) 
[gap]
[poly]
[face]
[0/1]

(12,30,28,10) 
prism over octahedron 
[gap]
[poly]
[face]
[0/1]

Open cases
fvector 
Name in Table 2 of paper 
Resources 
(7,19,23,11) 
Q_{1} 
[0/1]

(8,25,32,15) 
Q_{2} 
[0/1]

9dimensional example
The permutation polytope [poly]
associated to the permutation group
G := Group((1,2,3), (1,2)(4,5), (2,3)(6,7), (6,7,8))

has facets whose complements are not contained in proper faces.
Using the GAPpackage pp.g
 Download the package: pp.g
Start GAP, include the package via:
Read("pp.g");
 Calculation of the faces F(S), see Remark 3.3:
1. Given a subset S of a permutation group G in S_{n}.
2. Calculate the matrix M(S) by the following command:
A:=redpermmat(S,n);
3. Output the polytope F(S) in the polymake format via:
print_out_face(A,G,n,"example.poly");
 Here is an example how to use this package:
We construct a permutation polytope with a set
S
of three vertices such that
F(S)
is not the minimal face containing
S:
> Read("pp.g");
> G:=Group( [ (1,2)(3,4), (1,2)(5,6), (1,2)(7,8) ] );
Group([ (1,2)(3,4), (1,2)(5,6), (1,2)(7,8) ])
This is a 4dimensional crosspolytope. Here are the
vertices:
> Elements(G);
[ (), (5,6)(7,8), (3,4)(7,8), (3,4)(5,6), (1,2)(7,8), (1,2)(5,6), (1,2)(3,4), (1,2)(3,4)(5,6)(7,8) ]
We determine the matrix defined by S:=[ (), (3,4)(7,8), (3,4)(5,6) ]:
> S:=[ (), (3,4)(7,8), (3,4)(5,6) ];
[ (), (3,4)(7,8), (3,4)(5,6) ]
> A:=redpermmat(S,8);
[ [ 1, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 1, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 1, 1, 0, 0, 0, 0 ], [ 0, 0, 1, 1, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 1, 1, 0, 0 ], [ 0,
0, 0, 0, 1, 1, 0, 0 ], [ 0, 0,
0, 0, 0, 0, 1, 1 ], [ 0, 0, 0,
0, 0, 0, 1, 1 ] ]
and find out the number of vertices in
that face:
> check_verts(A,G,8);
()
(5,6)(7,8)
(3,4)(7,8)
(3,4)(5,6)
Found 4 vertices
However, the vertices in
S:=[(), (3,4)(7,8), (3,4)(5,6) ]
do not contain a pair of elements with disjoint support. Therefore, they contain no pair of centrally symmetric vertices,
so the elements of S form a triangle.