# Permutation Polytopes of Cyclic Groups

Barbara Baumeister¹, Christian Haase², Benjamin Nill³, Andreas Paffenholz⁴

¹Universität Bielefeld, Germany

²Goethe-Universität Frankfurt, Germany

³Case Western Reserve University, Cleveland, OH, USA

⁴Technische Universität Darmstadt, Germany

**Abstract.** We investigate the combinatorics and geometry of permutation polytopes associated to cyclic permutation groups, i.e., the convex hulls of cyclic groups of permutation matrices. In the situation that the generator of the group consists of at most two orbits, we can give a complete combinatorial description of the associated permutation polytope. In the case of three orbits the facet structure is already quite complex. For a large class of examples we show that there exist exponentially many facets.

**Résumé.** Nous étudions les propriétés combinatoires et géométriques des polytopes de permutations pour des groupes cycliques. C'est à dire, donné un groupe cyclique de matrices de permutations, nous considérons son enveloppe convexe. Si le générateur du groupe possède un ou deux orbites il y a une déscription simple du polytope. Par contre, le cas de trois (ou plus) orbites est beaucoup plus compliqué. Pour une classe ample d'exemples nous construisons un nombre exponentiel de faces de co-dimension un.

**Keywords:** permutation groups, cyclic groups, convex polytopes, 0/1-polytopes, marginal polytopes

## Introduction

A *Permutation polytope* is the convex hull of a group of permutation matrices. We refer to [2] for some historical and motivational remarks. The most famous permutation polytope is the *Birkhoff polytope*, whose vertex set is the entire set of $n \times n$-permutation matrices. In [2] we proposed the systematic study of permutation polytopes in their own right. We introduced suitable notion of equivalences, studied the vertex-edge graph, products and free sums, and classified all permutation polytopes up to dimension four.

This article is an abridged version of [3], where we investigate permutation polytopes associated to cyclic permutation groups. In order to learn more about general permutation polytopes it seems to be crucial to enhance our understanding of the convex hulls of subgroups generated by only one element. This boils down to the study of the elementary number theory of the cycle structure of the generator permutation. Already a relatively small input can generate fairly complicated polytopes: take the group generated by a permutation which is the product of three disjoint cycles of lengths 10, 18, 45. This leads to a 57-dimensional polytope with 90 vertices and 15373 facets whose vertex-edge graph is complete. This example is about as complex as we can handle computationally. Still, using the structure of a permutation polytope it is possible to determine important invariants of the polytope like the dimension and to give a criterion when the vertex-edge graph is complete (see Section 2). For groups generated by a permutation
which is a product of at most two cycles we can characterize the polytopes completely (Proposition 3.3). However, the previous example indicates that in the situation of three cycles the complexity of the facet structure of these polytopes becomes enormous. We show in Theorem 3.5 that the number of facets in such a specific situation grows indeed exponentially in the dimension.

In many respects, our experience has turned out to be similar to the challenges faced by Hood and Perkinson [11] when investigating the facets of the permutation polytope associated to the group of even permutations. They also constructed exponentially many facets with respect to the dimension of the polytope. However, in their situation the number of vertices grows exponentially as well, while in our case the number of vertices remains polynomially bounded.

The features of many of these objects such as a large number of facets and a complete vertex-edge graph are reminiscent of the properties of cyclic polytopes [20, pp.10-16]. While the latter ones are simplicial, in many of the cases considered here, each facet contains far more than half of the total number of vertices of the polytope. Permutation polytopes of cyclic permutation groups might be considered as highly symmetric analogues of cyclic polytopes. It was recently shown by Rehn [16] that if the order of a cyclic permutation group is $n = k_1 \cdots k_r$, where $k_1, \ldots, k_r$ are coprime prime powers, then the associated permutation polytope has at least $k_1! \cdots k_r!$ many affine automorphisms. On the other hand, Kaibel and Waßmer [15] show that the order of the combinatorial automorphism group of a cyclic polytope is at most twice its number of vertices.

Cyclic permutation polytopes – and more generally abelian permutation polytopes – are instances of so-called marginal polytopes. Their inequality description is important in statistics and optimization. This will be explored in an upcoming paper [4], see also the last section.

### Note

One should not confuse ‘permutation polytopes’ with ‘orbitopes’, the convex hull of an orbit of a compact group acting linearly on a vector space. Recently, Sanyal, Sottile and Sturmfels [17] gave a systematic approach to orbitopes. They also studied the permutation polytopes associated to the groups $O(n)$ and $SO(n)$. In this setting permutation polytopes are called *tautological orbitopes*. Since for each orbitope there is a permutation polytope mapping linearly onto it, permutation polytopes serve as *initial objects* in this context.

### Organization of the paper.

In Section 1 we introduce notation and basic properties. In Section 2 we give formulas for the dimension and investigate the vertex-edge graph. In Section 3 we study closely the situation when the group generator is decomposed in at most three cycles. While we can completely describe the case of the one or two cycles, the first difficult situation occurs for three cycles, where we construct a large family of facets for one infinite class of examples. In Section 4 we sketch the results in the forthcoming paper [4].

