%
%
%
\documentclass[finalversion]{FPSAC2025}
\articlenumber{155}
%

%
%
%
%
\usepackage{xargs, bbm}
%

\usepackage[T1]{fontenc}
%
%
%
%
%
%
%
%
%
%
%
\usepackage{pifont}
%
\usepackage[all]{xy}
\usepackage{tikz}
\usepackage{tikz-cd}
\usepackage{tkz-graph}
\usetikzlibrary{trees, decorations, decorations.pathmorphing, decorations.markings, decorations.shapes, shapes, arrows, matrix, calc, fit, intersections, patterns, angles}
\graphicspath{{figures/}{figures/diagonals/}{figures/walks/}{figures/tubes/}{figures/blocks/}}
\makeatletter\def\input@path{{figures/}}\makeatother
\usepackage{caption}
\captionsetup{width=\textwidth}
\usepackage[export]{adjustbox}
\usepackage[dvipsnames]{xcolor}

\usepackage{paralist}
\usepackage{shuffle}

%


%
\newtheorem{theorem}{Theorem}[section]
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{conjecture}[theorem]{Conjecture}
%

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{question}[theorem]{Question}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{assumption}[theorem]{Assumption}
\newtheorem{convention}[theorem]{Convention}
%



%
\newcommand{\R}{\mathbb{R}} %
\newcommand{\Q}{\mathbb{Q}} %
\newcommand{\N}{\mathbb{N}} %
\newcommand{\Z}{\mathbb{Z}} %
\newcommand{\C}{\mathbb{C}} %
%
\newcommand{\HH}{\mathbb{H}} %
\newcommand{\K}{k} %
\newcommand{\f}[1]{{\mathfrak{#1}}} %
\let\ccc\c
\renewcommand{\c}[1]{{\mathcal{#1}}} %
\renewcommand{\b}[1]{{\boldsymbol{#1}}} %
\newcommand{\scr}[1]{{\mathscr{#1}}} %
\newcommand{\go}[1]{{\textgoth{#1}}} %
\newcommand{\h}{\widehat} %

\renewcommand{\emptyset}{\varnothing} %
\renewcommand{\epsilon}{\varepsilon} %

%
\newcommand{\set}[2]{\left\{ #1 ~;~ #2 \right\}} %
\newcommand{\bigset}[2]{\big\{ #1 ~;~ #2 \big\}} %
\newcommand{\Bigset}[2]{\Big\{ #1 ~;~ #2 \Big\}} %
\newcommand{\setangle}[2]{\left\langle #1 \;\middle|\; #2 \right\rangle} %
\newcommand{\ssm}{\smallsetminus} %
\newcommand{\inner}[1]{\left\langle#1\right\rangle}
\newcommand{\dotprod}[2]{\inner{#1,~#2}} %
\newcommand{\bigdotprod}[2]{\big\langle \, #1 \; \big| \; #2 \, \big\rangle} %
\newcommand{\symdif}{\,\triangle\,} %
\newcommand{\one}{{1\!\!1}} %
\newcommandx{\ones}[1][1=n]{\one_{#1}} %
\newcommand{\eqdef}{:=}%
\newcommand{\defeq}{\mbox{~\ensuremath{=}\raisebox{0.2ex}{\scriptsize\ensuremath{\mathrm:}} }} %
\renewcommand{\implies}{\Rightarrow} %
\newcommand{\transpose}[1]{{#1}^T} %

%
\DeclareMathOperator{\conv}{conv} %
\DeclareMathOperator{\vect}{vect} %
\DeclareMathOperator{\cone}{cone} %
\DeclareMathOperator{\vol}{vol} %

%
\newcommand{\ie}{\textit{i.e.}~} %
\newcommand{\eg}{\textit{e.g.}~} %
\newcommand{\Eg}{\textit{E.g.}~} %
\newcommand{\cf}{\textit{cf.}~} %
\newcommand{\apriori}{\textit{a priori}} %
\newcommand{\viceversa}{\textit{vice versa}} %
\newcommand{\versus}{\textit{vs.}~} %
\newcommand{\aka}{\textit{a.k.a.}~} %
\newcommand{\perse}{\textit{per se}} %
\newcommand{\ordinal}{\textsuperscript{th}} %
\newcommand{\ordinalst}{\textsuperscript{st}} %
\newcommand{\ordinalnd}{\textsuperscript{nd}} %
\newcommand{\ordinalrd}{\textsuperscript{rd}} %
\definecolor{darkblue}{rgb}{0,0,0.7} %
\definecolor{green}{RGB}{57,181,74} %
\definecolor{violet}{RGB}{147,39,143} %
\newcommand{\red}{\color{red}} %
\newcommand{\blue}{\color{blue}} %
\newcommand{\orange}{\color{orange}} %
\newcommand{\green}{\color{green}} %
\newcommand{\darkblue}{\color{darkblue}} %
\newcommand{\defn}[1]{\textsl{\darkblue #1}} %
\newcommand{\mathdefn}[1]{{\darkblue #1}} %
\newcommand{\para}[1]{\medskip\noindent\uline{\textit{#1.}}} %
\renewcommand{\topfraction}{1} %
\renewcommand{\bottomfraction}{1} %
\newcommand{\ex}{_{\textrm{exm}}} %
\newcommand{\pa}{_{\textrm{pa}}} %
\newcommand*\circled[1]{\tikz[baseline=(char.base)]{\node[shape=circle, draw, inner sep=1.5pt, scale=.7] (char) {#1};}}
\newcommand{\compactVectorD}[2]{\begin{bmatrix} #1 \\ #2 \end{bmatrix}}
\newcommand{\compactVectorT}[3]{\begin{bmatrix} #1 \\[-.1cm] #2 \\[-.1cm] #3 \end{bmatrix}}
\newcommand{\yes}{\textcolor{green}{\ding{52}}}
\newcommand{\no}{\textcolor{red}{\ding{55}}}

%

%
\makeatletter
\def\part{\@startsection{part}{1}%
	\z@{.7\linespacing\@plus\linespacing}{.8\linespacing}%
	{\LARGE\sffamily\centering}}
%
\makeatother
\renewcommand{\thepart}{\Roman{part}}
%


%
\newcommand{\pol}[1][P]{\mathsf{#1}}%
\newcommand{\DefoCone}[1][\pol]{\mathbb{DC}(#1)}%
%
\newcommand{\EDefoCone}[1][\pol]{\mathbb{DC}(#1)}%
\newcommand{\permuto}[1][n]{\pol[\Pi]_{#1}}%
\newcommand{\verts}{V}
%
\newcommand{\facets}{F}
\newcommand{\edges}{E}
\newcommand{\G}{\mathcal{G}}

%
%

\newcommand{\ELD}[1][\pol]{ED(#1)}%
%
\newcommand{\EELD}[1][\pol]{{ED}^*(#1)}%
\newcommand{\zELD}[1][ij]{ED_{#1}}%

\newcommandx{\ZG}[1][1=G]{\pol[Z]_{#1}} %
%
\newcommandx{\ZGKnm}[2][1=n,2=m]{\pol[Z]_{#1, #2}}
%
%
%
%
\newcommandx{\Pnm}[2][1=n,2=m]{\pol[Z]^{\rightarrow}_{#1, #2}}%
\newcommandx{\Qnm}[2][1=n,2=m]{\pol[Z]^{\leftrightarrow}_{#1, #2}}%
%
%

\newcommand{\simplex}[1][n]{\mathsf{\Delta}_{#1}}%

%
\newcommandx{\restrG}[2][1=\mu,2=G]{{#2}\left|_{#1}\right.}
\newcommandx{\contrG}[2][1=\mu,2=G]{{#2}\left/_{#1}\right.}
\newcommandx{\Knm}[2][1=n,2=m]{K_{#1, #2}}

\newcommand{\AO}{\c A}%


%
%
%



%
\title[New criteria for polytope indecomposability]{\texorpdfstring{New criteria for polytope indecomposability \\ and new rays of the submodular cone}{New criteria for polytope indecomposability and new rays of the submodular cone}}
%
%
	
	
%
%
%
\author[A. Padrol and G. Poullot]{\texorpdfstring{Arnau Padrol\thanks{\href{mailto:arnau.padrol@ub.edu}{arnau.padrol@ub.edu}. A.P. 
		is supported by grants PAGCAP ANR-21-CE48-0020,  PID2022-137283NB-C21, PCI2024-155081-2, 2021 SGR 00697, and CEX2020-001084-M.
		}\addressmark{1} \and Germain Poullot\thanks{\href{mailto:germain.poullot@uni-osnabrueck.de}{germain.poullot@uni-osnabrueck.de}}\addressmark{2}}{Arnau Padrol and Germain Poullot}}

%
\address{\addressmark{1}Departament de Matem\`atiques i Inform\`atica, Universitat de Barcelona, Barcelona, Spain and Centre de Recerca Matem\`atica, Bellaterra, Spain.\\ \addressmark{2}Institut of Mathematics, University of Osnabr\"uck, Germany}

%
\received{\today}

%
%

%
%
%
\abstract{
	A polytope is indecomposable if it cannot be expressed (non-trivially) as a Minkowski sum of other polytopes. Certifying indecomposability is difficult, and several criteria have been developed since Gale introduced the concept in 1954. Our first contribution is a new indecomposability criterion that encompasses most of the previous techniques. The major new ingredient is the introduction of the (extended) graph of edge-length dependencies, which has diverse applications in the study of deformation cones of polytopes.
	Our main motivation is to provide new indecomposable deformed permutahedra that are not matroid polytopes. In 1970, Edmonds proposed the problem of characterizing the extreme rays of the submodular cone, that is, indecomposable deformed permutahedra. Matroid polytopes from connected matroids give one such family of polytopes. We present a new infinite disjoint family via truncations of certain graphical zonotopes.
	This way, we obtain $2\lfloor\frac{n-1}{2}\rfloor$ new indecomposable deformations of the $n$-permutahedron $\permuto\subseteq \R^n$. 
}

%
\resume{Un polytope est indécomposable s'il est impossible de l'écrire comme une somme de Minkowski (non-triviale).
Il est ardu de prouver l'indécomposabilité, et plusieurs critères ont été développés depuis que Gale a introduit le concept en 1954.
Nous prouvons un nouveau critère qui encapsule la plupart des précédents.
L'in\-gré\-dient majeur est la construction du graphe (étendu) des dépendances entre les longueurs d'arêtes, qui a des applications diverses dans l'étude des cônes des déformations.
Notre motivation première est de créer de nouveaux permutaèdres déformés indécomposables qui ne sont pas des polytopes de matroïdes.
En 1970, Edmonds appelle à caractériser les rayons extrémaux du cône sous-modulaire, c'est-à-dire les permutaèdres déformés indécomposables. Les polytopes de matroïdes sont de tels rayons.
Nous créons une nouvelle famille infinie, disjointe de ces derniers, en tronquant des zonotopes graphiques.
Ainsi, nous obtenons $2\lfloor\frac{n-1}{2}\rfloor$ nouvelles déformations indécomposables du $n$-permutaèdre $\permuto\subseteq \R^n$.}

%
\keywords{Indecomposable polytopes, Minkowski addition, Deformed/generalized permutahedra, Submodular cone, Graphical zonotopes}

%
%

%
%
\usepackage[backend=bibtex, giveninits]{biblatex}
\addbibresource{Biblio.bib}
\appto\bibfont{\setlength{\emergencystretch}{.5em}}

%

\begin{document}

\maketitle
%

\section{Introduction}

We say that a polytope $\pol[Q]$ is a \defn{weak Minkowski summand} or a \defn{deformation} of a polytope~$\pol$ if there exist a polytope $\pol[R]$ and $\lambda > 0$ such that $\lambda \pol=\pol[Q]+\pol[R]$. %
%
Closed under addition and dilation, the set of deformations of $\pol$ forms a convex cone, called the \defn{deformation cone} of~$\pol$.
%
%
%
If all the deformations of $\pol$ are translated dilates of $\pol$, we say that $\pol$ is \defn{indecomposable}.
Indecomposable polytopes are the building blocks of Minkowski addition: they are the rays of deformation cones, and every polytope is a finite sum of indecomposable ones. 
They have applications in convex geometry, game theory, toric varieties, and computational algebra, among others.
Since Gale introduced the first criteria for certifying indecomposability in 1954~\cite{Gale1954}, many new stronger criteria have been found \cite{Gale1954,Kallay1982,McMullen1987,PrzeslawskiYost2008,PrzeslawskiYost2016,Shephard1963}. Yet, they do not apply to the truncated graphical zonotopes that we will study.

In \Cref{thm:rigidFacetsIndecomposable}, we provide a new indecomposability criterion that encompasses the majority of the aforementioned methods.
Most of these rely on finding suitable ``\emph{strong chains}'' of ``\emph{indecomposable subgraphs}'' in the $1$-skeleton of $\pol$ that meet all facets. Our method is more flexible, allowing for deducing dependencies between edges of the $1$-skeleton through non-indecomposable subgraphs. It is articulated through the \defn{(extended) graph of edge-length dependencies} of a polytope~$\pol$, which is a clique if and only if~$\pol$ is indecomposable.
Beyond indecomposability, these graphs allow us to deduce other properties of deformation cones, as demonstrated in \Cref{sec:productszonotopes}.

Our driving motivation is to produce new rays of the submodular cone. The \defn{{$n$-permutahedron}}~$\permuto$ is the convex hull of the $n!$ permutations of the vector $(1,2,\dots,n)\in \R^n$. 
%
A \defn{deformed permutahedron} (\aka \defn{generalized permutahedron}) is a deformation of~$\permuto$. Originally introduced by Edmonds in 1970 under the name of \defn{polymatroids} in linear optimization~\cite{Edmonds}, they were popularized by Postnikov~\cite{Postnikov2009} in algebraic combinatorics. Nowadays, they are widely studied in fields like algebraic combinatorics, statistics, optimization, and game theory. 
%
The deformation cone of the $\permuto$ is parametrized by the cone of \defn{submodular functions}. Edmonds ends his seminal paper~\cite{Edmonds} by observing the difficulty of characterizing its extreme rays (\ie indecomposable deformed permutahedra). This has been studied from several disciplines, 
see \cite{RosenmullerWeidner,StudenyKroupa2016} and their references, but the question is still wide open. In particular, we are still short of explicit examples. An infinite family of rays is given by matroid polytopes of connected matroids~\cite{Nguyen} (see also~\cite[Section~7.2]{StudenyKroupa2016}).


Graphical zonotopes, which are Minkowski sums of edges of the standard simplex indexed by the arcs of an associated graph~$G$, are deformed permutahedra. %
We show that, when~$G$ is a complete bipartite graph~$\Knm$, we can (deeply) truncate one or two (particular) vertices of its graphical zonotope to obtain polytopes that are simultaneously: deformed permutahedra (\Cref{thm:PandQareGP}), indecomposable (\Cref{thm:PandQareIndecomposable}), and not matroid polytopes (\Cref{thm:PandQnotMatroidPolytopes}).
This way, we obtain $2\lfloor\frac{n-1}{2}\rfloor$ new indecomposable deformations of~$\permuto$ (\Cref{cor:NewMIGP}). Moreover, we use some of these examples to refute a conjecture of Smilansky from 1987 {\cite[Conjecture~6.12]{Smilansky1987}}.




\section{New indecomposability criteria}

\subsection{Preliminaries}
%


A \defn{polytope} $\pol\subset\R^d$ is the convex hull of finitely many points. Its \defn{faces} are the zero-sets of non-negative affine functions on~$\pol$.  For a linear functional $ \b u\in (\R^d)^*$, let $\pol^{\b u}$ be the face of~$\pol$ containing the points maximizing~${\b u}$; \ie $\pol^{\b u} = \{\b x\in \pol ~;~ \b u(\b x) = \max_{\b y\in \pol} \b u(\b y)\}$. 
Faces of dimension~$0$,~$1$, and codimension~$1$ are called \defn{vertices}, \defn{edges} and \defn{facets}, respectively. 
The sets of vertices, edges and facets of $\pol$ are denoted $\verts(\pol)$, $\edges(\pol)$, and $\facets(\pol)$. 
The \defn{$1$-skeleton} of~$\pol$ is the graph $\G(\pol)$ with node set $\verts(\pol)$, and where two vertices are joined by an arc if they form an edge in $\edges(\pol)$.
Since several notions of vertex and edge appear in our paper, we reserve the names \emph{vertex} and \emph{edge} for the faces of polytopes, and use \emph{node} and \emph{arc} for graphs. Similarly, we  use \emph{$1$-skeleton} instead of \emph{graph} when referring to~$\G(\pol)$.

The \defn{Minkowski sum} of $\pol$ and $\pol[Q]$ is $\pol + \pol[Q] \eqdef \bigl\{\b p + \b q ~;~ \b p \in \pol, ~ \b q\in \pol[Q]\bigr\}.$
A polytope $\pol[Q]$ is a \defn{deformation} or a \defn{weak Minkowski summand} of $\pol$ if there exist $\pol[R]$ and $\lambda > 0$ such that  $\pol = \lambda \pol[Q] + \pol[R]$.
%
A polytope $\pol$ is \defn{(Minkowski) indecomposable} if its only deformations are of the form $\lambda \pol+\b t$ with $\lambda \geq 0$ and $\b t\in\R^d$ (the polytope $0 \,\pol$ is the point $\b 0$).
If $\pol[Q]$ is a deformation of $\pol$, then $\dim(\pol[Q]^{\b u})\leq \dim(\pol^{\b u})$ for all ${\b u}\in (\R^d)^*$.
%
In particular, there is a (not necessarily injective) correspondence between the vertices of $\pol$ and the vertices of~$\pol[Q]$. Let $\b p, \b  p'$ be vertices of $\pol$ and $\b q, \b q'$ be the associated vertices of~$\pol[Q]$. Then the edges joining $\b p\b p'$ and $\b q\b q'$ are parallel, and there is some $\lambda\in \R_+$ such that 
\begin{equation}\label{eq:ELD}\lambda(\b p-\b p')=\b q-\b q'.\end{equation}
In \cite{Shephard1963}, Shephard proved that this property characterizes deformations of $\pol$.
We use it to parametrize the cone of deformations of $\pol$ (modulo translations), and refer to  \cite[Appendix]{PostnikovReinerWilliams} for more details and other parametrizations.
%

We associate to every deformation $\pol[Q]$ its \defn{edge-length vector} $\mathdefn{\b\ell(\pol[Q])}\in\R_+^{E(\pol)}$, where for an edge~$\pol[e]$ joining the vertices $\b p$  and $\b p'$, we have 
that $\b\ell(\pol[Q])_{\pol[e]}$ is the $\lambda \geq 0$ from \eqref{eq:ELD}.
The \defn{edge-length deformation cone} of $\pol$ is the set \defn{$\EDefoCone[\pol]$} consisting of the nonnegative vectors $\b\ell\in\R_+^{\edges(\pol)}$ such that for every $2$-dimensional face $\pol[F]$ of $\pol$ with cyclically ordered vertices $\b p_1\b p_2\dots\b p_k$ and edges $\pol[e]_1=\b p_1\b p_2$, $\dots$, $\pol[e]_{k-1}=\b p_{k-1}\b p_k$, $\pol[e]_k=\b p_k\b p_1$, the following \defn{polygonal face equation} is satisfied:
\[\b \ell_{\pol[e]_1}(\b p_1-\b p_2) +\b \ell_{\pol[e]_2}(\b p_2-\b p_3) +\cdots+\b \ell_{\pol[e]_k}(\b p_k-\b p_1)=0.\]

The edge-length vector of every deformation of $\pol$ lies in~$\EDefoCone[\pol]$. Conversely, we can recover a deformation $\pol[P]_{\b\ell}$ of $\pol$ (unique up to translation) for every vector $\b\ell\in\EDefoCone[\pol]$. 
We fix a vertex $\b p$ of~$\pol$. For any other vertex $\b p'\in \verts(\pol)$, there is a path $\c P_{\b p'}=(\b p=\b p_0,\b p_1,\dots,\b p_r=\b p')$ joining $\b p$ and $\b p'$ in~$\G(\pol)$. Denoting by $\pol[e]_{ij}$ the edge $\b p_i\b p_j$, we construct
\({\darkblue \pol[P]_{\b \ell}} \eqdef \conv\bigl\{\sum_{\pol[e]_{ij}\in\c P_{\b p'}}\b \ell_{\pol[e]_{ij}} (\b p_j-\b p_i)~\mid  \text{ for } \b p' \in \verts(\pol)\bigr\}.	\)
%


\subsection{The graph of edge-length dependencies}

%

\begin{definition}
	The \defn{graph of edge-length dependencies} of a polytope $\pol$, denoted \defn{$\ELD$} is the graph whose node set is $E(\pol)$, the set of edges of $\pol$, and where two edges $\pol[e], \pol[f]\in E(\pol)$ are linked with an arc if for every $\b \ell\in \EDefoCone[\pol]$ we have $\b\ell_{\pol[e]}=\b\ell_{\pol[f]}$. In this case, we say that ${\pol[e]}$ and ${\pol[f]}$ are \defn{dependent}.
\end{definition}

\begin{example}\label{ex:ELDindecomposable}
$\pol$ is indecomposable if and only if $\ELD$ is a complete graph.
Indeed, $\pol$ is indecomposable when
all its deformations are (translations) of dilations of $\pol$, 
that is, if $\b\ell(\pol[Q])$ is of the form $(\lambda, \dots, \lambda)$ for any deformation $\pol[Q]$ of $\pol[P]$, which is equivalent to $\ELD$ being complete.
\end{example}

\begin{example}\label{ex:parallelogram}
If $\pol$ is a two-dimensional parallelogram with edges $\pol[e],\pol[f],\pol[e]',\pol[f]'$ in cyclic order. Then $\ELD$ consists of two disjoint arcs $\pol[e]\pol[e]'$ and $\pol[f]\pol[f]'$.
Indeed, the polygonal face equations of a parallelogram impose that all of its deformations are parallelograms and that parallel (opposite) edges have the same length in all deformations.
\end{example}

This example shows that there can be a subset of edges which induces a connected subgraph in $\ELD$, but a disconnected subskeleton in $\G(\pol)$ (note that in $\ELD$ the edges play the role of nodes whereas in $\G(\pol)$ the play the role of arcs).

%
%
%
%
%
%
Dependency is an equivalence relation on $\edges(\pol)$: we directly have that $\ELD$ is a \defn{cluster graph}.
We combine this with \Cref{ex:ELDindecomposable} to get the next corollary.

\begin{lemma}\label{lem:WclusterGraph}
All connected components of 
%
$\ELD$
are cliques.
\end{lemma}
%
%
%
%
%
%

%
%

\begin{corollary}\label{cor:WconnectedPMinkowskiIndecomposable}
	$\pol$ is indecomposable if and only if $\ELD$ is connected.
	%
\end{corollary}

%

While previous works do not use this language explicitly, many exploited indecomposable faces to prove the connectedness of $\ELD$.

\begin{corollary}\label{cor:indecfacesclique}
If $\pol[F]$ is an indecomposable face of $\pol$, then its edges form a clique in $\ELD$.
\end{corollary}

The asset of our perspective is that it also allows for other methods to find dependencies between the edges.
%
%
%
%
%
%
%
%
Most of the former methods for proving the indecomposability of a polytope rely on finding enough 
``indececomposable subgraphs'' of $\G(\pol)$ (such as triangles), and cleverly tying them together to show that $\ELD$ is connected.
\Cref{ex:parallelogram} allows us to also exploit parallelisms to deduce connections in $\ELD$.
%

\begin{lemma}\label{lem:parallelogram}
	Let $\pol$ be a polytope, and $\pol[F]$ a two dimensional face that is a parallelogram with edges $\pol[e],\pol[f],\pol[e]',\pol[f]'$ in cyclic order. Then both $\pol[e]\pol[e]'$ and $\pol[f]\pol[f]'$ are arcs in $\ELD$.
\end{lemma}
%



We say that a subset of edges $X\subseteq \edges(\pol)$ is \defn{dependent} if they induce a connected subgraph of $\ELD$ (and thus a clique, by \Cref{lem:WclusterGraph}), \ie if they are pairwise dependent.
For example, in the cube $[0, 1]^d$, any subset of parallel edges is dependent by \Cref{lem:parallelogram}.

With this, we can formulate our first indecomposability criterion (which will be later subsumed by the stronger, but harder to state \Cref{thm:rigidFacetsIndecomposable}).


\begin{theorem}\label{thm:WspanningPMinkowskiIndecomposable}
	Let $\pol$ be a polytope. If there exists a dependent subset of edges $X\subseteq \edges(\pol)$ such that any pair of vertices of $\pol$ is connected in $\G(\pol)$ through a path of edges in~$X$, then $\ELD$ is a complete graph and $\pol$ is indecomposable.
\end{theorem}
\begin{proof}
	Suppose that $\ELD$ satisfies the hypotheses, and let $\b \ell\in\EDefoCone[\pol]$ be an edge-length vector in the deformation cone, and $\pol_{\b \ell}$ the associated deformation. Let $\lambda\eqdef\b\ell_{\pol[e]}$ for any $\pol[e]\in X$ ($\lambda$ does not depend on the edge chosen because because $X$ is a dependent subset). 

	Now, fix a vertex $\b p_0\in \pol$. For any other vertex $\b p$ there is a path $\c P = (\b p_0, \b p_1,\dots , \b p_r=\b p)$ connecting $\b p_0$ and $\b p$, in which all the edges $\b p_i\b p_{i+1}$ belong to~$X$. Use $\b q_i$ to denote the corresponding vertices of $\pol_{\b \ell}$.
	We have 
	\[\b q - \b q_0= \sum\nolimits_{1\leq i\leq r} (\b q_i-\b q_{i-1})  = \sum\nolimits_{1\leq i\leq r} \lambda (\b p_i-\b p_{i-1}) = \lambda(\b p - \b p_0).\]
	Since this holds for any vertex $\b q\in\verts(\pol_{\b\ell})$, we have $\pol_{\b\ell} = \lambda \pol$, up to translation. Thus, $\pol$ is indecomposable, and $\ELD$ is complete by \Cref{lem:WclusterGraph}.
\end{proof}


%

%
%
%
%
%
%

\subsection{The extended graph of edge-length dependencies}

For some applications, it is useful to extend $\ELD$ with more pairs of vertices which, while not forming an edge, always satisfy an equation like \eqref{eq:ELD}. This allows us to present a stronger indecomposability theorem that subsumes the criterion stated before (and many previous criteria). 
%

\begin{definition}
	A \defn{rigid pair} of vertices of a polytope~$\pol$ is a pair of vertices $\b p_i \b p_j$ (not necessarily in forming an edge) such that for any deformation $\pol[Q]$ of $\pol$, there is some ${\lambda_{ij}\in\R_+}$ so that
	\(\lambda_{ij}(\b p_i-\b p_j)=\b q_i-\b q_j\)
	where $\b q_i$ and $\b q_j$ are the vertices of $\pol[Q]$ corresponding to $\b p_i$ and $\b p_j$.
	The \defn{extended graph of edge-length dependencies} of $\pol$, denoted \defn{$\EELD$}, is the graph whose nodes are the rigid pairs of $\pol$, and where two such couples $\b p_i\b p_j$ and $\b p_k\b p_l$ are joined by an arc in $\EELD$ if $\lambda_{ij}=\lambda_{kl}$. We say that these two rigid pairs are \defn{dependent}.
\end{definition}
Computing all rigid pairs of vertices (and thus the nodes of $\EELD$) is not easy, but this is usually not needed. The next result shows how to derive some of them.


\begin{lemma}\label{lem:connectedrigid}
	Let $\b p$ and $\b p'$ be vertices of $\pol$ that are connected in $\G(\pol)$ through a path of dependent edges. Then, for any deformation $\pol[Q]$ we have 
	$\lambda(\b p'-\b p)=\b q'-\b q$
    where $\lambda=\b \ell_{\pol [e]}$ for any edge $\pol[e]$ in the path joining $\b p$ and $\b p'$, and $\b q $ and $\b q'$ are the corresponding vertices in $\pol[Q]$.
\end{lemma}
%
%
%
%
%

Of course, $\ELD$ is a subgraph of $\EELD$, and $\EELD$ is mainly interesting to deduce properties of $\ELD$. Many properties carry over from $\ELD$ to $\EELD$. We omit their proof because it is analogous to those of \Cref{lem:WclusterGraph,cor:indecfacesclique,lem:parallelogram}

\begin{lemma}\label{lem:EELDCCcliques}
	The connected components of $\EELD$ are cliques.
\end{lemma}	

The following analogues of \Cref{cor:indecfacesclique,lem:parallelogram} admit more natural wordings in terms of \emph{indecomposable geometric graphs} as in \cite{Kallay1982,PrzeslawskiYost2008,PrzeslawskiYost2016}. However, for the sake of brevity and self-containment, we formulate everything in terms of polytopes.

\begin{corollary}\label{cor:indecomposablerigid}
	Let $\pol$ be a polytope, and $\b p_1,\dots,\b p_r\in\verts(\pol)$. If $\conv(\b p_1,\dots,\b p_r)$ is indecomposable and its $1$-skeleton only consists of rigid pairs, then the corresponding nodes of $\EELD$ induce a clique.
\end{corollary}

\begin{lemma}
	Let $\pol$ be a polytope, and $\b p_1,\b p_2,\b p_3,\b p_4$ some of its vertices whose convex hull is a parallelogram in that cyclic order. If $\b p_1\b p_2$, $\b p_2\b p_3$, $\b p_3\b p_4$ and $\b p_4\b p_1$ are rigid pairs, then 
	$\b p_1\b p_2$ and $\b p_3\b p_4$, as well as $\b p_2\b p_3$ and $\b p_4\b p_1$ are connected in $\EELD$.
\end{lemma}

We say that a subset $S\subseteq\verts(\pol)$ of vertices is \defn{dependent} if every pair of vertices of $S$ is a rigid pair, and they are all pairwise dependent. Note that despite our presentation, this dependence is not arising from an equivalence relation on the set of vertices (as it could be that both $\b p_i\b p_j$  and $\b p_i\b p_k$ form rigid pairs, but that these pairs are not dependent, like in a parallelogram), but from an equivalence relation on the set of pairs of vertices. 


We are ready to state our main theorem of this part, and some of its consequences. We omit its proof due to space constraints. It combines ideas from \Cref{thm:WspanningPMinkowskiIndecomposable} and \cite{McMullen1987}.




\begin{theorem}\label{thm:rigidFacetsIndecomposable}
	Let $\pol$ be a polytope. If there is a dependent subset of vertices $S\subseteq \verts(\pol)$ such that every facet of $\pol$ contains a vertex in $S$, then $\pol$ is indecomposable.
\end{theorem}
%
%
%
%
%
%
%
	
	
%
%
%
%
%
%
%
%
%
%


With the following lemma, we see directly that  \Cref{thm:WspanningPMinkowskiIndecomposable} is a corollary of \Cref{thm:rigidFacetsIndecomposable}, as it implies that the whole set of vertices is dependent.

\begin{lemma}\label{lem:connecteddependentrigid}
	If the vertices in $S\subseteq\verts(\pol)$ are pairwise connected in $\G(\pol)$ through a path of dependent edges, then $S$ is dependent.
\end{lemma}
%
%
%
	
%
%
%


\noindent
This also implies McMullen's and Shephard's criteria from \cite{McMullen1987,Shephard1963}. In fact, \cite[Theorem~1]{McMullen1987} cites \cite[Theorem~12]{Shephard1963} with a slightly stronger statement: both are true. 
%
We cite this stronger version, which also follows from \Cref{thm:rigidFacetsIndecomposable}.
A \defn{strong chain} of faces of a polytope~$\pol$ is a sequence of faces $\pol[F]_0,\dots,\pol[F]_k$ such that $\dim(\pol[F]_{i}\cap\pol[F]_{i-1})\geq 1$ for $1\leq i\leq k$. Any vertex or edge of $\pol[F]_0$ is said to be connected to any vertex or edge of $\pol[F]_i$ with $1\leq i\leq k$.


\begin{corollary}[{\cite[Theorem 12]{Shephard1963}, \cite[Theorem 1]{McMullen1987}}]\label{cor:McMullen1}
	Let $\pol$ be a polytope. If any pair of vertices of $\pol$ can be connected by a strong chain of indecomposable faces, then $\pol$ is itself indecomposable.
\end{corollary}
\begin{proof}
	If $\b p,\b q\in\verts(\pol)$ are connected by a strong chain of indecomposable faces, then they are connected by a dependent set of edges, by \Cref{cor:indecfacesclique}. By \Cref{lem:connecteddependentrigid}, $\verts(\pol)$ is a dependent set. Every facet contains a vertex, and we conclude by \Cref{thm:rigidFacetsIndecomposable}.
\end{proof}


Another indecomposability criterion was introduced in~\cite{McMullen1987}. While not strictly comparable to \Cref{cor:McMullen1}, both turn out to be consequences of \Cref{thm:rigidFacetsIndecomposable}.
A family of faces $\c F$ of a polytope is \defn{strongly connected} if for any $\pol[F],\pol[G]\in \c F$ there is a strong chain $\pol[F]=\pol[F]_0,\pol[F]_1,\dots,\pol[F]_k=\pol[G]$ with each $\pol[F]_i\in \c F$. We say that $\c F$ touches a face $\pol[F]$ if $(\bigcup \c F)\cap \pol[F]\neq \emptyset$.
	
	\begin{corollary}[{\cite[Theorem~2]{McMullen1987}}]
		If a polytope $\pol$ has a strongly connected family of indecomposable faces which touches each of its facets, then $\pol$ is itself indecomposable.
	\end{corollary}
	\begin{proof}
		The vertices of the %
		faces in the strongly connected family form a dependent subset by \Cref{cor:indecomposablerigid,lem:EELDCCcliques}. We conclude with \Cref{thm:rigidFacetsIndecomposable}.
        %
	\end{proof}


	From \Cref{thm:rigidFacetsIndecomposable} we can also naturally derive other stronger indecomposability criteria from \cite{Kallay1982,PrzeslawskiYost2008,PrzeslawskiYost2016}. However, these results involve the concept of indecomposable geometric graph, which we have decided to omit from this abstract for the sake of brevity. 


	\section{Other applications: Cartesian products and zonotopes}\label{sec:productszonotopes}
	
		
	
	The (extended) graph of edge-length dependencies has applications beyond indecomposability criteria. For example, it is easy to see that the number of connected components of $\ELD$ is an upper bound for the dimension of the deformation cone.
        
    We showcase first an application concerning Cartesian products. The \defn{Cartesian} product of $\pol\subseteq \R^d$ and $\pol[Q]\subseteq \R^e$ is $\pol\times\pol[Q]=\set{(\b p, \b q)\in\R^{d+e}}{\b p\in \pol, \b q\in \pol[Q]}\subseteq \R^{d+e}$. Its faces are of the form $\pol[F]\times\pol[G]$ where $\pol[F]$ and $\pol[G]$ are faces of $\pol$ and $\pol[Q]$, respectively.
%
	
	
	
	\begin{theorem}
		All deformations of a Cartesian product $\pol\times\pol[Q]$ are of the form $\pol'\times\pol[Q]'$, where $\pol'$ and $\pol[Q]'$ are deformations of $\pol$ and $\pol[Q]$ respectively. 
		Consequently, the deformation cone of $\pol\times\pol[Q]$ is the Cartesian product of the deformation cones
        %
        of $\pol$ and $\pol[Q]$:
		\(\EDefoCone[\pol\times\pol[Q]]=\EDefoCone[\pol]\times \EDefoCone[\pol[Q]].\)
	\end{theorem}

	\begin{proof}
		Let $\pol[e]\in \edges(\pol)$ and $ \b q, \b q'\in \verts(\pol[Q])$.
        Consider a path	$ \b q_0= \b q, \b q_1,\dots, \b q_k= \b q'$ from $ \b q$ to $\b q'$ in the $1$-skeleton $\G(\pol[Q])$.
		For each $1\leq i\leq k$, $\pol[f]_i\eqdef \conv( \b q_{i-1}, \b q_i)$ is an edge of $\pol[Q]$. Hence $ \pol[e]\times \pol[f]_i$ is a parallelogram face of $\pol\times\pol[Q]$, and thus $ \pol[e]\times  \b q_i$ and $ \pol[e]\times  \b q_{i-1}$ are dependent by \Cref{lem:parallelogram}. By transitivity, the edges $\pol[e]\times \b q$ and $\pol[e]\times  \b q'$ of $\pol\times\pol[Q]$ are dependent.
		
		Hence, in a deformation $\pol[R]$ of $\pol\times\pol[Q]$, all the faces corresponding to $\pol\times  \b q$ with $ \b q\in \verts(\pol[Q])$ are translations of the same deformation $\pol'$ of $\pol$, because they have the same edge-lengths. Similarly, all the faces of the form $ \b p\times \pol[Q]$ with $\b p\in\verts(\pol)$ are translations of the same deformation $\pol[Q]'$ of $\pol[Q]$. Since $\pol[R]$ and $\pol[P]'\times \pol[Q]'$ have the same edge-lengths, they must coincide up to translation. 
	\end{proof}	

%
A \defn{zonotope} is a Minkowski sum of segments $\pol[Z] = \sum_{i=1}^r [\b p_i,\, \b q_i]$, where we use the notation $[\b p_i,\, \b q_i]\eqdef \conv(\b p_i,\, \b q_i)$.


\begin{theorem}\label{thm:ZonotopesWithOnlyParallelograms}
The deformation cone of a zonotope $\pol[Z]$ is simplicial and all its deformations are zonotopes, if and only if all its $2$-faces are parallelograms. In this case we have:
	$$\EDefoCone[{\pol[Z]}] = \set{	\b\ell \in \R_{\geq 0}^{\edges(\pol[Z])}}{\ell_{\pol[e]} = \ell_{\pol[f]} \,\text{ if } \pol[e] \text{ and } \pol[f] \text{ are parallel edges}}$$
\end{theorem}

\begin{proof}
	Let $\pol[Z] = \sum_{i=1}^r \pol[s]_i$, where $\pol[s]_i\eqdef[\b p_i,\, \b q_i]$, and no two $\pol[s]_i$ are parallel (otherwise we replace them by their sum), and assume all $2$-faces are parallelograms.
	Fix $1\leq i\leq r$.
    %
	The collection of faces parallel to $\pol[s]_i$ (known as the \defn{$i$th zone}) is isomorphic to the product of $\pol[s]_i$ with the boundary of	$\pi_i(\pol[Z])$,  where $\pi_i$ is the orthogonal projection in the direction of $\pol[s]_i$ (\cf \cite[Section~2.2]{OrientedMatroids}).
	Every edge $\pol[e]$ of $\pi_i(\pol[Z])$ induces a $2$-face of $\pol[Z]$ isomorphic to the parallelogram $\pol[e]\times \pol[s]_i$. By \Cref{lem:parallelogram}, the subgraph of $\ELD[{\pol[Z]}]$ induced by the edges parallel to $\pol[s]_i$ contains a copy of the $1$-skeleton of $\pi_i(\pol[Z])$. As the later is $(\dim\pol[Z]-1)$-connected, we deduce that all the edges parallel to $\pol[s]_i$ are dependent.	
	Therefore, in any deformation $\pol[Z]_{\b \ell}$ of $\pol[Z]$, all the edges parallel to $\pol[s]_i$ have the same length~$\lambda_i$, and~$\pol[Z]_{\b \ell}$ must be a translation of the zonotope $\sum_{i=1}^r \lambda_i \pol[s]_i$.
	Hence, $\EDefoCone[{\pol[Z]}] $ is linearly isomorphic to the simplicial cone $\R_{\geq 0}^{r}$.
    For the reciprocal, see that all faces of a zonotope are its Minkowski summands, and that a centrally symmetric $n$-gon has a triangle summand whenever $n\geq 5$.
\end{proof}
%
%
%
	%
	
%
	
	
	
	\section{New rays of the submodular cone}\label{sec:newrays}
	\subsection{Graphical zonotopes}

Let $G=(V,E)$ a graph with node set $V$ and arc\footnote{Recall that we reserve \emph{vertex} and \emph{edge} for the faces of polytopes, and use \emph{node} and \emph{arc} for graphs.} 
set $E$.
An orientation of $G$ is \defn{acyclic} if there is no directed cycle.
%
Let \defn{$\AO(G)$} be the set of acyclic orientations of $G$.
The \defn{graphical zonotope} $\ZG \subset \R^V$ is defined as the Minkowski sum 
$\ZG 
%
= \sum_{\{i, j\} \in E} [\b e_i, \b e_j]$, where $(\b e_i)_{i \in V}$ is the standard basis of $\R^V$.
%
%
An \defn{ordered partition} of~$G$ is a pair consisting of a partition $\mu$ of $V$ where each part induces a connected subgraph of~$G$, together with an acyclic orientation $\omega$ of the contraction $\contrG$. The faces of a graphical zonotope are indexed by ordered partitions (see for example \cite[Proposition~2.5]{Stanley2007} or \cite[Section~1.1]{OrientedMatroids}). In particular:
\begin{compactenum}
    \item The vertices of $\ZG$ are in bijection with the acyclic orientations $\AO(G)$. Namely, 
   each $\rho\in \AO(G)$ is in correspondence with the vertex $\b v_\rho = \sum_{i\in V} d_{in}(i, \rho) \,\b e_i$ where $d_{in}(i, \rho)$ is the in-degree of the node $i\in V$ in the acyclic orientation $\rho$.
    \item The edges $\pol[e]_{g, \rho}$ of $\ZG$ are in bijection with the couples $(g, \rho)$ where $g\in E$ and $\rho\in \AO (\contrG[e])$, \ie with the couples of acyclic orientations $\rho_1, \rho_2\in \AO(G)$ which differ only on the orientation of the arc $g$. Moreover, if $g = \{i, j\}$ is oriented $i\to j$ in $\rho_1$, then $\b v_{\rho_1} - \b v_{\rho_2} = \b e_j - \b e_i$.
    \item The $2$-faces of $\ZG$ are:
    \begin{compactenum}
        \item Hexagons: one per $(t, \rho)$ where $t$ is a triangle in $G$ and $\rho\in\AO(\contrG[t])$.
        \item Parallelograms: one per 
        $(s, \rho)$ where $s$ is either the union of two disjoint edges or an induced path of length 2, and $\rho\in \AO(\contrG[s])$
    \end{compactenum}
\end{compactenum}

This result from \cite{PPP2023gZono} follows thus from \Cref{thm:ZonotopesWithOnlyParallelograms}:

\begin{corollary}[{\cite[Corollary 2.10]{PPP2023gZono}}]
The deformation cone $\EDefoCone[\ZG]$ is simplicial and all the deformations of $\ZG$ are zonotopes if and only if $G$ is triangle-free.
\end{corollary}

%
%
%

\subsection{Truncated graphical zonotopes of complete bipartite graphs}
For $n, m\geq 1$, let $\Knm$ be the complete bipartite graph with nodes $a_1,\dots, a_n$ and $b_1, \dots, b_m$ and arcs $a_ib_j$ for all $i\in [n]$ and $j\in [m]$.
Note that $\Knm$ is triangle-free.
We abbreviate its graphical zonotope by $\ZGKnm\eqdef\pol[Z]_{K_{n, m}}$.
We define two new polytopes by intersecting $\ZGKnm$ with some half-spaces. 
Precisely, recall that $\ZGKnm$ is embedded in $\R^{n + m}$ whose coordinates are labeled by $a_i$, $i\in [n]$ and $b_j$, $j\in [m]$, and define 
\begin{align*}
\mathdefn{\Pnm} &\eqdef \ZGKnm \cap \big\{\b x ~;~ \sum\nolimits_{j=1}^m x_{b_j} \leq nm-1\big\},&&\text{and} &\mathdefn{\Qnm} &\eqdef \Pnm \cap \big\{\b x ~;~ \sum\nolimits_{i=1}^n x_{a_i} \leq nm - 1\big\}.
\end{align*}


\begin{example}\label{exmp:SmallDimPandQ}
	We describe $\Pnm$ and $\Qnm$ for $n + m \leq 4$, which are those in dimension up to~$3$.
	We summarized their properties in the following table.
	\begin{center}
%
%
%
%
%
%
%
%
%
%
%
%
%
\begin{small}
	\begin{tabular}{c|cccc|ccc}
     & \multicolumn{4}{c|}{$\Pnm$} & \multicolumn{3}{c}{$\Qnm$} \\
		$ (m,n)$ & (1,1) & (1,2) & (1,3) & (2,2) & (1,2) & (1,3) & (2,2)  \\ \hline
		name  & point & triangle & \emph{strawberry}
		&\emph{persimmon} & segment & octahedron & cuboctahedron \\
		\text{indec.} & \yes & \yes & \yes & \yes & \yes & \yes & \no \\
		\text{matroid} & \yes & \yes & \no  &\no & \yes & \yes & \no
	\end{tabular}
\end{small}
\end{center}
	
The first row answers ``Is this polytope indecomposable?'', and the second ``Is this polytope a matroid polytope?'' (\yes~ is ``yes'', and \no~ is ``no'').

The polytopes $\Pnm[3][1]$, $\Qnm[3][1]$, and $\Pnm[2][2]$, $\Qnm[2][2]$ are depicted in \Cref{fig:SmallDimPandQ}. The polytope $\Pnm[3][1]$ (nicknamed \emph{strawberry}) has $f$-vector is $(7, 12, 7)$; and $\Pnm[2][2]$ (nicknamed \emph{persimmon}) has $f$-vector $(13, 24, 13)$.
As illustrated in the figure, $\ELD[{\Pnm[3][1]}]$, $\ELD[{\Qnm[3][1]}]$ and $\ELD[{\Pnm[2][2]}]$ contain connected subgraphs whose associated edges touch all the vertices: by \Cref{thm:WspanningPMinkowskiIndecomposable}, $\Pnm[3][1]$, $\Qnm[3][1]$ and $\Pnm[2][2]$ are indecomposable.
	The cuboctahedron $\Qnm[2][2] $ is decomposable as the Minkowski sum of a regular tetrahedron and its central reflection.
	
	%
	%
		\begin{figure}[htpb]
		\centering
		\includegraphics[width=0.2\linewidth]{Figures/Strawberry.pdf}
        \includegraphics[width=0.2\linewidth]{Figures/Octahedron.pdf}
        %
		\includegraphics[width=0.28\linewidth]{Figures/Persimmon.pdf}
		\includegraphics[width=0.28\linewidth]{Figures/Cuboctahedron.pdf}
        \caption{(Left to right) strawberry $\Pnm[3][1]$, octahedron $\Qnm[3][1]$, persimmon $\Pnm[2][2]$, cuboctahedron $\Qnm[2][2]$.
        Each polytope is in \textcolor{blue}{blue}, while the \textcolor{gray}{gray} dashed edges outline $\ZGKnm$.
        %
        In \textcolor{OrangeRed}{red}, the subgraphs of $\ELD$ obtained by linking opposite edges of (some) parallelograms and edges of (some) triangles (these are the subgraphs from the proof of \Cref{thm:PandQareIndecomposable}).
        $\ELD[{\Qnm[2][2]}]$ has two connected components: the cliques on the \textcolor{OrangeRed}{red} and \textcolor{green}{green} subgraphs.}
		\label{fig:SmallDimPandQ}
	\end{figure}
    
	$\Pnm[3][1]$ and $\Pnm[2][2]$ are self-dual and have exactly 4 triangular faces.
	Smilansky proved in \cite[Corollary 6.7, 6.8]{Smilansky1987} that every indecomposable $3$-polytope has at least 4 triangular faces, and has (weakly) more facets than vertices: $\Pnm[3][1]$ and $\Pnm[2][2]$ are extremal in this sense.
\end{example}

	Denote by $\b v_{n\to m}$ (resp. $\b v_{n \leftarrow m}$) the vertex of $\ZGKnm$ associated to the acyclic orientation $\rho_{n\to m}$ (resp. $\rho_{n \leftarrow m}$) given by $a_i \to b_j$ (resp. $a_i \leftarrow b_j$)for all $i\in [n]$ and $j\in [m]$. An acyclic orientation of $\Knm$ is \defn{almost left-right} (resp. \defn{almost right-left}) if it is obtained from $\rho_{n \to m}$ (resp. $\rho_{n \leftarrow m}$) by reversing the orientation of one arc called its \defn{reversed arc}.

%

\begin{lemma}[Facial structure of $\Pnm$ and $\Qnm$]\label{lem:FacesOfPandQ}
Let $n, m\geq 1$ with $nm > 2$.
\begin{compactenum}
    \item $\verts(\Pnm)=\verts(\ZGKnm) \ssm \{\b v_{n \to m}\}$, and $\verts(\Qnm)=\verts(\ZGKnm) \ssm \{\b v_{n \to m}, \b v_{n \leftarrow m}\}$. That is, $\Pnm = \ZGKnm \ssm \b v_{n\to m}$ and $\Qnm = \ZGKnm \ssm \{\b v_{n\to m}, \, \b v_{n \leftarrow m}\}$, 
    where $\pol\ssm \b v$ denotes the polytope obtained as the the convex hull of all the vertices of $\pol$ except $\b v$.
    \item The edges of $\Pnm$ (resp. $\Qnm$) are either: (i) edges of $\ZGKnm$  not containing $\b v_{n \to m}$ (resp. $\b v_{n \to m}$ nor $\b v_{n \leftarrow m}$), or (ii) edges $\b v_{\rho_1} \b v_{\rho_2}$ for two almost left-right orientations (resp. two almost left-right or almost right-left orientations) $\rho_1$, $\rho_2$ whose reversed arcs share an endpoint.
   %
   %
   %
   %
       
    \end{compactenum}
\end{lemma}
%
%

%
%
%
%

	
Now, we focus on $\Pnm$ and $\Qnm$ for $n, m\geq 1$, $(n, m) \ne (1, 1)$.
We prove that they are deformed permutahedra (\Cref{thm:PandQareGP}), indecomposable (except $\Qnm[2][2]$, \Cref{thm:PandQareIndecomposable}), and not matroid polytopes (except $\Pnm[1][1]$, $\Pnm[1][2]$, $\Qnm[1][2]$, $\Qnm[1][3]$, \Cref{thm:PandQnotMatroidPolytopes}).
This implies that:

\begin{corollary}\label{cor:NewMIGP}
For $n\geq 5$, there exist (at least) $2\lfloor\frac{n-1}{2}\rfloor$ non-isomorphic indecomposable deformed permutahedra which are not matroid polytopes.
\end{corollary}

Building on numerical computations we led for $n \in\{3, 4, 5, 6\}$, we furthermore conjecture the following. Let $\mathdefn{t_n}$ be the number of indecomposable deformed permutahedra, and $\mathdefn{m_n}$ be the number of indecomposable deformed permutahedra which are matroid polytopes (\ie deformed permutahedra on $0/1$ coordinates). 
As $m_n$ is doubly exponential, \Cref{cor:NewMIGP} is far too weak to tackle the following conjecture:

\begin{conjecture}${m_n}/{t_n} \to 0$ when $n\to+\infty$.
\end{conjecture}

%
%
%
%
%


\subsubsection{Deformed permutahedra}
The deformations of $\permuto$ are characterized~\cite{Postnikov2009} by having all its edges parallel to $\b e_i - \b e_j$ (for some~$i, j$). 
Using \Cref{lem:FacesOfPandQ}, we can verify that $\Pnm$ and $\Qnm$ satisfy this condition.

	\begin{theorem}\label{thm:PandQareGP}
		The polytopes $\Pnm$ and $\Qnm$ are deformed permutahedra.
	\end{theorem}
%
%
		
%
%
		
%
%
%
%
%
%
%
\noindent {Unfortunately, our construction only gives deformed permutahedra for $\Knm$.%
}

\begin{theorem}
For a graph $G$ and a vertex $\b v$ of $\ZG$, if $\ZG\ssm \b v$ is a deformed permutahedron, then $G$ is a complete bi-partite graph $\Knm$ and $\b v = \b v_{n\to m}$ or $\b v = \b v_{m\to n}$.
\end{theorem}


\subsubsection{Indecomposability}
We use \Cref{thm:WspanningPMinkowskiIndecomposable} to prove indecomposability. For $n+m\leq 4$, see \Cref{exmp:SmallDimPandQ}.

\begin{theorem}\label{thm:PandQareIndecomposable}
%
For $n, m\geq 1$ with $n+m\geq 5$, $\Pnm$ and $\Qnm$ are indecomposable. 
\end{theorem}

\begin{proof}
%
For an arc $ij$ of $\Knm$, call \defn{$ij$-edges} the edges of $\ZGKnm$, $\Pnm$ or $\Qnm$ in direction $\b e_i-\b e_j$, and \defn{$a$-edges} the $ij$-edges for some arc $ij$ (the ones of form (i) in \Cref{lem:FacesOfPandQ}).
Let $\zELD[ij]$ (resp. $\zELD[ij]^{\rightarrow}$ and $\zELD[ij]^{\leftrightarrow}$) be the subgraph of $\ELD[\ZGKnm]$ (resp. $\ELD[\Pnm]$ and $\ELD[\Qnm]$) induced on all $ij$-edges.
We have seen in the proof of \Cref{thm:ZonotopesWithOnlyParallelograms} that $\zELD[ij]$ contains a subgraph isomorphic to the 1-skeleton of the graphical zonotope of ${\contrG[ij][\Knm]}$. It is $(n+m-2)$-connected, so removing 1 or 2 vertices does not break connectivity: $\zELD[ij]^{\rightarrow}$ and $\zELD[ij]^{\leftrightarrow}$ are connected.
Let $ij$, $ik$ be two arcs of $\Knm$ sharing an endpoint.
Let $\rho_1$, $\rho_2$ be their associated almost left-right orientations.
The edge $\b v_{\rho_1}\b v_{\rho_2}$ shares a triangular $2$-face with an $ij$-edge and a $ik$-edge.
As any triangle is indecomposable, \Cref{cor:indecfacesclique} ensures that $\zELD[ij]^{\rightarrow}$ and $\zELD[ik]^{\rightarrow}$ are connected together.
As $\Knm$ is connected, so is its line-graph, thus the subgraph of $\ELD[\Pnm]$ induced on the set of all $a$-edges is connected.
The $a$-edges form a dependent subset, and every vertex of $\Pnm$ appears as endpoint of one of these edges in $\G(\Pnm)$ (because any $\rho\in\AO(G)$ has a re-orientable arc): by \Cref{thm:WspanningPMinkowskiIndecomposable}, we get that $\Pnm$ is indecomposable. The same reasoning holds for $\Qnm$.
\end{proof}

This allows for refuting Smilanski's conjecture from 1987 {\cite[Conjecture~6.12]{Smilansky1987}},
stating that a $d$-polytope $\pol$ is decomposable if it satisfies 
\begin{equation}\label{eq:smilanski}
\verts > 1+ \binom{\facets - 1-\lfloor{d}/{2}\rfloor }{\facets-d}+ \binom{\facets - 1-\lfloor({d+1})/{2}\rfloor }{\facets-d},\end{equation}
where $\verts\eqdef|\verts(\pol)|$, $\facets\eqdef|\facets(\pol)|$.
%
%
%
%
%
For $d = 4$, \eqref{eq:smilanski} is $\verts\geq 2\facets -4$. Both $\Pnm[1][4]$ and $\Pnm[2][3]$ are indecomposable and yet their $f$-vectors, $(15, 34, 28, 9)$ and $(45, 111, 89, 23)$, fulfill~\eqref{eq:smilanski}. 
 

\subsubsection{Not matroid polytopes}
The \defn{matroid polytope} of a matroid is the convex hull of the indicator vectors of its bases. Matroid polytopes are characterized by being the deformed permutahedra with $0/1$-coordinates \cite{GelfandGoreskiMacPhersonSerganova}.
We can show that $\Pnm$ and $\Qnm$ are not matroid polytopes (except for sporadic cases) by providing vertices whose coordinates take at least $3$ different values.

%
%
%
%

%
%
%
%
%
%
%

\begin{theorem}\label{thm:PandQnotMatroidPolytopes}
For $1\leq n\leq m$, $\Pnm$ (resp. $\Qnm$) is normally equivalent to a matroid polytope if and only if $n = 1$ and $m \in \{1, 2\}$  (resp. $n = 1$ and $m \in \{1, 2, 3\}$).
%
\end{theorem}
	
%
%
%
%

%
%
%
%
%
		
%
%
%
%
%
%
%
					
%
%
%
%
					
%
%
%
%
					
%
%
%
%
					
%
%
				
%
%
%
%
%
					
%
%
%
%
					
%
%
%
%
					
%
%
%
%
					
%
%
				
%
%
%
%
%
					
%
%
%
%
					
%
%
%
%
					
%
%
%
%
					
%
%
%
%
        
%
%

%

%
%
%
%


\acknowledgements{
%
We thank Georg Loho for many interesting conversations on the topic;
%
and Winfried Bruns for his help on the computation of $\EDefoCone[\permuto]$ for $n=4$ (and higher).}

%
%
\printbibliography

%
%
%


\end{document}
