<figure><img src="image_1.png" /></figure>

HAL
open science

Deformed graphical zonotopes

Arnau Padrol, Vincent Pilaud, Germain Poullot

► To cite this version:

Arnau Padrol, Vincent Pilaud, Germain Poullot. Deformed graphical zonotopes. Discrete and Com- putational Geometry, 2023, 10.1007/s00454-023-00586-x. http://dx.doi.org/10.1007/s00454-023-00783-9

HAL Id: hal-03788987

https://hal.science/hal-03788987v1

Submitted on 11 Sep 2024

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Deformed Graphical Zonotopes

Arnau Padrol<fnref n="1" /> ID · Vincent Pilaud<fnref n="2" /> ID · Germain Poullot<fnref n="3" />

Received: 21 February 2023 / Revised: 30 June 2023 / Accepted: 8 July 2023
© The Author(s) 2023

## Abstract

We study deformations of graphical zonotopes. Deformations of the classical permutahedron (which is the graphical zonotope of the complete graph) have been intensively studied in recent years under the name of generalized permutahedra. We provide an irredundant description of the deformation cone of the graphical zonotope associated to a graph $G$, consisting of independent equations defining its linear span (in terms of non-cliques of $G$) and of the inequalities defining its facets (in terms of common neighbors of neighbors in $G$). In particular, we deduce that the faces of the standard simplex corresponding to induced cliques in $G$ form a linear basis of the deformation cone, and that the deformation cone is simplicial if and only if $G$ is triangle-free.

**Keywords** Deformation cones of polytopes · Graphical zonotopes · Generalized permutahedra · Submodular cone

Editor in Charge: Kenneth Clarkson

Partially supported by the French ANR grants CAPPS 17CE400018, CHARMS 19CE400017, and PAGCAP 21CE480020, as well as by grant PID2019-106188GB-I00 funded by MCIN/AEI/10.13039/501100011033 and by project CLaPPo (21.SI03.64658) of Universidad de Cantabria and Banco Santander.

Arnau Padrol
arnau.padrol@ub.edu
https://www.ub.edu/comb/arnaupadrol/

Vincent Pilaud
vincent.pilaud@lix.polytechnique.fr
http://www.lix.polytechnique.fr/pilaud/

Germain Poullot
germain.poullot@imj-prg.fr
https://webusers.imj-prg.fr/germain.poullot

<footnote n="1">1 Departament de Matemàtiques i Informàtica, Universitat de Barcelona, Barcelona, Spain</footnote>

<footnote n="2">2 CNRS & LIX, École Polytechnique, Palaiseau, France</footnote>

<footnote n="3">3 Institut de Mathématiques de Jussieu - Paris Rive Gauche, Sorbonne Université, Paris, France</footnote>
Introduction

The *graphical zonotope* of a graph $G$ is a convex polytope $Z_G$ whose geometry encodes
several combinatorial properties of $G$. For example, its vertices are in bijection with
the acyclic orientations of $G$ [39, Prop. 2.5] and its volume is the number of spanning
trees of $G$ [40, Ex. 4.64]. When $G$ is the complete graph $K_n$, the graphical zonotope
is a translation of the classical $n$-dimensional *permutahedron*. This polytope, obtained
as the convex hull of the $n!$ permutations of the vector $(1, 2, \dots, n) \in \mathbb{R}^n$, was first
introduced by Schoute in 1911 [37], and has become one of the most studied polytopes
in geometric and algebraic combinatorics.

A *deformed permutahedron* (a.k.a. *generalized permutahedron*) is a polytope
obtained from the permutahedron by translating its facet-defining hyperplanes without
passing through a vertex. These polytopes were originally introduced by Edmonds in
1970 under the name of *polymatroids* as a polyhedral generalization of matroids in
the context of linear optimization [16]. They were rediscovered by Postnikov in 2009
[31], who initiated the investigation of their rich combinatorial structure. They have
since become a widely studied family of polytopes that appears naturally in several
areas of mathematics, such as algebraic combinatorics [1, 2, 34], optimization [17],
game theory [14], statistics [27, 28], and economic theory [20]. The set of deformed
permutahedra can be parametrized by the cone of *submodular functions* [16, 31].

In general, a deformation of a polytope P can be equivalently described as (i) a
polytope obtained from P by moving the vertices so that the directions of all edges
are preserved [31, 34], (ii) a polytope obtained from P by translating its facet-defining
halfspaces without passing through a vertex [31, 34], (iii) a polytope whose normal
fan coarsens the normal fan of P [23], (iv) a polytope whose support function is a
convex piecewise linear continuous function supported on the normal fan of P [13,
Sec. 6.1] [15, Sec. 9.5], or (v) a Minkowski summand of a dilate of P [26, 38]. The set
of deformations of P always forms a polyhedral cone under dilation and Minkowski
addition, which is called the *deformation cone* of P [31]. Its interior is called the *type
cone* of the normal fan of P [23], and contains those polytopes with the same normal
fan as P. When P has rational vertex coordinates, then the type cone is known as the
*numerically effective cone* and encodes the embeddings of the associated toric variety
into projective space [13].

There exist several methods to parametrize and describe the deformation cone of a
given polytope (see e.g. [34, App. 15]), for example via the *height deformation space*
and the *wall-crossing inequalities* or via the *edge deformation space* and the *polygonal*
*face equalities*. However, these methods only provide redundant inequality descrip-
tions of the deformation cone. Not even the dimension of the deformation cone is easily
deduced from these descriptions, as illustrated by the difficulty of describing which
fans have a nonempty type cone (i.e. describing *realizable fans* [15, Chap. 9.5.3]), or
a one dimensional type cone (i.e. describing *Minkowski indecomposable* polytopes
[21, 24, 26, 36, 38]).
The search of irredundant facet descriptions of deformation cones of particular families of combinatorial polytopes has received considerable attention recently [3, 7, 9, 10, 12, 32, 33]. One of the motivations sparking this interest arises from the *amplituhedron program* to study scattering amplitudes in mathematical physics [6]. As described in [33, Sec. 1.4], the deformation cone provides canonical realizations of a polytope (seen as a *positive geometry* [5]) in the positive region of the kinematic space, akin to those of the *associahedron* in [4].

The main result of this paper (Theorem 2.6) presents complete irredundant descriptions of the deformation cones of graphical zonotopes. Note that, since graphical zonotopes are deformed permutahedra, their type cones appear as particular faces of the submodular cone. Faces of the submodular cone are far from being well understood. For example, determining its rays remains an open problem since the 1970s, when it was first asked by Edmonds [16].

It is worth noting that most of the existing approaches to compute deformation cones only focus on simple polytopes with simplicial normal fans [11, 34]. Nevertheless, most graphical zonotopes are not simple. They are simple only for chordful graphs (those where every cycle induces a clique), see [34, Prop. 5.2], [22, Rem. 6.2], or [29, Prop. 52]. In this paper, we thus use an alternative approach to describe the deformation cone of a non-simple polytope based on a simplicial refinement of its normal cone.

The paper is organized as follows. We first recall in Sect. 1 the necessary material concerning polyhedral geometry (Sect. 1.1), deformation cones (Sect. 1.2), and graphical zonotopes (Sect. 1.3). We then describe in Sect. 2 the deformation cone of any graphical zonotope, providing first a possibly redundant description (Sect. 2.1), then irredundant descriptions of its linear span (Sect. 2.2) and of its facet-defining inequalities (Sect. 2.3), and finally a characterization of graphical zonotopes with simplicial type cones (Sect. 2.4).

# 1 Preliminaries

## 1.1 Fans and Polytopes

We mainly follow [41] for the notation concerning polyhedral geometry, and we refer to it for more background and details.

A *polytope* P in $\mathbb{R}^d$ is the convex hull of finitely many points. Its *faces* are the zero-sets of non-negative affine functions on P. Its *vertices*, *edges* and *facets* are its faces of dimension 0, dimension 1, and codimension 1, respectively. A *d*-dimensional polytope is called *simple* if every vertex is incident to *d* facets.