### Acknowledgments

Many of these results are based on extensive calculations using the software packages GAP [8] and polymake [12]. The last three authors were supported by Emmy Noether fellowship HA 4383/1 of the German Research Foundation (DFG). The third author is supported by the US National Science Foundation (DMS 1203162). The last author is supported by the DFG Priority Program 1489.
# 1 Notation and Basic Properties

## 1.1 Notation

For a positive integer $n \in \mathbb{N}$ we denote

$$[n] := \{1, \dots, n\}.$$

Since it will be more suitable later on, we also define

$$[[n]] := \{0, \dots, n-1\}.$$

For a finite set $I \subset \mathbb{N}$ we denote by $\gcd(I)$ and $\gcd(I)$ the greatest common divisor and the least common multiple of all elements in $I$, respectively. By convention $\gcd(\emptyset) := 0$ and $\gcd(\emptyset) := 1$. For integers $k, l \in \mathbb{Z}$ we write $k | l$ if $k$ divides $l$.

The convex, affine and linear hull of a set $S$ in a real vector space will be denoted by $\text{conv}(S)$, $\text{aff}(S)$ and by $\text{lin}(S)$, respectively.

## 1.2 Representation polytopes

Let $V$ be a real $n$-dimensional vector space. Then $\text{GL}(V)$ denotes the set of automorphisms. By choosing a basis we can identify $\text{GL}(V)$ with the set $\text{GL}_n(\mathbb{R})$ of invertible $n \times n$-matrices. In the same way, we identify $\text{End}(V)$ with the vector space $\text{Mat}_n(\mathbb{R})$ of $n \times n$-matrices.

Let $G$ be a group. A homomorphism $\rho: G \to \text{GL}(V)$ is called a *real representation*. In this case

$$(\rho) := \text{conv}(\rho(g) : g \in G) \subseteq \text{Mat}_n(\mathbb{R}) \cong \mathbb{R}^{n^2}$$

is called the associated *representation polytope*.

## 1.3 Permutation polytopes

The symmetric group $S_n$ acts on the set $[n]$. By identifying $[n]$ with the basis vectors $\{e_1, \dots, e_n\}$ of $\mathbb{R}^n$, we get a representation $S_n \to \text{GL}(\mathbb{R}^n)$. This map identifies the symmetric group $S_n$ with the set of $n \times n$ permutation matrices, i.e., the set of matrices with entries 0 or 1 such that in any column and any row there is precisely one 1. For a subset $G \subseteq S_n$ we let $\text{M}(G)$ be the corresponding set of permutation matrices. For $S \subseteq G$ we let $\langle S \rangle$ be the smallest subgroup of $G$ containing $S$.

An injective homomorphism $G \to S_n$ is called *permutation representation*. Subgroups $G \le S_n$ are called *permutation groups*. In this case, the representation polytope

$$P(G) := \text{conv}(\text{M}(G))$$

is called the *permutation polytope associated to* $G$.

The special case $G = S_n$ yields the well-known $n$th Birkhoff polytope $B_n := P(\text{M}(S_n))$ (see e.g. [5]). It has dimension $(n-1)^2$.

When working with permutation polytopes, one would like to identify permutation groups that clearly define affinely equivalent permutation polytopes. Therefore, we introduced in [2] the notion of effectively equivalence. Two permutation groups are effectively equivalent if they are isomorphic as abstract groups such that via this isomorphism the permutation representations contain the same non-trivial irreducible factors. In this case, the associated permutation polytopes are affinely equivalent. The vector space $\text{Mat}_n(\mathbb{R})$ in which permutation polytopes live comes also with a natural lattice $\text{Mat}_n(\mathbb{Z})$ of integral matrices. Lattice equivalence of permutation polytopes is a subtle issue – cf. [2, Example 2.9].
# 2 Dimension and vertex-edge graph

## 2.1 Our setting

In this section, we give formulas for the dimension and the vertex degree of cyclic permutation polytopes in terms of the cycle type of the generator permutation. Let $G = \langle g \rangle$, where $g$ has a disjoint cycle decomposition into $t$ cycles of lengths $\ell_1, \dots, \ell_t$. In this case, we set

$$d := |G| = o(g) = \text{lcm}(\ell_1, \dots, \ell_t),$$

$$\text{so } G = \{e, g, \dots, g^{d-1}\}.$$

## 2.2 Dimension formula

In our setting, we can explicitly determine the dimension of $P(G)$ using a result by Guralnick and Perkinson [10]. For the proof of the following two results see [3].

**Proposition 2.1** $\dim(P(G))$ equals the number of $\ell_i^{th}$-roots of unity, $i \in [t]$, which are different from 1.

**Corollary 2.2**

