## 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/1-polytopes.

- In the [gap] column you find explicit GAP-code 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/1-polytope from the list of Aichholzer, given in the polymake format.

### 2-dimensional faces of permutation polytopes

There are only two possible combinatorial types of 2-dimensional faces, a triangle and a square. Both appear already as permutation polytopes.

Combin. type | f-vector | Isom. type | Eff. equiv type | Resources |

triangle | (3,3) | Z/3Z | ⟨(123)⟩ | [gap] [poly] |

square | (4,4) | (Z/2Z)^{2} |
⟨(12),(34)⟩ | [gap] [poly] |

### 3-dimensional permutation polytopes

Combin. type | f-vector | 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] |

### 3-dimensional faces of permutation polytopes

### Faces of the Birkhoff polytope

These combinatorial types appear as faces of the Birkhoff polytope
B_{6}.

f-vector | 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.

f-vector | Type | Resources |

(6,12,8) | octahedron | [gap] [poly] [face] [0/1] |

### 4-dimensional permutation polytopes

Combin. type | f-vector | 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] |

### 4-dimensional faces of permutation polytopes

Any 4-dimensional face of a permutation polytope is a four-dimensional 0/1-polytope, possibly living in a higher dimensional ambient space. However, any such polytope can be represented as a 4-dimensional 0/1-polytope. Except for two polytopes, we could determine, whether such a 0/1-polytope appears as the combinatorial type of a 4-dimensional face of a permutation polytope.

### Faces of the Birkhoff polytope

f-vector | 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

f-vector | Type | Resources |

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

(7,18,20,9) | pyramid over octahedron (for explanation of files, please read gap-file) | [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) | 4-crosspolytope (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 gap-file) | [gap] [poly] [face] [0/1] |

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

### Open cases

f-vector | Name in Table 2 of paper | Resources |

(7,19,23,11) | Q_{1} |
[0/1] |

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

### 9-dimensional 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)) |

### Using the GAP-package `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 4-dimensional 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.