Similarly, a *polyhedral cone* C in $\mathbb{R}^d$ is the positive span of finitely many vectors, and its *faces* are the zero-sets of non-negative linear functions on C. Its *rays* and *facets* are its faces of dimension and codimension 1, respectively. Its *lineality space* is the inclusion-minimal face, which is always the largest linear subspace contained in C. A cone is *simplicial* if its rays are linearly independent, and *pointed* if its lineality is {0}. Note that every cone can be decomposed as the free sum of its lineality with a pointed cone (obtained from any section transversal to the lineality).
A fan $\mathcal{F}$ in $\mathbb{R}^d$ is a collection of cones closed under taking faces and such that the intersection of any two cones is a common face of the two cones. Two cones of a fan are *adjacent* if they share a facet. The fan $\mathcal{F}$ is *complete* if the union of its cones is $\mathbb{R}^d$, *essential* if all its cones are pointed, and *simplicial* if all its cones are simplicial. We will say that $\mathcal{F}$ is *supported* on the set of vectors $S$ if every cone of $\mathcal{F}$ is the cone spanned by a subset of $S$. An *essential fan* is supported by representatives of its rays, and this is the unique inclusion-minimal set with this property, up to positive rescaling. For non-essential fans, however, non-canonical choices have to be made. We say that $\mathcal{F}$ *coarsens* $\mathcal{G}$ and that $\mathcal{G}$ *refines* $\mathcal{F}$ if every cone of a fan $\mathcal{F}$ is a union of cones of a fan $\mathcal{G}$.

The normal cone of a face F of a polytope P in $\mathbb{R}^d$ is the polyhedral cone in the dual space $(\mathbb{R}^d)^*$ (which we identify with $\mathbb{R}^d$ via the standard inner product) consisting of the linear forms whose maximal value on P is attained on all the points of F. The normal fan of P is the collection of all the normal cones to its faces. It is always complete, and essential whenever P is full dimensional.

The *Minkowski sum* of two polytopes P and Q is the polytope $P + Q := \{p+q \mid p \in P \text{ and } q \in Q\}$. The normal fan of $P+Q$ is the common refinement of the normal fans of P and Q. We say that P is a *Minkowski summand* of $\mathbb{R}$ if there is a polytope Q such that $P+Q = \mathbb{R}$, and a *weak Minkowski summand* if there is a scalar $\lambda \ge 0$ and a polytope Q such that $P+Q = \lambda \mathbb{R}$. Equivalently, P is a weak Minkowski summand of Q if and only if the normal fan of Q refines the normal fan of P [38, Thm. 4]. The polytope $P \subset \mathbb{R}^d$ is called *Minkowski indecomposable* if all its weak Minkowski summands are of the form $\lambda P + t$ for some scalar $\lambda \ge 0$ and vector $t \in \mathbb{R}^d$.

A *zonotope* is a Minkowski sum of line segments, called its *generators*. Its normal fan is the fan induced by the arrangement of hyperplanes orthogonal to these segments, see [41, Sec. 7.3].

## 1.2 Deformation Cones

The weak Minkowski summands of a polytope $P \subset \mathbb{R}^d$ are also known as *deformations* of P, as they can be always obtained from P by translations of its facet-defining inequalities. It is sometimes convenient to consider the set of deformations of P embedded inside the real vector space of *virtual d-dimensional polytopes* $\mathcal{V}^d$ [30]. This is the set of formal differences of polytopes $P-Q$ under the equivalence relation $(P_1 - Q_1) = (P_2 - Q_2)$ whenever $P_1 + P_2 = Q_1 + Q_2$. Endowed with Minkowski addition, it is the Grothendieck group of the semigroup of polytopes, which are embedded into $\mathcal{V}^d$ via the map $P \mapsto P - \{0\}$. It extends to a real vector space via dilation: for $P-Q \in \mathcal{V}^d$ and $\lambda \in \mathbb{R}$, we set $\lambda(P-Q) := \lambda P - \lambda Q$ when $\lambda \ge 0$, and $\lambda(P-Q) := ((-\lambda)Q) - ((-\lambda)P)$ when $\lambda < 0$. Here, $\lambda P := \{\lambda p \mid p \in P\}$ denotes the dilation of P by $\lambda \ge 0$. (Note in particular that $-P$ does not represent the reflection of P, but its group inverse.)

As we already mentioned, the set of deformations of a polytope $P \subset \mathbb{R}^d$ forms a polyhedral cone under dilation and Minkowski addition, called the *deformation cone* and denoted by $\mathcal{D}\mathcal{C}(P)$:

$$ \mathcal{D}\mathcal{C}(P) := \{Q \subset \mathbb{R}^d \mid Q \text{ is a weak Minkowski summand of } P\}. $$

<figure><img src="image_3.png" /></figure>
Note that $\mathbb{D}\mathbb{C}(P)$ is a closed convex cone (dilations and Minkowski sums preserve weak Minkowski summands) and contains a lineality subspace of dimension $d$ (translations preserve weak Minkowski summands). It is the set of all polytopes whose normal fan coarsens the normal fan $\mathcal{F}$ of $P$. Its interior consists of all polytopes whose normal fan is $\mathcal{F}$, and was called the *type cone* of $\mathcal{F}$ by McMullen [23]. The faces of $\mathbb{D}\mathbb{C}(P)$ are the deformation cones of the Minkowski summands of $P$, and the face lattice is described by the inclusions $\mathbb{D}\mathbb{C}(Q) \subseteq \mathbb{D}\mathbb{C}(R)$ whenever the normal fan of $Q$ coarsens the normal fan of $R$. Having into account the lineality, we will say that the deformation cone is *simplicial* when its quotient modulo translations is simplicial. We will also talk about the rays of $\mathbb{D}\mathbb{C}(P)$, meaning the rays of its quotient modulo translations. They are spanned by the indecomposable Minkowski summands of $P$ of dimension at least 1 (note that 0-dimensional summands account for the space of translations).

There are several linearly isomorphic presentations of this cone. The first ones we are aware of are due to McMullen [23] and Meyer [26], even though a description was already implicit in previous work of Shephard [38]. In fact, the type cone can also be reinterpreted as a chamber of regular triangulations of a vector configuration, as introduced in the theory of secondary polytopes [18], see [15, Sect. 9.5] for details. Other formulations can be found, for example, in the appendix of [34].

The following convenient formulation from [11, Lem. 2.1] shows that the deformation cone of simple polytopes is isomorphic to a polyhedral cone, and provides an explicit inequality description, usually called the *wall-crossing inequalities*.

Let $P \subset \mathbb{R}^d$ be a polytope with normal fan $\mathcal{F}$ supported on the vector set $S$. Let $G$ be the $N \times d$-matrix whose rows are the vectors in $S$. For any height vector $h \in \mathbb{R}^N$, we define the polytope $P_h := \{x \in \mathbb{R}^d \mid Gx \le h\}$. It is not hard to see that any weak Minkowski summand of $P$ is of the form $P_h$ for some $h \in \mathbb{R}^N$.