$$\dim(P(G)) = -1 + \sum_{\emptyset \neq I \subseteq [t]} (-1)^{|I|+1} \gcd(\ell_i : i \in I).$$

For instance, for $\ell_1 = 2, \ell_2 = 4, \ell_3 = 8$ we get $\dim(P(G)) = 7$, cf. Corollary 2.3.

Since a polytope is a simplex if and only if $\dim(P(G))+1$ equals the number of vertices (here, $|G| = d$) we get from Proposition 2.1 the following criterion (cf. [10]). Let us define the *unimodular m-simplex* $\Delta_m$ as the convex hull of the standard basis vectors in $\mathbb{R}^{m+1}$.

**Corollary 2.3** Let $G$ be a cyclic group with $|G| = d$. Then $P(G)$ is a simplex if and only if $G$ has a cycle of order $d$. In this case, there is an isomorphism $\mathbb{Z}^{n^2} \cap \text{aff}(P(G)) \to \mathbb{Z}^d \cap \text{aff}(\Delta_{d-1})$ mapping the vertices of $P(G)$ onto the vertices of $\Delta_{d-1}$. In other words, $P(G)$ is a unimodular simplex up to lattice isomorphisms. In particular this holds, if $|G|$ is a prime power.

The proof is given in [3]. In particular, since Ehrhart polynomials and volume of unimodular simplices are well-known, this gives an immediate proof of Theorem 1.2(1) and Lemma 3.1 in [6].

Here is another special situation, which is a generalization of 2.3.

**Proposition 2.4** Let $G = \langle g \rangle \leq S_n$ be a cyclic permutation group where the orders $\ell_1, \dots, \ell_t$ of the disjoint cycles of $g$ are pairwise coprime. Then $P(G)$ is a product of unimodular simplices of dimensions $\ell_1 - 1, \dots, \ell_t - 1$.

The proof is contained in [3].

## 2.3 The vertex-edge graph

Based upon previous work by Guralnick and Perkinson [10], it is possible to give an explicit (however, slightly involved) formula for the (constant) vertex degree of a permutation polytope associated to a cyclic group. For this, we refer to Section 2.3 in [3]. Here, let us only note the following application:

Let $g = z_1 \circ \dots \circ z_t$ be the cycle decomposition into $t$ cycles of lengths $\ell_1, \dots, \ell_t$. For $I \subset [t]$ we set

$$I^c := [t] \setminus I, \text{ and } d_I := \text{lcm}(\ell_i \mid i \in I).$$
**Proposition 2.5** The vertex-edge graph of P(G) is complete if and only if for all $I \subseteq [t]$: $d_I = d$ or $d_{I^c} = d$.

This criterion may be used to give many interesting high-dimensional examples of such polytopes, cf. Section 3. We finish the section with the following conjecture, which holds for $l = 1$ by the previous corollary and has been experimentally checked in many cases.

**Conjecture 2.6** Let $l \ge 1$. If $d_I = d$ for all $I \subseteq [t]$ with $|I| \ge \lfloor \frac{t}{l+1} \rfloor$, then $P(G)$ is $(l+1)$-neighborly, i.e, every subset of at most $l+1$ vertices of $P(G)$ forms the vertex set of a face.

# 3 Cyclic permutation groups with few orbits

Cyclic permutation groups with one orbit are completely described in Corollary 2.3. In this section we study those with two or more orbits.

## 3.1 Projection map and joins

Let $G \le S_n$ be a permutation group with orbits $O_1, \dots, O_t$. Let $g \in G$. The permutation matrix $M(g)$ has a blockdiagonal-structure corresponding to the $t$ orbits:

<figure><img src="image_1.png" /><figcaption>**Fig. 1:** A permutation matrix with three orbits and the relevant first rows of each block</figcaption></figure>

For any such matrix let $v_i(M) \in \mathbb{R}^{|O_i|}$ be the first row in the $i$th block. Since any element in $\text{aff}(P(G))$ has such a block-diagonal-structure, we define the linear projection map

$$ \pi : \text{aff}(P(G)) \rightarrow \{x \in \mathbb{R}^n : \sum_{i=1}^{n} x_i = t\} $$

by projecting any matrix $M$ onto $(v_1(M), \dots, v_t(M))$.

Let us assume that $G$ acts cyclic on every orbit, i.e., for each $i \in [t]$ the quotient group $G/K_i$ is cyclic, where $K_i$ is the kernel of the action of $G$ on $O_i$ (the set of group elements which leave each element in $O_i$ fixed). Under this assumption, $\pi$ is a lattice isomorphism of $P(G)$ onto its image in $\mathbb{R}^n$.

In some cases one can say more. For this let us give the following definition.
**Definition 3.1** Let us assume that the polytope P lies in an affine hyperplane of $\mathbb{R}^n$. Then P is a join of polytopes $P_1, \dots, P_s$, if P is the convex hull of $P_1, \dots, P_s$, and $\text{lin}(P) = \bigoplus_{i=1}^s \text{lin}(P_i)$. We say, P a $\mathbb{Z}$-join, if $\text{lin}(P) \cap \mathbb{Z}^n = \bigoplus_{i=1}^s \text{lin}(P_i) \cap \mathbb{Z}^n$.

