%% 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[finalversion]{FPSAC2024}
\articlenumber{28}
%% 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}

% 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]

\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}

\usepackage{xargs}
\usepackage{hypcap}
\usepackage{paralist}
\usepackage{afterpage}
\graphicspath{{figures/}}

% 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{\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{\smallset}[2]{\{ #1 \;\big|\; #2 \}} % small 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}{{\mathbb{1}}} % the all one vector
\newcommand{\zero}{{\mathbb{0}}} % the all zero vector

\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

% operators
\DeclareMathOperator{\conv}{conv} % convex hull
\DeclareMathOperator{\vect}{vect} % linear span
\DeclareMathOperator{\cone}{cone} % cone hull
\DeclareMathOperator{\sign}{sign} % sign
\DeclareMathOperator{\suppmin}{\mu} % support minimal

% 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]{\medskip\noindent\textsc{#1.}} % paragraph
\renewcommand{\topfraction}{1} % possibility to have one page of pictures
\renewcommand{\bottomfraction}{1} % possibility to have one page of pictures
\newcommand{\ex}{_{\textrm{exm}}} % examples
\newcommand{\pa}{_{\textrm{pa}}} % path
\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}}

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

% geometry
\newcommandx{\polytope}[1][1 = P]{\mathsf{#1}} % polytope
\newcommandx{\Asso}[1][1=n]{\mathsf{Asso}(#1)} % associahedron
\newcommandx{\Zono}[1][1=\digraph]{\mathsf{Zono}(#1)} % zonotope
\newcommand{\Nest}{\mathsf{Nest}} % nestohedron
\newcommand{\Acycl}{\mathsf{Acyc}} % acyclonestohedron
\newcommand{\AcyclProj}{\mathsf{A\overline{cyc}}} % acyclonestohedron
\newcommand{\OrderPolytope}{\mathsf{OrdPol}} % order polytope

% Nestohedra and graph associahedra
\newcommand{\ground}{S} % ground set
\newcommandx{\graphG}[1][1=G]{#1} % graph
\newcommandx{\digraph}[1][1=D]{#1} % directed graph
\newcommandx{\hypergraph}[1][1=H]{\graphG[#1]} % hypergraph
\newcommandx{\tube}[1][1=t]{#1} % tube
\newcommandx{\tubes}[1][1=\graphG]{\building(#1)} % all tubes
\newcommandx{\tubing}[1][1=T]{#1} % tubing
\newcommandx{\pretube}[1][1=t]{\bar{#1}} % pretube
\newcommand{\connectedComponents}{\kappa} % connected components
\newcommand{\nestedComplex}{\mathfrak{N}} % nested complex
\newcommand{\acyclicNestedComplex}{\mathfrak{A}} % acyclic nested complex
\newcommand{\posetNestedComplex}{\mathfrak{P}} % poset nested complex
\newcommand{\affinePosetNestedComplex}{\mathfrak{AP}} % poset nested complex
\newcommand{\building}{\mathcal{B}} % building set
\newcommandx{\fbuilding}[1][1=\building]{\widehat{#1}} % facial building set
\newcommandx{\nested}[1][1=N]{\mathcal{#1}} % nested set
\newcommand{\btree}{\mathsf{T}} % b-trees
\newcommandx{\restrGround}[2][1=B, 2=\nested]{{\ground_{#1 \in #2}}} % restricted ground set
\newcommandx{\complRestrGround}[2][1=B, 2=\nested]{{R_{#1 \in #2}}} % complement of restricted ground set
\newcommandx{\restrBuilding}[2][1=B, 2=\nested]{{\building_{#1 \in #2}}} % restricted building set
\newcommandx{\restrOM}[2][1=B, 2=\nested]{{\OM_{#1 \in #2}}} % restricted oriented matroid
\newcommandx{\restrOB}[2][1=B, 2=\nested]{{(\building, \OM)_{#1 \in #2}}} % restricted ground set
\newcommand{\block}[2]{B(#1,#2)} % block of vertex of nested set
\newcommandx{\vertexNest}[2][1 = \nested, 2 = \b{\lambda}]{\b{v}(#1, #2)} % vertex of nestohedron

% Oriented matroids
\newcommand{\OM}{\c{M}} % oriented matroid
\newcommandx{\dependences}[1][1 = \b{A}]{\mathcal{D}(#1)} % dependences
\newcommandx{\evaluations}[1][1 = \b{A}]{\mathcal{D}^*(#1)} % evaluations
\newcommandx{\circuits}[1][1 = \b{A}]{\mathcal{C}(#1)} % circuits
\newcommandx{\cocircuits}[1][1 = \b{A}]{\mathcal{C}^*(#1)} % cocircuits
\newcommandx{\vectors}[1][1 = \b{A}]{\mathcal{V}(#1)} % vectors
\newcommandx{\covectors}[1][1 = \b{A}]{\mathcal{V}^*(#1)} % covectors
\newcommandx{\rank}[1][1 = \b{A}]{\mathrm{rk}(#1)} % rank
\newcommandx{\corank}[1][1 = \b{A}]{\mathrm{rk}^*(#1)} % corank
\newcommand{\signature}{\sigma} % signature
\newcommandx{\UOM}[1][1=\OM]{\underline{#1}} % underlying unoriented matroid
\newcommandx{\Ucircuits}[1][1 = \b{A}]{\underline{\mathcal{C}}(#1)} % circuits
\newcommandx{\Ucocircuits}[1][1 = \b{A}]{\underline{\mathcal{C}}^*(#1)} % cocircuits
%\newcommand{\FL}{\FP_{\textsc{lv}}} % Las Vergnas face lattice
\newcommand{\FL}{\FP} % Las Vergnas face lattice
\newcommandx{\sdOM}[2][1=\OM,2=\fbuilding]{\sd(\Delta({#1}),{#2})} % nested complex oriented matroid of a building set
\newcommandx{\circuitSupports}[1][1 = \b{A}]{\underline{\mathcal{C}}(#1)} % supports of circuits

%lattices 
\newcommand{\lattice}{\mathcal{L}} % lattice
\newcommand{\topone}{\hat{1}} % top
\newcommand{\botzero}{\hat{0}} % bottom

% poset associahedron
\newcommand{\precdot}{\mathrel{{\prec \!\! \cdot}}} % cover relation
\newcommandx{\poset}[1][1 = P]{\mathrm{#1}} % poset

% affine poset cyclohedron
\renewcommand{\t}[1]{{\smash{\tilde{#1}}}} % tiilde letters
\newcommand{\tb}[1]{\t{\b{#1}}} % tiilde bold letters
\newcommandx{\affinePoset}[1][1 = \poset]{\t{#1}} % affine poset
\renewcommand{\mod}[2]{\text{mod}(#1)} % modulus
\newcommand{\quo}[2]{\text{quo}(#1)} % quotient
\newcommand{\cl}[2]{\text{cl}(#1)} % class
\newcommandx{\elev}[1][1 = \affinePoset]{E(#1)} % elevators 
\newcommandx{\quotientGraph}[1][1 = \affinePoset]{#1/\Z}
%\newcommandx{\quotientGraph}[1][1 = \affinePoset]{\nicefrac{#1}{\Z}}

% CW complexes
\newcommandx{\sph}[1][1 = n]{\mathbb{S}^{#1}} % unit n-sphere
\newcommandx{\ball}[1][1 = n]{\mathbb{B}^{#1}} % unit n-ball
\newcommand{\FP}{\mathcal{F}} % face poset
\newcommand{\CW}{\Delta} %CW complex
\newcommand{\cell}{\sigma} %cell of a CW complex
\newcommand{\inter}[1]{\mathring{#1}} %interior
\newcommand{\bdy}[1]{\partial {#1}} %boundary
\newcommandx{\spa}[1][1 = \CW]{\left\lVert{#1}\right\rVert} %underlying space
\newcommand{\join}{\ast} %join
\DeclareMathOperator{\sd}{sd} %stellar subdivision
\DeclareMathOperator{\ostar}{star} %open star
\newcommand{\cstar}{\overline \ostar} %closed star

%% define your title in the usual way
\title{Acyclonestohedra}
%\thanks{Supported by the French project CHARMS (ANR~19\,CE40\,0017), the French\,--\,Austrian project PAGCAP (ANR~21\,CE48\,0020 \& FWF I 5788), the project PID2019-106188GB-I00 of MCIN/AEI/10.13039/501100011033 and the project CLaPPo (21.SI03.64658) of Universidad de Cantabria and Banco Santander.}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{
	Chiara Mantovani\thanks{\href{mailto:chiara.mantovani@lix.polytechnique.fr}{chiara.mantovani@lix.polytechnique.fr}. Supported by the projects CHARMS (ANR~19\,CE40\,0017) of the French ANR and PAGCAP (ANR~21\,CE48\,0020 \& FWF I 5788) of the French ANR and Austrian FWF.}\addressmark{1}, 
	Arnau Padrol\thanks{\href{mailto:arnau.padrol@ub.edu}{arnau.padrol@ub.edu}. Supported by the projects 
	PAGCAP, PID2019-106188GB-I00 and PID2022-137283NB-C21 of MCIN/AEI/\-10.13039/501100011033 and CLaPPo (21.SI03.64658) of Universidad de Cantabria and Banco~Santander.}\addressmark{2},
	\and
	Vincent Pilaud\thanks{\href{mailto:vincent.pilaud@ub.edu}{vincent.pilaud@ub.edu}. Supported by the above mentioned projects CHARMS, PAGCAP, PID2019-106188GB-I00, PID2022-137283NB-C21 and CLaPPo.}\addressmark{2}
}

%% then use \addressmark to match authors to institutions here
\address{
	\addressmark{1} Laboratoire d'Informatique de l'École Polytechnique, Palaiseau, France
	\\
	\addressmark{2} Departament de Matemàtiques i Informàtica, Universitat de Barcelona, Spain
}

%% 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{
Given a building set~$\building$ and an oriented matroid~$\OM$ on the same ground set, we define the acyclic nested complex as the simplicial complex of nested sets on~$\building$ which are in some sense acyclic with respect to~$\OM$.
We prove that this complex is always the face lattice of an oriented matroid, obtained as a stellar subdivision of the positive tope of the oriented matroid~$\OM$.
When the oriented matroid~$\OM$ is the oriented matroid of a vector configuration~$\b{A}$, we moreover prove that this complex is the boundary complex of an acyclonestohedron, a polytope obtained as the section of a nestohedron for~$\building$ by the evaluation space of~$\b{A}$.
Our work specializes to explicit polytopal realizations of the poset associahedra and affine poset cyclohedra of Galashin.
%We also provide an alternative realization in the space of the vector configuration~$\b{A}$, inspired by the recent work of A.~Sack.
%This construction realizes and generalizes the poset associahedra recently introduced by Galashin.
%Namely, we prove that the associahedron of a poset with Hasse diagram~$H$ is realized as the boundary complex of the acyclonestohedron where the building set is the graphical building set of the line graph of~$H$, and the oriented matroid is the graphical matroid of~$H$.
%This also extends to the affine poset cyclohedra of Galashin.
}

%% put your French abstract here, or comment this out if you don't have one
\resume{
Étant donné un ensemble de construction~$\building$ et un matroïde orienté~$\OM$ sur le même ensemble, nous définissons le complexe imbriqué acyclique comme le complexe simplicial des ensembles imbriqués de~$\building$ qui sont acycliques pour~$\OM$ en un certain sens.
Nous montrons que ce complexe est toujours le treillis des faces d'un matroïde orienté, obtenu par subdivisions stellaires du tope positif du matroïde orienté~$\OM$.
Quand le matroïde orienté~$\OM$ est le matroïde orienté d'une configuration de vecteurs~$\b{A}$, nous montrons que ce complexe est le complexe de bord d'un acyclonestoèdre, un polytope obtenu comme la section du nestoèdre de~$\building$ par l'espace vectoriel des évaluations linéaires sur~$\b{A}$.
Notre travail se spécialise à des réalisations polytopales explicites des associaèdres d'ordres et des cycloèdres d'ordres affines~de~Galashin.
}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{building sets, nested complexes, oriented matroids, poset associahedra}

%% 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; i.e., [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}
\addbibresource{posetAssociahedra.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}

Motivated by the recent work of Galashin on poset associahedra and affine poset cyclohedra~\cite{Galashin}, we introduce the acyclic nested complexes and the acyclonestohedra, some simplicial complexes and polytopes at the interface between nestohedra~\cite{Postnikov, FeichtnerKozlov2004, FeichtnerSturmfels, Zelevinsky} (\cref{subsec:buildingSetsNestedComplexes}) and oriented matroids~\cite{BjornerLasVergnasSturmfelsWhiteZiegler} (\cref{subsec:orientedMatroids}).

\clearpage

The input data is an oriented building set~$(\building,\OM)$ (\cref{subsec:orientedBuildingSets}), that is, a building set~$\building$ and an oriented matroid~$\OM$ on the same ground set so that any circuit of~$\OM$ is a block of~$\building$.
The acyclic nested complex~$\acyclicNestedComplex(\building,\OM)$ is the simplicial complex of nested sets on~$\building$ which are in some sense acyclic with respect to~$\OM$ (\cref{subsec:acyclicNestedComplexes}).

Prototypical examples are graphical oriented building sets.
The graphical oriented building set of a directed graph~$D$ is formed by the graphical building set of the line graph~$L(D)$ together with the graphical oriented matroid of~$D$.
The graphical acyclic nested complex is then given by all tubings~$T$ on~$L(D)$ such that for each tube~$t \in T$, the contraction in the restriction~$D_{|t}$ of all arcs contained in some tube~$s \in T$ with~$s \subsetneq t$ yields an acyclic directed graph.
It is not difficult to see that this definition actually only depends upon the transitive closure of~$D$ and coincides with the poset associahedron~of~\cite{Galashin}.
A similar (but slightly more intricate) construction shows that the affine poset cyclohedra of~\cite{Galashin} are also acyclic nested complexes of specific oriented building~sets.

 Our main results are geometric realizations of acyclic nested complexes (\cref{subsec:stellarSubdivisions,subsec:acyclonestohedra}).
We show that the acyclic nested complex of an oriented building set~$(\building, \OM)$ is
 \begin{compactenum}[(i)]
 \item the face lattice of an oriented matroid obtained by stellar subdivisions~of~$\OM$, 
\item the boundary complex of a convex polytope, obtained by stellar subdivisions of the positive tope of~$\OM$ when the latter is realizable,
 \item the boundary complex of the polar of the acyclonestohedron, a polytope obtained as the section of a nestohedron for~$\building$ with the evaluation space of~$\b{A}$, when~$\OM$ is realized by the vector configuration~$\b{A}$.
 \end{compactenum}
Note that~(i) is valid for all oriented matroids (realizable or not), while (ii) and (iii) only apply to realizable oriented matroids.
The advantage of~(iii) over~(ii) is that it leads to explicit realizations with controlled integer coordinates.
For poset associahedra and affine poset cyclohedra, (ii) recovers the construction of~\cite{Galashin} using stellar subdivisions of order polytopes, and (iii) answers a question left open in~\cite{Galashin}, and \mbox{independently settled~in~\cite{Sack}.}

In fact, the oriented building sets and their acyclic nested complexes are closely related to the lattice building sets and their lattice nested complexes of~\cite{FeichtnerKozlov2004, FeichtnerSturmfels}.
Namely, we show that the building sets on the Las Vergnas face lattice of~$\OM$ are obtained from the oriented building sets~$(\building,\OM)$ by keeping only the blocks of~$\building$ which are faces of~$\OM$, and that the two notions of nested complexes % on these facial building sets and on oriented building sets
coincide (\cref{sec:acyclonestohedron}).
We exploit this correspondence in both directions: we recover our results on stellar subdivisions % (implying the results of~\cite{Galashin}) 
as reformulations of~\cite{FeichtnerMuller2005, FeichtnerKozlov2004}, and we use our acyclonestohedra to get explicit polytopal realizations with integer coordinates for the all nested complexes over face lattices of realizable matroids.

Finally, Galashin's main motivation for poset associahedra was that they model compactifications of the space of order preserving maps $P\to \R$, which can be identified with the interior of an order polytope.
We observe that results of~\cite{Gaiffi2003} imply that acyclonestohedra are associated to nice compactifications of interiors of polytopes~(\cref{sec:compactifications}).

Many details and all proofs are omitted in this extended abstract due to space limitations.
We refer to the long version of this work which should soon become available.

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

\newpage
\section{Preliminaries}
\label{sec:preliminarires}

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

\subsection{Building sets, nested complexes, and nestohedra}
\label{subsec:buildingSetsNestedComplexes}

We start with the classical definitions of building sets, nested sets, nested complexes, and nestohedra from~\cite{Postnikov, FeichtnerKozlov2004, FeichtnerSturmfels, Zelevinsky} and their specializations to the graphical case~\cite{CarrDevadoss}.
% The presentation and some illustrations are borrowed from~\cite{PadrolPilaudPoullot-deformedNestohedra}.

\begin{definition}[\cite{Postnikov, FeichtnerKozlov2004, FeichtnerSturmfels}]
\label{def:building}
A \defn{building set} on~$\ground$ is a set~$\building$ of non-empty subsets of~$\ground$~such~that
\begin{compactitem}
\item $\building$ contains all singletons~$\{s\}$ for~$s \in \ground$, and
\item if~$B,B' \in \building$ and~$B \cap B' \ne \varnothing$, then~$B \cup B' \in \building$.
\end{compactitem} 
We denote by~$\connectedComponents(\building)$ its set of \defn{$\building$-connected components}, \ie its inclusion maximal elements. %, and we say that $\building$ is \defn{connected} if $\connectedComponents(\building)=\{\ground\}$.
\end{definition}
%We denote by~$\elementary(\building)$ the set of \defn{elementary blocks} of~$\building$, defined as 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\}$.
%%

\begin{example}[\cite{CarrDevadoss}]
\label{exm:graphicalBuilding}
Consider a graph~$\graphG$ on~$\ground$.
A \defn{tube} of~$\graphG$ is a non-empty subset of~$\ground$ which induces a connected subgraph of~$\graphG$.
The set~$\tubes$ of all tubes of~$\graphG$ is a \defn{graphical building set}.
Moreover, the blocks of $\connectedComponents(\tubes)$ are the connected components~of~$\graphG$.
\end{example}

\begin{remark}[\cite{DosenPetric}]
\label{rem:hypergraphicalBuilding}
More generally, a hypergraph~$\hypergraph$ on~$\ground$ defines a building set~$\building(\hypergraph)$ on~$\ground$ given by all non-empty subsets of~$\ground$ which induce connected subhypergraphs of~$\hypergraph$.
% (a path in~$\hypergraph$ is a sequence of vertices where any two consecutive ones belong to a common hyperedge of~$\hypergraph$).
Any building set~$\building$ on~$\ground$ is the building set of a hypergraph, but not always of a graph.
%See \cite{DosenPetric} for details.
\end{remark}

%\begin{example}
%\label{exm:building}
%For a more specific instance, consider the building set~$\building_\circ$ on~$[5]$ defined by
%\[
%\building_\circ \eqdef \{1, 2, 3, 4, 5, 6, 12, 14, 25, 123, 124, 125, 456, 1234, 1235, 1245, 1456, 2456, 12345, 12456, 123456\}
%\]
%(since all labels have a single digit, we can abuse notation and write $123$ for $\{1,2,3\}$).
%It has a single $\building_\circ$-connected component $\connectedComponents(\building_\circ) = \{123456\}$. 
%It is the building set of the hypergraph~$\{12, 14, 25, 123, 456\}$ represented in \cref{fig:exmNested}\,(left).
%%
%\begin{figure}
%	\capstart
%	\centerline{\includegraphics[scale=.9]{exmNested}}
%	\caption{The elementary blocks of a building set~$\building_\circ$ (left), a subset of~$\building_\circ$ which is not a nested set on~$\building_\circ$ (middle left), a nested set on~$\building_\circ$ (middle right), and a maximal nested set on~$\building_\circ$ (right).}
%	\label{fig:exmNested}
%\end{figure}
%\end{example}

%\begin{definition}[{\cite[Lem.~3.10]{FeichtnerSturmfels}}]
%\label{def:buildingClosure}
%Let $\c{X} \subseteq 2^\ground$, we define the \defn{building closure} of $\c{X}$ as the smallest building set $\building$ containing $\c{X}$.
%It is composed of the singletons $\{s\}$ for $s\in \ground$ and the sets $\bigcup_{Y \in \c{Y}} Y$ for each $\c{Y} \subseteq \c{X}$ with a connected intersection graph.
%\end{definition}

\begin{definition}[\cite{Postnikov, FeichtnerKozlov2004, FeichtnerSturmfels}]
\label{def:nested}
%Let~$\building$ be a building set on~$\ground$.
A \defn{nested set} is a subset~$\nested$ of~$\building$ containing~$\connectedComponents(\building)$ such that
% for any~$k \ge 2$ pairwise non-nested~$B_1,\dots,B_k \in \nested$, the union~$B_1 \cup \dots \cup B_k$ does not belong to~$\building$, or equivalently
\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$.
\end{compactitem}
The \defn{nested complex} of~$\building$ is the simplicial complex~$\nestedComplex(\building)$ whose faces are $\nested \ssm \connectedComponents(\building)$ for all nested sets~$\nested$ on~$\building$.
\end{definition}

%The nested complex is a simplicial sphere of dimension~$|\ground| - |\connectedComponents(\building)|$.
%Note that it is convenient to include~$\connectedComponents(\building)$ in all nested sets as in~\cite{Postnikov} for certain combinatorial manipulations, but to remove $\connectedComponents(\building)$ from all nested sets as in~\cite{Zelevinsky} when defining the $\building$-nested complex.

\begin{example}[\cite{CarrDevadoss}]
\label{exm:graphicalNested}
Consider a graph~$\graphG$ on~$\ground$.
Two tubes~$\tube, \tube'$ of~$\graphG$ are \defn{compatible} if they are either nested (\ie $\tube \subseteq \tube'$ or~$\tube' \subseteq \tube$), or disjoint and non-adjacent~(\ie~${\tube \cup \tube' \notin \tubes}$).
%Note that any connected component of~$\graphG$ is compatible with any other tube of~$\graphG$.
A \defn{tubing} on~$\graphG$ is a set~$\tubing$ of pairwise compatible tubes of~$\graphG$ containing all connected components~$\connectedComponents(\graphG)$.
%Examples are illustrated in \cref{fig:exmGraphicalNested}.
Tubings are precisely the nested sets of the graphical building set~$\tubes$.
The nested complex~$\nestedComplex(\tubes)$ is a \defn{graphical nested complex}.
%%
%\begin{figure}
%	\capstart
%	\centerline{\includegraphics[scale=.45]{exmGraphicalNested}}
%	\caption{Some incompatible tubes (left and middle), and a maximal tubing (right).}
%	\label{fig:exmGraphicalNested}
%\end{figure}
\end{example}

%\begin{example}
%\label{exm:nested}
%For instance, consider the building set~$\building_\circ$ of \cref{exm:building}.
%The subset~$\{14, 25, 3\}$ is not a nested set on~$\building_\circ$ since its union is~$12345 \in \building_\circ$ (and it does not contain~$\connectedComponents(\building)$).
%In contrast, the subsets~$\{3, 4, 25, 123456\}$ and~$\{3, 4, 5, 25, 12345, 123456\}$ are nested sets on~$\building_\circ$ and the later is maximal.
%These subsets of~$\building_\circ$ are illustrated in \cref{fig:exmNested}.
%\end{example}

We now introduce restrictions and contractions of building sets. These operations are used to describe links of nested complexes~\cite[Prop.~3.2]{Zelevinsky}, and will be crucial here to define acyclic nested complexes.
% to describe the links of nested complexes, following~\cite[Prop.~3.2]{Zelevinsky}.

\begin{definition}
\label{def:restrictionContractionBuilding}
For any~$R \subseteq \ground$, define
\begin{compactitem}
\item the \defn{restriction} of~$\building$ to~$R$ as the building set~$\building_{|R} \eqdef \! \set{B \in \building}{B \subseteq R}$ on~$R$,
\item the \defn{contraction} of~$R$ in~$\building$ as the building set~$\building_{\!/R} \eqdef \! \set{B \ssm R}{B \in \building, \, B \not\subseteq R}$~on~${\ground \ssm R}$.
\end{compactitem}
\end{definition}

\begin{example}
\label{exm:restrictionContractionGraphicalBuilding}
For a graph~$\graphG$ on~$\ground$ and $R \subseteq \ground$,
\begin{compactitem}
\item $\tubes_{|R} = \tubes[G_{|R}]$ where~$\graphG_{|R}$ is the subgraph of~$\graphG$ induced by~$R$,
\item $\tubes_{\!/R} = \tubes[G_{\!/R}]$ where~$\graphG_{\!/R}$ is the \defn{reconnected complement} of~$R$ in~$\graphG$, \ie the graph on~$\ground \ssm R$ with an edge~$\{r,s\}$ if there is a path between~$r$ and~$s$ in~$\graphG$ with vertices in~$R \cup \{r,s\}$, see~\cite{CarrDevadoss}.
\end{compactitem}
\end{example}

%\begin{example}
%For instance, consider the building set~$\building_\circ$ of \cref{exm:building}, illustrated in \cref{fig:exmNested}.
%For~$R \eqdef 1234$, we have~${\building_\circ}_{|R} = \{1, 2, 3, 4, 12, 14, 123, 124, 1234\}$ and~${\building_\circ}_{\!/R} = \{5, 6, 56\}$.
%\end{example}

%Note that our definition of contraction in \cref{def:restrictionContractionBuilding} slightly differs from that of~\cite[Def.~3.1]{Zelevinsky}, in order to fit better with the restriction of oriented matroids.
%However, it coincides for~$R \in \building$, which enables us to borrow directly the following statement.

%\begin{proposition}[{\cite[Prop.~3.2]{Zelevinsky}}]
%\label{prop:linksNestedComplex}
%For $B \in \building \ssm \connectedComponents(\building)$, the link~$\set{\nested \ssm \{B\}}{B \in \nested \in \nestedComplex(\building)}$ is the join~$\nestedComplex(\building_{|B}) \join \nestedComplex(\building_{\!/B})$.
%\end{proposition}

%The following statement is very similar in flavour.
%We skip the straightforward proof.
%
%\begin{proposition}
%\label{prop:disconnectedNestedComplex}
%If $\building$ is a building set on~$\ground$ with~$|\connectedComponents(\building)| = k$, then~$\nestedComplex(\building \cup \{\ground\})$ is isomorphic to the join~$\nestedComplex(\building) \join \partial(\triangle_{k-1})$, where~$\triangle_{k-1}$ denotes the $(k-1)$-dimensional simplex.
%\end{proposition}
%
%Our next statement gives a simple way to construct nested sets from ordered partitions, in particular from permutations.
%
%\begin{proposition}
%\label{prop:surjectionBuilding}
%For any ordered partition~$\pi = \pi_1 | \dots | \pi_k$ of~$\ground$, the set~$\nested_\pi \eqdef \bigcup_{i \in [k]} \connectedComponents(\building_{|\pi_1 \cup \dots \cup \pi_k})$ is a nested set on~$\building$.
%If~$k = |\ground|$, then~$\nested_\pi$ is maximal.
%\end{proposition}

Finally, we recall the definition of the nestohedron which realizes the nested complex.
See for instance \cref{fig:nestohedra}.
We denote by~$(\b{e}_s)_{s \in \ground}$ the standard basis of~$\R^\ground$.
For a building set~$\building$, we denote by~$\R^\building_+ \eqdef \set{\b{\lambda} \in \R^\building}{\lambda_B > 0 \text{ for all } B \in \building \text{ with } |B| \ge 2}$.

\begin{definition}[\cite{Postnikov, FeichtnerSturmfels}]
\label{def:nestohedron}
For a building set~$\building$ and a positive vector~$\b{\lambda} = (\lambda_B)_{B \in \building} \in \R^\building_+$, the \defn{nestohedron}~$\Nest(\building, \b{\lambda})$ is the Minkowski sum~$\sum_{B \in \building} \lambda_B \triangle_B$, where~$\triangle_B \eqdef \conv\set{\b{e}_b}{b \in B}$ denotes the face of the standard simplex~$\triangle_\ground$ corresponding to~$B$.
%
\begin{figure}[h]
	\capstart
	\centerline{\includegraphics[scale=.45]{nestohedronGraphAssociahedron}}
	\caption{A nestohedron whose vertices are labeled by the corresponding maximal nested sets (left), and a graph associahedron whose vertices are labeled by the corresponding maximal tubings (right). The maximal block or tubing is always omitted.}
	\label{fig:nestohedra}
\end{figure}
\end{definition}

\begin{theorem}[\cite{Postnikov, FeichtnerSturmfels, Zelevinsky}]
\label{thm:nestohedron}
For a building set~$\building$ and any~$\b{\lambda} \in \R^\building_+$, the nested complex~$\nestedComplex(\building)$ is isomorphic to the boundary complex of the polar of the nestohedron~$\Nest(\building, \b{\lambda})$.
\end{theorem}

%Note that for this statement, it is important that~$\lambda_B > 0$ for~$|B| \ge 2$, while~$\lambda_B$ is irrelevant for~$|B| = 1$ (as it corresponds to translations in the Minkowski sum), hence the definition of~$\R^\building_+$.
%We will also need the explicit vertex and facet descriptions of the nestohedron~$\Nest(\building, \b{\lambda})$.

\begin{proposition}
\label{prop:vertexDescriptionNestohedron}
%For any~$\b{\lambda} \in \R^\building$ with~$\lambda_B > 0$ for~$|B| \ge 2$, the vertex of the nestohedron~$\Nest(\building, \b{\lambda})$ corresponding to a maximal nested set~$\nested$ is
For~$\b{\lambda} \in \R^\building_+$, the vertex of the nestohedron~$\Nest(\building, \b{\lambda})$ corresponding to a maximal nested set~$\nested$ is
\[
\vertexNest = \sum_{s \in \ground} \sum_{B \in \building, \; s \in B \subseteq \block{v}{\nested}} \lambda_B \b{e}_s,
\]
where~$\block{s}{\nested}$ denotes the inclusion minimal block of~$\nested$ containing~$s$.
\end{proposition}

\begin{proposition}
\label{prop:facetDescriptionNestohedron}
For~$\b{\lambda} \in \R^\building_+$, the nestohedron~$\Nest(\building, \b{\lambda})$ is given by the equalities~${g_B(\b{x}) = 0}$ for all~$B \in \connectedComponents(\building)$ and the inequalities~$g_B(\b{x}) \ge 0$ for all~$B \in \building$, where
\[
g_B(\b{x}) \eqdef \bigdotprod{\sum_{b \in B} \b{e}_b}{\b{x}} - \sum_{B' \in \building, \; B' \subseteq B} \lambda_{B'}.
\]
\end{proposition}

%\begin{proposition}
%\label{prop:descriptionsNestohedron}
% For any~$\b{\lambda} \in \R^\building_+$, the nestohedron~$\Nest(\building, \b{\lambda})$ is contained in the hyperplane of~$\R^\ground$ equation~$\sum_{v \in \ground} x_v = \sum_{B \in \building} \lambda_B$ and has
%\begin{itemize}
%\item a facet defined by the inequality~$\sum_{b \in B} x_b \ge ...$ for each~$B \in \building$,
%\item a vertex~$\b{v}(\nested, \b{\lambda}) = \sum_{v \in \ground} \sum_{B \in \building, v \in B \subseteq \block{v}{\nested}} \lambda_B \b{e}_v$ for each maximal nested set~$\nested$ on~$\building$, where~$\block{v}{\nested}$ denotes the inclusion minimal element of~$\nested$ containing~$v$.
%\end{itemize}
%\end{proposition}

\begin{example}
\label{exm:graphAssociahedron}
For a graph~$\graphG$ on~$\ground$, the nestohedra of~$\tubes$ are the \defn{graph associahedra} of~$\graphG$, introduced in~\cite{CarrDevadoss}.
For instance, the associahedron of the complete graph is a permutahedron, the associahedron of a path graph is an associahedron, and the associahedron of a cycle graph is a cyclohedron.
%See \cref{fig:permutahedronAssociahedronCyclohedron}.
%Two other examples are illustrated in \cref{fig:graphAssociahedra}.
%%
%\begin{figure}
%	\capstart
%	\centerline{\includegraphics[scale=.45]{permutahedronPermutations} \quad \includegraphics[scale=.45]{permutahedronTubings}}
%	\bigskip
%	\centerline{\includegraphics[scale=.45]{associahedronTriangulations} \quad \includegraphics[scale=.45]{associahedronTubings}}
%	\bigskip
%	\centerline{\includegraphics[scale=.45]{cyclohedronTriangulations} \quad \includegraphics[scale=.45]{cyclohedronTubings}}
%	\caption{The permutahedron (top), the associahedron (middle), and the cyclohedron (bottom), with vertices labeled by standard combinatorial objects (left) and by maximal tubings of special graphs (right). The maximal tube is omitted in all tubings.}
%	\label{fig:permutahedronAssociahedronCyclohedron}
%\end{figure}
%%
%\begin{figure}
%	\capstart
%	\centerline{\includegraphics[scale=.45]{graphAssociahedra}}
%	\caption{Two graph associahedra, whose vertices are labeled by the corresponding maximal tubings. The maximal tube is omitted in all tubings. Illustration from~\cite{PadrolPilaudPoullot-deformedNestohedra}.}
%	\label{fig:graphAssociahedra}
%\end{figure}
\end{example}

%\begin{example}
%For instance, consider the building set~$\building_\circ$ of \cref{exm:building}, illustrated in \cref{fig:exmNested}.
%The vertex~$\vertexNest[\nested_\circ]$ of the nestohedron~$\Nest(\building_\circ, \b{\lambda})$ corresponding to the maximal nested set~$\nested_\circ \eqdef \{3, 4, 5, 25, 12345, 123456\}$ on~$\building_\circ$ illustrated in \cref{fig:exmNested}\,(right) is given by
%\begin{multline*}
%\vertexNest[\nested_\circ] = (\lambda_1 + \lambda_{12} + \lambda_{14} + \lambda_{123} + \lambda_{124} + \lambda_{125} + \lambda_{1234} + \lambda_{1235} + \lambda_{1245} + \lambda_{12345}) \b{e}_1 \\ + (\lambda_2 + \lambda_{25}) \b{e}_2 + \lambda_3 \b{e}_3 + \lambda_4 \b{e}_4 + \lambda_5 \b{e}_5 + (\lambda_6 + \lambda_{456} + \lambda_{1456} + \lambda_{2456} + \lambda_{12456} + \lambda_{123456}) \b{e}_6.
%\end{multline*}
%The inequalities corresponding to the blocks~$25$, $125$, and~$1234$ are given by
%\begin{gather*}
%x_2 + x_5 \ge \lambda_2 + \lambda_5 + \lambda_{25}
%\qquad
%x_1 + x_2 + x_5 \ge \lambda_1 + \lambda_2 + \lambda_5 + \lambda_{12} + \lambda_{25} + \lambda_{125}
%\\
%x_1 + x_2 + x_3 + x_4 \ge \lambda_1 + \lambda_2 + \lambda_3 + \lambda_4 + \lambda_{12} + \lambda_{14} + \lambda_{123} + \lambda_{124} + \lambda_{1234}.
%\end{gather*}
%Note that since the nested set~$\nested_\circ$ contains the blocks~$25$ (but neither~$125$ nor~$1234$), the first  inequality (but not the last two) is tight for the vertex~$\vertexNest[\nested_\circ]$.
%\end{example}

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

\subsection{Vector configurations and oriented matroids}
\label{subsec:orientedMatroids}

We now recall some aspects of oriented matroids.
We only give the precise definition for those associated to vector configurations and refer to~\cite{BjornerLasVergnasSturmfelsWhiteZiegler} for the general definition.


\begin{definition}
\label{def:dependencesEvaluationsVectorConfiguration}
For a finite vector configuration~$\b{A} \eqdef (\b{a}_s)_{s \in \ground} \in (\R^d)^\ground$, we denote by
\begin{compactitem}
\item $\dependences \eqdef \! \set{\b{\delta} \in \R^\ground}{\sum_{s \in \ground} \delta_s \b{a}_s = \b{0}}$ the space of linear \defn{dependences} on~$\b{A}$,
\item $\evaluations \eqdef \! \set{(f(\b{a}_s))_{s \in \ground} \! \in \! \R^\ground}{f  \! \in \! \smash{(\R^d)}^*\!}$ the space of \defn{evaluations} of linear forms~on~$\b{A}$.
\end{compactitem}
%Note that the dimension of the evaluation space~$\evaluations$ is the \defn{rank}~$\rank$ of~$\b{A}$, while the dimension of the dependence space~$\dependences$ is the \defn{corank}~$\corank \eqdef |\ground| - \rank$ of~$\b{A}$.
Note that, $\evaluations$ and~$\dependences$ are orthogonal spaces whose dimensions are the \defn{rank}~$\rank$ and the he \defn{corank}~$\corank \eqdef |\ground| - \rank$ of~$\b{A}$ respectively.
\end{definition}

\begin{notation}
Define~$\signature(\ground) \eqdef \set{(x_+, x_-)}{x_+, x_- \subseteq \ground \text{ and } x_+ \cap x_- = \varnothing}$.
The \defn{signature} of~${\b{\delta} \in \R^\ground}$ is~$\signature(\b{\delta}) \eqdef (\set{s \in \ground}{\delta_s > 0}, \set{s \in \ground}{\delta_s < 0})$ in~$\signature(\ground)$.
For~${x = (x_+, x_-) \in \signature(\ground)}$, we define the \defn{support} of~$x$ by $\underline{x} \eqdef x_+ \cup x_-$, and the \defn{opposite} of~$x$ by~$-x \eqdef (x_-, x_+)$.
\end{notation}

\begin{definition}
\label{def:orientedMatroidVectorConfiguration}
%The \defn{sign vector} of~$\b{\delta} \in \R^\ground$ is~$\sign(\delta) \eqdef (\sign(\delta_\b{A}))_{\b{v} \in \b{A}} \in \{-, 0, +\}^\b{A}$, where $\sign(x) \in \{-, 0, +\}$ denotes the sign of~$x \in \R$.
The \defn{oriented matroid}~$\OM(\b{A})$ of a finite vector configuration~$\b{A} \subset \R^d$ is the combinatorial data given equivalently by
\begin{compactitem}
\item the \defn{vectors}~$\vectors$ of~$\b{A}$, \ie signatures of linear dependences of~$\b{A}$,
\item the \defn{covectors}~$\covectors$ of~$\b{A}$, \ie signatures of linear evaluations on~$\b{A}$,
\item the \defn{circuits}~$\circuits$ of~$\b{A}$, \ie support minimal signatures of linear dependences of~$\b{A}$,
\item the \defn{cocircuits}~$\cocircuits$ of~$\b{A}$, \ie support minimal signatures of linear evaluations on~$\b{A}$.
\end{compactitem}
\end{definition}

%\begin{example}
%Consider the vector configuration~$\b{A}_\diamond$ obtained by linearization of the point configuration~$\set{\pm \b{e}_i}{i \in [n]}$, and label the vector~\smash{\raisebox{.05cm}{\scalebox{.6}{$\begin{bmatrix} -\b{e}_i \\ 1 \end{bmatrix}$}}} by~$\overline{i}$ and the vector~\smash{\raisebox{.05cm}{\scalebox{.6}{$\begin{bmatrix} \b{e}_i \\ 1 \end{bmatrix}$}}} by~$\underline{i}$.
%Then its circuits are~$\circuits = \bigset{(\underline{i}\overline{i}, \underline{j}\overline{j})}{i \ne j \in [n]}$ and its cocircuits are~$\cocircuits = \bigset{\pm(\underline{i}, \overline{i})}{i \in [n]} \cup \bigset{\pm(X,\varnothing)}{X \in \prod_{i \in [n]} \{\underline{i},\overline{i}\}}$.
%\end{example}

\begin{example}
\label{exm:graphicalOM}
Consider a directed graph~$\digraph$ with vertex set~$V$ and arc set~$\ground$ (loops and multiple arcs are allowed).
Let~$(\b{b}_v)_{v \in V}$ denote the standard basis of~$\R^V$.
The \defn{incidence configuration}~$\b{A}_{\digraph}$ of~$\digraph$ has a vector~$\b{a}_{(u,v)} \eqdef \b{b}_u - \b{b}_v \in \R^V$ for each arc~$(u,v)$ of~$\digraph$.
Its oriented matroid, whose ground set is the set~$\ground$ of arcs of~$\digraph$, is the \defn{graphical oriented matroid}~$\OM(\digraph)$ of~$\digraph$.
%Its ground set is the set~$\ground$ of arcs of~$\digraph$, and it has
%\begin{compactitem}
%\item a vector~$v$ for each collection of cycles, with clockwise arcs~$v_+$ and counter-clockwise~arcs~$v_-$,
%\item a covector~$v^*$ for each edge cut, with forward arcs~$v^*_+$ and backward arcs~$v^*_-$,
%\item a circuit~$c$ for each simple cycle, with clockwise arcs~$c_+$ and counter-clockwise arcs~$c_-$,
%\item a cocircuit~$c^*$ for each support minimal cut, with forward arcs~$c^*_+$ and backward arcs~$c^*_-$.
%\end{compactitem}
See \cite[Prop.~1.1.7 \& Chap.~5]{Oxley} and \cite[Sect.~1.1]{BjornerLasVergnasSturmfelsWhiteZiegler}.
\end{example}

In this paper, we will consider abstract oriented matroids, which are combinatorial abstractions for the dependences and evaluations of vector configurations considered in \cref{def:dependencesEvaluationsVectorConfiguration,def:orientedMatroidVectorConfiguration}.
We rest on \cite{BjornerLasVergnasSturmfelsWhiteZiegler} to avoid the detailed axioms.

\begin{definition}
\label{def:OM}
An \defn{oriented matroid} on~$\ground$ is the combinatorial data~$\OM$ given by four subsets of~$\sigma(S)$, the \defn{vectors}~$\vectors[\OM]$, \defn{covectors}~$\covectors[\OM]$, \defn{circuits}~$\circuits[\OM]$ and \defn{cocircuits}~$\cocircuits[\OM]$, which satisfy the axioms of \cite[Sect.~3]{BjornerLasVergnasSturmfelsWhiteZiegler}.
\end{definition}

\begin{definition}
\label{def:realizableOM}
An oriented matroid~$\OM$ is \defn{realizable} if there exists a vector configuration \linebreak $\b{A} \eqdef (\b{a}_s)_{s \in \ground} \in (\R^d)^\ground$ such that~$\vectors[\OM] = \vectors$, $\covectors[\OM] = \covectors$, $\circuits[\OM] = \circuits$, and~$\cocircuits[\OM] = \cocircuits$ (these four conditions are actually equivalent).
\end{definition}

\begin{definition}
\label{def:acyclicOM}
An oriented matroid~$\OM$ is acyclic if it has no positive circuit.
\end{definition}

\begin{example}
\label{def:acyclicRealizableOM}
A realizable oriented matroid~$\OM(\b{A})$ is acyclic if and only if~$\b{A}$ has no positive dependence, \ie if and only if $\b{A}$ is contained in a positive linear half-space~of~$\R^d$.
%For instance, the oriented matroid~$\OM(\b{A}_\circ)$ of the vector configuration~$\b{A}_\circ$ of \cref{exm:vectorConfiguration} is acyclic.
A graphical oriented matroid~$\OM(\digraph)$ is acyclic if and only if~$\digraph$ is acyclic (no~directed~cycle).
\end{example}

\begin{definition}
\label{def:LasVergnasFaceLattice}
Let $\OM$ be an acyclic oriented matroid.
A set $F\subseteq \ground$ is a \defn{face} of $\OM$ if it is the complement of a non-negative covector, \ie $(\ground\ssm F,\varnothing)\in\covectors[\OM]$.
%\end{definition}
%
%\begin{definition}
The \defn{Las Vergnas face lattice} $\FL(\OM)$ is the poset of faces of $\OM$ ordered by~inclusion.
\end{definition}

We conclude with restrictions and contractions in oriented matroids.

\begin{definition}
\label{def:restrictionContractionOM}
For any~$R \subseteq \ground$, define
\begin{compactitem}
%
% \item the \defn{restriction} of~$\OM$ to~$U$ as the oriented matroid~$\OM_{|U}$ on~$U$ with circuits~$\set{c \in \circuits[\OM]}{\underline{c} \subseteq U}$
% and whose cocircuits are the support minimal elements of~$\set{c^* \ssm U}{c^* \in \cocircuits[\OM]}$, where~$c^* \ssm U \eqdef (c^*_+ \ssm U, c^*_- \ssm U)$,
% \item the \defn{contraction} of~$U$ in~$\OM$ as the oriented matroid~$\OM_{\!/U}$ on~$\ground \ssm U$ whose circuits are the support minimal elements of~$\set{c \ssm U}{c \in \circuits[\OM]}$, where~$c \ssm U \eqdef (c_+ \ssm U, c_- \ssm U)$, and with cocircuits~$\set{c^* \in \cocircuits[\OM]}{\underline{c^*} \subseteq U}$ .
%
\item the \defn{restriction}~$\OM_{|R}$ as the oriented matroid on~$R$ with circuits~$\set{c \in \circuits[\OM]}{\underline{c} \subseteq R}$,
\item the \defn{contraction}~$\OM_{\!/R}$ as the oriented matroid on~$\ground \! \ssm \! R$ with vectors $\set{v \! \ssm \! R \!}{\! v \! \in \! \vectors[\OM]\!}$, where~$v \ssm R \eqdef (v_+ \ssm R, v_- \ssm R)$.
\end{compactitem}
%Note that acyclicity is preserved by restriction but not by contraction.
\end{definition}

\begin{example}
\label{exm:resctrictionContractionRealizableOM}
For a vector configuration~$\b{A} \eqdef (\b{a}_s)_s \in \ground$ and~$R \subseteq \ground$,
\begin{compactitem}
\item $\OM(\b{A})_{|R} = \OM(\b{A}_{|R})$ where $\b{A}_{|R}$ is the vector subconfiguration~$(\b{a}_r)_{r \in R}$,
\item $\OM(\b{A})_{\!/R} = \OM(\b{A}_{\!/R})$ where $\b{A}_{\!/R}$ is the vector configuration obtained by projecting the vectors~$\b{a}_s$ with~$s \notin R$ on the space orthogonal to all vectors~$\b{a}_r$ with~$r \in R$.
\end{compactitem}
For a directed graph~$\digraph$ and a subset~$R$ of arcs of~$\digraph$,
\begin{compactitem}
\item $\OM(\digraph)_{|R} = \OM(\digraph_{|R})$ where $\digraph_{|R}$ is the subgraph of~$\digraph$ formed by the arcs in~$R$,
\item $\OM(\digraph)_{\!/R} = \OM(\digraph_{\!/R})$ where~$\digraph_{\!/R}$ is the contraction of the arcs of~$R$ in~$\digraph$.
\end{compactitem}
\end{example}

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

\section{Acyclic nested complexes and acyclonestohedra}
\label{sec:acyclonestohedra}

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

\subsection{Oriented building sets}
\label{subsec:orientedBuildingSets}

%We first combine building sets and oriented matroids to obtain the following data.

\begin{definition}
\label{def:orientedBuilding}
An \defn{oriented building set} is a pair~$(\building, \OM)$ where~$\building$ is a building set and~$\OM$ is an oriented matroid on the same ground set~$\ground$ such that~$\underline{c} \in \building$ for any~$c \in \circuits[\OM]$.
We say that~$(\building, \OM)$ is \defn{realizable} if~$\OM$ is realizable.
\end{definition}

%\begin{remark}
%Given an oriented matroid~$\OM$, the building sets~$\building$ such that~$(\building, \OM)$ is an oriented building set form an upper ideal in the inclusion poset of building sets.
%This upper ideal is generated by a unique building set~$\building(\OM)$, which is the minimal building set containing~$\underline{c}$ for all~$c \in \circuits[\OM]$.
%In other words, the blocks of~$\building(\OM)$ are the connected components of~$\OM$ and all its restrictions.
%\end{remark}

%\begin{definition}
%For~$B \in \nested \in \nestedComplex(\building)$, we define the oriented matroid~$\restrOM$ as the contraction of~$\bigcup_{B' \in \nested, B' \subsetneq B} B'$ in the restriction of~$\OM$ to~$B$.
%\end{definition}

\begin{example}
\label{exm:graphicalOrientedBuildingSet}
Consider a directed graph~$D$ with vertex set~$V$ and arc set~$\ground$.
The \defn{line graph} of~$D$ is the graph~$L(D)$ on~$\ground$ with an edge between two arcs of~$D$ if and only if they share an endpoint.
The \defn{graphical oriented building set} of~$D$ is the pair~$(\building(L(D)), \OM(D))$.
Note that it is indeed an oriented building set: $\ground$ is the ground set of both~$\building(L(D))$ and~$\OM_D$, and the circuits in~$\OM(D)$ are cycles in~$D$, hence of~$L(D)$, thus belong to~$\building(L(D))$.
\end{example}

%Using the operations of contraction and deletion from \cref{def:restrictionContractionBuilding,def:restrictionContractionOM}, we now define a certain localization operation of oriented building sets.

\begin{lemma}
\label{lem:restrictionContractionOrientedBuilding}
If~$(\building, \OM)$ is an oriented building set on~$\ground$ and~$R \subseteq \ground$, then both $(\building_{|R}, \OM_{|R})$ and~$(\building_{\!/R}, \OM_{\!/R})$ are oriented building sets on~$R$ and~$\ground \ssm R$ respectively.
\end{lemma}
%
%\begin{proof}
%If~$c \in \circuits[\OM_{|R}]$, then~$c \in \circuits[\OM]$ so that~$\underline{c} \in \building$, and~$\underline{c} \subseteq R$ so that~$\underline{c} \in \building_{|R}$.
%If~$c' \in \circuits[\OM_{\!/R}]$, then~$c' = c' \ssm R$ for some~$c \in \circuits[\OM]$, so that~$\underline{c} \in \building$ and thus~$\underline{c'} = \underline{c} \ssm R \in \building_{\!/R}$.
%\end{proof}
%
%The following combinations of restrictions and contractions will be the keystone of \cref{subsec:acyclicNestedComplexes}.

\begin{definition}
\label{def:restrictionContractionOrientedBuilding}
Given an oriented building set~$(\building, \OM)$, a nested set~$\nested$ on~$\building$ and~${B \in \nested}$, we consider the oriented buiding set~$\restrOB \eqdef (\restrBuilding, \restrOM)$ on ${\restrGround \eqdef B \ssm R}$ defined by~$\restrBuilding \eqdef (\building_{|B})_{\!/R}$ and~$\restrOM \eqdef (\OM_{|B})_{\!/R}$, where~$R = \complRestrGround \eqdef \bigcup_{B' \in \nested, \; B' \subsetneq B} C$.
\end{definition}

%\begin{lemma}
%\label{lem:restrictionContractionOrientedBuilding2}
%For any~$B \in \nested \in \nestedComplex(\building)$, the pair~$(\restrBuilding, \restrOM)$ is an oriented building set on~$\restrGround$.
%\end{lemma}
%
%\begin{proof}
%Immediate consequence of \cref{lem:restrictionContractionOrientedBuilding}.
%\end{proof}

\begin{example}
\label{exm:graphicalRestrictionContractionOrientedBuiding}
Consider the graphical oriented building set of a directed graph~$D$ of~Exam\-ple~\ref{exm:graphicalOrientedBuildingSet}, and a tube~$t$ in a tubing\,$T$\,of\,$L(D)$.
The oriented building set\,$(\building(L(D)), \OM(D))_{t \in T}$ is the graphical oriented building set of the directed graph obtained as the contraction in the restriction~$D_{|t}$ of all arcs contained in some tube~$s \in T$ with~$s \subsetneq t$.
\end{example}

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

%\pagebreak
\subsection{Acyclic nested complexes}
\label{subsec:acyclicNestedComplexes}

%Using \cref{def:restrictionContractionOrientedBuilding}, we define the acyclic nested complex of an oriented building set.

%We denote~$\bigcup \nested \eqdef N_1 \cup \dots \cup N_k$ for~$\nested \eqdef \{N_1, \dots, N_k\}$.

%\begin{lemma}
%\label{lem:characterizationAcyclicNestedSets}
%The following conditions are equivalent for a nested set~$\nested$~on~$\building$:
%\begin{enumerate}[(i)]
%\item $\restrOM$ is acyclic for every~$B \in \nested$,
%\item $\OM_{\!/\bigcup \nested'}$ is acyclic for every~$\nested' \subseteq \nested$,
%\item $\bigcup \nested'$ is a face of $\OM$ for every~$\nested' \subseteq \nested$,
%\item there is no~$c \in \circuits[\OM]$ and~$B \in \nested$ with~$\underline{c} \subseteq B$ such that~$\restrGround$ intersects~$c_+$~but~not~$c_-$,
%\item there is no~$c \in \circuits[\OM]$ and~$\nested' \subseteq \nested$ with~$c_+ \subseteq \bigcup \nested'$ while~$c_- \not\subseteq \bigcup \nested'$,
%% \item $\complRestrGround$ is a face of $M_{|B}$ for each $B\in\nested$.
%\end{enumerate}
%We then say that~$\nested$ is \defn{acyclic} for~$\OM$.
%\end{lemma}
%
%\begin{proof}
%\vincent{todo: write details.}
%\end{proof}

\begin{definition}
\label{def:acyclicNestedComplex}
The \defn{acyclic nested complex} of an oriented building set~$(\building, \OM)$ is the simplicial complex~$\acyclicNestedComplex(\building, \OM)$ whose faces are~$\nested \ssm \connectedComponents(\building)$ for all nested sets~$\nested$ of~$\building$ such that $\restrOM$ is acyclic for every~$B \in \nested$.
\end{definition}

\begin{remark}
\label{rem:trivialCases}
Observe that:
\begin{compactitem}
\item For any building set~$\building$ on~$\ground$, the nested complex~$\nestedComplex(\building)$ is the acyclic nested complex~$\acyclicNestedComplex(\building, \c{I})$, where~$\c{I}$ is the independent (\ie no circuit) oriented matroid~on~$\ground$.
\item If~$\OM$ is not acyclic, then the acyclic nested complex~$\acyclicNestedComplex(\building, \OM)$ is empty.
\item If~$\OM$ contains a circuit~$c = (c_+, c_-)$ with~$|c_-| = 1$, then~$\acyclicNestedComplex(\building, \OM)$ is isomorphic to~$\acyclicNestedComplex(\building_{|\ground \ssm \{s\}}, \OM_{|\ground \ssm \{s\}})$.
\end{compactitem}
\end{remark}

\begin{example}
\label{exm:graphicalAcyclicNestedComplex}
From \cref{exm:graphicalOrientedBuildingSet}, consider a directed graph~$D$ and its graphical oriented building set~$(\building(L(D)), \OM(D))$.
%
\begin{figure}[b]
	\capstart
	\centerline{\includegraphics[scale=.45]{acyclicNestedComplexes}}
	\caption{Two graphical acyclic nested complexes. For each one, we have drawn the directed graph~$D$, its line graph~$L(D)$ with vertices colored black and white according to the sign of the corresponding arcs in the only circuit of~$D$, and all tubings of~$L(D)$ labeling the faces of the graph associahedron, colored green if acyclic and red if cyclic.}
	\label{fig:acyclicNestedComplexes}
\end{figure}
%
The \defn{graphical acyclic nested complex}~$\acyclicNestedComplex(\building(L(D)), \OM(D))$ is then given by all tubings~$T$ on~$L(D)$ such that for each tube~$t \in T$, the contraction in the restriction~$D_{|t}$ of all arcs contained in some tube~$s \in T$ with~$s \subsetneq t$ yields an acyclic directed graph.
\cref{fig:acyclicNestedComplexes} illustrates two graphical acyclic nested complexes.
Note that these two directed graphs have the same line graph, but distinct graphical oriented matroids, and thus distinct graphical acyclic nested complexes.
\end{example}

\begin{remark}
\label{rem:posetAssociahedra}
It follows from \cref{rem:trivialCases} that the graphical acyclic nested complex of~$D$~is
\begin{compactitem}
\item isomorphic to the classical nested complex of the line graph~$L(D)$ when~$D$ is an oriented forest (for instance, it is isomorphic to the simplicial permutahedron if~$D$ is a star, and to the simplicial associahedron if~$D$ is a path),
\item empty if~$D$ is cyclic (\ie has an oriented cycle),
\item isomorphic to the graphical acyclic nested complex of the Hasse diagram of the transitive closure of~$D$ if~$D$ is acyclic.
\end{compactitem}
Hence, graphical acyclic nested complexes are in fact intrinsically associated to posets.
The graphical case of \cref{exm:graphicalOrientedBuildingSet,exm:graphicalAcyclicNestedComplex} actually motivated \cref{def:orientedBuilding,def:acyclicNestedComplex}, and was inspired from the poset associahedra defined in~\cite{Galashin}.
The following statement can serve as definition of poset associahedra, which we omit here for space reason.
\end{remark}

\begin{proposition}
\label{prop:posetAssociahedra}
The poset associahedron of a finite poset~$P$ defined in~\cite{Galashin} is isomorphic to the graphical acyclic nested set of the Hasse diagram of~$P$.
\end{proposition}

We note that affine poset associahedra of~\cite{Galashin} are also acyclic nested complexes of certain specific oriented building sets, although their definition is slightly more intricate.

%\begin{remark}
%\label{rem:reduction}
%Observe that if~$\OM$ has a circuit~$c = (c_+, c_-)$ with 
%\begin{itemize}
%\item $c_- = \varnothing$ (\ie $\OM$ is not acyclic), then~$\acyclicNestedComplex(\building, \OM)$ is empty,
%\item $c_- = \{s\}$, then~$\acyclicNestedComplex(\building, \OM)$ is isomorphic to~$\acyclicNestedComplex(\building_{|\ground \ssm \{s\}}, \OM_{|\ground \ssm \{s\}})$.
%\end{itemize}
%We can thus restrict our attention to the case where~$|c_+| > 1$ and~$|c_-| > 1$ for any circuit~$c$ of~$\OM$.
%\end{remark}

%We now describe the links in the acyclic nested complex~$\acyclicNestedComplex(\building, \OM)$.
%Note that here is a place where it is very convenient to consider that the connected components of~$\building$ belong to any nested set on~$\building$.

%We conclude with the description of links in acyclic nested complexes.
%
%\begin{proposition}
%\label{prop:linksAcyclicNestedComplex}
%The link of an acyclic nested set~$\nested$ in the acyclic nested complex~$\acyclicNestedComplex(\building, \OM)$ is the join of the acyclic nested complexes~$\acyclicNestedComplex(\restrBuilding, \restrOM)$ for all~$B \in \nested$.
%\end{proposition}

%\begin{proof}
%\vincent{todo}
%\end{proof}

%We now state the analogue of \cref{prop:disconnectedNestedComplex} for acyclic nested complexes.
%
%\begin{proposition}
%\label{prop:disconnectedAcyclicNestedComplex}
%If $(\building,\OM)$ is an oriented building set on~$\ground$ with~$|\connectedComponents(\building)| = k$, then $\acyclicNestedComplex(\building \cup \{\ground\},\OM)$ is isomorphic to~$\acyclicNestedComplex(\building,\OM) \join \partial(\triangle_{k-1})$, where~$\triangle_{k-1}$ denotes the $(k-1)$-dimensional simplex.
%\end{proposition}
%
%\begin{proof}
%From \cref{prop:disconnectedNestedComplex}, the nested~$\nestedComplex(\building \cup \{\ground\})$ is isomorphic to the join~$\nestedComplex(\building) \join \partial(\triangle_{k-1})$
%Consider a nested set~$\nested$ on~$\building \cup \{\ground\}$, and the corresponding nested set~$\bar\nested \eqdef \big( \nested \cup \connectedComponents(\building) \big) \ssm \{\ground\}$ on~$\building$.
%For any circuit~$c \in \circuits[\OM]$, we imposed in \cref{def:orientedBuilding} that~$\underline{c} \in \building$, which implies that~$\underline{c}$ is contained in one of the connected components of~$\building$ by maximality.
%Hence, by \cref{lem:characterizationAcyclicNestedSets}\,(v), we obtain that~$\nested$ is acyclic for~$\OM$ if and only if~$\bar\nested$ is acyclic for~$\OM$.
%\end{proof}
%
%We now consider with a little more care the maximal acyclic nested sets, which will be important in our proof of \cref{thm:acyclonestohedron}.
%
%\begin{proposition}
%\label{prop:rank1}
%If~$\nested$ is a maximal acyclic nested set of~$(\building, \OM)$, then~$\restrOM$ has rank~$1$ for any~$B \in \nested$.
%\end{proposition}

%\begin{proof}
%Assume by contradiction that~$\restrOM$ has rank larger than~$1$ for some~$B \in \nested$.
%Hence, it admits a proper positive cocircuit~$c^*$ with~$\varnothing \ne c^*_+ \ne \restrGround$ (consider any facet of~$\restrOM$).
%Define
%\[
%\nested' \eqdef \nested \cup \connectedComponents(\set{B' \in \building}{B' \subseteq B \ssm c^*_+}).
%\]
%We claim that
%\begin{enumerate}[(i)]
%\item $\nested \subsetneq \nested'$, since~$\varnothing \ne c^*_+ \ne \restrGround$.
%\item $\nested'$ is a nested set of~$\building$. Indeed,
%	\begin{itemize}
%	\item Any~$B', B'' \in \nested$ (resp.~$B', B'' \in \nested' \ssm \nested$) are clearly nested or disjoint since they belong to a nested set (resp.~since they are connected components of a building set). Consider now~$B' \in \nested$ and~$B'' \in \nested' \ssm \nested$. Since~$B$ and~$B'$ belong to the nested set~$\nested$, they are nested or disjoint. If~$B \subseteq B'$, then~$B'' \subset B'$. If~$B' \subsetneq B$, then~$B' \subseteq B \ssm c^*_+$, so that~$B' \subseteq B''$ or~$B' \cap B'' = \varnothing$. Otherwise, $B' \cap B = \varnothing$, thus~$B' \cap B'' = \varnothing$.
%	\item Consider~$k \ge 2$ pairwise disjoint~$B_1, \dots, B_k$ in~$\nested'$. If they all belong to~$\nested$, then ${B_1 \cup \dots \cup B_k} \notin \building$. Otherwise, let~$B_j \in \nested' \ssm \nested$. If~$I = \set{i \in [k]}{B_i \not\subseteq B} \ne \varnothing$, then~$B \cup B_1 \cup \dots \cup B_k = B \cup \bigcup_{i \in I} B_i \notin \building$ (since~$\nested$ is a nested set) so that~$B_1 \cup \dots \cup B_k \notin \building$ (since~$\building$ is a building set and~$B \cap B_j \ne \varnothing$). If~$I = \varnothing$, then $B_1 \cup \dots \cup B_k \notin \building$ by maximality of~$B_j$.
%	\item $\nested'$ contains~$\nested$ which contains~$\connectedComponents(\building)$.
%	\end{itemize}
%\item $\nested'$ is still acyclic for~$\OM$. Indeed,
%	\begin{itemize}
%	\item For~$B' \in \nested \ssm \{B\}$, we have~$\complRestrGround[B'][\nested'] = \complRestrGround[B'][\nested]$ so that~$\restrOM[B'][\nested'] = \restrOM[B'][\nested]$ is acyclic.
%	\item For~$B' \in \connectedComponents(\set{B' \in \building}{B' \subseteq B \ssm c^*_+})$, we have~$\complRestrGround[B'][\nested'] = \complRestrGround[B][\nested] \cap B'$ so that~$\restrOM[B'][\nested'] = (\restrOM[B][\nested])_{|B'}$ is acyclic since~$ \restrOM[B][\nested]$ is.
%	\item As circuits and cocircuits are sign orthogonal and~$c^*$ is a positive cocircuit of~$\restrOM$, $c^*_+ \cap c_+ \ne \varnothing$ implies~$c^*_+ \cap c_- \ne \varnothing$ for any circuit~$c$ of~$\restrOM$, hence for any circuit~$c$ of~$\OM$ with~$\underline{c} \subseteq B$. Since~$\restrGround[B][\nested'] = c^*_+$, we obtain that~$\restrOM[B][\nested]$ is acyclic by \cref{lem:characterizationAcyclicNestedSets}.
%	\end{itemize}
%\end{enumerate}
%This contradicts the maximality of~$\nested$.
%\end{proof}

%\begin{corollary}
%\label{coro:pureAcyclicNestedComplex}
%The acyclic nested complex~$\acyclicNestedComplex(\building, \OM)$ is pure of dimension~$\rank[\OM]-|\connectedComponents(\building)|-1$.
%\end{corollary}

%\begin{proof}
%For a maximal nested set~$\nested$, we have~$\connectedComponents(\building) \subseteq \nested$ and~${\rank[\OM] = \sum_{B \in \nested} \rank[\restrOM] = |\nested|}$ by \cref{prop:rank1}.
%Hence, the corresponding face has cardinality~$|\nested \ssm \connectedComponents(\building)| = \rank[\OM] - |\connectedComponents(\building)|$.
%\end{proof}

%\begin{corollary}
%\label{coro:rank1}
%For any maximal acyclic nested set~$\nested$ of~$(\building, \OM)$, and any~$B \in \nested$, the building set~$\restrBuilding$ on~$\restrGround$ is complete.
%%\begin{itemize}
%%\item $\restrBuilding$ is the complete building set on~$\restrGround$,
%%\item for any~$c \in \OM(B)$, we have~$|c_+ \cap \restrGround| = |c_- \cap \restrGround|$.
%%\end{itemize}
%\end{corollary}
%
%\begin{proof}
%Since~$\restrOM$ has rank~$1$ by \cref{prop:rank1}, any two elements~$u,v \in \restrGround$ form a circuit of~$\restrOM$, hence a block of~$\restrBuilding$ by \cref{def:orientedBuilding}.
%Since~$\restrBuilding$ is a building set, we conclude that~$\restrBuilding = 2^{\restrGround}$.
%\end{proof}

%\begin{corollary}
%\label{cor:in_facets}
%Let $\OM$ be an acyclic oriented matroid on~$\ground$, let~$(\building, \OM)$ be a connected oriented building set (\ie $\connectedComponents(\building) = \ground$), and let $\nested$ be a maximal acyclic nested set.
%Then there is a facet~$F$ of~$\OM$ such that the inclusion maximal elements of $\nested\ssm \ground$ are the connected components of $\OM_{|F}$.
%\end{corollary}
%
%\begin{proof}
%As $\building$ is connected, $\ground \in \building$. We have that $\restrOM[\ground]$ is acyclic and of rank~$1$ by \cref{prop:rank1}, which is equivalent to saying that $\complRestrGround[\ground]$ indexes a facet of~$\OM$.
%\vincent{Don't understand that...}
%\end{proof}

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

\subsection{Stellar subdivisions}
\label{subsec:stellarSubdivisions}

We now show that the acyclic nested complex of any oriented building set (realizable or not) is always the face lattice of an oriented matroid, hence a topological sphere \cite[Thm.~4.3.5]{BjornerLasVergnasSturmfelsWhiteZiegler}.
The main tool here is that of stellar subdivisions.

\begin{definition}
For a cell~$\cell$ in a regular cell complex $\CW$, the \defn{stellar subdivision} $\sd(\CW,\cell)$ is the cell complex obtained by gluing the cone~$s \join \left(\cstar(\cell,\CW) \ssm \ostar(\cell,\CW) \right)$ to~${\CW\ssm \ostar(\cell,\CW)}$ along~$\cstar(\cell,\CW) \ssm \ostar(\cell,\CW)$, where $s$ is a new vertex, and $
\ostar(\cell,\CW) \eqdef \set{\tau\in\CW}{\sigma\subseteq \tau}$ is the star of~$\sigma$ and~$\cstar(\cell,\CW) \eqdef \set{\rho\in\CW}{\rho\subseteq \tau\text{ for some }\tau\in \ostar(\sigma,\CW)}$ is its closure.
\end{definition}

\begin{proposition}[{\cite[Prop.~9.2.3 \& Sect.~7.2]{BjornerLasVergnasSturmfelsWhiteZiegler}}]
\label{prop:stellarSubdivisionOrientedMatroid}
Let $\OM$ be an acyclic oriented matroid with ground set~$\ground$, and $F$ be one of its proper faces.
Then the face lattice of the stellar subdivision~$\sd(\Delta(\OM),F)$ is isomorphic to the face lattice of an oriented matroid on~$\ground \cup \{F\}$ (this oriented matroid is not unique, but its face lattice is).
Moreover, this oriented matroid can be chosen to be realizable when~$\OM$ is realizable.
\end{proposition}

\begin{theorem}
\label{thm:orientedMatroidRealizationStellarSubdivisions}
For any oriented building set~$(\building, \OM)$ (realizable or not), the acyclic nested complex~$\acyclicNestedComplex(\building, \OM)$ is the face lattice of an oriented matroid, obtained by stellar subdivisions~of~$\OM$. % of rank $\rank[\OM]-|\connectedComponents(\building)|-1$.
\end{theorem}

\begin{corollary}
\label{coro:polytopalRealizationStellarSubdivisions}
For any realizable oriented building set~$(\building, \OM(\b{A}))$, the acyclic nested complex $\acyclicNestedComplex(\building, \OM(\b{A}))$ is isomorphic to the boundary complex of a convex polytope, obtained by stellar subdivisions of the positive tope of~$\b{A}$.
\end{corollary}

\begin{example}
In the graphical situation discussed in \cref{exm:graphicalOrientedBuildingSet,exm:graphicalAcyclicNestedComplex,rem:posetAssociahedra,prop:posetAssociahedra}, we obtain that the poset associahedron of a poset~$P$ can be realized as a stellar subdivision of the order polytope of~$P$, thus recovering the construction of~\cite{Galashin}.
\end{example}

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

\newpage
\subsection{Acyclonestohedra}
\label{subsec:acyclonestohedra}

We now consider a realizable oriented building set~$(\building, \OM(\b{A}))$.
From \cref{coro:polytopalRealizationStellarSubdivisions}, we know that the acyclic nested complex~$\acyclicNestedComplex(\building, \OM(\b{A}))$ is realizable as a polytope by stellar subdivisions of the positive tope of~$\b{A}$.
However, this non-explicit approach does not allow any control on the coordinates of the realizations.
In this section, we obtain explicit polytopal realizations with controlled integer coordinates, using sections of nestohedra.

\begin{definition}
As each~$c \in \circuits$ is the signature of a unique (up to rescaling) linear dependence~$\b{\delta} \in \dependences$, we define~$r_c \eqdef \max \b{\delta}^{\ne 0} / \min \b{\delta}^{\ne 0}$ where~${\b{\delta}^{\ne 0} \eqdef \set{|\delta_s|}{s \in \ground} \ssm \{0\}}$ and~$R \eqdef |\building| \cdot \max_{c \in \circuits} r_c$.
We then define~$\b{\rho} \eqdef (\rho_B)_{B \in \building} \in \R^\building_+$ by~$\rho_B \eqdef 0$ if~$|B| = 1$ and~$\rho_B \eqdef \smash{R^{|B|}}$ if~${|B| \ge 2}$. 
\end{definition}

We use these coefficients~$\b{\rho} \in \R^\building_+$ to define two polytopes~$\Acycl(\building, \b{A})$ and~$\AcyclProj(\building, \b{A})$ that we both call \defn{acyclonestohedra}.
While these two polytopes are affinely equivalent, the first is more natural for our construction, but the second has the advantage to live in the right dimensional space.

\begin{definition}
\label{def:acyclonestohedron}
The \defn{acyclonestohedron}~$\Acycl(\building, \b{A})$ is the polytope in~$\R^\ground$ defined as the intersection of the nestohedron $\Nest(\building, \b{\rho})$ with the evaluation space~$\evaluations$~of~$\b{A}$.
\end{definition}

\begin{definition}
\label{def:acyclonestohedronProj}
The \defn{acyclonestohedron}~$\AcyclProj(\building, \b{A})$ is the polytope of~$\R\b{A}$ defined by the equalities~$\overline{g}_B(\b{y}) = 0$ for all~$B \in \connectedComponents(\building)$ and the inequalities~$\overline{g}_B(\b{y}) \ge 0$ for all~$B \in \building$, where
\[
\overline{g}_B(\b{y}) \eqdef \bigdotprod{\sum_{b \in B} \b{a}_b}{\b{y}} - \sum_{B' \in \building, \; B' \subseteq B} \rho_{B'}.
\]
\end{definition}

\begin{proposition}
The acyclonestohedron~$\Acycl(\building, \b{A}) \subset \R^\ground$ of \cref{def:acyclonestohedron} and the acyclonestohedron~$\AcyclProj(\building, \b{A}) \subset \R\b{A}$ of \cref{def:acyclonestohedronProj} are affinely equivalent.
\end{proposition}

\begin{theorem}
\label{thm:acyclonestohedron}
For any realizable oriented building set~$(\building, \OM(\b{A}))$, the acyclic nested complex $\acyclicNestedComplex(\building, \OM(\b{A}))$ is isomorphic to the boundary complex of the polar of the acyclonestohedron~$\Acycl(\building, \b{A})$ (or equivalently of~$\AcyclProj(\building, \b{A})$).
\end{theorem}

\begin{remark}
Following \cref{rem:trivialCases}, note that if~$\b{A}$ is linearly independent, then its evaluation space~$\evaluations$ is~$\R^S$, and the acyclonestohedra~$\Acycl(\building, \b{A})$ and~$\AcyclProj(\building, \b{A})$ both coincide with the classical nestohedron~$\Nest(\building, \b{\rho})$.
For instance, the acyclonestohedron of the graphical oriented building set of an oriented forest~$D$ is the graph associahedron~of~$L(D)$ (for instance, a permutahedron if~$D$ is a star, and an associahedron if~$D$~is~a~path).
\end{remark}

\begin{example}
\label{exm:acyclonestohedron}
Specializing \cref{def:acyclonestohedron,def:acyclonestohedronProj,thm:acyclonestohedron} to the graphical situation discussed in \cref{exm:graphicalOrientedBuildingSet,exm:graphicalAcyclicNestedComplex,rem:posetAssociahedra,prop:posetAssociahedra}, we obtain that the poset associahedron of a poset~$P$ with Hasse diagram~$D$ is explicitly realized~as
\begin{compactitem}
\item the section of a graph associahedron of the line graph of~$D$ with the linear hyperplanes normal to~$\one_{c_+} - \one_{c_-}$ for all circuits~$c = (c_+, c_-)$~of~$D$, see \cref{fig:acyclonestohedra},
\item the polytope in~$\R^P$ defined by the equality~$\overline{g}_P(\b{y}) = 0$ and the inequalities~$\overline{g}_{\tube}(\b{y}) \ge 0$ for all~$\tube \in \building(\poset$), where
\[
\overline{g}_{\tube}(\b{y}) \eqdef \bigdotprod{\sum_{\substack{p,q \in \tube \\ p \precdot q}} \b{b}_p - \b{b}_q}{\b{y}} - \sum_{\substack{\tube' \in \building(\poset) \\ \tube' \subseteq \tube}} |\building(\poset)|^{|\tube|}.
\]
\end{compactitem}
This answers an open question of~\cite{Galashin}.
During the completion of this paper, we became aware that this question was independently solved in~\cite{Sack}.
The approach of~\cite{Sack} is quite different but leads essentially to the same realization of poset associahedra.
We actually want to acknowledge that we originally only worked with the acyclonestohedron of \cref{def:acyclonestohedron}, and that the affinely equivalent acyclonestohedron of \cref{def:acyclonestohedronProj} was motivated by the approach of~\cite{Sack}.
%
\begin{figure}
	\capstart
	\centerline{\includegraphics[scale=.45]{acyclonestohedra}}
	\caption{The graphical acyclonestohedra (green polygons) realizing the graphical acyclic nested complexes of \cref{fig:acyclicNestedComplexes}, obtained as the section of the line graph of~$L(D)$ by the evaluation space of the graphical oriented matroid of~$D$.}
	\label{fig:acyclonestohedra}
\end{figure}
%
\end{example}

\begin{remark}
To conclude this section, we want to give a vague idea of the proof of \cref{thm:acyclonestohedron}.
As illustrated in \cref{fig:acyclicNestedComplexes,fig:acyclonestohedra}, the main point is that our choice of coefficients~$\b{\rho}$ guaranties that a face of~$\Nest(\building, \b{\rho})$ intersects the evaluation space~$\evaluations$ if and only if the corresponding nested set on~$\building$ is acyclic for~$\OM(\b{A})$.
Note that the coefficients could sometimes be chosen smaller, our exponential choice is just a convenient hammer to kill all small contributions.
For instance, for graphical oriented building sets, the coefficient~$\rho_t$ of a tube~$t$ can in fact be chosen of order~$4^{|t|}$.
\end{remark}


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

\clearpage
\section{Nested complexes of building sets of the face lattice}
\label{sec:acyclonestohedron}

%We finaly relate the acyclic nested complexes of oriented building sets for an oriented matroid~$\OM$ to the nested complexes of building sets over the Las Vergnas face lattice~of~$\OM$, and discuss some consequences of this interpretation.
%
%%%%%%%%%%%%%%%%%
%
%\subsection{Lattice building sets and nested complexes}
%\label{subsec:preliminaries}

Although less popular in the combinatorics community, the original definition of~\cite{FeichtnerKozlov2004} for building sets and their nested complexes depends upon an underlying lattice. % meet semilattice. We recall it here for lattices as we will only use it in this case.

% The original definition of~\cite{FeichtnerKozlov2004} for building sets and their nested complexes depends upon an underlying meet semilattice. The case of the Boolean lattice is the one that has been more popular in the combinatorics community, to the point that it is often the only one presented, like in \cref{def:building,def:nested}.
% We recall it here for lattices as we will only use it in this case.

\begin{definition}[\cite{FeichtnerKozlov2004, FeichtnerSturmfels}]
\label{def:latticeBuilding}
A subset~$\building$ of a finite lattice~$\lattice$ is a \defn{$\lattice$-building set} if the lower interval of any element~$x \in \lattice$ is the direct product of the lower intervals of the maximal elements of~$\building$ below~$x$.
%We note in particular that $\building$ must contain all \defn{atoms} of~$\lattice$ (\ie all elements covering~$\botzero$).
We denote by~$\connectedComponents(\building) \eqdef \max(\building)$ the set of \defn{$\building$-connected components}.
% (\ie maximal elements of~$\building$).
%, and we say that $\building$ is \defn{connected} if $\connectedComponents(\building)=\{\ground\}$.
\end{definition}

\begin{definition}[\cite{FeichtnerKozlov2004, FeichtnerSturmfels}]
\label{def:latticeNested}
Let~$\building$ be an $\lattice$-building set.
An \defn{$\lattice$-nested set} $\nested$ on~$\building$ is a subset of~$\building$ containing~$\connectedComponents(\building)$ and such that for any $k\geq 2$  pairwise incomparable elements $B_1,\dots,B_k\in\nested$, the join $B_1\vee \cdots \vee B_k$ does not belong to $\building$.
%
The \defn{$\lattice$-nested complex} of~$\building$ is the simplicial complex~$\nestedComplex_\lattice(\building)$ whose faces are $\nested \ssm \connectedComponents(\building)$ for all $\lattice$-nested sets~$\nested$ on~$\building$.
\end{definition}

%We will use this $\lattice$-building and $\lattice$-nested sets on face lattices of oriented matroids.
%
%\begin{definition}
%\label{def:LasVergnasFaceLattice}
%Let $\OM$ be an acyclic oriented matroid. A set $F\subseteq \ground$ is a \defn{face} of $\OM$ if it is the complement of a non-negative covector, \ie $(\ground\ssm F,\varnothing)\in\covectors[\OM]$.
%%\end{definition}
%%
%%\begin{definition}
%The \defn{Las Vergnas face lattice} $\FL(\OM)$ is the poset of faces of $\OM$ ordered by~inclusion.
%\end{definition}

\begin{example}
\label{exm:boolean}
If $\lattice$ is the boolean lattice on~$\ground$, then the $\lattice$-building sets are the building sets on~$\ground$ of \cref{def:building} and the $\lattice$-nested sets are the nested sets of \cref{def:nested}.
\end{example}

We will use these definitions over the Las Vergnas face lattice~$\FL(\OM)$ of the oriented matroid~$\OM$, see \cref{def:LasVergnasFaceLattice}. We first select the facial part of an oriented building set.

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

%\subsection{Facial building sets and facial nested complexes}
%\label{subsec:facialBuildingSetsNestedComplexes}

%For any acyclic oriented matroid~$\OM$, we now show that 
%%the oriented building sets~$(\building,\OM)$ of \cref{def:orientedBuilding} essentially coincide with the $\FL(\OM)$-building sets \cref{def:latticeBuilding,def:LasVergnasFaceLattice}, and that the acyclic nested complexes~$\acyclicNestedComplex(\building,\OM)$ of~\cref{def:acyclicNestedComplex} coincide with the $\FL(\OM)$-nested complexes of \cref{def:latticeNested}.
%\begin{compactitem}
%\item the oriented building sets~$(\building,\OM)$ of \cref{def:orientedBuilding} essentially coincide with the $\FL(\OM)$-building sets \cref{def:latticeBuilding,def:LasVergnasFaceLattice},
%\item the acyclic nested complexes~$\acyclicNestedComplex(\building,\OM)$ of~\cref{def:acyclicNestedComplex} coincide with the $\FL(\OM)$-nested complexes of \cref{def:latticeNested}.
%\end{compactitem}
%For this, we need to select the facial part of an oriented building set.

\begin{definition}
The \defn{facial building set} $\fbuilding$ of an oriented building set $(\building,\OM)$ is the set of blocks~${B \in \building}$ that are also faces of~$\OM$.
%We will directly say that $\fbuilding$ is a \defn{facial building set} of~$\OM$ without necessarily specifying $\building$.
\end{definition}

\begin{theorem}
\label{thm:facialBuildingSetAreLasVergnasLatticeBuildingSets}
The facial building sets of~$\OM$ coincide with the $\FL(\OM)$-building sets. % of the Las Vergnas lattice of~$\OM$.
\end{theorem}

\begin{definition}
%Let~$\fbuilding$ be a facial building set of an oriented matroid~$\OM$.
%A \defn{facial nested set} on~$\fbuilding$ is an $\FL(\OM)$-nested set on~$\fbuilding$.
The \defn{facial nested complex}~$\nestedComplex_{\FL(\OM)}(\fbuilding)$ is the $\FL(\OM)$-nested complex~of~$\fbuilding$.
\end{definition}

\begin{theorem}
\label{thm:acyclicNestedComplexesAreLatticeNestedComplexes}
Let $\fbuilding$ be the facial building set of an oriented building set~$(\building,\OM)$. Then the acyclic nested complex $\acyclicNestedComplex(\building, \OM)$ and the facial nested complex $\nestedComplex_{\FL(\OM)}(\fbuilding)$ coincide.
\end{theorem}

\begin{example}
If~$\OM$ is independent (\ie no circuit), then its positive tope is a simplex, its Las Vergnas face lattice is boolean, so that we are in the classical situation of \cref{exm:boolean}.
\end{example}

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

%\subsection{Consequences}
%\label{subsec:consequences}

We conclude with a few remarks in light of \cref{thm:facialBuildingSetAreLasVergnasLatticeBuildingSets,thm:acyclicNestedComplexesAreLatticeNestedComplexes}.
First, we observe that this interpretation actually recovers the results of \cref{subsec:stellarSubdivisions}. Namely,
\begin{compactitem}
\item \cite[Cor.~4.3]{FeichtnerMuller2005} proved that the nested complex of a finite atomic meet-semilattice is homeomorphic to its order complex. Since the face lattices of oriented matroids encode face lattices of regular cell decompositions of spheres \cite[Thm.~4.3.5]{BjornerLasVergnasSturmfelsWhiteZiegler}, their order complexes are the face lattices of the barycentric subdivisions of these spheres.
\item The stellar subdivisions of \cref{thm:orientedMatroidRealizationStellarSubdivisions} are actually oriented matroid realizations of the combinatorial blowups of~\cite[Thm.~3.4]{FeichtnerKozlov2004} on face lattices of oriented matroids.
\end{compactitem}
In turn, our acyclonestohedra of \cref{subsec:acyclonestohedra} provide explicit polytopal realizations with integer coordinates for the $\FL(\OM)$-nested complexes over \mbox{realizable matroids.\,To\,sum\,up:}

\begin{corollary}
Any\,$\FL(\!\!\;\OM\!\!\;)$-nested\,complex\,of\,any\,$\FL(\!\!\;\OM\!\!\;)$-building\,set\,over\,the\,face\,lattice~$\FL(\!\!\;\OM\!\!\;)$ of an acyclic oriented matroid~$\OM$ is the face lattice of an oriented matroid obtained by stellar subdivisions of the positive tope of~$\OM$.
When~$\OM$ is realizable, it can be realized as a polytope either by realizing these stellar subdivisions polytopaly, or as the polar of a section of a nestohedron.
\end{corollary}

 \newpage
 \section{Compactifications}
\label{sec:compactifications}

Galashin's main motivation for defining poset associahedra was that they model compactifications of the space of order preserving maps $P\to \R$, which can be identified with the interior of an order polytope.
In fact, the connection above reveals that all acyclonestohedra are associated to nice compactifications of interiors of polytopes, via~\cite{Gaiffi2003}.

\begin{theorem}[\cite{Gaiffi2003}]
Consider a realizable oriented building set~$(\building, \OM(\b{A}))$, and let $P$ be the polytope associated to the positive tope.
Then there is a compactification $P^\building$ of the interior of~$P$ that is a stratified $C^\infty$ manifold with corners such that
\begin{compactenum}[(i)]
 \item except for the open dense stratum, all the strata lie in the boundary,
 \item the codimension~$1$ strata are in correspondence with the facial blocs of $\fbuilding$,
 \item the intersection of the closures of the strata indexed by a subset $ \nested\subseteq\fbuilding$ is non empty if and only if $\nested$ is a $\FL(\OM)$-nested set,
 \item the strata of $P^\building$ can be indexed by the faces of the acyclic nested complex~$\acyclicNestedComplex(\building, \OM(\b{A}))$.
\end{compactenum}
\end{theorem}


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

%% 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}