Moreover, for deformations $P_h$ and $P_{h'}$ of $P$, we have $P_h + P_{h'} = P_{h+h'}$ and $\lambda P_h = P_{\lambda h}$ for any $\lambda > 0$. Hence, the deformation cone, which lies in the space of virtual polyhedra, is linearly isomorphic to the cone

$$ \{h \in \mathbb{R}^N | P_h \in \mathbb{D}\mathbb{C}(P)\}. $$

To describe this cone with the wall-crossing inequalities, we need some extra notation. For any pair of adjacent maximal cones $\mathbb{R}_{\ge 0}\mathbf{R}$ and $\mathbb{R}_{\ge 0}\mathbf{R}'$ of a simplicial fan $\mathcal{F}$ there is a non-zero linear dependence

$$ \sum_{s \in \mathbf{R} \cup \mathbf{R}'} \alpha_{\mathbf{R}, \mathbf{R}'}(s) s = 0 $$

among the rays of $\mathbf{R} \cup \mathbf{R}'$. This dependence is unique up to rescaling, because the vectors in $\mathbf{R}$ are linearly independent. For convenience in the exposition, we will denote by $\alpha_{\mathbf{R}, \mathbf{R}'}(s)$ the coefficient of $s$ in the unique linear dependence such that $\alpha_{\mathbf{R}, \mathbf{R}'}(\mathbf{r}) + \alpha_{\mathbf{R}, \mathbf{R}'}(\mathbf{r}') = 2$, where $\mathbf{R} \setminus \{\mathbf{r}\} = \mathbf{R}' \setminus \{\mathbf{r}'\}$.

**Proposition 1.1** ([11, 18]) Let $P \subset \mathbb{R}^d$ be a simple polytope with simplicial normal fan $\mathcal{F}$ supported on the rays $S$. Then the deformation cone $\mathbb{D}\mathbb{C}(P)$ is the set of
<figure><img src="image_4.png" /><figcaption>Fig. 1 A polygon and its normal fan</figcaption></figure>

polytopes $P_h$ for all $h$ in the cone of $\mathbb{R}^S$ defined by the inequalities

$$ \sum_{s \in \mathbb{R} \cup \mathbb{R}'} \alpha_{\mathbb{R}, \mathbb{R}'}(s) h_s \geq 0 $$

for all adjacent maximal cones $\mathbb{R}_{\geq 0}\mathbb{R}$ and $\mathbb{R}_{\geq 0}\mathbb{R}'$ of $\mathcal{F}$.

**Example 1.2** Consider the hexagon P and its normal fan depicted in Fig. 1. The fan has six rays labeled 1, ..., 6 and six maximal cones labeled a, ..., f. The deformation cone $\mathcal{D}\mathbb{C}(P)$ lies in $\mathbb{R}^6$, but has a 2-dimensional lineality space. The six pairs of adjacent maximal cones of $\mathcal{F}$ give rise to following six defining inequalities for $\mathcal{D}\mathbb{C}(P)$:

$$ H_{ab}^{\geq} : \mathbf{h}_1 + \mathbf{h}_3 - \mathbf{h}_2 \geq 0 \qquad H_{bc}^{\geq} : \mathbf{h}_2 + \mathbf{h}_4 - \mathbf{h}_3 \geq 0 \qquad H_{cd}^{\geq} : \mathbf{h}_3 + \mathbf{h}_5 - 2\mathbf{h}_4 \geq 0 $$

$$ H_{de}^{\geq} : \mathbf{h}_4 + \mathbf{h}_6 - \mathbf{h}_5 \geq 0 \qquad H_{ef}^{\geq} : \mathbf{h}_5 + \mathbf{h}_1 - \mathbf{h}_6 \geq 0 \qquad H_{af}^{\geq} : \mathbf{h}_6 + \mathbf{h}_2 \geq 0 $$

where $H_{ij}^{\geq}$ denotes the halfspace defined by the inequality corresponding to the two adjacent maximal cones i and j. Note that the inequality $H_{af}^{\geq}$ is redundant. The hexagon P corresponds to the height vector (1/2, 3/4, 5/4, 1, 3/2, 5/4).

This characterization can be extended to general (not necessarily simple) polytopes. One straightforward way to do so is via a simplicial refinement of the normal fan. If such a simplicial refinement contains additional rays, then the type cone will be embedded in a higher dimensional space, but projecting out these additional coordinates gives a linear isomorphism with the standard presentation. See [35, Prop. 3] and [33, Prop. 1.7].

**Proposition 1.3** Let $P \subset \mathbb{R}^d$ be a polytope whose normal fan $\mathcal{F}$ is refined by the simplicial fan $\mathcal{G}$ supported on the rays $S$. Then the deformation cone $\mathcal{D}\mathbb{C}(P)$ is the set of polytopes $P_h$ for all $h$ in the cone of $\mathbb{R}^S$ defined by

* the equalities $\sum_{s \in \mathbb{R} \cup \mathbb{R}'} \alpha_{\mathbb{R}, \mathbb{R}'}(s) h_s = 0$ for any adjacent maximal cones $\mathbb{R}_{\geq 0}\mathbb{R}$ and $\mathbb{R}_{\geq 0}\mathbb{R}'$ of $\mathcal{G}$ belonging to the same maximal cone of $\mathcal{F}$,

* the inequalities $\sum_{s \in \mathbb{R} \cup \mathbb{R}'} \alpha_{\mathbb{R}, \mathbb{R}'}(s) h_s \geq 0$ for any adjacent maximal cones $\mathbb{R}_{\geq 0}\mathbb{R}$ and $\mathbb{R}_{\geq 0}\mathbb{R}'$ of $\mathcal{G}$ belonging to distinct maximal cones of $\mathcal{F}$.

<figure><img src="image_5.png" /></figure>
## 1.3 Graphical Zonotopes

Let $G := (V, E)$ be a graph with vertex set $V$ and edge set $E$. The graphical arrangement $\mathcal{A}_G$ is the arrangement of the hyperplanes $\{\mathbf{x} \in \mathbb{R}^V \mid \mathbf{x}_u = \mathbf{x}_v\}$ for all edges $\{u, v\} \in E$. It induces the graphical fan $\mathcal{F}_G$ whose cones are all the possible intersections of one of the sets $\{\mathbf{x} \in \mathbb{R}^V \mid \mathbf{x}_u = \mathbf{x}_v\}$, $\{\mathbf{x} \in \mathbb{R}^V \mid \mathbf{x}_u \ge \mathbf{x}_v\}$, or $\{\mathbf{x} \in \mathbb{R}^V \mid \mathbf{x}_u \le \mathbf{x}_v\}$ for each edge $\{u, v\} \in E$. The lineality of $\mathcal{F}_G$ is the subspace $\mathbb{L}_G$ of $\mathbb{R}^V$ spanned by the characteristic vectors of the connected components of $G$.

The graphical zonotope $Z_G$ is the Minkowski sum of the line segments $[e_u, e_v]$ in $\mathbb{R}^V$ for all edges $\{u, v\} \in E$. Here, $(e_v)_{v \in V}$ denotes the canonical basis of $\mathbb{R}^V$. Note that $Z_G$ lies in a subspace orthogonal to $\mathbb{L}_G$. The graphical fan $\mathcal{F}_G$ is the normal fan of the graphical zonotope $Z_G$.

The following result is well-known. For example, it can be easily deduced from [39, Prop. 2.5] or [8] (for the latter, see that the graphical matroid from Sec. 1.1 is realized by the graphical arrangement, and use the description of the cells of the arrangement in terms of covectors from Sec. 1.2(c)).

An ordered partition $(\mu, \omega)$ of $G$ consists of a partition $\mu$ of $V$ where each part induces a connected subgraph of $G$, together with an acyclic orientation $\omega$ of the quotient graph $G/\mu$. We say that $(\mu, \omega)$ refines $(\mu', \omega')$ if each part of $\mu$ is contained in a part of $\mu'$ and the orientations are compatible; that is, for all $u, v \in V$ if there is a directed path in $\omega$ between the parts of $\mu$ respectively containing $u$ and $v$, then there is a directed path in $\omega'$ between the parts of $\mu'$ respectively containing $u$ and $v$.

**Proposition 1.4** *The face lattice of $\mathcal{F}_G$ is antiisomorphic to the lattice of ordered partitions of $G$ ordered by refinement. Explicitly, the antiisomorphism is given by the map that associates the ordered partition $(\mu, \omega)$ to the cone $C_{\mu,\omega}$ defined by the inequalities $\mathbf{x}_u \le \mathbf{x}_v$ for all $u, v \in V$ such that there is a directed path in $\omega$ from the part containing $u$ to the part containing $v$ (in particular, $\mathbf{x}_u = \mathbf{x}_v$ if $u, v$ are in the same part of $\mu$).*

Some easy consequences of Proposition 1.4 are:

* The maximal cones of $\mathcal{F}_G$ are in bijection with the acyclic orientations of $G$. We denote by $C_\omega$ the maximal cone of $\mathcal{F}_G$ associated to the acyclic orientation $\omega$.

* The minimal cones of $\mathcal{F}_G$, that is the rays of $\mathcal{F}_G/\mathbb{L}_G$, are in bijection with the biconnected subsets of $G$, i.e. non-empty subsets $S$ of $V$ such that there is a disjoint non-empty subset $T$ of $V$ such that $S \cup T$ is a connected component of $G$ and the induced subgraphs $G[S]$ and $G[T]$ are connected.

* The rays of $\mathcal{F}_G/\mathbb{L}_G$ that belong to the maximal cone associated to an acyclic orientation are the biconnected subsets which form an upper set of the acyclic orientation (hence, they are in bijection with the minimal directed cuts of the acyclic orientation).

* Similarly, the rays of $\mathcal{F}_G/\mathbb{L}_G$ that belong to the cone associated to an ordered partition $(\mu, \omega)$ are the biconnected sets that contracted by $\mu$ give rise to an upper set of $\omega$.

Note that the natural embedding of a graphical fan $\mathcal{F}_G$ is not essential, as it has a lineality given by its connected components. This is why we cannot directly talk
about the rays of the fan in the enumeration above. The usual solution to avoid this is to consider the quotient by the subspace $\mathbb{L}_G$. However, this subspace depends on the graph, and with such a quotient we would lose the capacity of uniformly treating all the graphs with a fixed vertex set. We will instead work with the natural non-essential embedding, together with a collection of vectors supporting simultaneously all graphical fans.

**Example 1.5** When $G$ is the complete graph $K_n$, the graphical zonotope is the *per-mutahedron*. The graphical fan is the *braid fan* $\mathcal{B}_n$, induced by the *braid arrangement* consisting of the hyperplanes $\{\mathbf{x} \in \mathbb{R}^n \mid \mathbf{x}_i = \mathbf{x}_j\}$ for all $1 \le i < j \le n$. Its lineality is spanned by the all-ones vector $\mathbb{1}_n := (1, \dots, 1)$. Since all the proper subsets of $[n] := \{1, 2, \dots, n\}$ are biconnected in $K_n$, the face lattice of $\mathcal{B}_n$ is isomorphic to the lattice of ordered partitions of $[n]$. The rays of $\mathcal{B}_n/\mathbb{1}_n$ correspond to proper subsets of $[n]$, and its maximal cells are in bijection with permutations of $[n]$. Each maximal cell is the positive hull of the $n-1$ rays corresponding to the proper upper sets of the order given by the permutation. In particular, $\mathcal{B}_n/\mathbb{1}_n$ is a simplicial fan.

## 2 Graphical Deformation Cones

Our main result is an irredundant facet description of the deformation cone of $Z_G$ for every graph $G := (V, E)$. Our starting point is Proposition 2.4, which gives a (possibly redundant) description derived from Proposition 1.3. It is strongly based on the fact that the braid fan simultaneously refines all the graphical fans. Note however that the braid fan is not simplicial (due to its lineality). The classical approach to overcome this issue is to quotient the braid fan by its lineality space. However, we prefer to triangulate the braid fan, since it simplifies the presentation of the proof.

### 2.1 A First Polyhedral Description

Associate to each subset $S \subseteq V$ the vector

$$ \iota_S := \sum_{v \in S} e_v - \sum_{v \notin S} e_v. $$

This is essentially the characteristic vector of $S$, but it has the advantage that $\iota_V = \mathbb{1}_V$ and $\iota_{\emptyset} = -\mathbb{1}_V$ positively span the line $\mathbb{1}_V \mathbb{R}$, which is the lineality $\mathbb{L}_{K_V}$ of the braid fan.

**Lemma 2.1** For any ordered partition $(\mu, \omega)$ of a graph $G := (V, E)$, we have

$$ C_{\mu, \omega} = \text{cone} \{ \iota_S \mid S \subseteq V \text{ upper set of } \omega \}. $$

Here, we mean that $S$ is an upper set of $\omega$ when contracted by $\mu$. Note that $\emptyset$ and $V$ are always upper sets, which is consistent with the fact that the lineality of $\mathcal{F}_G$ always contains the line spanned by $\mathbb{1}_V$.
<figure><img src="image_6.png" /><figcaption>Fig. 2 The fan $\hat{B}_{123}$ intersected with the unit sphere. (For brevity, here and in the labels we write 123 to denote the set $\{1, 2, 3\}$, and so on.) The braid fan $B_{123}$ is the Cartesian product of a regular hexagonal fan with a line. To obtain $\hat{B}_{123}$, each maximal cell is divided into two simplicial cells, one containing $\iota_{\emptyset}$ and one containing $\iota_{123}$</figcaption></figure>

We will work with a refined version $\hat{B}_V$ of the braid fan whose maximal cells are

$$C_{\sigma}^{\emptyset} := \text{cone} \{ \iota_S | S \subsetneq V \text{ upper set of } \sigma \} \text{ and}$$

$$C_{\sigma}^{V} := \text{cone} \{ \iota_S | \emptyset \neq S \subseteq V \text{ upper set of } \sigma \}$$

for every acyclic orientation of the complete graph $K_V$, which we identify with a permutation $\sigma$ of $V$. An example is depicted in Fig. 2. The following two immediate statements are left to the reader.

**Lemma 2.2** For any finite set $V$:

(i) The fan $\hat{B}_V$ is an essential complete simplicial fan in $\mathbb{R}^V$ supported on the $2^{|V|}$ vectors $\iota_S$ for $S \subseteq V$.

(ii) For any permutation $\sigma$, the maximal cones $C_{\sigma}^{\emptyset}$ and $C_{\sigma}^{V}$ are adjacent, and the unique linear relation supported on the rays of $C_{\sigma}^{\emptyset} \cup C_{\sigma}^{V}$ is $\iota_{\emptyset} + \iota_{V} = \mathbf{0}$.

(iii) The other pairs of adjacent maximal cells are of the form $C_{\sigma}^{X}$ and $C_{\sigma'}^{X}$, where $X \in \{\emptyset, V\}$ and $\sigma = PuvS$ and $\sigma' = PvuS$ are permutations that differ in the inversion of two consecutive elements. The two rays that are not shared by $C_{\sigma}^{X}$ and $C_{\sigma'}^{X}$, are $\iota_{S \cup \{u\}}$ and $\iota_{S \cup \{v\}}$, and the unique linear relation supported on the rays of $C_{\sigma}^{X} \cup C_{\sigma'}^{X}$ is given by

$$\iota_{S \cup \{u\}} + \iota_{S \cup \{v\}} = \iota_{S} + \iota_{S \cup \{u, v\}}.$$

**Lemma 2.3** For any graph $G := (V, E)$:

(i) The fan $\hat{B}_V$ is a simplicial refinement of the graphical fan $\mathcal{F}_G$.

(ii) For an acyclic orientation $\omega$ of $G$ and $S \subseteq V$, we have $\iota_S \in C_{\omega}$ if and only if $S$ is an upper set of $\omega$.

(iii) For an acyclic orientation $\sigma$ of $K_V$ and $X \in \{\emptyset, V\}$ we have $C_{\sigma}^{X} \subseteq C_{\omega}$ if and only if $\sigma$ is a linear extension of $\omega$.
We are now ready to describe the deformation cone of the graphical zonotope $Z_G$. For any $h \in \mathbb{R}^{2^V}$, let $D_h$ be the polytope given by

$$D_h := \{ \mathbf{x} \in \mathbb{R}^V \mid \sum_{v \in S} \mathbf{x}_v - \sum_{v \notin S} \mathbf{x}_v \le h_S \text{ for all } S \subseteq V \}.$$

**Proposition 2.4** For any graph $G := (V, E)$, the deformation cone $\mathbb{DC}(Z_G)$ of the graphical zonotope $Z_G$ is the set of polytopes $D_h$ for all $h$ in the cone of $\mathbb{R}^{2^V}$ defined by the following (possibly redundant) description:

$$\bullet h_{\emptyset} = -h_V,$$

$$\bullet h_{S \cup \{u\}} + h_{S \cup \{v\}} = h_S + h_{S \cup \{u, v\}} \text{ for each } \{u, v\} \in \binom{V}{2} \setminus E \text{ and } S \subseteq V \setminus \{u, v\}, \text{ and}$$

$$\bullet h_{S \cup \{u\}} + h_{S \cup \{v\}} \geq h_S + h_{S \cup \{u, v\}} \text{ for each } \{u, v\} \in E \text{ and } S \subseteq V \setminus \{u, v\}.$$

*Proof* Observe first that, as stated in Lemma 2.3, $\tilde{B}_V$ provides a simplicial refinement of $\mathcal{F}_G$. Following Proposition 1.3, we need to consider all pairs of adjacent maximal cones of $\tilde{B}_V$, and to study which ones lie in the same cone of $\mathcal{F}_G$.

Adjacent maximal cones of $\tilde{B}_V$ are described in Lemma 2.2, and the containment relations of the cones of $\tilde{B}_V$ in the cones of $\mathcal{F}_G$ are described in Lemma 2.3.

For any $\sigma$, the cones $C_{\sigma}^{\emptyset}$ and $C_{\sigma}^{V}$ belong to the same cell of $\mathcal{F}_G$. Hence, by Proposition 1.3, the following equation holds in the deformation cone:

$$h_{\emptyset} = -h_V.$$

The remaining pairs of adjacent maximal cones of $\tilde{B}_V$ correspond to pairs of acyclic orientations of $K_V$ differing in a single edge; or equivalently, to pairs of permutations of $V$ of the form $\sigma = PuvS$ and $\sigma' = PvuS$. The unique linear relation supported on the rays of $C_{\sigma}^{X} \cup C_{\sigma'}^{X}$ for $X \in \{\emptyset, V\}$ is then

$$\iota_{S \cup \{u\}} + \iota_{S \cup \{v\}} = \iota_S + \iota_{S \cup \{u, v\}}.$$

We consider first the case when $\{u, v\} \notin E$. Observe that both $\sigma$ and $\sigma'$ induce the same acyclic orientation of $G$, which we call $\omega$. We have then $C_{\sigma}^{X} \cup C_{\sigma'}^{X} \subseteq C_{\omega}$ by Lemma 2.3. Therefore, by Proposition 1.3 and Lemma 2.2, we have

$$h_{S \cup \{u\}} + h_{S \cup \{v\}} = h_S + h_{S \cup \{u, v\}}$$

for any $h$ in $\mathbb{DC}(Z_G)$. Note that, for any $\{u, v\} \notin E$ and $S \subseteq V \setminus \{u, v\}$, we can construct such permutations $\sigma$ and $\sigma'$. This gives the claimed description of the linear span of $\mathbb{DC}(Z_G)$.

In contrast, if $\{u, v\} \in E$, then $\sigma$ and $\sigma'$ induce different orientations of $G$, and hence they belong to different adjacent cones of $\mathcal{F}_G$ by Lemma 2.3. Therefore, by Proposition 1.3 and Lemma 2.2, we have
$$h_{S \cup \{u\}} + h_{S \cup \{v\}} \geq h_S + h_{S \cup \{u, v\}}$$

for any $h$ in $\mathbb{D}(Z_G)$. As before, for any $\{u, v\} \in E$ and $S \subset V \setminus \{u, v\}$, we can construct such permutations $\sigma$ and $\sigma'$. This gives the claimed inequalities describing $\mathbb{D}(Z_G)$. $\square$

## 2.2 The Linear Span of Graphical Deformation Cones

The description of the deformation cone of Proposition 2.4 is highly redundant, both in the equations describing its linear span and in the inequalities describing its facets. We will give a non-redundant description in Theorem 2.6. The first step will be to give linearly independent equations describing the linear span. As a by-product, we will obtain the dimension and a linear basis of the deformation cone $\mathbb{D}(Z_G)$.

For a polytope $P \subset \mathbb{R}^d$, we define the space $\mathbb{V}\mathbb{D}(P) \subset \mathbb{V}^d$ of virtual deformations of $P$ as the vector subspace of virtual polytopes generated by the deformations of $P$. Equivalently, $\mathbb{V}\mathbb{D}(P)$ is the linear span of the deformation cone $\mathbb{D}\mathbb{C}(P)$. Every virtual polytope in $\mathbb{V}\mathbb{D}(P)$ is of the form $P_h - P_{h'}$ for deformations $P_h, P_{h'} \in \mathbb{D}\mathbb{C}(P)$. Note that the vector $h - h'$ uniquely describes the equivalence class of this virtual polytope, and we will use the notation $P_{h-h'}$ to denote it.