A typical example is a tetrahedron: it is the join of two disjoint edges.

**Lemma 3.2** Let $G \le S_n$ be a permutation group with orbits $O_1, \dots, O_t$. For each $i \in [t]$ let $G_i$ be the stabilizer of an element $k_i \in O_i$.

If $G$ acts cyclic on every orbit, then the permutation polytope $P(G)$ is the $[G : H]$-fold $\mathbb{Z}$-join of permutation polytopes $P(H)$, for $H := G_1 \cdots G_t \le G$.

**Proof:** Let $K_i$ be the kernel of the action of $G$ on $O_i$, $i \in [t]$. Then, as $G/K_i$ is cyclic, $[G, G] \le K_i$ for $i \in [t]$. Thus $[G, G] \le \bigcap_{i=1}^t K_i = \{e\}$. So $G$ is abelian. This implies that $K_i = G_i$ for $i \in [t]$ and that $H := G_1 \cdots G_t$ is a subgroup of $G$.

Now let $s := [G : H]$, and let $Hg_1, \dots, Hg_s$ be the right cosets of $G/H$. For $j \in [s]$ we define $P_j := \pi(P(Hg_j)) \cong P(Hg_j) \cong P(H)$, where these are lattice isomorphisms. It remains to show that $\pi(P(G))$ is the $\mathbb{Z}$-join of $P_1, \dots, P_s$. It is clear that $\pi(P(G))$ is the convex hull of $P_1, \dots, P_s$.

Let $i, j \in [t]$. We set $k_i^{Hg_j} := \{k_i^{hg_j} : h \in H\}$. Then it is straightforward to prove that the orbit $O_i$ is partitioned into the sets $k_i^{Hg_1}, \dots, k_i^{Hg_s}$. This implies that for $j_1, j_2 \in [s]$ with $j_1 \ne j_2$, the vertices of $P_{j_1}$ and $P_{j_2}$ have disjoint support. Therefore, $\text{lin}(\pi(P(G))) \cap \mathbb{Z}^n = \bigoplus_{i=1}^s \text{lin}(P_i) \cap \mathbb{Z}^n$. $\square$

Let us apply this lemma to the cyclic case. Let $g \in S_n$ have cycle decomposition into cycles of lengths $\ell_1, \dots, \ell_t$. Then $G_i$ is generated by $g^{\ell_i}$ for $i \in [t]$. Let $q := \gcd(\ell_1, \dots, \ell_t)$. Hence, $H$ is generated by $g^q$. Therefore, $[G : H] = q$. Moreover, since $g^q$ has a cycle decomposition into cycles of the lengths $\ell_1/q, \dots, \ell_t/q$ (with possible repetitions), we see that $H$ is effectively equivalent (for this term see [2]) to a permutation group $H'$ generated by a product of $t$ disjoint cycles of lengths $\ell_1/q, \dots, \ell_t/q$. Therefore, $P(H) \cong P(H')$, and this projection map is even a lattice isomorphism. Lemma 3.2 implies that it suffices to consider the case $\gcd(\ell_1, \dots, \ell_t) = 1$ in order to understand the complete face structure of $P(G)$. Together with Proposition 2.4 we obtain the following result.

**Proposition 3.3** Let $G = \langle g \rangle \le S_n$ where $g$ has a cycle decomposition into two cycles of lengths $\ell_1, \ell_2$. We set $q := \gcd(\ell_1, \ell_2)$. Then $P(G)$ is the $q$-fold $\mathbb{Z}$-join of

$$ \Delta_{\ell_1 q - 1} \times \Delta_{\ell_2 q - 1}, $$

where $\Delta_l$ is the $l$-dimensional unimodular simplex.

The dimension of this polytope is $\ell_1 + \ell_2 - \gcd(\ell_1, \ell_2) - 1$ in accordance with the dimension formula given in Corollary 2.2. It has $\text{lcm}(\ell_1, \ell_2)$ vertices and $\ell_1 + \ell_2$ facets.

Ehrhart polynomials count lattice points in multiples of a lattice polytope [19, 7]. In [6] Ehrhart polynomials of certain permutation polytopes are computed, including the case of a cyclic permutation group with one orbit. In [3] we provide the following explicit formula for the generating function of the Ehrhart polynomial of a permutation polytope associated to a cyclic permutation group with two orbits.
**Corollary 3.4** Let $G = \langle g \rangle \le S_n$ where $g$ has a cycle decomposition into two cycles of lengths $\ell_1, \ell_2$. We set $q := \gcd(\ell_1, \ell_2)$. Then

