%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[final]{FPSAC2022}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}
\usepackage{xargs, bbm, enumerate, paralist}
\usepackage[shortlabels, inline]{enumitem}
\graphicspath{{figures/}}
\usepackage{ulem}\normalem

% theorems
\newtheorem{theorem}{Theorem}[section]
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{conjecture}[theorem]{Conjecture}
%\newtheorem*{theorem*}{Theorem}%[section]
\newtheorem{question}[theorem]{Question}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{assumption}[theorem]{Assumption}
\newtheorem{convention}[theorem]{Convention}


\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\theoremstyle{remark}
\newtheorem{example}[theorem]{Example}
\newtheorem{remark}[theorem]{Remark}

\crefname{equation}{Equation}{Equations}

% math special letters
\newcommand{\R}{\mathbb{R}} % reals
\newcommand{\Q}{\mathbb{Q}} % rationals
\newcommand{\N}{\mathbb{N}} % naturals
\newcommand{\Z}{\mathbb{Z}} % integers
\newcommand{\C}{\mathbb{C}} % complex
\newcommand{\I}{\mathbb{I}} % set of integers
\newcommand{\HH}{\mathbb{H}} % hyperplane
\newcommand{\K}{k} % field
\newcommand{\bb}[1]{{\mathbb{#1}}} % mathbb letters
\newcommand{\f}[1]{{\mathfrak{#1}}} % mathfrak letters
\renewcommand{\c}[1]{{\mathcal{#1}}} % call letters
\renewcommand{\b}[1]{{\boldsymbol{#1}}} % bold letters
\newcommand{\h}{\widehat} % hat letters

% math commands
\newcommand{\set}[2]{\left\{ #1 \;\middle|\; #2 \right\}} % set notation
\newcommand{\bigset}[2]{\big\{ #1 \;\big|\; #2 \big\}} % big set notation
\newcommand{\Bigset}[2]{\Big\{ #1 \;\Big|\; #2 \Big\}} % Big set notation
\newcommand{\setangle}[2]{\left\langle #1 \;\middle|\; #2 \right\rangle} % set notation
\newcommand{\ssm}{\smallsetminus} % small set minus
\newcommand{\dotprod}[2]{\langle \, #1 \; | \; #2 \, \rangle} % dot product
\newcommand{\bigdotprod}[2]{\big\langle \, #1 \; \big| \; #2 \, \big\rangle} % dot product
\newcommand{\symdif}{\,\triangle\,} % symmetric difference
% \newcommand{\one}{{1\!\!1}} % the all one vector
\newcommand{\one}{\mathbbm{1}} % the all one vector
\newcommandx{\ones}[1][1=n]{\one_{#1}} % the all one vector of length n
\newcommand{\eqdef}{\mbox{\,\raisebox{0.2ex}{\scriptsize\ensuremath{\mathrm:}}\ensuremath{=}\,}} % :=
\newcommand{\defeq}{\mbox{~\ensuremath{=}\raisebox{0.2ex}{\scriptsize\ensuremath{\mathrm:}} }} % =:
\newcommand{\simplex}{\triangle} % simplex
\renewcommand{\implies}{\Rightarrow} % imply sign
\newcommand{\transpose}[1]{{#1}^T} % transpose matrix
\newcommand{\truth}[1]{\left[ #1 \right]} % truth (kronecker delta)

% operators
\DeclareMathOperator{\conv}{conv} % convex hull
\DeclareMathOperator{\vect}{vect} % linear span
\DeclareMathOperator{\cone}{cone} % cone hull

% others
\newcommand{\ie}{\textit{i.e.}~} % id est
\newcommand{\eg}{\textit{e.g.}~} % exempli gratia
\newcommand{\Eg}{\textit{E.g.}~} % exempli gratia
\newcommand{\apriori}{\textit{a priori}} % a priori
\newcommand{\viceversa}{\textit{vice versa}} % vice versa
\newcommand{\versus}{\textit{vs.}~} % versus
\newcommand{\aka}{\textit{a.k.a.}~} % also known as
\newcommand{\perse}{\textit{per se}} % per se
\newcommand{\ordinal}{\textsuperscript{th}} % th for ordinals
\newcommand{\ordinalst}{\textsuperscript{st}} % st for ordinals
\definecolor{darkblue}{rgb}{0,0,0.7} % darkblue color
\definecolor{green}{RGB}{57,181,74} % green color
\definecolor{violet}{RGB}{147,39,143} % violet color
\newcommand{\red}{\color{red}} % red command
\newcommand{\blue}{\color{blue}} % blue command
\newcommand{\orange}{\color{orange}} % orange command
\newcommand{\green}{\color{green}} % green command
\newcommand{\darkblue}{\color{darkblue}} % darkblue command
\newcommand{\defn}[1]{\textsl{\darkblue #1}} % emphasis of a definition
\newcommand{\para}[1]{\paragraph{\uline{#1.}}} % paragraph
\renewcommand{\topfraction}{1} % possibility to have one page of pictures
\renewcommand{\bottomfraction}{1} % possibility to have one page of pictures

% marginal comments
\usepackage{todonotes}
\newcommand{\arnau}[1]{\todo[color=orange!30]{#1 --- A.}}
\newcommand{\vincent}[1]{\todo[color=blue!30]{#1 \\ \hfill --- V.}}
\newcommand{\germain}[1]{\todo[color=green!30]{#1 \\ \hfill --- G.}}

% polytopes
\newcommand{\polytope}[1]{\mathsf{#1}} % font polytopes
\newcommandx{\Perm}[1][1=n]{\polytope{Perm}_{#1}} % permutahedron

% geometry
\newcommandx{\Fan}[1][1=F]{\mathcal{#1}} % fan
\newcommand{\walls}{\b{W}} % walls
\newcommandx{\ray}[1][1=r]{\b{#1}} % ray
\newcommandx{\rays}[1][1=R]{\b{#1}} % rays

% graph associahedra
\newcommandx{\Asso}[1][1=G]{\polytope{A}_{#1}} % associahedron
\newcommandx{\Nest}[1][1=\building]{\polytope{N}_{#1}} % nestohedron
\newcommandx{\tube}[1][1=t]{#1} % tube
\newcommandx{\tubes}[1][1=G]{\mathcal{T}_{#1}} % all tubes
\newcommandx{\tubing}[1][1=T]{#1} % tubing
\newcommand{\connectedComponents}{\kappa} % connected components
\newcommand{\bConnectedComponents}{\overline{\kappa}} % connected components
\newcommandx{\nestedComplex}[1][1=G]{\mathsf{NC}_{#1}} % nested complex
\newcommandx{\nFan}[1][1=G]{\Fan[N]_{#1}} % graphical fan projected
\newcommand{\nonDisconnecting}{\mathrm{nd}} % non-disconnecting vertices

% nestohedra
\newcommand{\building}{\mathcal{B}} % building set
\newcommand{\elementary}{\varepsilon} % elementary subsets of a building set
\newcommand{\maximalBlocks}{\mu} % maximal blocks
\newcommandx{\nested}[1][1=N]{\mathcal{#1}} % nested set
\newcommand{\leaving}[3]{#1 \vdash #2 \subseteq #3} % leaving property
\newcommand{\rootset}[2]{\b{r}(#1,#2)} % root of element of nested set

% graphical zonotopes
\newcommandx{\gZono}[1][1=G]{\mathsf{Z}_{#1}} % graphical zonotope
\newcommandx{\gArr}[1][1=G]{\mathcal{A}_{#1}} % graphical arrangement
\newcommandx{\gFan}[1][1=G]{\Fan[G]_{#1}} % graphical fan projected
\newcommandx{\gFanO}[1][1=G]{\widehat{\Fan}_{#1}} % graphical fan unprojected
\newcommand{\gvector}[1]{\b{g}_{#1}} % g-vector
\newcommand{\ivector}[1]{\b{\iota}_{#1}} % i-vector
\newcommandx{\cc}[1][1=G]{\mathbb{K}_{#1}} % connected components space
\newcommandx{\braid}[1][1=n]{\mathcal{B}_{#1}} %braid fan/arrangement
\newcommandx{\sbraid}[1][1=n]{\widehat{\mathcal{B}}_{#1}} %split braid fan
\newcommandx{\dZono}[1][1=\b{h}]{\mathsf{D}_{#1}} % h-deformed zonotope


% hypergraphic polytopes
\newcommandx{\hypPol}[1][1=H]{\mathsf{P}_{#1}} % hypergraphic polytope
\newcommandx{\hypFan}[1][1=H]{\Fan[H]_{#1}} % hypergraphic fan 

% Type cone
\newcommand{\deformationCone}{\mathbb{DC}} % deformation cone
\newcommand{\typeCone}{\mathbb{TC}} % type cone
\newcommand{\ctypeCone}{\smash{\overline{\mathbb{TC}}}} % type cone
\newcommandx{\coefficient}[3][1={\b{s}}, 2=\b{r}, 3=\b{r}']{\alpha_{#2,#3}(#1)} % coefficient in linear dependence
\newcommandx{\virtualPolytopes}[1][1=d]{\mathbb{V}^{#1}} % virtual polytopes
\newcommandx{\VDP}[1][1=n]{\mathbb{VDP}^{#1}} % virtual deformed permutahedra
\newcommandx{\CVDP}[1][1=n]{\overrightarrow{\mathbb{VDP}}^{#1}} % caged virtual deformed permutahedra
% \newcommand{\deformationCone}{\mathbb{DC}} % deformation cone
\newcommand{\VD}[1][1=n]{\mathbb{VD}} % virtual deformations
\newcommand{\Weight}{\mathbb{W}} % 1st weight space
\newcommandx{\opcone}[1][1={\mu,\omega}]{\polytope{C}_{#1}}
\newcommandx{\orcone}[1][1={\omega}]{\polytope{C}_{#1}}

%% define your title in the usual way
\title{Deformation Cones of Hypergraphic Polytopes}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author[A.~Padrol, V.~Pilaud, and G.~Poullot]{
	Arnau Padrol\thanks{\href{mailto:arnau.padrol@imj-prg.fr}{arnau.padrol@imj-prg.fr}. Supp.~by ANR CAPPS~17\,CE40\,0018.}\addressmark{1},
	%\stepcounter{footnote}%
	Vincent Pilaud\thanks{\href{mailto:vincent.pilaud@lix.polytechnique.fr}{vincent.pilaud@lix.polytechnique.fr}. Supp.~by ANR CAPPS~17\,CE40\,0018 and CHARMS~19\,CE40\,0017.}\addressmark{2}, \and %
	Germain Poullot\thanks{\href{mailto:germain.poullot@imj-prg.fr}{germain.poullot@imj-prg.fr}. Supp.~by ANR CAPPS~17\,CE40\,0018.}\addressmark{1}
}

%% then use \addressmark to match authors to institutions here
\address{
	\addressmark{1}Institut de Math\'ematiques de Jussieu - Paris Rive Gauche, Sorbonne Universit\'e, Paris, France \\ 
	\addressmark{2}CNRS \& LIX, \'Ecole Polytechnique, Palaiseau, France%
}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{
A hypergraphic polytope is a Minkowski sum of faces of the standard simplex.
We study deformations of two fundamental families of hypergraphic polytopes: the graphical zonotopes and the nestohedra.
Namely, we provide irredundant facet descriptions for the deformation cones of these polytopes.
Moreover, we show that the faces of the standard simplex contained in the deformation cone provide a linear basis of its vector span, a result that extends to any hypergraphic polytope.
}

%% put your French abstract here, or comment this out if you don't have one
\resumetitle{R\'esum\'e}
\resume{
Un polytope hypergraphique est une somme de Minkowski de faces du simplexe standard.
Nous \'etudions les d\'eformations de deux familles fondamentales de polytopes hypergraphiques~:~les zonotopes graphiques et les nesto\`edres.
Nous donnons des descriptions irredondantes des in\'egalit\'es d\'efinissant les facettes des cones de d\'eformation de ces polytopes.
En outre, nous montrons que les faces du simplexe standard contenues dans le cone de d\'eformation forment une base lin\'eaire de l'espace vectoriel qu'il engendre, un r\'esultat qui s'\'etend \`a tout polytope hypergraphique.
}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{deformations, hypergraphic polytopes, graphical zonotopes, nestohedra}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations, ie. [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex]{biblatex}
%\DeclareFieldFormat[article,inbook,incollection,inproceedings,patent,thesis,unpublished]{title}{\textit{#1}\isdot}
%\renewbibmacro{in:}{}
\addbibresource{graphicalDeformationCones.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above

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

\section{Introduction}

A \defn{deformation} of a polytope~$\polytope{P}$ can be equivalently described as 
\begin{enumerate*}[(i)]
 \item a polytope obtained from~$\polytope{P}$ by gliding its facets orthogonally to their normal vectors without passing a vertex~\cite{Postnikov,PostnikovReinerWilliams}, 
 \item a polytope obtained from~$\polytope{P}$ by perturbing the vertices so that the directions of all edges are preserved~\cite{Postnikov,PostnikovReinerWilliams}, 
 \item a polytope whose normal fan coarsens the normal fan of~$\polytope{P}$~\cite{McMullen-typeCone}, 
 \item a polytope whose support functionial is a convex  piecewise linear continuous function supported on the normal fan of~$\polytope{P}$~\cite[Section~6.1]{CoxLittleSchenck}\cite[Section~9.5]{DeLoeraRambauSantos},  or
 \item a Minkowski summand of a dilate of~$\polytope{P}$~\cite{Meyer,Shephard}.
\end{enumerate*}
The deformations of~$\polytope{P}$ form a polyhedral cone under dilation and Minkowski addition, called the \defn{deformation cone} of~$P$~\cite{Postnikov}.
Its interior is the \defn{type cone} of the normal fan of $\polytope{P}$~\cite{McMullen-typeCone}, and contains those polytopes with the same normal fan as~$\polytope{P}$. 
When~$\polytope{P}$ has rational vertex coordinates, then the type cone is known as the \defn{numerically effective cone} and encodes the embeddings of the associated toric variety into projective space~\cite{CoxLittleSchenck}.

There exist several methods to parametrize and describe the deformation cone of a given polytope (see \eg\cite[Appendix]{PostnikovReinerWilliams}), for example via the \defn{height deformation space} and the \defn{wall-crossing inequalities} or via the \defn{edge deformation space} and the \defn{polygonal face equations}.
However, these methods only provide redundant inequality descriptions 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 (\ie{}describing \defn{realizable fans} \cite[Chapter~9.5.3]{DeLoeraRambauSantos}), or a one dimensional type cone (\ie{}describing \defn{Minkowski indecomposable} polytopes~\cite{McMullen1987,Meyer,PreslawskiYost2016,Shephard}).

The search for irredundant facet descriptions of deformation cones of particular families of combinatorial polytopes has received considerable attention~\cite{ACEP-DeformationsCoxeterPermutahedra, CDGRY2020, CastilloLiu2020, PadrolPaluPilaudPlamondonFpsac2020, Postnikov}.
% One of the motivations sparking this interest arises from the \defn{amplituhedron program} to study scattering amplitudes in mathematical physics~\cite{ArkaniHamedTrnka-Amplituhedron}. As described in \cite[Section~1.4]{PadrolPaluPilaudPlamondonFpsac2020}, the deformation cone provides canonical realizations of a polytope %(seen as a \defn{positive geometry}~\cite{ArkaniHamedBaiLam-PositiveGeometries}) 
% in the positive region of the kinematic space, akin to those of the associahedron in~\cite{ArkaniHamedBaiHeYan}.
The most prominent example is certainly that of \defn{deformed permutahedra}.
The \defn{permutahedron}, defined as the convex hull of the $n!$ permutations of the vector $(1,2,\dots,n)\in \R^n$, is one of the most studied polytopes in geometric and algebraic combinatorics.
Deformed permutahedra were originally introduced under the name of \defn{polymatroids} by J.~Edmonds in~1970 as a polyhedral generalization of matroids in the context of linear optimization~\cite{Edmonds}.
They were rediscovered under the name of \defn{generalized permutahedra} by A.~Postnikov in~2009, who initiated the investigation of their rich combinatorial structure~\cite{Postnikov}.
They have since become a widely studied family of polytopes that appears naturally in several areas of mathematics, such as algebraic combinatorics~\cite{AguiarArdila, ArdilaBenedettiDoker, PostnikovReinerWilliams}, optimization~\cite{SubmodularFunctionsOptimization},  game theory~\cite{DanilovKoshevoy2000}, statistics~\cite{MortonPachterShiuSturmfelsWienand2009}, and economic theory~\cite{JoswigKlimmSpitz2021}.
The set of deformed permutahedra can be parametrized by the cone of \defn{submodular functions}~\cite{Edmonds,Postnikov}. 

The permutahedron can also be described as the graphical zonotope of the complete graph or as the nestohedron of the complete building set.
A \defn{graphical zonotope} is a Minkowski sum of edges of the standard simplex, and encodes several combinatorial properties of the associated graph~$G$. 
For example, its vertices are in bijection with the acyclic orientations of~$G$~\cite{Greene} and its volume is the number of spanning trees of~$G$~\mbox{\cite[Example~4.64]{StanleyEC1}}. 
A \defn{nestohedron} is a simple polytope realizing the nested complex of an arbitrary \defn{building set} (a hypergraph fulfilling certain connectivity condition), and is the Minkowski sum of the associated faces of the standard simplex~\cite{FeichtnerSturmfels,Postnikov,Zelevinsky}.
When the building set consists of all connected induced subgraphs of a graph~$G$, one gets the \defn{graph associahedron} of~$G$ defined in~\cite{CarrDevadoss} in connection to the wonderful arrangements~of~\cite{DeConciniProcesi}.

In this extended abstract, we study the deformation cones of arbitrary graphical zonotopes and nestohedra.
Since all these polytopes are deformed permutahedra, their deformation cones appear as particular faces of the submodular cone.
However, faces of the submodular cone are far from being well understood: determining its rays for instance remains an open problem since the 1970s~\cite{Edmonds}.
We provide complete irredundant descriptions of their deformation cones, derive their dimensions and characterize those which are simplicial.
We also obtain that the faces of the standard simplex contained in these deformation cones provide a linear basis of their vector span, generalizing~\cite{ArdilaBenedettiDoker}.
In contrast to our irredundant facet descriptions, this latter result easily extends to all \defn{hypergraphic polytopes}~\cite{AguiarArdila}, \ie{}the polytopes obtained as Minkowski sums of faces of the standard simplex (which include both graphical zonotopes and nestohedra).

%After some preliminaries on deformation cones of polytopes, we begin by describing the deformation cone of graphical zonotopes. Then, we describe the deformation cones of nestohedra. 
Note that the deformation cones of graph associahedra were determined in~\cite{PadrolPaluPilaudPlamondonFpsac2020}. This invited the investigation of arbitrary deformed nestohedra.
We thus include here a short description of the relevant results from~\cite{PadrolPaluPilaudPlamondonFpsac2020}, to which we oppose the situation of general nestohedra. 
We intend to highlight the complexity of the case of general nestohedra compared to the case of graph associahedra.

Details and proofs omitted in this extended abstract can be found in~\cite{PadrolPilaudPoullot-deformedNestohedra, PadrolPilaudPoullot-deformedGraphicalZonotopes}.

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

\section{Deformation cones of polytopes}

Let~$\polytope{P} \subseteq \R^d$ be a polytope
% \footnote{A \defn{polytope} is the convex hull of finitely many points in~$\R^d$.}
with normal fan
% \footnote{The \defn{normal cone} of a face~$\polytope{F}$ of a polytope~$\polytope{P}$ is the cone generated by the normal vectors of the facets of~$\polytope{P}$ containing~$\polytope{F}$. The \defn{normal fan} of~$\polytope{P}$ is the set of normal cones of all its faces.}
$\Fan$.
We consider the \defn{deformation cone}~$\deformationCone(\polytope{P})$ formed by all polytopes whose normal fans coarsen~$\Fan$ (alternative definitions were recalled in the introduction).
Note that~$\deformationCone(\polytope{P})$ is a closed convex cone (dilations and Minkowski sums preserve deformations) and contains a lineality subspace of dimension~$d$ (translations preserve deformations).
%It is the set of all polytopes whose normal fan coarsens the normal fan~$\Fan$ of~$\polytope{P}$.
%Its interior consists of all polytopes whose normal fan is~$\Fan$, and was called the \defn{type cone} of~$\Fan$ by McMullen~\cite{McMullen-typeCone}. 
Its interior, called the \defn{type cone} of~$\Fan$ by P.~McMullen~\cite{McMullen-typeCone}, consists of all polytopes whose normal fan is~$\Fan$.
Taking into account the lineality, we say that the deformation cone is \defn{simplicial} when its quotient modulo translations is simplicial, and we call \defn{rays} of~$\deformationCone(\polytope{P})$ the rays of its quotient modulo translations.
They are spanned by the Minkowski indecomposable deformations of~$\polytope{P}$ of dimension at least~$1$ (note that $0$-dimensional deformations account for the space of translations).

There are several linearly isomorphic presentations of the deformation cone~\cite{McMullen-typeCone, Meyer, PostnikovReinerWilliams}.
The following convenient formulation \cite[Proposition~3]{PilaudSantos-quotientopes} is adapted from the classical \defn{wall-crossing inequalities}~\cite[Lemma~2.1]{ChapotonFominZelevinsky}.
To deal with non-simple polytopes as well, it uses a simplicial refinement of the normal fan. If the refinement contains additional rays, then the type cone is embedded in a higher dimensional space, but these additional coordinates can just be projected out. We say that a fan~$\Fan$ is \defn{supported} on the set of vectors~$\b{S}$ if every cone of~$\Fan$ is spanned by a subset of~$\b{S}$.

\begin{proposition}
\label{prop:deformationConeNonSimplicial}
Let $\polytope{P} \subseteq \R^d$ be a polytope whose normal fan $\Fan$ is refined by the simplicial fan~$\Fan[G]$ supported on~$\b{S}$.
Then the deformation cone~$\deformationCone(\polytope{P})$ of~$\polytope{P}$ is the set of polytopes $\set{\b{x} \in \R^d}{\dotprod{\b{s}}{\b{x}} \le \b{h}_\b{s} \text{ for all } \b{s} \in \b{S}}$ for all~$\b{h}$ in the cone of~$\R^\b{S}$ defined by
\begin{compactenum}[(i)]
\item the equalities~$\sum_{\ray[s] \in \rays \cup \rays'} \coefficient[{\ray[s]}][\rays][\rays'] \, \b{h}_{\ray[s]} = 0$ for any adjacent maximal cones~$\R_{\ge0}\rays$ and~$\R_{\ge0}\rays'$ of~$\Fan[G]$ belonging to \textbf{the same} maximal cone of $\Fan$,
\item the inequalities~$\sum_{\ray[s] \in \rays \cup \rays'} \coefficient[{\ray[s]}][\rays][\rays'] \, \b{h}_{\ray[s]} \geq  0$ for any adjacent maximal cones~$\R_{\ge0}\rays$ and\,$\R_{\ge0}\rays'$ of~$\Fan[G]$ belonging to \textbf{distinct} maximal cones of $\Fan$,
\end{compactenum}
where
\(
\sum_{\b{s} \in \b{R} \cup \b{R}'} \coefficient[{\b{s}}][\b{R}][\b{R}'] \, \b{s} = \b{0}
\)
is the unique linear dependence with~${\coefficient[{\b{r}}][\b{R}][\b{R}'] + \coefficient[{\b{r}'}][\b{R}][\b{R}'] = 2}$ among the rays of two adjacent maximal cones~$\R_{\ge0}\b{R}$ and~$\R_{\ge0}\b{R}'$ of~$\Fan$ with~${\b{R} \! \ssm \! \{\b{r}\} = \b{R}' \! \ssm \! \{\b{r}'\}}$.
\end{proposition}

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

\section{Deformation cones of graphical zonotopes}
\label{sec:graphicalZonotopes}

\para{Graphical zonotopes}

Let $G \eqdef (V,E)$ be a graph with vertex set $V$ and edge set~$E$.
Let~$(\b{e}_v)_{v \in V}$ denote the canonical basis of~$\R^V$. 
The \defn{graphical arrangement}~$\gArr$ is the arrangement of the hyperplanes $\set{\b{x} \in \R^V}{\b{x}_u = \b{x}_v}$ for all edges ${\{u,v\} \in E}$. 
The \defn{graphical fan}~$\gFan$ is the fan whose cones are all the possible intersections of one of the sets $\set{\b{x} \in \R^V}{\b{x}_u \! = \! \b{x}_v}$, $\set{\b{x} \in \R^V}{\b{x}_u \! \ge \! \b{x}_v}$, or $\set{\b{x} \in \R^V}{\b{x}_u \! \le \! \b{x}_v}$ for each edge ${\{u,v\}\in E}$. 
The \defn{graphical zonotope}~$\gZono$ is the Minkowski sum~$\gZono \eqdef \sum_{(u,v) \in E} [\b{e}_u,\b{e}_v]$ of the line segments $[\b{e}_u,\b{e}_v] \subseteq \R^V$ for all edges ${\{u,v\}\in E}$.
The normal fan of~$\gZono$ is~$\gFan$.
%The graphical fan~$\gFan$ is the normal fan of the graphical zonotope~$\gZono$.
Note that the lineality space of~$\gFan$ is the subspace~$\cc$ of~$\R^V$ spanned by the characteristic vectors of the connected components of~$G$, and that~$\gZono$ lies in a subspace orthogonal to~$\cc$. 

%The following result is well-known. For example, it can be easily deduced from \cite[Proposition~2.5]{Stanley2007} or \cite{OrientedMatroids} (for the latter, see that the graphical matroid from Section~1.1 is realized by the graphical arrangement, and use the description of the cells of the arrangement in terms of covectors from Section~1.2(c)).

An \defn{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$. 
It corresponds to the cone $\opcone$ of~$\gFan$ defined by the inequalities $\b{x}_u \leq \b{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$ (hence, $\b{x}_u = \b{x}_v$ if $u,v$ are in the same part of~$\mu$).
In particular:
\begin{compactitem}
\item The maximal cones of~$\gFan$ are in bijection with the acyclic orientations of~$G$. % We denote by~$\orcone$ the maximal cone of~$\gFan$ associated to the acyclic orientation~$\omega$.
\item The minimal cones of $\gFan$ (\ie{}the rays of $\gFan/\cc$) are in bijection with the \defn{biconnected subsets} of~$G$, \ie{}non-empty connected subsets of~$V$ whose complements in their connected components are also non-empty and connected. 
\item The rays of $\gFan/\cc$ that belong to the cone~$C_{\mu,\omega}$ of an ordered partition~$(\mu,\omega)$ of~$G$ are the biconnected sets of~$G$ that contracted by~$\mu$ give rise to an upper set of~$\omega$.  
 \end{compactitem}
%
%\begin{example}\label{ex:complete}
When $G$ is the complete graph~$K_n$, the graphical fan is the \defn{braid fan}~$\braid$ and the graphical zonotope is the \defn{permutahedron}. 
In~$\braid$, the faces correspond to ordered partitions of~$[n]$, the rays to all proper subsets of~$[n]$, and the maximal cones to all permutations of~$[n]$.
%\end{example}

\para{Common simplicial refinement}

\enlargethispage{.4cm}
It is worth noting that most graphical zonotopes are not simple (they are simple only for chordful graphs, where every cycle induces a clique \cite[Proposition~5.2]{PostnikovReinerWilliams}). % and \cite[Remark~6.2]{Kim08}.
To describe the deformation cones of non-simple graphical zonotopes, we thus use a simplicial refinement common to all graphical fans.
This refining fan is obtained from the braid fan~$\braid[V]$ by cutting each region into two simplices as follows.
Associate to any subset $U \subseteq V$ the vector ${\ivector{U} \eqdef  \sum_{u \in U} \b{e}_u  - \sum_{v \notin  U} \b{e}_v}$ and consider the fan~$\sbraid[V]$ whose maximal cells are $\opcone[\sigma]^\varnothing \eqdef \cone\set{\ivector{U}}{U\subsetneq V\text{ upper set of }\sigma}$ and~$\opcone[\sigma]^V \eqdef \cone\set{\ivector{U}}{\varnothing\neq U\subseteq V\text{ upper set of }\sigma}$ for every total order~$\sigma$ of~$V$.
The fan~$\sbraid[V]$ is an essential complete simplicial fan in~$\R^V$ supported on the $2^{|V|}$ vectors~$\ivector{U}$ for ${U\subseteq V}$.
It has two types of pairs of adjacent maximal~cones:
\begin{compactitem}
\item the pairs~$\{\opcone[\sigma]^\varnothing, \opcone[\sigma]^V\}$ for any~$\sigma$, which yields the linear dependence~$\ivector{\varnothing} + \ivector{V} = \b{0}$,
\item the pairs~$\{\opcone[\sigma]^X, \opcone[\sigma']^X\}$ for any~$X \in \{\varnothing, V\}$ and any total orders~${\sigma  \! = \! PuvS}$ and ${\sigma' \! = \! PvuS}$ that differ in the inversion of two consecutive elements. The two rays that are not shared by~$\smash{\opcone[\sigma]^X}$ and~$\smash{\opcone[\sigma']^X}$ are $\smash{\ivector{S\cup \{u\}}}$ and $\smash{\ivector{S\cup \{v\}}}$, and the unique linear relation supported on the rays of~$\smash{\opcone[\sigma]^X\cup\opcone[\sigma']^X}$ is given by~$\smash{\ivector{S \cup \{u\}} + \ivector{S \cup \{v\}} = \ivector{S} + \ivector{S \cup \{u, v\}}}$.
\end{compactitem}
Moreover, the fan~$\sbraid[V]$ refines any graphical fan~$\gFan$: for any acyclic orientation~$\omega$ of~$G$, any total order~$\sigma$ on~$V$ and any~$X \in \{\varnothing, V\}$, we have~$\orcone[\sigma]^X\subseteq\orcone$ if and only if~$\sigma$ is a linear extension of~$\omega$.
Applying~\cref{prop:deformationConeNonSimplicial}, we obtain the following description~of~$\deformationCone(\gZono)$.

\begin{corollary}
\label{coro:deformationConeGraphZono}
The deformation cone~$\deformationCone(\gZono)$ of the graphical zonotope~$\gZono$ is the set of polytopes
\(
\set{\b{x} \in \R^V}{\sum_{u \in U} \b{x}_u - \sum_{v \notin U} \b{x}_v \le \b{h}_U \text{ for all } U \subseteq V}
%\bigset{\b{x} \in \R^V}{\dotprod{\ivector{U}}{\b{x}} \le \b{h}_U \text{ for all } U \subseteq V}
\)
for all~$\b{h}$ in the cone of~$\R^{2^V}$ defined by the following (possibly redundant) description:
\begin{compactitem}
\item $\b{h}_\varnothing=-\b{h}_{V}$,
\item $\b{h}_{S \cup \{u\}} + \b{h}_{S \cup \{v\}} = \b{h}_{S} + \b{h}_{S \cup \{u, v\}}$ for each~$\{u,v\} \notin E$ and~$S\subseteq V\ssm \{u,v\}$,
\item $\b{h}_{S \cup \{u\}} + \b{h}_{S \cup \{v\}} \geq \b{h}_{S} + \b{h}_{S \cup \{u, v\}}$ for each~$\{u,v\}\in E$ and~$S\subseteq V\ssm \{u,v\}$.
\end{compactitem}
\end{corollary}

\para{Irredundant description}

The description of the deformation cone of \cref{coro:deformationConeGraphZono} is highly redundant, both in the equations describing its linear span and in the inequalities describing its facets. 
Choosing a basis for the equations and discarding the irredundant inequalities, we obtain the following description, whose proof is the purpose of~\cite{PadrolPilaudPoullot-deformedGraphicalZonotopes}.
We denote by~$N(v) \eqdef \set{u\in V}{\{u,v\}\in E}$ the neighbors of a vertex~$v$ in~$G$.

\begin{theorem}
\label{thm:facetsDeformationConeGraphZono}
The deformation cone~$\deformationCone(\gZono)$ of the graphical zonotope~$\gZono$ is the set of polytopes
\(
\set{\b{x} \in \R^V}{\sum_{u \in U} \b{x}_u - \sum_{v \notin U} \b{x}_v \le \b{h}_U \text{ for all } U \subseteq V}
%\bigset{\b{x} \in \R^V}{\dotprod{\ivector{U}}{\b{x}} \le \b{h}_U \text{ for all } U \subseteq V}
\)
for all~$\b{h}$ in the cone of~$\smash{\R^{2^V}}$ defined by the following irredundant facet description:
\begin{compactitem}
\item $\b{h}_\varnothing=-\b{h}_{V}$,
\item $\b{h}_{S \ssm \{u\}} + \b{h}_{S \ssm \{v\}} = \b{h}_S + \b{h}_{S \ssm \{u, v\}}$ for each~$\varnothing\neq S\subseteq V$ and any%
\footnote{For any non-clique~$S$, only one missing edge is choosen (\eg{}the lexicographically smallest).}
$\{u,v\}\in \binom{S}{2}\ssm E$,
\item $\b{h}_{S \cup \{u\}} + \b{h}_{S \cup \{v\}} \geq  \b{h}_{S} + \b{h}_{S \cup \{u, v\}}$ for each~$\{u,v\}\in E$ and~$S \subseteq N(u) \cap N(v)$.
\end{compactitem}
\end{theorem}

\begin{example}
When $G$ is complete, $\deformationCone(\gZono)$ is a permutahedron and we recover the submodular cone given by the irredundant inequalities~${\b{h}_{S \cup \{u\}} + \b{h}_{S \cup \{v\}} \geq  \b{h}_{S} + \b{h}_{S \cup \{u, v\}}}$ for each~$\{u,v\}\subseteq S \subset V$. (The usual presentation imposes $\b{h}_\varnothing = 0$, but both presentations are clearly equivalent up to translation).

\end{example}

\begin{corollary}
\label{coro:basisDeformationConesGraphZono}
\hspace*{-.2cm}\footnote{This fact was proved independently by Raman Sanyal and Josephine Yu (personnal communication).}
The faces~$\simplex_K \eqdef \conv \set{\b{e}_v}{v \in K}$ of the standard simplex~$\simplex_V$ corresponding to the non-empty induced cliques~$K$ of~$G$ form a linear basis of the space spanned by~$\deformationCone(\gZono)$.
\end{corollary}

\begin{corollary}
\label{coro:numerologyDeformationConeGraphZono}
The dimension of~$\deformationCone(\gZono)$ is the number of induced cliques in~$G$, the dimension of the lineality space of~$\deformationCone(\gZono)$ is~$|V|$, and the number of facets of~$\deformationCone(\gZono)$ is the number of triplets~$(u,v,S)$ with~$\{u,v\} \in E$ and~$S \subseteq N(u) \cap N(v)$.
\end{corollary}

\begin{example}
If~$G = K_V$ is complete, $\deformationCone(\gZono[K_V])$ has dimension~$2^{|V|}-1$ and $\binom{|V|}{2} 2^{|V|-2}$ facets.
If~$G$ is triangle-free, $\deformationCone(\gZono)$ has dimension~$|V|+|E|$ and~$|E|$ facets.
%In both cases, the lineality is $|V|$-dimensional, given by the space of translations in~$\R^{|V|}$.
\end{example}

\begin{corollary}
\label{cor:simplicialDeformationConeGraphZono}
The deformation cone~$\deformationCone(\gZono)$ is simplicial (modulo its lineality) if and only if $G$ is triangle-free.
In that case, every deformation of $\gZono$ is a zonotope, which is the graphical zonotope of a subgraph of~$G$ up to rescaling of the generators.
\end{corollary}

%\begin{corollary}
%If $G$ is triangle-free, then every deformation of $\gZono$ is a zonotope, which is the graphical zonotope of a subgraph of~$G$ up to rescaling of the generators.
%\end{corollary}

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

\section{Deformation cones of nestohedra}

%\subsection{Deformation cones of graph associahedra}
%\label{subsec:graphAssociahedra}

\para{Graph associahedra}

\enlargethispage{.2cm}
We recall the description of~\cite{PadrolPaluPilaudPlamondonFpsac2020} for graph associahedra as a prototype for nestohedra.
For coherence with \cref{sec:graphicalZonotopes}, we consider graph associahedra and nestohedra embedded in the ambient space~$\R^V$ instead of their affine spans.

Let $G \eqdef (V,E)$ be a graph.
A \defn{tube} of~$G$ is subset of~$V$ which induces a connected subgraph of~$G$.
Let~$\tubes$ denote the set of tubes of~$G$.
The $\subseteq$-maximal tubes of~$G$ are its connected components~$\connectedComponents(G)$.
Let~$\bConnectedComponents(G) \eqdef \{\varnothing\} \cup \connectedComponents(G)$.
%The tubes which are neither empty nor maximal are called \defn{proper}.
Two tubes~$\tube, \tube'$ of~$G$~are \defn{compatible} if they are nested (\ie$\tube \subseteq \tube'$ or~$\tube' \subseteq \tube$), or disjoint and non-adjacent (\ie${\tube \cup \tube'}$ is not a tube of~$G$).
A \defn{tubing} on~$G$ is a set~$\tubing$ of pairwise compatible tubes of~$G$ containing~$\bConnectedComponents(G)$.

%Let~$(\b{e}_v)_{v \in V}$ denote the canonical basis of~$\R^V$.
Define~$\gvector{U} \eqdef \sum_{u \in U} \b{e}_u$ for~$\varnothing \ne U \subseteq V$ and~${\gvector{\varnothing} \eqdef -\sum_{v \in V} \b{e}_v}$.
%Let~${\gvector{\varnothing} \eqdef -\sum_{v \in V} \b{e}_v}$, let ${\gvector{\tube} \eqdef \sum_{v \in \tube} \b{e}_v}$ for~$\tube \in \connectedComponents(G)$, and let~$\gvector{\tube}$ be the orthogonal projection of~$ \sum_{v \in \tube} \b{e}_v$ on the subspace~$\set{\b{x} \in \R^V}{\sum_{v \in K} x_v = 0 \text{ for all } K \in \connectedComponents(G)}$ for~${\tube \notin \bConnectedComponents(G)}$.
The \defn{nested fan}~$\nFan$ is the fan with a cone generated by~$\set{\gvector{\tube}}{\tube \in \tubing}$ for each tubing~$\tubing$ of~$G$.
Note that $\nFan$ is the direct sum of a simplicial fan with the space spanned by~$\gvector{\tube}$ for~${\tube \in \bConnectedComponents(G)}$.
We obtain a simplicial refinement by spliting each maximal cone into $|\bConnectedComponents(G)|$ simplicial cones, in a similar way as in \cref{sec:graphicalZonotopes}. 
%We refine this linear space with the triangulation supported by the vectors~$\gvector{\tube}$ for~${\tube \in \bConnectedComponents(G)}$. % as in \cref{sec:graphicalZonotopes}.
%Note that as in \cref{sec:graphicalZonotopes}, the fan $\nFan$ is not simplicial but we can obtain a simplicial refinement using the vectors~$\ivector{\tube}$ for~$\tube \in \bConnectedComponents(G)$, which span the lineality space of~$\nFan$.
The \defn{graph associahedron}~$\Asso$ is the Minkowski sum~$\Asso \eqdef \sum_{\tube \in \tubes \ssm \{\varnothing\}} \simplex_{\tube}$, see~\mbox{\cite{CarrDevadoss, Postnikov}}.
%The nested fan~$\nFan$ is the normal fan of the graph associahedron~$\Asso$.
The normal fan of~$\Asso$ is~$\nFan$.
The next statement describes the adjacent maximal cones of~$\nFan$ and their linear dependences.

\begin{proposition}
\label{prop:exchangeRelationsGraphAsso}
Let~$\tube, \tube'$ be two tubes of~$G$.
\begin{compactenum}[(i)]
\item There exist two maximal tubings~$\tubing, \tubing'$ on~$G$ with ${\tubing \ssm \{\tube\} = \tubing' \ssm \{\tube'\}}$ if and only if $\tube'$ has a unique neighbor~$v$ in~$\tube \ssm \tube'$ and $\tube$ has a unique neighbor~$v'$ in~$\tube' \ssm \tube$.
\item For any maximal tubings~$\tubing, \tubing'$ on~$G$ with $\tubing \ssm \{\tube\} = \tubing' \ssm \{\tube'\}$, both~$\tubing$ and~$\tubing'$ contain the tube~$\tube \cup \tube'$ and the connected components~$\connectedComponents(\tube \cap \tube')$ of~$\tube \cap \tube'$.
\item For any maximal tubings~$\tubing, \tubing'$ on~$G$ with $\tubing \ssm \{\tube\} = \tubing' \ssm \{\tube'\}$, the unique (up to rescaling) linear dependence among~$\set{\gvector{\tube}}{\tube \in (\tubing \cup \tubing') \ssm \bConnectedComponents(G)}$ is~${\gvector{\tube} + \gvector{\tube'} = \gvector{\tube \cup \tube'} + \sum_{\tube[s] \in \connectedComponents(\tube \cap \tube')} \gvector{\tube[s]}}$.
\end{compactenum}
\end{proposition}

From \cref{prop:deformationConeNonSimplicial,prop:exchangeRelationsGraphAsso}, we derive a redundant description of the deformation cone~$\deformationCone(\Asso)$, with one inequality for each pair of exchangeable tubes.
Deleting redundant inequalities, we obtain the following description.

\begin{theorem}
\label{thm:facetsDeformationConeGraphAsso}
The deformation cone~$\deformationCone(\Asso)$ of the graph associahedron~$\Asso$ is the set of polytopes
\(
\set{\b{x} \in \R^V}{-\sum_{v \in V} \b{x}_v \le \b{h}_\varnothing \text{ and } \sum_{v \in \tube} \b{x}_v \le \b{h}_{\tube} \text{ for all } \tube \in \tubes \ssm \{\varnothing\}}
%\bigset{\b{x} \in \R^V}{\dotprod{\gvector{\tube}}{\b{x}} \le \b{h}_{\tube} \text{ for all } \tube \in \tubes}
\)
for all~$\b{h}$ in the cone of~$\R^{\tubes}$ defined by the following irredundant description:
\begin{compactitem}
\item $\sum_{K \in \bConnectedComponents(G)} \b{h}_K = 0$ (where~$\bConnectedComponents(G)$ contains all connected components of~$G$ and~$\varnothing$),
\item $\b{h}_{\tube} + \b{h}_{\tube'} \ge \b{h}_{\tube \cup \tube'} + \sum_{\tube[s] \in \connectedComponents(\tube \cap \tube')} \b{h}_{\tube[s]}$ for any tubes~$\tube, \tube'$ of~$G$ such that~$\tube \ssm \{v\} = \tube' \ssm \{v'\}$ for some neighbor~$v$ of~$\tube'$ in~$\tube \ssm \tube'$ and some neighbor~$v'$ of~$\tube$ in~$\tube' \ssm \tube$.
\end{compactitem}
\end{theorem}

\begin{example}
When~$G$ is complete, $\Asso$ is the permutahedron and the facets of~$\deformationCone(\Asso)$ are $\b{h}_{U \ssm \{v\}} + \b{h}_{U \ssm \{v'\}} \ge \b{h}_{U} + \b{h}_{U \ssm \{v,v'\}}$ for~$\{v,v'\} \subseteq U \subseteq V$.
When~$G$ is a path, $\Asso$ is the associahedron and the facets of~$\deformationCone(\Asso)$ are $\b{h}_{[i,j-1]} + \b{h}_{[i+1,j]} \ge \b{h}_{[i,j]} + \b{h}_{[i+1,j-1]}$ for~$i < j$.
\end{example}

%\begin{example}
%For instance, the facets of the deformation cone~$\deformationCone(\Asso)$ are defined by
%\begin{compactitem}
%\item $\b{h}_{U \ssm \{v\}} + \b{h}_{U \ssm \{v'\}} \ge \b{h}_{U} + \b{h}_{U \ssm \{v,v'\}}$ for~$\{v,v'\} \subseteq U \subseteq V$ when~$G$ is complete,
%\item $\b{h}_{[i,j-1]} + \b{h}_{[i+1,j]} \ge \b{h}_{[i,j]} + \b{h}_{[i+1,j-1]}$ for~$1 \le i < j \le n$ when~$G$ is the path.
%\end{compactitem}
%\end{example}

%Equivalently, $\deformationCone(\Asso)$ has one facet for each pair~$\{\tube, \tube'\}$ such that $\tube = \tube[s] \ssm \{v'\}$ and $\tube' = \tube[s] \ssm \{v\}$ for some tube~$\tube[s]$ of~$G$ and some distinct non-disconnecting vertices~$v, v'$~of~$\tube[s]$.

\begin{corollary}
\label{coro:numberFacetsDeformationConeGraphAsso}
The deformation cone~$\deformationCone(\Asso)$ has~$\sum_{\tube[s] \in \tubes} \binom{\nonDisconnecting(\tube[s])}{2}$ facets, where~$\nonDisconnecting(\tube[s])$ denotes the number of non-disconnecting vertices of~$\tube[s]$.
\end{corollary}

\begin{corollary}
\label{coro:simplicialDeformationConeGraphAsso}
The deformation cone~$\deformationCone(\Asso)$ is simplicial if and only if~$G$ is a union of paths.
\end{corollary}

%%%%%%%%%%%%%%%
%
%\subsection{Deformation cones of nestohedra}
%\label{subsec:nestohedra}

\para{Nestohedra}

A \defn{building set}~$\building$ on~$V$ is a set of subsets of~$V$ such that
\begin{compactitem}
\item if~$B,B' \in \building$ and~$B \cap B' \ne \varnothing$, then~$B \cup B' \in \building$, and
\item $\building$ contains~$\varnothing$ and all singletons~$\{v\}$ for~$v \in V$.
\end{compactitem} 
Let~$\connectedComponents(\building)$ denote the \defn{connected components} of~$\building$ (\ie{}the $\subseteq$-maximal elements of~$\building$), let $\bConnectedComponents(G) \eqdef \{\varnothing\} \cup \connectedComponents(G)$, and let~$\elementary(\building)$ denote the \defn{elementary blocks} of~$\building$ (\ie{}the blocks~$B \in \building$ such that~$|B| > 1$, and $B = B' \cup B''$ implies~$B' \cap B'' = \varnothing$ for any~$B', B'' \in \building \ssm \{B\}$).
For example, $\connectedComponents(\building_\circ) = \{123456, 789\}$ and $\elementary(\building_\circ) = \{14, 25, 123, 456, 789\}$ for the building set
\(
\building_\circ \eqdef \{1, 2, 3, 4, 5, 6, 7, 8, 9, 14, 25, 123, 456, 789, 1234, 1235, 1456, 2456, 12345, 12456, 123456\}
\)
\linebreak
on~$[9]$ (we abuse notation and write $123$ for $\{1,2,3\}$).
See \cref{fig:exmNested}\,(left).

Given a building set~$\building$, a \defn{$\building$-nested set}~$\nested$ is a subset of~$\building$ such that
\begin{compactitem}
\item for any~$B,B' \in \nested$, either~$B \subseteq B'$ or~$B' \subseteq B$ or~$B \cap B' = \varnothing$,
\item for any~$k \ge 2$ pairwise disjoint~$B_1,\dots,B_k \in \nested$, the union~$B_1 \cup \dots \cup B_k$ is not in~$\building$,
\item $\nested$ contains~$\bConnectedComponents(\building)$.
\end{compactitem}
For instance, the two maximal $\building_\circ$-nested sets $\nested_\circ \eqdef \{3, 4, 5, 7, 8, 14, 789, 12345, 123456\}$ and~$\nested'_\circ \eqdef \{3, 4, 5, 7, 8, 25, 789, 12345, 123456\}$ are represented in \cref{fig:exmNested}\,(middle).

\begin{figure}[b]
	\centerline{\includegraphics[scale=.9]{exmNested}}
	\caption{The elementary blocks of a building set~$\building_\circ$ (left), the two adjacent maximal $\building_\circ$-nested sets~$\nested_\circ$ and~$\nested_\circ'$ (middle), and the corresponding exchange frame (right).}
	\label{fig:exmNested}
\end{figure}

Define~$\gvector{U} \eqdef \sum_{u \in U} \b{e}_u$ for~$\varnothing \ne U \subseteq V$ and~${\gvector{\varnothing} \eqdef -\sum_{v \in V} \b{e}_v}$.
%Let~${\gvector{\varnothing} \eqdef -\sum_{v \in V} \b{e}_v}$, let ${\gvector{B} \eqdef \sum_{v \in B} \b{e}_v}$ for~$B \in \connectedComponents(\building)$, and let~$\gvector{B}$ be the orthogonal projection of~$\sum_{v \in B} \b{e}_v$ on the subspace~$\set{\b{x} \in \R^V}{\sum_{v \in K} x_v = 0 \text{ for all } K \in \connectedComponents(\building)}$ for~${B \notin \bConnectedComponents(\building)}$.
The \defn{nested fan}~$\nFan[\building]$ is the fan with a cone generated by~$\set{\gvector{B}}{B \in \nested}$ for each $\building$-nested set~$\nested$.
As before, $\nFan[\building]$ is the direct sum of a simplicial fan with a linear space, and we obtain a simplicial refinement by triangulating the lineality, which is spanned by~$\gvector{B}$ for~${B \in \bConnectedComponents(\building)}$.
% We obtain a simplicial refinement by spliting the maximal cones as before.
% each maximal cone into $|\bConnectedComponents(G)|$ simplicial cones, in a similar way as in \cref{sec:graphicalZonotopes}. 
%We refine this linear space with the triangulation supported by the vectors~$\gvector{B}$ for~$B \in \bConnectedComponents(\building)$.
%Note that as in \cref{sec:graphicalZonotopes}, the fan $\nFan[\building]$ is not simplicial but we can obtain a simplicial refinement using the vectors~$\ivector{B}$ for~$B \in \bConnectedComponents(\building)$, which span the lineality space of~$\nFan[\building]$.
The \defn{nestohedron}~$\Nest$ is the Minkowski sum~$\Nest \eqdef \sum_{B \in \building \ssm \{\varnothing\}} \simplex_B$, see~\cite{FeichtnerSturmfels, Postnikov, Zelevinsky}.
%The nested fan~$\nFan[\building]$ is the normal fan of the nestohedron~$\Nest$.
The normal fan of~$\Nest$ is~$\nFan[\building]$.

\begin{example}
For a graph~$G$, the tubes of~$G$ form a building set~$\building_G$, the tubings of~$G$ are the $\building_G$-nested sets, and the graph associahedron~$\Asso$ is the nestohedron~$\smash{\Nest[\building_G]}$.
%Our goal is to extend \cref{thm:facetsDeformationConeGraphAsso} to describe the deformation cone~$\deformationCone(\Nest)$ for any building~set~$\building$.
\end{example}

\para{Exchange frames and exchange relations}

\!We now describe the adjacent maximal~cones of the nested fan~$\nFan[\building]$ and their linear dependences to derive a first redundant description of $\deformationCone(\Nest)$ by \cref{prop:deformationConeNonSimplicial}.
\mbox{We start with a simple observation, see \cref{fig:exmNested}\,(right).}

\begin{proposition}
\label{prop:parentNesto}
If~$\nested$ and~$\nested'$ are two maximal $\building$-nested sets with~$\nested \ssm \{B\} = \nested \ssm \{B'\}$, then $\set{C \in \nested}{B \subsetneq C}$ and~$\set{C' \in \nested'}{B' \subsetneq C'}$ coincide and admit a unique $\subseteq$-minimal element~$P$.
We say that $P$ is the \defn{parent} and that~$(B, B', P)$ is the \defn{frame} of the exchange between~$\nested$ and~$\nested'$.
\end{proposition}

Our next statement is the analogue of \cref{prop:exchangeRelationsGraphAsso}.
Even if the linear dependences of~(iii) were studied in~\cite{Zelevinsky}, the characterization of~(i) for the exchangeable blocks was surprisingly missing in the literature to the best of our knowledge.
Note that, in contrast to the graphical case, the linear dependence of~(iii) does not only depend on the two exchanged blocks, but also on the exchange frame.

\begin{proposition}
\label{prop:exchangeRelationsNesto}
Let~$B, B' \in \building$ be two blocks of~$\building$.
\begin{compactenum}[(i)]
\item There exist two maximal $\building$-nested sets~$\nested, \nested'$ with~$\nested \ssm \{B\} = \nested' \ssm \{B'\}$ if and only if there exist a block~$P \in \building$, and some vertices~$v \in B \ssm B'$ and~$v' \in B' \ssm B$ such that
\begin{compactitem}
\item $B \subsetneq P$ and~$B' \subsetneq P$, and
\item $v' \in C$ for any~$C \subseteq P$ such that~$B \cap C \ne \varnothing$ but~$C \not\subseteq B$, while $v \in C'$ for any~$C' \subseteq P$ such that~$B' \cap C' \ne \varnothing$ but~$C' \not\subseteq B'$.
%\item $v' \in C$ for any~$\leaving{B}{C}{P}$ while $v \in C'$ for any~$\leaving{B'}{C'}{P}$, where we use the notation $\leaving{B}{C}{P}$ to abbreviate the conditions~$B \cap C \ne \varnothing$ and $C \subseteq P$ but~$C \not\subseteq B$.
\end{compactitem}

\item For two maximal $\building$-nested sets~$\nested$ and~$\nested'$ with~$\nested \ssm \{B\} = \nested' \ssm \{B'\}$ and parent~$P$, all connected components of~$\connectedComponents(B \cap B')$ and of~$\connectedComponents \big(P \ssm (B \cup B'))$ belong to~$\nested \cap \nested'$.

\item For two maximal $\building$-nested sets~$\nested$ and~$\nested'$ with~$\nested \ssm \{B\} = \nested' \ssm \{B'\}$ and parent~$P$, the unique (up to rescaling) linear dependence among~$\set{\gvector{\tube}}{\tube \in (\nested \cup \nested') \ssm \bConnectedComponents(\building)}$ is
\[
\gvector{B} + \gvector{B'} + \sum_{K \in \connectedComponents(P \ssm (B \cup B'))} \gvector{K} = \gvector{P} + \sum_{K \in \connectedComponents(B \cap B')} \gvector{K}.
\]
In particular, the linear dependence only depends on the exchange frame~$(B,B',P)$.
\end{compactenum}
\end{proposition}

From \cref{prop:deformationConeNonSimplicial,prop:exchangeRelationsNesto}, we directly derive the following redundant description of the deformation cone~$\deformationCone(\Nest)$, with one inequality for each exchange frame.

\begin{corollary}
\label{coro:deformationConeNesto}
The deformation cone~$\deformationCone(\Nest)$ of the nestohedron~$\Nest$ is the set of polytopes
\(
\set{\b{x} \in \R^V}{-\sum_{v \in V} \b{x}_v \le \b{h}_\varnothing \text{ and } \sum_{v \in B} \b{x}_v \le \b{h}_B \text{ for all } B \in \building \ssm \{\varnothing\}}
%\bigset{\b{x} \in \R^V}{\dotprod{\gvector{B}}{\b{x}} \le \b{h}_B \text{ for all } B \in \building}
\)
for all~$\b{h}$ in the cone \linebreak of~$\R^\building$ defined by the following (possibly redundant) description:
\begin{compactitem}
\item $\sum_{K \in \bConnectedComponents(\building)} \b{h}_K = 0$ (where~$\bConnectedComponents(\building)$ contains all connected components of~$\building$ and~$\varnothing$),
\item $\b{h}_B + \b{h}_{B'} + \sum_{K \in \connectedComponents(P \ssm (B \cup B'))} \b{h}_K \ge \b{h}_P + \sum_{K \in \connectedComponents(B \cap B')} \b{h}_K$ for any exchange frame~$(B, B', P)$.
\end{compactitem}
\end{corollary}

\para{Irredundant description}
We now need to characterize the facet defining inequalities among the inequalities of \cref{coro:deformationConeNesto}.
This is the main difficulty of \cite{PadrolPilaudPoullot-deformedNestohedra}.
We denote by~$\maximalBlocks(P)$ the $\subseteq$-maximal blocks of~$\building$ strictly contained in a block~$P \in \building$.

\begin{proposition}
\label{prop:maximalExchanges}
$(B, B', P)$ is an exchange frame for any~$P \in \building$ and any~$B \ne B'$ in~$\maximalBlocks(P)$. %, which is called \defn{maximal}.
\end{proposition}

\begin{proposition}
\label{prop:maximalExtremal}
The exchange frames corresponding to facet defining inequalities of~$\deformationCone(\Nest)$ in \cref{coro:deformationConeNesto} are precisely the exchange frames of \cref{prop:maximalExchanges}.
\end{proposition}

This enables us to delete all inequalities of~\cref{coro:deformationConeNesto} which do not correspond to exchange frames of \cref{prop:maximalExchanges}.
However, it may happen that some different exchange frames of \cref{prop:maximalExchanges} still lead to the same inequality.
This problem is controled by the following statement.

\begin{proposition}
\label{prop:mutualizedExchange}
For an elementary block~$P \in \elementary(\building)$, all exchange frames~$(B, B', P)$ for~${B \ne B'}$ in~$\maximalBlocks(P)$ lead to the same linear dependence~$\sum_{B \in \maximalBlocks(P)} \gvector{B} = \gvector{P}$.
Conversely, if~$(B_1, B'_1, P)$ and $(B_2, B'_2, P)$ are two distinct exchange frames with~$B_1, B_2, B_1', B_2' \in \maximalBlocks(P)$ and the same linear dependence, then $P$ is elementary.
\end{proposition}

Finally, we obtain an irredundant description of~$\deformationCone(\Nest)$ extending \cref{thm:facetsDeformationConeGraphAsso}.

\begin{theorem}
\label{thm:facetsDeformationConeNesto}
The deformation cone~$\deformationCone(\Nest)$ of the nestohedron~$\Nest$ is the set of polytopes
\(
\set{\b{x} \in \R^V}{-\sum_{v \in V} \b{x}_v \le \b{h}_\varnothing \text{ and } \sum_{v \in B} \b{x}_v \le \b{h}_B \text{ for all } B \in \building \ssm \{\varnothing\}}
%\bigset{\b{x} \in \R^V}{\dotprod{\gvector{B}}{\b{x}} \le \b{h}_B \text{ for all } B \in \building}
\)
for all~$\b{h}$ in the cone \linebreak of~$\R^\building$ defined by the following irredundant description:
\begin{compactitem}
\item $\sum_{K \in \bConnectedComponents(\building)} \b{h}_K = 0$ (where~$\bConnectedComponents(\building)$ contains all connected components of~$\building$ and~$\varnothing$),
\item $\sum_{B \in\maximalBlocks(P)} \b{h}_{B} \ge \b{h}_P$ for any elementary block~$P$ of~$\building$,
\item $\b{h}_B + \b{h}_{B'} + \sum_{K \in \connectedComponents(P \ssm (B \cup B'))} \b{h}_K \ge \b{h}_P + \sum_{K \in \connectedComponents(B \cap B')} \b{h}_K$ for any block~$P$ of~$\building$ neither singleton nor elementary, and any two blocks~$B \ne B'$ in~$\maximalBlocks(P)$.
\end{compactitem}
\end{theorem}

\begin{corollary}
\label{coro:basisDeformationConesNesto}
The faces~$\simplex_B \eqdef \conv \set{\b{e}_v}{v \in B}$ of the standard simplex~$\simplex_V$ corresponding to the non-empty blocks~$B$ of~$\building$ form a linear basis of the vector space spanned by~$\deformationCone(\Nest)$.
\end{corollary}

\begin{corollary}
\label{coro:numberFacetsDeformationConeNesto}
The number of facets of the deformation cone~$\deformationCone(\Nest)$ is
\(
|\elementary(\building)| + \sum_P \binom{\maximalBlocks(P)}{2}
\)
where the sum runs over all blocks~$P$ of~$\building$ which are neither empty, nor singletons, nor elementary.
\end{corollary}

%\para{Simplicial deformation cones}
%Finally, we derive from \cref{coro:numberFacetsDeformationConeNesto} a characterization of the building sets~$\building$ for which the deformation cone~$\deformationCone(\Nest)$ is simplicial.

\begin{corollary}
\label{coro:simplicialDeformationConeNesto}
The deformation cone~$\deformationCone(\Nest)$ is simplicial if and only if all blocks of~$\building$ with at least three distinct maximal strict subblocks are elementary.
\end{corollary}

\begin{example}
An \defn{interval building set} is a building set on~$[n] \eqdef \{1, \dots, n\}$ whose blocks are intervals.
%We call \defn{interval nested fan} and \defn{interval nestohedron} the nested fan and nestohedron of an interval building set.
There are two relevant examples of nestohedra of interval building sets:
\begin{compactitem}
\item the classical associahedron of~\cite{Loday} for the building set with all intervals of~$[n]$,
\item the Pitman-Stanley polytope of~\cite{PitmanStanley} for the building set with all singletons~$\{i\}$ and all intervals~$[i]$~for~${i \in [n]}$.
\end{compactitem}
It is not difficult to derive from \cref{coro:simplicialDeformationConeNesto} that the deformation cone~$\deformationCone(\Nest)$ is simplicial for any interval building set~$\building$.
\end{example}

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

\section{Deformation cones of hypergraphic polytopes}
\label{sec:hypergraphicalPolytopes}

\para{Hypergraphic polytopes}

A \defn{hypergraph} on the set~$V$ is a collection~$H$ of subsets of~$V$ such that~$|U|\geq 2$ for each $U\in H$. The \defn{hypergraphic polytope}~$\hypPol$ is the Minkowski sum~$\hypPol \eqdef \sum_{U\in H}\simplex_U$ of the faces~$\simplex_U \eqdef \conv \set{\b{e}_u}{u \in U}$ of the standard simplex~$\simplex_V$ corresponding to its elements~\cite{AguiarArdila}.
The faces of~$\hypPol$ are in correspondence with the acyclic orientations of~$H$~\cite{BenedettiBergeronMachacek}.
Its normal fan is the \defn{hypergraphic fan}~$\hypFan$ whose cones are all possible intersections of faces of the cones $\polytope{C}_u(U) \eqdef \set{\b{x} \in \R^V}{\b{x}_v \leq  \b{x}_u\text{ for }v\in U}$ for $u\in U\in H$.
% The faces of hypergraphic polytopes were described in~\cite{BenedettiBergeronMachacek} in terms of acyclic orientations of hypergraphs.

\begin{example}
All graphical zonotopes, graph associahedra, and nestohedra are hypergraphic polytopes.
\end{example}

\para{Redundant description}

We now give a redundant description of the deformation cone~$\deformationCone(\hypPol)$ using the simplicial refinement of the hypergraphic fan~$\hypFan$ given by the fan~$\sbraid[V]$ of \cref{sec:graphicalZonotopes}. 
Note that the cones $\{\opcone[\sigma]^X, \opcone[\sigma']^X\}$ for $\sigma=PuvS$, $\sigma'=PvuS$, and $X \in \{\varnothing, V\}$ belong in the same cell of~$\hypFan$ if and only if they lie in the same cell of the normal fan of $\simplex_U$ for all $U\in H$, that is, if there is no $U\in H$ such that $\{u,v\}\subseteq U\subseteq P\cup \{u,v\}$.
\cref{prop:deformationConeNonSimplicial} thus gives the following description of~$\deformationCone(\hypPol)$.


\begin{corollary}
\label{coro:deformationConeHypergraphPoly}
The deformation cone~$\deformationCone(\hypPol)$ of the hypergraphic polytope~$\hypPol$ is the set of polytopes
\(
\bigset{\b{x} \in \R^V}{\sum_{u \in U} \b{x}_u - \sum_{v \notin U} \b{x}_v \le \b{h}_U \text{ for all } U \subseteq V}
%\bigset{\b{x} \in \R^V}{\dotprod{\ivector{U}}{\b{x}} \le \b{h}_U \text{ for all } U \subseteq V}
\)
for all~$\b{h}$ in the cone of~$\R^{2^V}$ defined by the following (possibly redundant) description:
\begin{compactitem}
\item $\b{h}_\varnothing=-\b{h}_{V}$,
% \item for each $\{u,v\}\in \binom{V}{2}$ and~$S\subseteq V\ssm \{u,v\}$:
% \begin{compactitem}
% \item $\b{h}_{S \cup \{u\}} + \b{h}_{S \cup \{v\}} = \b{h}_{S} + \b{h}_{S \cup \{u, v\}}$ if there is no $U\in H$ such that $\{u,v\}\subseteq X\subseteq P\cup\{u,v\}$, and
% \item $\b{h}_{S \cup \{u\}} + \b{h}_{S \cup \{v\}} \geq \b{h}_{S} + \b{h}_{S \cup \{u, v\}}$ if there is some $U\in H$ such that $\{u,v\}\subseteq X\subseteq P\cup\{u,v\}$.
% \end{compactitem}
\item $\b{h}_{S \cup \{u\}} + \b{h}_{S \cup \{v\}} = \b{h}_{S} + \b{h}_{S \cup \{u, v\}}$ for each $S\subseteq V$ and each~$\{u,v\} \subseteq V \ssm S$ such that ${U \notin H}$ for any~$\{u,v\} \subseteq U \subseteq V \ssm S$,
\item $\b{h}_{S \cup \{u\}} + \b{h}_{S \cup \{v\}} \geq \b{h}_{S} + \b{h}_{S \cup \{u, v\}}$ for each $\{u,v\} \subseteq U \in H$ and~$S \subseteq V \ssm U$.
\end{compactitem}
\end{corollary}

Again, the description of \cref{coro:deformationConeHypergraphPoly} is highly redundant, both in the equations describing its linear span and in the inequalities describing its facets. 
To obtain irredundant descriptions, we benefited from a precise understanding of the combinatorics of the acyclic orientations of graphs in \cref{thm:facetsDeformationConeGraphZono} and of the nested complex in \cref{thm:facetsDeformationConeNesto}.

\para{Dimension and linear basis}

While we have not found the irredundant facet description of~$\deformationCone(\hypPol)$ yet, we do have independent equations for its linear span. To conclude, we determine the dimension, independent equations, and a linear basis for the linear span of the deformation cone~$\deformationCone(\hypPol)$ generalizing \cref{coro:basisDeformationConesNesto,coro:basisDeformationConesGraphZono}.
%
We say that~$K \subseteq V$ is an \defn{induced clique} of~$H$ if for every $u,v \in K$ there is some $U\in H$ with $\{u,v\}\subseteq U\subseteq K$. 

\begin{theorem}
\label{thm:equationsDeformationConeHypergraphPoly}
The linear span of the deformation cone~$\deformationCone(\hypPol)$ of the hypergraphic polytope~$\hypPol$ is given by the following independent equations:
\begin{compactitem}
\item $\b{h}_{\varnothing}=-\b{h}_{V}$,
\item $\b{h}_{S \cup \{u\}} + \b{h}_{S \cup \{v\}} = \b{h}_{S} + \b{h}_{S \cup \{u, v\}}$ for each~$\varnothing\neq S\subseteq V$ such that $V\ssm S$ does not induce a clique and any%
\footnote{Only one such pair $\{u,v\}$ for each non-clique is chosen; for example, the lexicographically smallest.}
$u,v\in V\ssm S$ such that $U \notin H$ for any~$\{u,v\} \subseteq U \subseteq V\ssm S$.
\end{compactitem}
\end{theorem}

F.~Ardila, C.~Benedetti and J.~Doker proved in~\cite{ArdilaBenedettiDoker} that the faces of the standard simplex form a basis of the space of deformed permutahedra.
This basis is actually compatible with the hypergraph polytopes in the following sense.

\begin{corollary}
\label{cor:basisDeformationConesHypergraphPoly}
The faces~$\simplex_K$ of the standard simplex~$\simplex_V$ corresponding to the non-empty induced cliques~$K$ of~$H$ form a linear basis of the vector space spanned by~$\deformationCone(\hypPol)$.
\end{corollary}

\begin{corollary}
\label{coro:basisDeformationConesHypergraphPoly}
The dimension of the deformation cone~$\deformationCone(\hypPol)$ is the number of non-empty induced cliques~$K$ of~$H$.
\end{corollary}

%\begin{remark}
%Another basis has this property: the shard polytopes. Not sure we want to mention it.
%\end{remark}

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

\newpage
\acknowledgements{

\cref{thm:facetsDeformationConeGraphAsso} appeared in a joint work~\cite{PadrolPaluPilaudPlamondonFpsac2020} with Yann Palu and Pierre-Guy Plamondon who we thank for many interesting discussions on deformation cones of cluster associahedra.
We are grateful to Raman Sanyal for letting us know about his proof of \cref{coro:numerologyDeformationConeGraphZono} with Josephine Yu, as well as for many helpful discussions on the topic.
}

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

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography



\end{document}