Denote by $\Delta_U := \text{conv}\{e_u | u \in U\}$ the face of the standard simplex $\Delta_V$ corresponding to a subset $U \subseteq V$. These polytopes are particularly important deformed permutahedra as they form a linear basis of the deformation space of the permutahedron [14] (see also [2, Prop. 2.4]). Namely, any (virtual) deformed permutahedron can be uniquely written as a signed Minkowski sum of dilates of $\Delta_I$. Our first result states that this linear basis is adapted to graphical zonotopes.

**Theorem 2.5** For any graph $G := (V, E)$:

(i) The dimension of $\mathbb{V}\mathbb{D}(Z_G)$ is the number of non-empty induced cliques in $G$ (the vertices of $G$ count for the dimension as they correspond to the lineality space).

(ii) The faces $\Delta_K$ of the standard simplex $\Delta_V$ corresponding to the non-empty induced cliques $K$ of $G$ form a linear basis of $\mathbb{V}\mathbb{D}(Z_G)$.

(iii) $\mathbb{V}\mathbb{D}(Z_G)$ is the set of virtual polytopes $D_h$ for all $h \in \mathbb{R}^{2V}$ fulfilling the following linearly independent equations:

* $h \emptyset = -h_V$ and

* $h_{S \setminus \{u\}} + h_{S \setminus \{v\}} = h_S + h_{S \setminus \{u, v\}}$ for each $S \subseteq V$ with $|S| \geq 2$ not inducing a clique of $G$ and any $\{u, v\} \in \binom{S}{2} \setminus E$ (here, we only choose one missing edge for each subset $S$, for example, the lexicographically smallest).