$$ \sum_{k=0}^{\infty} |(kP(G)) \cap \mathbb{Z}^{n^2}| t^k = \frac{\left( \sum_{i=0}^{\min(\ell_1/q-1, \ell_2/q-1)} \binom{\ell_1}{i} \binom{\ell_2}{i} t^i \right)^q}{(1-t)^{\ell_1+\ell_2-\gcd(\ell_1, \ell_2)}}. $$

## 3.2 Permutation polytopes of cyclic groups with three orbits

Let $G = \langle g \rangle \le S_n$ be a cyclic permutation group of order $d$. In Corollary 2.3 and Proposition 3.3 we completely described the combinatorial type of $P(G)$ when $G$ has at most two orbits. In the case of three orbits, we cannot present a corresponding result. Here the situation is much more complicated. In the following we will focus on one crucial case. For three pairwise coprime numbers $a, b, c \in \mathbb{N}_{\ge 2}$ let $z_{ab}$, $z_{ac}$ and $z_{bc}$ be three disjoint cycles of lengths $ab, ac$, and $bc$, respectively. We define

$$ P(a, b, c) := P(\langle z_{ab}z_{ac}z_{bc} \rangle). $$

By Corollary 2.2, $P(a, b, c)$ has dimension $ab + ac + bc - a - b - c$. The number of vertices is $abc$. By Corollary 2.5 all of these polytopes have a complete vertex-edge graph. In Table 1 we present the number of facets which we were able to compute using `polymake` [12]. Note that one very quickly reaches the limits of computational power.

<table><caption>**Tab. 1:** Dimension, vertices and facets of $P(a, b, c)$</caption><thead><tr><th>(a, b, c) |</th><th>(2, 3, 5)</th><th>(2, 3, 7)</th><th>(2, 5, 7)</th><th>(2, 5, 9)</th><th>(3, 4, 5)</th></tr></thead><tbody><tr><th># dimension |</th><td>21</td><td>29</td><td>45</td><td>57</td><td>35</td></tr><tr><th># vertices |</th><td>30</td><td>42</td><td>70</td><td>90</td><td>60</td></tr><tr><th># facets |</th><td>211</td><td>797</td><td>3839</td><td>15373</td><td>29387</td></tr></tbody></table>

The following result shows that the number of facets grows indeed exponentially.

**Theorem 3.5** Let $a, b, c \ge 2$ be pairwise coprime integers.

Then $P(a, b, c)$ has at least $\frac{1}{2}(2^a - 2)(2^b - 2)(2^c - 2) + ab + ac + bc$ facets.

For $a = 2$ this result seems to be optimal, see Table 1. This motivates the following conjecture. Note that the bound in the theorem is not sharp for $a = 3$.

**Conjecture 3.6** Let $b, c \ge 3$ be odd and coprime. Then the number of facets of $P(2, b, c)$ equals $(2^b - 2)(2^c - 2) + 2b + 2c + bc$.

The proof of Theorem 3.5 will be given in the remainder of this paper. We are going to describe explicitly a set of facets for $P(a, b, c)$.

### 3.2.1 Setting and outline of the proof of Theorem 3.5

From now on let $a, b, c$ be pairwise coprime positive integers. Let $n = ab + ac + bc$, and $G \le S_n$ be generated by the product $g$ of three disjoint cycles of lengths $ab, ac$ and $bc$. In the following we will always identify $P(a, b, c)$ with $\pi(P(a, b, c))$, as described in 3.1. In particular, any element of $G$ will be
<table><caption>**Tab. 2:** Coefficients of the vertex barycenter</caption><thead><tr><th colspan="3">k divisible by</th><th rowspan="2">coefficient of g<sup>k</sup> times abc</th><th rowspan="2">no. vertices of this type</th></tr><tr><th>a</th><th>b</th><th>c</th></tr></thead><tbody><tr><td>yes</td><td>no</td><td>no</td><td>a</td><td>(b - 1)(c - 1)</td></tr><tr><td>no</td><td>yes</td><td>no</td><td>b</td><td>(a - 1)(c - 1)</td></tr><tr><td>no</td><td>no</td><td>yes</td><td>c</td><td>(a - 1)(b - 1)</td></tr><tr><td>yes</td><td>yes</td><td>no</td><td>a + b - ab</td><td>c - 1</td></tr><tr><td>yes</td><td>no</td><td>yes</td><td>a + c - ac</td><td>b - 1</td></tr><tr><td>no</td><td>yes</td><td>yes</td><td>b + c - bc</td><td>a - 1</td></tr><tr><td>yes</td><td>yes</td><td>yes</td><td>abc - ab - ac - bc + a + b + c</td><td>1</td></tr></tbody></table>

considered as a vector in $\mathbb{R}^{ab+ac+bc}$ having coordinates $x_0, \dots, x_{ab-1}, y_0, \dots, y_{ac-1}$, and $z_0, \dots, z_{bc-1}$. For $u \in \mathbb{R}^{ab+ac+bc}$, we let $\pi_x(u), \pi_y(u)$, and $\pi_z(u)$ be the projections onto the $x$, $y$, and $z$-coordinates, respectively.

