PD Dr. Andreas Paffenholz

Home

Talks/Events

Publications

Software

Data

Teaching

CV

Database

Fano

normality

permutations

RUT

Birkhoff

other

2s2s

regular

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₆.

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)	S3	⟨(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)	Q1	[0/1]
(8,25,32,15)	Q2	[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))

has facets whose complements are not contained in proper faces.

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.