*Proof* Observe first that the faces $\Delta_I$ of the standard simplex $\Delta_V$ corresponding to the induced cliques $I$ of $G$ are all in the deformation cone $\mathbb{D}\mathbb{C}(Z_G)$. Indeed, faces of the standard simplex $\Delta_I$ belong to the deformation cone of the complete graph $K_I$ by [31, Prop. 6.3]. The graphical zonotope $Z_{G'}$ is a Minkowski summand of $Z_G$ for any subgraph $G'$ of $G$, and hence summands of $Z_{G'}$ are also summands of $Z_G$.

Moreover, all faces $\Delta_I$ for $\emptyset \neq I \subseteq V$ are Minkowski independent by [2, Prop. 2.4]. This shows that the dimension of $\mathbb{V}\mathbb{D}(Z_G)$ is at least the number of non-empty induced cliques of $G$.
Let $(f_X)_{X \subseteq V}$ be the canonical basis of $(\mathbb{R}^{2^V})^*$. The vectors

$$ \mathbf{o}^S := f_S - f_{S \setminus \{u\}} - f_{S \setminus \{v\}} + f_{S \setminus \{u,v\}}, $$

for all subsets $\emptyset \neq S \subseteq V$ not inducing a clique of $G$ and one selected missing edge $\{u, v\}$ for each $S$, are clearly linearly independent. Indeed, if the $f_X$ are ordered according to any linear extension of the inclusion order on the indices $X$, and the $\mathbf{o}^S$ are ordered analogously in terms of the indices $S$, then the equations are already in echelon form, as $f_S$ is the greatest non-zero coordinate of $\mathbf{o}^S$. Finally, the vector $v \in 2^V$ with $v_X = |X|$ for $X \in 2^V$ is orthogonal to any $\mathbf{o}^S$ with $|S| \ge 2$ but not to $\mathbf{o}^\emptyset := f_\emptyset + f_V$, showing that the latter is linearly independent to the former. This proves that the dimension of $\mathbb{V}\mathcal{D}(Z_G)$ is at most the number of non-empty induced cliques of $G$.

We conclude that $\{\Delta_K | \emptyset \neq K \subseteq V \text{ inducing a clique of } G\}$ is a linear basis of the deformation cone, and that $\{\mathbf{o}^S | S = \emptyset \text{ or } S \subseteq V \text{ not inducing a clique of } G\}$ is a basis of its orthogonal complement (we slightly abuse notation here as $\mathbf{o}^S$ was defined in $(\mathbb{R}^{2^V})^*$ instead of in $(\mathbb{V}^d)^*$, but note that each $f_X$ can be considered as a linear functional in $(\mathbb{V}^d)^*$ if seen as a support function). $\square$

Note that the dimension of the deformation space of graphical zonotopes has been independently computed by Raman Sanyal and Josephine Yu (personal communication), who computed the space of Minkowski 1-weights of graphical zonotopes in the sense of McMullen [25]. Their proof also uses the basis from Theorem 2.5 (ii), but with an alternative argument to show that they are a generating family.

## 2.3 The Facets of Graphical Deformation Cones

To conclude, it remains to compute the facets of the deformation cones, i.e. a non-redundant inequality description.

We define the neighborhood of a vertex $v$ of a graph $G := (V, E)$ as $N(v) := \{u \in V | \{u, v\} \in E\}$.

**Theorem 2.6** For any graph $G := (V, E)$, the deformation cone $\mathbb{D}\mathcal{C}(Z_G)$ of the graphical zonotope $Z_G$ is the set of polytopes $D_h$ for all $h$ in the cone of $\mathbb{R}^{2^V}$ defined by the following irredundant facet description:

* $h_\emptyset = -h_V$,

* $h_{S \setminus \{u\}} + h_{S \setminus \{v\}} = h_S + h_{S \setminus \{u, v\}}$ for each $\emptyset \neq S \subseteq V$ and any $\{u, v\} \in \binom{S}{2} \setminus E$,

* $h_{S \cup \{u\}} + h_{S \cup \{v\}} \ge h_S + h_{S \cup \{u, v\}}$ for each $\{u, v\} \in E$ and $S \subseteq N(v) \cap N(v)$.

Note that this description is given as a face of the submodular cone, embedded into $\mathbb{R}^{2^V}$. One gets easily an intrinsic presentation by restricting to the space spanned by the biconnected subsets of $V$. However, that presentation loses its symmetry, and the explicit equations depend on the biconnected sets of $G$.
**Proof of Theorem 2.6** We know by Proposition 2.4 that $\mathbb{D}\mathbb{C}(Z_G)$ is the intersection of the cone

$$h_{S \cup \{u\}} + h_{S \cup \{v\}} \geq h_S + h_{S \cup \{u, v\}} \quad (1)$$

for $\{u, v\} \in E$ and $S \subseteq V \setminus \{u, v\}$ with the linear space given by the equations $h_{\emptyset} = -h_V$ and

$$h_{S \cup \{u\}} + h_{S \cup \{v\}} = h_S + h_{S \cup \{u, v\}} \quad (2)$$

for $\{u, v\} \in \binom{V}{2} \setminus E$ and $S \subseteq V \setminus \{u, v\}$.

We have already determined the equations describing the linear span in Theorem 2.5, so it only remains to provide non-redundant inequalities describing the deformation cone.

We will prove first that the inequalities from (1) indexed by $\{u, v\} \in E$ and $S \subseteq N(v) \cap N(v)$ suffice to describe $\mathbb{D}\mathbb{C}(Z_G)$.

To this end, consider an inequality from (1) for which $S \not\subseteq N(v) \cap N(v)$. Without loss of generality, assume that there is some $x \in S$ such that $\{x, v\} \notin E$. We will show that this inequality is induced (in the sense that the halfspaces they define coincide on the linear span of $\mathbb{D}\mathbb{C}(Z_G)$) by the inequality

$$h_{S' \cup \{u\}} + h_{S' \cup \{v\}} \geq h_{S'} + h_{S' \cup \{u, v\}} \quad (3)$$

where $S' = S \setminus \{x\}$. Our claim will then follow from this by induction on the elements of $S \setminus (N(v) \cap N(v))$.

Indeed, if $\{x, v\} \notin E$, we know by (2) that the following two equations hold in the linear span of $\mathbb{D}\mathbb{C}(Z_G)$ by considering the non-edge $\{x, v\}$ with the subsets $S' \cup \{u\}$ and $S'$, respectively:

$$h_{S \cup \{u\}} + h_{S' \cup \{u, v\}} = h_{S' \cup \{u\}} + h_{S \cup \{u, v\}}, \quad (4)$$

$$h_S + h_{S' \cup \{v\}} = h_{S'} + h_{S \cup \{v\}}, \quad (5)$$

where we used that $(S' \cup \{u\}) \cup \{x\} = S \cup \{u\}$ and $(S' \cup \{u\}) \cup \{x, v\} = S \cup \{u, v\}$ in the first equation, and that $S' \cup \{x\} = S$ and $S' \cup \{x, v\} = S \cup \{v\}$ in the second equation. To conclude, note that (1) is precisely the linear combination $(3 + (4)-(5))$.

We know therefore that the descriptions in Proposition 2.4 and Theorem 2.6 give rise to the same cone. It remains to show that the latter is irredundant. That is, that each of the inequalities gives rise to a unique facet of $\mathbb{D}\mathbb{C}(Z_G)$.

Let $(f_X)_{X \subseteq V}$ be the canonical basis of $(\mathbb{R}^{2^V})^*$. For $u, v \in V$ and $S \subseteq V \setminus \{u, v\}$, let

$$\mathbf{n}(u, v, S) := f_{S \cup \{u\}} + f_{S \cup \{v\}} - f_S - f_{S \cup \{u, v\}}.$$

Note that, if $\{u, v\} \notin E$, then $\mathbf{n}(u, v, S)$ is orthogonal to $\mathbb{D}\mathbb{C}(Z_G)$, whereas if $\{u, v\} \in E$, then $\mathbf{n}(u, v, S)$ is an inner normal vector to $\mathbb{D}\mathbb{C}(Z_G)$.
Fix {$u, v \in E$ and $S \subseteq N(v) \cap N(v)$}. To prove that the halfspace with normal $n(u, v, S)$ is not redundant, we will exhibit a vector $w \in \mathbb{R}^{2^V}$ in the linear span of $\mathbb{DC}(Z_G)$ that belongs to the interior of all the halfspaces describing $\mathbb{DC}(Z_G)$ except for this one. That is, we will construct a vector $w \in \mathbb{R}^{2^V}$ respecting the system:

$$ egin{cases} 
\langle w | n(u, v, S) \rangle \le 0, \\
\langle w | n(u, v, X) \rangle > 0 & \text{for } S \ne X \subseteq N(u) \cap N(v), \\
\langle w | n(a, b, X) \rangle > 0 & \text{for } \{a, b\} \in E \setminus \{u, v\} \text{ and } X \subseteq N(a) \cap N(b), \text{ and} \\
\langle w | n(a, b, X) \rangle = 0 & \text{for } \{a, b\} \in \binom{V}{2} \setminus E \text{ and } X \subseteq V \setminus \{a, b\}. 
\end{cases} 
\tag{6} $$

Denote by $T := N(u) \cap N(v) \setminus S$. We will construct $w$ as the sum $w := t^S - t^T + c$ for some vectors $t^S, t^T$, and $c \in \mathbb{R}^{2^V}$ defined below, whose scalar products with $n(a, b, X)$ for $\{a, b\} \in \binom{V}{2}$ and $X \subseteq V \setminus \{a, b\}$ fulfill:

<table><thead><tr><th></th><th>⟨t<sup>S</sup> | n(a, b, X)⟩</th><th>⟨-t<sup>T</sup> | n(a, b, X)⟩</th><th>⟨c | n(a, b, X)⟩</th></tr></thead><tbody><tr><td>if {a, b} = {u, v} and X = S</td><td>-|S|</td><td>0</td><td>|S|</td></tr><tr><td>if {a, b} = {u, v} and S ≠ X ⊆ N(u) ∩ N(v)</td><td>-|S ∩ X|</td><td>|T ∩ X|</td><td>|S|</td></tr><tr><td>if {a, b} ∈ E ∖ {u, v} and X ⊆ N(a) ∩ N(b)</td><td>≥ -1</td><td>≥ 0</td><td>2</td></tr><tr><td>if {a, b} ∉ E</td><td>0</td><td>0</td><td>0</td></tr></tbody></table>

It immediately follows from this table that the vector $w$ will fulfill the desired properties from (6). For the second one, note that if $S \ne X \subseteq S \sqcup T$, then either $|S \cap X| < |S|$ or $|T \cap X| > 0$.

To define these vectors, first, for $\{x, y, z\} \in \binom{V}{3}$, let $t^{xyz} \in \mathbb{R}^{2^V}$ be the vector such that $t_X^{xyz} = 1$ if $\{x, y, z\} \subseteq X$ and $t_X^{xyz} = 0$ otherwise. Note that, for any $a, b \in \binom{V}{2}$ and $X \subseteq V \setminus \{a, b\}$, we have

$$ \langle t^{xyz} | n(a, b, X) \rangle = \begin{cases} -1 & \text{if } \{x, y, z\} = \{a, b, t\} \text{ for some } t \in X, \text{ and} \\ 0 & \text{otherwise.} \end{cases} \tag{7} $$

We define

$$ t^S := \sum_{s \in S} t^{uvs} \quad \text{and} \quad t^T := \sum_{t \in T} t^{uvt}. $$

It is straightforward to derive the identities in the table from (7). For the inequalities, notice that if $\langle t^{uvx} | n(a, b, X) \rangle = -1$ but $\{a, b\} \ne \{u, v\}$, then either $\{a, b\} = \{u, x\}$ or $\{a, b\} = \{v, x\}$, and in both cases $\langle t^{uvy} | n(a, b, X) \rangle = 0$ for any $y \ne x$.

Now, for $\{x, y\} \in \binom{V}{2}$, let $c^{xy} \in \mathbb{R}^{2^V}$ be the vector such that $c_X^{xy} = 1$ if $|\{x, y\} \cap X| = 1$ (that is, if $\{x, y\}$ belongs to the cut defined by $X$), and $c_X^{xy} = 0$ otherwise. Note that, for any $a, b \in \binom{V}{2}$ and $X \subseteq V \setminus \{a, b\}$, we have
$$ \langle \mathbf{c}^{xy} | \mathbf{n}(a, b, X) \rangle = \begin{cases} 2 & \text{if } \{a, b\} = \{x, y\}, \text{ and} \\ 0 & \text{otherwise.} \end{cases} \qquad (8) $$

We set

$$ \mathbf{c} := \frac{|S|}{2} \mathbf{c}^{uv} + \sum_{\{a,b\} \in E \setminus \{u,v\}} \mathbf{c}^{ab}. $$

The identities in the table are straightforward to derive from (8). □

**Corollary 2.7** For any graph $G := (V, E)$, the dimension of $\mathcal{D}\mathcal{C}(Z_G)$ is the number of induced cliques in $G$, the dimension of the lineality space of $\mathcal{D}\mathcal{C}(Z_G)$ is $|V|$, and the number of facets of $\mathcal{D}\mathcal{C}(Z_G)$ is the number of triplets $(u, v, S)$ with $\{u, v\} \in E$ and $S \subseteq N(u) \cap N(v)$.

**Example 2.8** For the complete graph $K_V$, the graphical zonotope $Z_{K_V}$ is a permutohedron and the deformation cone $\mathcal{D}\mathcal{C}(Z_{K_V})$ is the submodular cone given by the irredundant inequalities $\mathbf{h}_{S \cup \{u\}} + \mathbf{h}_{S \cup \{v\}} \ge \mathbf{h}_S + \mathbf{h}_{S \cup \{u, v\}}$ for each $\{u, v\} \subseteq V$ and $S \subseteq V \setminus \{u, v\}$. (The usual presentation imposes $\mathbf{h}_{\emptyset} = 0$, but both presentations are clearly equivalent up to translation). It has dimension $2^{|V|} - 1$ and $\binom{|V|}{2} 2^{|V|} - 2$ facets. The lineality is $|V|$-dimensional, given by the space of translations in $\mathbb{R}^{|V|}$.

For instance, for the triangle $K_3$, the graphical zonotope $Z_{K_3}$ is the regular hexagon depicted in the bottom left of Fig. 3, which arises as the Minkowski sum of 3 coplanar vectors in $\mathbb{R}^3$. Its deformation cone $\mathcal{D}\mathcal{C}(Z_{K_3})$ lives in the 8-dimensional space $\mathbb{R}^{2^{[3]}}$, has dimension 7, a lineality space of dimension 3, and 6 facets. It admits as irredundant description the equation $\mathbf{h}_{\emptyset} = -\mathbf{h}_{123}$ and the following 6 inequalities:

$$ \begin{aligned} \mathbf{h}_1 + \mathbf{h}_2 \ge \mathbf{h}_{\emptyset} + \mathbf{h}_{12} & \qquad \mathbf{h}_1 + \mathbf{h}_3 \ge \mathbf{h}_{\emptyset} + \mathbf{h}_{13} & \qquad \mathbf{h}_2 + \mathbf{h}_3 \ge \mathbf{h}_{\emptyset} + \mathbf{h}_{23} \\ \mathbf{h}_{12} + \mathbf{h}_{13} \ge \mathbf{h}_1 + \mathbf{h}_{123} & \qquad \mathbf{h}_{12} + \mathbf{h}_{23} \ge \mathbf{h}_2 + \mathbf{h}_{123} & \qquad \mathbf{h}_{13} + \mathbf{h}_{23} \ge \mathbf{h}_3 + \mathbf{h}_{123}. \end{aligned} $$

After quotienting the lineality and intersecting with an affine hyperplane, we get the bipyramid illustrated on Fig. 3. Note that the four rays of $\mathcal{D}\mathcal{C}(Z_{K_3})$ (i.e. vertices of the bipyramid) of the form $\Delta_K$ for an induced clique $K$ of $K_3$ provide a linear basis of $\mathcal{D}\mathcal{C}(Z_{K_3})$ (i.e. an affine basis of the bipyramid). Nevertheless, the last ray can not be written as a positive Minkowski sum of $\Delta_K$.

**Example 2.9** For a triangle-free graph $G := (V, E)$, the deformation cone $\mathcal{D}\mathcal{C}(Z_G)$ has dimension $|V| + |E|$ and $|E|$ facets. As before, the lineality is $|V|$-dimensional, given by the space of translations in $\mathbb{R}^{|V|}$. Thus $\mathcal{D}\mathcal{C}(Z_G)$ is simplicial.

For instance, for the 4-cycle $C_4$, the graphical zonotope $Z_{C_4}$ is the 3-dimensional zonotope depicted in the bottom right of Fig. 4, which arises as the Minkowski sum of 4 vectors in a hyperplane of $\mathbb{R}^4$. Its deformation cone $\mathcal{D}\mathcal{C}(Z_{C_4})$ lives in the 16-dimensional space $\mathbb{R}^{2^{[4]}}$, has dimension 8, a lineality space of dimension 4, and 4 facets. It admits as irredundant description the following 8 equations and 4 inequalities:
<figure><img src="image_7.png" /><figcaption>Fig. 3 A 3-dimensional affine section of the deformation cone DC(Zₖ) for the triangle K₃. The deformations of Zₖ corresponding to some of the points of DC(Zₖ) are depicted</figcaption></figure>

$$ 
\begin{aligned}
\mathbf{h}_{\emptyset} &= -\mathbf{h}_{1234} & \mathbf{h}_{12} + \mathbf{h}_{14} &= \mathbf{h}_{124} + \mathbf{h}_{1} & \mathbf{h}_{1} + \mathbf{h}_{2} &\geq \mathbf{h}_{12} + \mathbf{h}_{\emptyset} \\
\mathbf{h}_{1} + \mathbf{h}_{3} &= \mathbf{h}_{13} + \mathbf{h}_{\emptyset} & \mathbf{h}_{12} + \mathbf{h}_{23} &= \mathbf{h}_{123} + \mathbf{h}_{2} & \mathbf{h}_{2} + \mathbf{h}_{3} &\geq \mathbf{h}_{23} + \mathbf{h}_{\emptyset} \\
\mathbf{h}_{2} + \mathbf{h}_{4} &= \mathbf{h}_{24} + \mathbf{h}_{\emptyset} & \mathbf{h}_{23} + \mathbf{h}_{34} &= \mathbf{h}_{234} + \mathbf{h}_{3} & \mathbf{h}_{3} + \mathbf{h}_{4} &\geq \mathbf{h}_{34} + \mathbf{h}_{\emptyset} \\
\mathbf{h}_{123} + \mathbf{h}_{134} &= \mathbf{h}_{1234} + \mathbf{h}_{13} & \mathbf{h}_{14} + \mathbf{h}_{34} &= \mathbf{h}_{134} + \mathbf{h}_{4} & \mathbf{h}_{1} + \mathbf{h}_{4} &\geq \mathbf{h}_{14} + \mathbf{h}_{\emptyset}.
\end{aligned}
$$

After quotienting the lineality and intersecting with an affine hyperplane, we get the 3-simplex illustrated in Fig. 4.

## 2.4 Simplicial Graphical Deformation Cones

As an immediate corollary, we obtain a characterization of those graphical zonotopes whose deformation cone is simplicial.

**Corollary 2.10** The deformation cone DC(Z_G) is simplicial (modulo its lineality) if and only if G is triangle-free.

<figure><img src="image_8.png" /></figure>
<figure><img src="image_9.png" /><figcaption>Fig. 4 A 3-dimensional affine section of the deformation cone $\mathcal{D}\mathcal{C}(Z_{C_4})$ for the 4-cycle $C_4$. The deformations of $Z_{C_4}$ corresponding to some of the points of $\mathcal{D}\mathcal{C}(Z_{C_4})$ are depicted</figcaption></figure>

**Proof** If $G$ is triangle-free, the deformation cone $\mathcal{D}\mathcal{C}(Z_G)$ has dimension $|V| + |E|$, lineality space of dimension $|V|$, and $|E|$ facets, and hence it is simplicial. If $G$ is not triangle-free, then we claim that the number of induced cliques $K$ of $G$ with $|K| \ge 2$ is strictly less than the number of triples $(u, v, S)$ with $\{u, v\} \in E$ and $S \subseteq N(u) \cap N(v)$. Indeed, each induced clique $K$ of $G$ with $|K| \ge 2$ already produces $\binom{|K|}{2}$ triples of the form $(u, v, K \setminus \{u, v\})$ which satisfy $\{u, v\} \in E$ and $K \setminus \{u, v\} \subseteq N(u) \cap N(v)$ and are all distinct. Since $\binom{|K|}{2} > |K|$ as soon as $|K| \ge 3$, by Corollary 2.7, this shows that the deformation cone $\mathcal{D}\mathcal{C}(Z_G)$ is not simplicial. $\square$

**Corollary 2.11** If $G$ is triangle-free, then every deformation of $Z_G$ is a zonotope, which is the graphical zonotope of a subgraph of $G$ up to rescaling of the generators.

**Proof** For any induced clique $K$ of $G$ of size at least 2, $\Delta_K$ is a Minkowski indecomposable ($|K| - 1$)-dimensional polytope in the deformation cone $\mathcal{D}\mathcal{C}(Z_G)$ (see for example [19, 15.1.3] for a certificate of indecomposability). It spans therefore a ray of $\mathcal{D}\mathcal{C}(Z_G)$. When $G$ is triangle-free, the deformation cone modulo its lineality is of dimension $|E|$, and the polytopes $\Delta_e$ for $e \in E$ account for the $|E|$ rays of the simplicial deformation cone $\mathcal{D}\mathcal{C}(Z_G)$.

Therefore, each polytope $P \in \mathcal{D}\mathcal{C}(Z_G)$ can be uniquely expressed as a Minkowski sum

$$P = \sum_{e \in E} \lambda_e \Delta_e$$

with nonnegative coefficients $\lambda_e$. Since each $\Delta_e$ is a segment, $P$ is a zonotope, normally equivalent to the graphical zonotope of the subgraph $G' = (V, E')$ with $E' = \{e \in E | \lambda_e \neq 0\}$. $\square$
**Acknowledgements** We are grateful to Raman Sanyal for letting us know about his proof of Theorem 2.5 with Josephine Yu, as well as for many helpful discussions on the topic.

**Funding** Open Access funding provided thanks to the CRUE-CSIC agreement with Springer Nature.

**Data availability** Data sharing not applicable to this article as no datasets were generated or analysed during the current study.

**Open Access** This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.

## References

1. Aguiar, M., Ardila, F.: Hopf monoids and generalized permutahedra. Mem. Amer. Math. Soc. **289**, 1437 (2023)

2. Ardila, F., Benedetti, C., Doker, J.: Matroid polytopes and their volumes. Discrete Comput. Geom. **43**(4), 841–854 (2010)

3. Ardila, F., Castillo, F., Eur, C., Postnikov, A.: Coxeter submodular functions and deformations of Coxeter permutahedra. Adv. Math. **365**, 107039, 36 (2020)

4. Arkani-Hamed, N., Bai, Y., He, S., Yan, G.: Scattering forms and the positive geometry of kinematics, color and the worldsheet. J. High Energy Phys. (5):096, front matter+75 (2018)

5. Arkani-Hamed, N., Bai, Y., Lam, T.: Positive geometries and canonical forms. J. High Energy Phys. (11):039, front matter+121 (2017)

6. Arkani-Hamed, N.: Trnka, Jaroslav: The amplituhedron. J. High Energy Phys. **10**, 30 (2014)

7. Albertin, D., Pilaud, V., Ritter, J.: Removahedral congruences versus permutree congruences. Electron. J. Combin. **28**(4), Paper No. 4.8, 38 (2021)

8. Björner, Anders, L.V., Michel, S., Bernd, W., Neil, Z., Günter M.: Oriented matroids, Volume 46 of Encyclopedia of Mathematics and its Applications, 2nd Edn. Cambridge University Press, Cambridge (1999)

9. Bazier-Matte, V., Douville, G., Mousavand, K.: Hugh Thomas, and Emine Yıldırım. ABHY Associahedra and Newton polytopes of $F$-polynomials for finite type cluster algebras. Preprint (2018) arXiv:1808.09986

10. Castillo, F., Doolittle, J., Goeckner, B., Ross, M.S., Ying, L.: Minkowski summands of cubes. Bull. Lond. Math. Soc. **54**, 996–1009 (2022)

11. Chapoton, F., Fomin, S., Zelevinsky, A.: Polytopal realizations of generalized associahedra. Canad. Math. Bull. **45**(4), 537–566 (2002)

12. Castillo, F., Liu, F.: Deformation cones of nested braid fans. Int. Math. Res. Not, IMRN (2020)

13. Cox, D.A., Little, J.B., Schenck, H.K.: Toric Varieties. Graduate Studies in Mathematics, vol. 124. American Mathematical Society, Providence, RI (2011)

14. Danilov, V.I., Koshevoy, G.A.: Cores of cooperative games, superdifferentials of functions, and the Minkowski difference of sets. J. Math. Anal. Appl. **247**(1), 1–14 (2000)

15. De Loera, J.A., Rambau, J., Santos, F.: Triangulations: Structures for Algorithms and Applications, Volume 25 of Algorithms and Computation in Mathematics. Springer, New York (2010)

16. Edmonds, J.: Submodular functions, matroids, and certain polyhedra. In: Combinatorial Structures and their Applications (Proc. Calgary Internat. Conf., Calgary, Alta., 1969), pages 69–87. Gordon and Breach, New York (1970)

17. Fujishige, S.: Submodular Functions and Optimization. volume 58 of Annals of Discrete Mathematics, 2nd edn. Elsevier B. V., Amsterdam (2005)
18. Gelfand, I., Kapranov, M., Zelevinsky, A.: Discriminants, resultants and multidimensional determinants. Modern Birkhäuser Classics. Birkhäuser Boston Inc., Boston, MA, Reprint of the 1994 edition (2008)

19. Grünbaum, B.: Convex polytopes, volume 221 of Graduate Texts in Mathematics. Springer-Verlag, New York, second edition.; Prepared and with a preface by Volker Kaibel. Victor Klee and Günter M. Ziegler (2003)

20. Joswig, M., Klimm, M., Spitz, S.: Generalized permutahedra and optimal auctions. SIAM J. Appl. Algebra Geom. 6(4), 711–739 (2022)

21. Kallay, M.: Indecomposable polytopes. Israel J. Math. 41(3), 235–243 (1982)

22. Kim, S.: Shellable complexes and topology of diagonal arrangements. Discrete Comput. Geom. 40(2), 190–213 (2008)

23. McMullen, P.: Representations of polytopes and polyhedral sets. Geom. Dedicata 2, 83–99 (1973)

24. McMullen, P.: Indecomposable convex polytopes. Israel J. Math. 58(3), 321–323 (1987)

25. McMullen, P.: Weights on polytopes. Discrete Comput. Geom. 15(4), 363–388 (1996)

26. Meyer, W.: Indecomposable polytopes. Trans. Am. Math. Soc. 190, 77–86 (1974)

27. Morton, J., Pachter, L., Shiu, A., Sturmfels, B., Wienand, O.: Convex rank tests and semigraphoids. SIAM J. Discrete Math. 23(3), 1117–1134 (2009)

28. Mohammadi, F., Uhler, C., Wang, C., Josephine, Yu.: Generalized permutohedra from probabilistic graphical models. SIAM J. Discrete Math. 32(1), 64–93 (2018)

29. Pilaud, V.: Acyclic reorientation lattices and their lattice quotients. Preprint (2021) arXiv:2111.12387

30. Pukhlikov, A.V., Khovanskiǐ, A.G.: Finitely additive measures of virtual polyhedra. Algebra i Analiz 4(2), 161–185 (1992)

31. Postnikov, A.: Permutohedra, associahedra, and beyond. Int. Math. Res. Not. IMRN 6, 1026–1106 (2009)

32. Padrol, A., Pilaud, V., Poullot, G.: Deformation cones of graph associahedra and nestohedra. Eur. J. Combin. 107, Paper No. 103594 (2023)

33. Padrol, A., Palu, Y., Pilaud, V., Plamondon, P.-G.: Associahedra for finite type cluster algebras and minimal relations between $g$-vectors. Proc. Lond. Math. Soc. 127(3), 513–588 (2023)

34. Postnikov, A., Reiner, V., Williams, L.K.: Faces of generalized permutohedra. Doc. Math. 13, 207–273 (2008)

35. Pilaud, V., Santos, F.: Quotientopes. Bull. Lond. Math. Soc. 51(3), 406–420 (2019)

36. Przesławski, K., Yost, D.: More indecomposable polyhedra. Extracta Math. 31(2), 169–188 (2016)

37. Schoute, P.H.: Analytical treatment of the polytopes regularly derived from the regular polytopes. Section I: The simplex., volume 11 (1911)

38. Geoffrey, C.: Shephard. Decomposable convex polyhedra. Mathematika 10, 89–95 (1963)

39. Stanley, R.P.: An introduction to hyperplane arrangements. In: Geometric combinatorics, volume 13 of IAS/Park City Math. Ser., pp. 389–496. Amer. Math. Soc., Providence, RI (2007)

40. Stanley, R.P.: Enumerative combinatorics. Volume 1, Volume 49 of Cambridge Studies in Advanced Mathematics, 2nd Edn. Cambridge University Press, Cambridge (2012)

41. Ziegler, G.M.: Lectures on Polytopes. Graduate texts in Mathematics, Vol. 152. Springer, New York (1998)

**Publisher's Note** Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.