**Proposition 3.7** *The inequalities*

$$x_i \ge 0 \qquad y_j \ge 0 \qquad z_k \ge 0$$

define facets of $P(a, b, c)$.

**Proof:** It suffices to prove that these faces are facets. For this, we will show that for any vertex $g^m$ outside of such a face $F$ we can write

$$\hat{G} := \frac{1}{abc} \sum_{g \in G} g$$

as an affine combination of vertices of the face together with the given vertex.

Up to symmetry, we may assume that the face $F$ of concern is given by $x_1 \ge 0$. In particular, it contains all vertices $g^k$ such that $k$ is divisible by $a$ or $b$. The vertices outside of $F$ are of the form $g^m$ for $m \equiv 1 \pmod{ab}$. Again, up to symmetry, we can choose $m$ such that $m \equiv 0 \pmod{c}$. Now, Table 2 gives the coefficients of $\hat{G}$ as an affine combination of all vertices $g^k$ such that $k$ is divisible by $a, b$ or $c$.

Here is how the reader can check its validity: For instance, the projection on the $x$-coordinates of $abc \hat{G}$ equals $(c \cdots c) \in \mathbb{R}^{ab}$. Let's consider the $x$-coordinate corresponding to 0 (mod $a$) and 1 (mod $b$). There are $c$ vertices $g^k$ in this equivalence class, $c - 1$ not divisible by $c$ and one divisible by $c$. By the first and fifth rows of Table 2, this coordinate of the affine combination equals

$$(c - 1)a + (a + c - ac) = c.$$

In the same manner, the statement can be verified for any coordinate. $\square$

We say that a facet is *essential*, if it is not of the type $x_i \ge 0$, $y_j \ge 0$, or $z_k \ge 0$. There are $n = ab + ac + bc$ non-essential facets. We want to define a large family of essential facets of $P(a, b, c)$. The next subsection defines a certain class of subsets of $[[abc]]$ via projections onto the $x$, $y$, and $z$-coordinates. In Lemma 3.8 we give a general criterion when such a set defines a face of $P(a, b, c)$. The final subsection gives an explicit construction of sets that satisfy the conditions of the lemma. We prove that our vertex sets define facets and count their number.
### 3.2.2 Faces as unions of preimages of projection maps

Throughout, we will identify [[abc]] and G via the natural bijection $i \mapsto g^i$. The Chinese remainder theorem yields a bijection between [[abc]] and [[a]] × [[b]] × [[c]] by mapping k to (k (mod a), k (mod b), k (mod c)). In the same way, we identify [[ab]] and [[a]] × [[b]], [[ac]] and [[a]] × [[c]], and [[bc]] and [[b]] × [[c]].

<figure><img src="image_2.png" /><figcaption>Fig. 2: How to think of $\pi_x, \pi_y, \pi_z$</figcaption></figure>

To any proper subset $S_x \subset [[ab]]$ we associate a subset of [[abc]] via

$$F_x(S_x) := \pi_x^{-1}(\{e_i : i \in S_x\}) = \bigcup_{x \in S_x} x \times [[c]] \subset [[abc]],$$

where $e_0, \dots, e_{ab-1}$ is the standard basis of $\mathbb{R}^{ab}$. This is (the vertex set of) a face of $P(a, b, c)$, given by setting $x_i = 0$ for $i \notin S_x$. Similarly, we define $F_y(S_y)$ and $F_z(S_z)$ for subsets $S_y \subset [[ac]]$ and $S_z \subset [[bc]]$.

In the following we want to consider unions of the form $F_x(S_x) \cup F_y(S_y) \cup F_z(S_z)$ for $S_x \subset [[ab]]$, $S_y \subset [[ac]]$, $S_z \subset [[bc]]$. In general, this is not the vertex set of a face. However, the following lemma gives a sufficient criterion.

**Lemma 3.8** Let $S_x \subset [[ab]]$, $S_y \subset [[ac]]$ and $S_z \subset [[bc]]$. If

$$F_x(S_x) \cap F_y(S_y) \cap F_z(S_z) = \emptyset, \qquad (1)$$

and if for all permutations $(i, j, k)$ of $(x, y, z)$

$$F_i(S_i) \cap \pi_k^{-1}(\pi_k(F_i(S_i) \cap F_j(S_j))) \subseteq F_j(S_j), \qquad (2)$$

then $F_x(S_x) \cup F_y(S_y) \cup F_z(S_z)$ is the vertex set of a (not necessarily proper) face of $P(a, b, c)$.
**Proof:** The first assumption implies that

$$ 
\begin{align*}
S_x \cap \pi_x(F_y(S_y) \cap F_z(S_z)) &= \emptyset, \\
S_y \cap \pi_y(F_x(S_x) \cap F_z(S_z)) &= \emptyset, \\
\text{and} \quad S_z \cap \pi_z(F_x(S_x) \cap F_y(S_y)) &= \emptyset.
\end{align*}
$$

We define a functional $\lambda = (\lambda^{(x)}, \lambda^{(y)}, \lambda^{(z)}) \in \mathbb{R}^n$ in the following way. Let $I_x := [[ab]]$, $I_y := [[ac]]$ and $I_z := [[bc]]$. For all permutations $(i, j, k)$ of $(x, y, z)$ we define

$$ \lambda_m^{(i)} := \begin{cases} -1 & m \in S_i \\ 1 & m \in \pi_i(F_j(S_j) \cap F_k(S_k)) \\ 0 & \text{else.} \end{cases} $$

Let $\langle \cdot, \cdot \rangle$ by the standard scalar product on $\mathbb{R}^n$ and $v \in G$. Using assumptions (1) and (2) it is straightforward to check that $\langle \lambda, v \rangle \ge -1$, with equality if and only if $v \in F_x(S_x) \cup F_y(S_y) \cup F_z(S_z)$. $\square$

### 3.2.3 An explicit construction of facets

**Proposition 3.9** Given three non-trivial subsets $\emptyset \ne I \subseteq [[a]]$, $\emptyset \ne J \subseteq [[b]]$, and $\emptyset \ne K \subseteq [[c]]$, the set

$$ ([[a]] \times [[b]] \times [[c]]) \setminus (I \times J \times K) \setminus (I^c \times J^c \times K^c) $$

is the set of vertices of a facet of $P(a, b, c)$.

**Proof:** We set

$$ 
\begin{align*}
S_x &:= I \times J^c \cup I^c \times J \subset [[a]] \times [[b]] \cong [[ab]], \\
S_y &:= I \times K^c \cup I^c \times K \subset [[a]] \times [[c]] \cong [[ac]] \\
S_z &:= J \times K^c \cup J^c \times K \subset [[b]] \times [[c]] \cong [[bc]]
\end{align*}
$$

Then $S_x, S_y, S_z$ satisfy the conditions of Lemma 3.8. The resulting face $F_x(S_x) \cup F_y(S_y) \cup F_z(S_z)$ has the vertex set $V$ as given in the statement. We claim that this face is, in fact, a facet. To prove this claim, let $v_0 \notin V$ be an additional vertex of $P(a, b, c)$. We show that any other vertex $v_1$ of $P(a, b, c)$ can be written as an affine combination of elements of $V$ together with $v_0$.

As before, we identify the elements of $G$ with triples $(i, j, k) \in [[a]] \times [[b]] \times [[c]]$. We can assume that $v_0 = (i_0, j_0, k_0) \in I \times J \times K$. Then either $v_1 = (i_1, j_1, k_1) \in I \times J \times K$ as well, or $v_1 \in I^c \times J^c \times K^c$.

In the latter case, we see that we have $v_1 = v_0 - (i_0, j_0, k_1) - (i_0, j_1, k_0) - (i_1, j_0, k_0) + (i_1, j_1, k_0) + (i_1, j_0, k_1) + (i_0, j_1, k_1)$, where the last six vertices all belong to $V$. When verifying this statement, the reader should beware that this is actually a sum of elements in $\mathbb{R}^{ab+ac+bc}$.

In the former case, we choose $v_2 \in I^c \times J^c \times K^c$, and construct combinations $v_0 = v_2 + w_0$, $v_1 = v_2 + w_1$, where $w_0$ and $w_1$ are combinations of elements of $V$ with vanishing coefficient sum. But then $v_1 = v_0 - w_0 + w_1$ yields the desired affine representation. $\square$

Finally, let us count the number of different facets we obtain in this way. We have $(2^a-2)(2^b-2)(2^c-2)$ different choices for $I, J, K$. Simultaneously exchanging all three sets by their complements yields the
same facet, so the facet depends only on the pairs $(I, I^c)$, $(J, J^c)$ and $(K, K^c)$. On the other hand, the set $S := (I \times J \times K) \cup (I^c \times J^c \times K^c)$ already determines these pairs: If $(i, j, k) \in S$, then either $I = \{i' \in [[a]] \mid (i', j, k) \in S\}$ or $I^c = \{i' \in [[a]] \mid (i', j, k) \in S\}$, and similarly for $(J, J^c)$ and $(K, K^c)$. Hence, we get $(2^a - 2)(2^b - 2)(2^c - 2)/2$ different facets of this type, and all of these facets are essential by construction. This finishes the proof of Theorem 3.5.

# 4 Outlook

Let us give an outlook on the forthcoming paper [4].

## 4.1 Marginal polytopes

Cyclic permutation polytopes can be seen as so-called marginal polytopes [14, 18] (sets of valid marginal probabilities), as Figure 2 should suggest. For instance, it is possible to trace the inequalities described in Lemma 3.8 back to the 'cycle inequalities' of marginal polytopes [18]. In particular, the 'checkerboard inequalities' in Proposition 3.9 may be also found in that paper. However, it is not shown in [18] that they actually define facets. In [4] we explore this relation in more detail.

## 4.2 3-neighborliness

It follows from [13] using the connection to marginal polytopes that $P(a, b, c)$ are 3-neighborly. In [4] we independently deduce this result from Lemma 3.8. Moreover, we precisely determine which sets of four vertices of $P(a, b, c)$ form a face and which do not.

## 4.3 Further constructions of facets

For $P(3, 4, 5)$ the above construction yields 1307 facets which is much smaller than the observed number of 29387 facets. In [4] we construct another type of facets which yields $2(3^b - 3 \cdot 2^b + 3)(3^c - 3 \cdot 2^c + 3)$ facets of $P(3, b, c)$. In particular, this gives 10800 new facets of $P(3, 4, 5)$.

In [4] we give an explicit, conjectural set of facets which we expect to be a complete set of facets of $P(a, b, c)$ for arbitrary coprime $a, b, c$. If this conjecture would turn out to be true, then the 89-dimensional polytope $P(5, 6, 7)$ with 210 vertices would have more than $10^9$ facets. So, no convex hull algorithm will be able to compute all its facets in our lifetime.

# References

[1] Federico Ardila, Matthias Beck, Serkan Hosten, Julian Pfeifle, and Kim Seashore, *Root polytopes and growth series of root lattices*, SIAM J. Discrete Math. **25** (2011), 360–378.

[2] Barbara Baumeister, Christian Haase, Benjamin Nill, and Andreas Paffenholz, *On permutation polytopes*, Adv. Math. **222** (2009), no. 2, 431–452.

[3] ———, *Permutation polytopes of cyclic groups*, (2011), arXiv:1109.0191.

[4] ———, *Face inequalities of marginal polytopes*, (2011), in preparation.

[5] Louis J. Billera and A. Sarangarajan, *The combinatorics of permutation polytopes*, Billera, Louis J. (ed.) et al., Formal power series and algebraic combinatorics. DIMACS, Ser. Discrete Math. Theor. Comput. Sci. 24, 1996, 1–23.
[6] Katherine Burggraf, Jesus A. De Loera, and Mohammed Omar, *On Volumes of Permutation Polytopes*, (2011), arXiv:1103.0039.

[7] Eugène Ehrhart, *Sur les polyèdres rationnels homothétiques à n dimensions*, C. R. Acad. Sci., Paris **254** (1962), 616-618.

[8] The GAP Group, *GAP – Groups, Algorithms, and Programming, Version 4.4.12*, 2008, (http://www.gap-system.org).

[9] Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, *Concrete mathematics*, second ed., Addison-Wesley Publishing Company, Reading, MA, 1994.

[10] Robert M. Guralnick and David Perkinson, *Permutation polytopes and indecomposable elements in permutation groups*, J. Comb. Theory, Ser. A **113** (2006), no. 7, 1243-1256.

[11] Jeffrey Hood and David Perkinson, *Some facets of the polytope of even permutation matrices*, Linear Algebra Appl. **381** (2004), 237-244.

[12] Michael Joswig and EWgenij Gawrilow, *polymake: A framework for analyzing convex polytopes*, Polytopes – combinatorics and computation (Oberwolfach, 1997), DMV Sem., 29, Birkhäuser, Basel, 2000, 43–73.

[13] Thomas Kahle, *Neighborliness of Marginal Polytopes*, Beiträge Algebra Geom. **51** (2010), 45–56.

[14] Thomas Kahle, Walter Wenzel, and Nihat Ay, *Hierarchical models, marginal polytopes, and linear codes*, Kybernetika (Prague) **45** (2009), no. 2, 189–207.

[15] Volker Kaibel and Arnold Waßmer, *Automorphism groups of cyclic polytopes*, To appear as Chapter 8 of: Frank H. Lutz, *Triangulated Manifolds with Few Vertices, Algorithms and Combinatorics*, Springer, 2011.

[16] Thomas Rehn, *Polyhedral description conversion up to symmetries*, Diploma thesis, Otto von Guericke University Magdeburg, 2010.

[17] Raman Sanyal, Frank Sottile, and Bernd Sturmfels, *Orbitopes*, Mathematika **57** (2011), 275–314.

[18] David Sontag and Tommi Jaakkola, *New outer bounds on the marginal polytope*, Advances in Neural Information Processing Systems 20 (Cambridge, MA) (J.C. Platt, D. Koller, Y. Singer, and S. Roweis, eds.), MIT Press, 2008, 1393–1400.

[19] Richard P. Stanley, *Enumerative combinatorics. Vol. I*, The Wadsworth & Brooks/Cole Mathematics Series, Wadsworth & Brooks/Cole Advanced Books & Software, Monterey, CA, 1986, With a foreword by Gian-Carlo Rota.

[20] Günter M. Ziegler, *Lectures on polytopes*, Graduate Texts in Mathematics, vol. 152, Springer-Verlag, New York, 1995.