%% 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]{FPSAC2018}
\articlenumber{15}
%% 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}
\usepackage{paralist}
\usepackage{overpic}
\usepackage{blkarray}
\graphicspath{{figures/}}

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

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{question}[theorem]{Question}

% 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{\fA}{\mathfrak{A}} % alternating group
\newcommand{\fS}{\mathfrak{S}} % symmetric group
\newcommand{\cA}{\mathcal{A}} % algebra
\newcommand{\cC}{\mathcal{C}} % collection
\newcommand{\cH}{\mathcal{H}} % hyperplane arrangement
\newcommand{\cX}{\mathcal{X}} % vectors
\newcommand{\rmX}{{\rm X}} % X
\renewcommand{\b}[1]{\mathbf{#1}} % bold letters
\newcommand{\h}{\widehat} % hat letters

% math commands
\newcommand{\set}[2]{\left\{ #1 \;\middle|\; #2 \right\}} % set notation
\newcommand{\setangle}[2]{\left\langle #1 \;\middle|\; #2 \right\rangle} % set notation
\newcommand{\bigset}[2]{\big\{ #1 \;\big|\; #2 \big\}} % big set notation
\newcommand{\biggset}[2]{\bigg\{ #1 \;\bigg|\; #2 \bigg\}} % bigg set notation
\newcommand{\ssm}{\smallsetminus} % small set minus
\newcommand{\dotprod}[2]{\left\langle \, #1 \, \middle| \, #2 \, \right\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{\eqdef}{\mbox{\,\raisebox{0.2ex}{\scriptsize\ensuremath{\mathrm:}}\ensuremath{=}\,}} % :=
\newcommand{\defeq}{\mbox{~\ensuremath{=}\raisebox{0.2ex}{\scriptsize\ensuremath{\mathrm:}} }} % =:
\newcommand{\polar}{^\diamond} % polar
\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{\inv}{inv} % inversions
\DeclareMathOperator{\des}{des} % descents

% polytopes
\newcommandx{\Perm}[2][1=\B_\circ]{\mathsf{Perm}^{#2}(#1)} % permutahedron
\newcommandx{\Zono}[2][1=\B_\circ]{\mathsf{Zono}^{#2}(#1)} % zonotope
\newcommandx{\Asso}[2][1=\B_\circ]{\mathsf{Asso}^{#2}(#1)} % associahedron
\newcommandx{\UnivAsso}[2][1=\B_\circ]{\mathsf{Asso}_{\mathrm{un}}^{#2}(#1)} % universal associahedron
\newcommand{\Para}[2][1=\B_\circ]{\mathsf{Para}^{#2}(#1)} % parallelepiped
\DeclareMathOperator{\face}{\mathbf{F}} % face of the permutahedron
\newcommand{\Fan}{\mathcal{F}} % fan
\newcommand{\Cone}{\mathrm{C}} % cone
\newcommand{\Face}{\mathrm{F}} % face

% triangulations
\newcommand{\polygon}{\Omega} % polygon
\newcommand{\triangulation}{\mathrm{T}} % triangulation
\newcommand{\diagonals}{\Delta} % diagonals of a triangulation
\newcommand{\fanTriangulation}{\mathrm{F}} % fan triangulation
\newcommand{\quadrangulation}{\mathrm{Q}} % quadrilateral
\newcommand{\dissection}{\mathrm{D}} % dissection
\newcommand{\cell}{\mathrm{C}} % cell in triangulation
\newcommand{\quadrilateral}{\mathrm{Q}} % quadrilateral in a triangulation
\newcommand{\accordion}{\mathrm{A}} % accordion in a triangulation
\newcommand{\zigzag}{\mathrm{Z}} % zigzag
\newcommand{\snake}{\reflectbox{$\mathrm{Z}$}} % snake
\newcommand{\tree}{\mathrm{T}} % tree

% signatures
\newcommand{\sign}[3]{\varepsilon({#1} \!\in\! {#2}, {#3})} % sign
\newcommand{\bigsign}[3]{\varepsilon \big( {#1} \!\in\! {#2}, {#3} \big)} % sign
\newcommand{\SSS}{\reflectbox{$\mathsf{Z}$}} % S
\newcommand{\sss}{\reflectbox{\tiny$\mathsf{Z}$}} % S
\newcommand{\ZZZ}{\mathsf{Z}} % Z
\newcommand{\zzz}{\text{\tiny$\mathsf{Z}$}} % Z
\newcommand{\VVV}{{\mathsf{{V \hspace{-.1686cm} I\,}}}} % V
\newcommand{\signature}{\varepsilon} % signature

% g-vectors
\newcommand{\gvector}[2]{\mathbf{g}(#1, #2)} % g-vector of the cluster variable #2 with respect to the initial cluster #1
\newcommand{\biggvector}[2]{\mathbf{g} \big( #1, #2 \big)} % g-vector of the cluster variable #2 with respect to the initial cluster #1
\newcommand{\gvectors}[2]{\mathbf{g}(#1, #2)} % g-vectors of the cluster #2 with respect to the initial cluster #1
\newcommand{\biggvectors}[2]{\mathbf{g} \big( #1, #2 \big)} % g-vectors of the cluster  #2 with respect to the initial cluster #1
\newcommandx{\gvectorFan}[1][1=\B_\circ]{\mathcal{F}^\mathbf{g}(#1)} % g-vector fan
\newcommandx{\UnivgvectorFan}[1][1=\B_\circ]{\mathcal{F}_{\mathrm{un}}^\mathbf{g}(#1)} % g-vector fan
\newcommand{\bg}[1]{\mathbf{g}(#1)}

% c-vectors
\newcommand{\cvector}[3]{\mathbf{c}(#1, #3 \in #2)} % c-vector of the cluster variable #3 in the cluster #2 with respect to the initial cluster #1
\newcommand{\bigcvector}[3]{\mathbf{c} \big( #1, #3 \in #2 \big)} % c-vector of the cluster variable #3 in the cluster #2 with respect to the initial cluster #1
\newcommand{\cvectors}[2]{\mathbf{c}(#1, #2)} % c-vectors of the cluster #2 with respect to the initial cluster #1
\newcommand{\bigcvectors}[2]{\mathbf{c} \big( #1, #2 \big)} % c-vectors of the cluster #2 with respect to the initial cluster #1
\newcommand{\allcvectors}[1]{\mathbf{C}(#1)} % all c-vectors with respect to the initial cluster #1
\newcommandx{\cvectorFan}[1][1=\B_\circ^\vee]{\mathcal{F}^\mathbf{c}(#1)} % c-vector fan
\newcommandx{\CoxeterFan}[1][1=\B_\circ^\vee]{\mathcal{F}^\mathbf{Cox}(#1)} % Coxeter fan

% u-vectors
\newcommand{\uvector}[3]{\mathbf{u}(#1, #3 \in #2)} % u-vector of the cluster variable #3 in the cluster #2 with respect to the initial cluster #1
\newcommand{\biguvector}[3]{\mathbf{u} \big( #1, #3 \in #2 \big)} % u-vector of the cluster variable #3 in the cluster #2 with respect to the initial cluster #1

% rhs
\newcommand{\rhs}[1]{k(#1)} % right hand side of zonotope

% points, hyperplanes, halfspaces
\newcommand{\point}[3]{\mathbf{p}^{#3}(#1, #2)} % vertex of the #1-associahedron corresponding to the cluster #2
\newcommand{\bigpoint}[3]{\mathbf{p}^{#3} \big( #1, #2 \big)} % vertex of the #1-associahedron corresponding to the cluster #2
\newcommand{\Univpoint}[3]{\mathbf{p}_{\mathrm{un}}^{#3}(#1, #2)} % vertex of the #1-associahedron corresponding to the cluster #2
\newcommand{\Univbigpoint}[3]{\mathbf{p}_{\mathrm{un}}^{#3} \big( #1, #2 \big)} % vertex of the #1-associahedron corresponding to the cluster #2
\newcommand{\HS}[3]{\mathbf{H}_{\le}^{#3}(#1, #2)} % half space
\newcommand{\bigHS}[3]{\mathbf{H}_{\le}^{#3} \big( #1, #2 \big)} % half space
\newcommand{\Hyp}[3]{\mathbf{H}_{=}^{#3}(#1, #2 )} % hyperplane
\newcommand{\bigHyp}[3]{\mathbf{H}_{=}^{#3} \big( #1, #2 \big)} % hyperplane
\newcommand{\coordSubspace}[1]{\mathbf{H}_{#1}} % coordinate hyperplane
\newcommand{\fix}[1]{\mathrm{Fix}(#1)} % fix space

% cluster algebras
\newcommand{\quiver}{\mathrm{Q}} % quiver
\newcommand{\CoxeterGroup}{\mathrm{W}} % Coxeter group
\newcommand{\mi}{-} % bottom triangulation
\newcommand{\ma}{+} % top triangulation
\newcommand{\B}{\mathrm{B}} % b-matrix
\newcommand{\A}[1]{\mathrm{A}({#1})} % b-matrix
\newcommand{\D}{\mathrm{D}} % symmetrizer
\newcommand{\type}{\mathrm{T}} % type
\newcommand{\ambient}{\Bbbk} % ambient field
\newcommand{\Trop}[1]{\mathbb{P}_{#1}} % tropical semifield
\newcommand{\positiveExponents}[1]{\left\{#1\right\}_+} % positive exponents in tropical semifield
\newcommand{\negativeExponents}[1]{\left\{#1\right\}_-} % negative exponents in tropical semifield
\newcommand{\seed}{\Sigma} % a cluster
\newcommand{\cluster}{\mathrm{X}} % a cluster
\newcommandx{\clusters}{\mathcal{X}} % all clusters
\newcommand{\coefficients}{\mathrm{P}} % a coefficients tuple
\newcommandx{\clusterAlgebra}[2][1=\B_\circ, 2=\coefficients_\circ]{\mathcal{A}(#1,#2)} % cluster algebra
\newcommandx{\clusterComplex}[1][1=\B_\circ]{\Delta(#1)} % cluster complex
\newcommandx{\principalClusterAlgebra}[1][1=\B_\circ]{\mathcal{A}_{\mathrm{pr}}\left(#1\right)} % principal coefficients cluster algebra
\newcommandx{\coefficientFreeClusterAlgebra}[1][1=\B_\circ]{\mathcal{A}_{\mathrm{fr}}(#1)} % coefficient free cluster algebra
\newcommandx{\universalClusterAlgebra}[1][1=\B_\circ]{\mathcal{A}_{\mathrm{un}}(#1)} % principal coefficients cluster algebra
\newcommandx{\clusterVariables}[1][1=\B_\circ]{\mathcal{X}(#1)} % all cluster variables
\newcommandx{\greenMutationsGraph}[1][1=\B_\circ]{\mathcal{G}(#1)} % directed graph of green mutations
\newcommand{\simpleRoot}{\alpha} % simple root
\newcommand{\fundamentalWeight}{\omega} % fundamental weights
\newcommand{\faceCC}{\mathrm{F}} % face of the cluster complex
\newcommand{\F}{h} % the magic F-function that we knew since 10 years
\newcommand{\signDep}[3]{\varepsilon(#1,#2,#3)} % the choice in the dependence
\newcommand{\bigsignDep}[3]{\varepsilon \big( #1,#2,#3 \big)} % the choice in the dependence
\newcommand{\compatibilityDegree}[2]{(\,#1\,\|\,#2\,)} % compatibility degree
\newcommand{\wo}{w_\circ} % longest element

% others
\newcommand{\fref}[1]{Figure~\ref{#1}} % reference figures
\newcommand{\ie}{\textit{i.e.,}~} % id est
\newcommand{\eg}{\textit{e.g.,}~} % exempli gratia
\newcommand{\Eg}{\textit{E.g.}~} % exempli gratia
\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{\apriori}{\textit{a priori}} % a priori
\newcommand{\ordinal}{\textsuperscript{th}} % th for ordinals
\newcommand{\ordinalst}{\textsuperscript{st}} % st for ordinals
\definecolor{darkblue}{rgb}{0,0,0.7} % darkblue color
\newcommand{\darkblue}{\color{darkblue}} % darkblue command
\newcommand{\defn}[1]{\textsl{\darkblue #1}} % emphasis of a definition
\usepackage{lipsum}

%% define your title in the usual way
\title{Universal associahedra}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{
	Christophe
	Hohlweg\thanks{\href{mailto:hohlweg.christophe@uqam.ca}{hohlweg.christophe@uqam.ca}.
	Canadian NSERC Discovery grant {\em Coxeter groups and related structures}.}\addressmark{1},
	\stepcounter{footnote}
	Vincent
	Pilaud\thanks{\href{mailto:vincent.pilaud@lix.polytechnique.fr}{vincent.pilaud@lix.polytechnique.fr}.
	French ANR grant SC3A~(15\,CE40\,0004\,01).}\addressmark{2}, \and
	Salvatore
	Stella\thanks{\href{mailto:stella@math.haifa.ac.il}{stella@math.haifa.ac.il}.
	Marie Curie - Cofund Fellow at INdAM.}\addressmark{3}}

%% then use \addressmark to match authors to institutions here
\address{
	\addressmark{1}LaCIM, Universit\'e du Qu\'ebec \`A Montr\'eal (UQAM) \\
	\addressmark{2}CNRS \& LIX, \'Ecole Polytechnique, Palaiseau \\
	\addressmark{3}University of Haifa
	}

%% 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{
For any finite Dynkin type, we construct a universal associahedron whose normal fan contains all $\b{g}$-vector fans of that type as sections.
}

%% put your French abstract here, or comment this out if you don't have one
\resume{
Pour tout type Dynkin fini, nous construisons un associa\`edre universel
dont l'\'eventail normal contient tous les \'eventails de $\b{g}$-vecteurs de ce type comme sections.
}

%% put your keywords here, or comment this out if you don't have them yet
%\keywords{math, maths, mathematics}

%% 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}
\addbibresource{15-Hohlweg-Pilaud-Stella.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

A \defn{generalized associahedron} is a polytope which realizes the cluster complex of a finite type cluster algebra of S.~Fomin and A.~Zelevinsky~\cite{FominZelevinsky-ClusterAlgebrasI, FominZelevinsky-ClusterAlgebrasII}.
Generalized associahedra were first constructed by F.~Chapoton, S.~Fomin and A.~Zelevinsky~\cite{ChapotonFominZelevinsky} using $\b{d}$-vectors.
Further realizations were obtained by C.~Hohlweg, C.~Lange and H.~Thomas~\cite{HohlwegLangeThomas} using $\b{g}$-vectors.
However, these realizations are limited to the special case when the initial seed is acyclic.
Our first contribution is to lift this constraint.

\begin{theorem*}
For any finite type initial exchange matrix~$\B_\circ$, the $\b{g}$-vector fan~$\gvectorFan$ with respect to~$\B_\circ$ is the normal fan of a generalized associahedron~$\Asso{}$.
\end{theorem*}

When we start from an acyclic initial exchange matrix, our construction precisely recovers the associahedra of~\cite{HohlwegLangeThomas}.
These can all be obtained by deleting inequalities from the facet description of the permutahedron of the corresponding finite reflection group.
The main difficulty to extend this approach to arbitrary initial exchange matrices lies in the fact that this property, intriguing as it might be, is essentially a coincidence.
In fact, the hyperplane arrangement~$\cH$ supporting the $\b{g}$-vector fan is no longer the Coxeter arrangement of a finite reflection group.
%
To overcome this situation, we develop an alternative approach based on a uniform understanding of the linear dependences among adjacent cones in the $\b{g}$-vector fan.
In fact, not only we cover uniformly all finite type $\b{g}$-vector fans, but we actually treat them simultaneously with a universal object.

\begin{theorem*}
\label{thm:universalAssociahedronIntro}
For any given finite Dynkin type~$\Gamma$, there exists a \defn{universal associahedron}~$\UnivAsso[\Gamma]{}$ such that, for any initial exchange matrix~$\B_\circ$ of type~$\Gamma$, the generalized associahedron~$\Asso{}$ is a suitable projection of the universal associahedron~$\UnivAsso[\Gamma]{}$.
In particular, all $\b{g}$-vector fans of type~$\Gamma$ are sections of the normal fan of the universal associahedron~$\UnivAsso[\Gamma]{}$.
\end{theorem*}

See the long version~\cite{HohlwegPilaudStella} of this extended abstract for details and complete proofs.
%This extended abstract summarizes the main results from~\cite{HohlwegPilaudStella}.

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

\section{Type~$A$ universal associahedra from triangulations}

Before addressing the problem in full generality, we illustrate the results in type~$A$ using triangulations of polygons.
We consider $2n+6$ points on the unit circle alternately colored black and white, and let~$\polygon_\circ$ (resp.~$\polygon_\bullet$) denote the convex hull of the white (resp.~black) points.
%
Let~$\triangulation$ be a triangulation of~$\polygon_\circ$ (resp.~of~$\polygon_\bullet$), let~$\delta \in \triangulation$, and let~$\gamma$ be a diagonal of~$\polygon_\bullet$ (resp.~of~$\polygon_\circ$).
When~$\gamma$ crosses~$\delta$, we define~$\sign{\delta}{\triangulation}{\gamma}$ to be $1$, $-1$, or~$0$ depending on whether~$\gamma$ crosses the quadrilateral formed by the two triangles of~$\triangulation$ incident to~$\delta$ as a~$\ZZZ$, as a~$\SSS$, or in a corner.
If~$\gamma$ and~$\delta$ do not cross, then we set~${\sign{\delta}{\triangulation}{\gamma} = 0}$.
The following definition is illustrated in \fref{fig:exmTriangulations}.

\begin{definition}
Fix an arbitrary reference triangulation~$\triangulation_\circ$ of~$\polygon_\circ$.
For a diagonal~$\delta_\bullet$ of~$\polygon_\bullet$, we define the \defn{$\b{g}$-vector} of~$\delta_\bullet$ with respect to~$\triangulation_\circ$ as ${\biggvector{\triangulation_\circ}{\delta_\bullet} \eqdef \big[ \bigsign{\delta_\circ}{\triangulation_\circ}{\delta_\bullet} \big]_{\delta_\circ \in \triangulation_\circ} \in \R^{\triangulation_\circ}}$.
For any diagonal~$\delta_\bullet$ of~$\polygon_\bullet$ and triangulation~$\triangulation_\bullet$ of~$\polygon_\bullet$ with~$\delta_\bullet \in \triangulation_\bullet$, we define the \defn{$\b{c}$-vector} of~$\delta_\bullet \in \triangulation_\bullet$ with respect to~$\triangulation_\circ$ as~$\bigcvector{\triangulation_\circ}{\triangulation_\bullet}{\delta_\bullet} \eqdef \big[ -\bigsign{\delta_\bullet}{\triangulation_\bullet}{\delta_\circ} \big]_{\delta_\circ \in \triangulation_\circ}$.
\end{definition}

\begin{figure}[h]
	\centerline{
	\begin{minipage}{1.1\textwidth}
	\begin{center}
  	\raisebox{-0.5\height}{\includegraphics[scale=1.3]{exmTriangulations}}
	\;
	\raisebox{-0.1\height}{$\begin{blockarray}{cc@{}c@{}c@{}c@{}c}
	& \rotatebox{90}{$2_\bullet 4_\bullet$} & \rotatebox{90}{$2_\bullet 8_\bullet$} & \rotatebox{90}{$4_\bullet 6_\bullet$} & \rotatebox{90}{$4_\bullet 7_\bullet$} & \rotatebox{90}{$4_\bullet 8_\bullet$}  \\
	\begin{block}{c[c][c][c][c][c]}
	2_\circ 5_\circ & 0 & \;0\;\; & \;0\;\; & \!-1\! & \!-1  \\
	2_\circ 7_\circ & 0 & 0 & 0 & 1 & 0 \\
	2_\circ 8_\circ & 0 & 1 & 0 & 0 & 1 \\
	3_\circ 5_\circ & \!-1\! & 0 & 0 & 0 & 0 \\
	5_\circ 7_\circ & 0 & 0 & 1 & 0 & 0 \\
	\end{block} \\[-.3cm]
	& & \multicolumn{3}{c}{$\gvectors{\triangulation_\circ}{\triangulation_\bullet}$} &
	\end{blockarray}$}
	\;\;
	\raisebox{-0.1\height}{$\begin{blockarray}{cc@{}c@{}c@{}c@{}c}
	& \rotatebox{90}{$2_\bullet 4_\bullet$} & \rotatebox{90}{$2_\bullet 8_\bullet$} & \rotatebox{90}{$4_\bullet 6_\bullet$} & \rotatebox{90}{$4_\bullet 7_\bullet$} & \rotatebox{90}{$4_\bullet 8_\bullet$}  \\
	\begin{block}{c[c][c][c][c][c]}
	2_\circ 5_\circ & 0 & \;1\;\; & \;0\;\; & \;0\;\; & \!-1  \\
	2_\circ 7_\circ & 0 & 1 & 0 & 1 & \!-1 \\
	2_\circ 8_\circ & 0 & 1 & 0 & 0 & 0 \\
	3_\circ 5_\circ & \!-1\! & 0 & 0 & 0 & 0 \\
	5_\circ 7_\circ & 0 & 0 & 1 & 0 & 0 \\
	\end{block} \\[-.3cm]
	& & \multicolumn{3}{c}{$\cvectors{\triangulation_\circ}{\triangulation_\bullet}$} &
	\end{blockarray}$}
	\end{center}
	\end{minipage}
	}
	\caption{Two triangulations~$\triangulation_\circ$ and~$\triangulation_\bullet$ with the corresponding $\b{g}$- and $\b{c}$-vectors.}
	\label{fig:exmTriangulations}
\end{figure}

For two triangulations~$\triangulation_\circ$ of~$\polygon_\circ$ and~$\triangulation_\bullet$ of~$\polygon_\bullet$, the sets~$\gvectors{\triangulation_\circ}{\triangulation_\bullet} {\eqdef} \! \set{\gvector{\triangulation_\circ}{\delta_\bullet}}{\delta_\bullet \! \in \! \triangulation_\bullet}$ and~$\cvectors{\triangulation_\circ}{\triangulation_\bullet} \eqdef \set{\cvector{\triangulation_\circ}{\triangulation_\bullet}{\delta_\bullet}}{\delta_\bullet \in \triangulation_\bullet}$ are dual bases.
%
Moreover, the $\b{g}$-vectors support a complete simplicial fan realizing the simplicial complex of collections of pairwise non-crossing diagonals of~$\polygon_\bullet$.
See Section~\ref{sec:prerequisitesFans} for basic notions of polyhedral geometry.

\begin{theorem}
For any reference triangulation~$\triangulation_\circ$ of~$\polygon_\circ$, the collection of cones \\[.1cm]
\centerline{
$\gvectorFan[\triangulation_\circ] \eqdef \bigset{\R_{\ge0} \gvectors{\triangulation_\circ}{\triangulation_\bullet}}{\triangulation_\bullet \text{ triangulation of } \polygon_\bullet},$
} \\[.1cm]
together with all their faces, forms a complete simplicial fan, called the \defn{$\b{g}$-vector fan} of~$\triangulation_\circ$.
\end{theorem}

We prove that this fan is realized by the following associahedra.
For a diagonal~$\delta_\bullet$ of~$\polygon_\bullet$, we denote by~$\F(\delta_\bullet)$ the number of diagonals of~$\polygon_\bullet$ crossed by~$\delta_\bullet$.

\begin{theorem}
For any reference triangulation~$\triangulation_\circ$ of~$\polygon_\circ$, the $\b{g}$-vector fan~$\gvectorFan[\triangulation_\circ]$ is the normal fan of the \defn{$\triangulation_\circ$-associahedron}~$\Asso[\triangulation_\circ]{}$ defined equivalently as
\begin{compactenum}[(i)]
\item the convex hull of the points
\(
\bigpoint{\triangulation_\circ}{\triangulation_\bullet}{} \eqdef \sum_{\delta_\bullet \in \triangulation_\bullet} \F(\delta_\bullet) \, \cvector{\triangulation_\circ}{\triangulation_\bullet}{\delta_\bullet}
\)
for all triangulations~$\triangulation_\bullet$ of~$\polygon_\bullet$, or
\item the intersection of the hyperplanes
\(
{\bigHS{\triangulation_\circ}{\delta_\bullet}{} \eqdef \bigset{\b{v} \in \R^{\triangulation_\circ}\!}{\!\dotprod{\gvector{\triangulation_\circ}{\delta_\bullet}}{\b{v}} \le \F(\delta_\bullet)}}
\)
for all diagonals~$\delta_\bullet$ of~$\polygon_\bullet$.
\end{compactenum}
\end{theorem}

When the triangulation~$\triangulation_\circ$ has no internal triangle, the $\triangulation_\circ$-associahedron was constructed by C.~Hohlweg and C.~Lange in~\cite{HohlwegLange}.

The geometry of these realizations depends on~$\triangulation_\circ$.
However, the crucial observation is that~$\F(\delta_\bullet)$ does not depend on~$\triangulation_\circ$.

\begin{definition}
%\label{def:universalAssociahedron}
Let~$\Delta(\polygon_\circ)$ be the set of all diagonals of~$\polygon_\circ$.
The \defn{universal $\triangulation_\circ$-associahedron} $\UnivAsso[\polygon_\circ]{} \subseteq \R^{\Delta(\polygon_\circ)}$ is the convex hull of the points
\(
\b{p}_{\mathrm{un}}(\triangulation_\bullet) \eqdef \sum_{\delta_\bullet \in \triangulation_\bullet} \F(\delta_\bullet) \, \b{u}(\delta_\bullet \in \triangulation_\bullet)
\)
for all triangulations~$\triangulation_\bullet$~of~$\polygon_\bullet$, where~$\b{u}(\delta_\bullet \in \triangulation_\bullet) \eqdef \big[ -\bigsign{\delta_\bullet}{\triangulation_\bullet}{\delta_\circ} \big]_{\delta_\circ \in \Delta(\polygon_\circ)} \in \R^{\Delta(\polygon_\circ)}$.
\end{definition}

This polytope has the following universal property.

\begin{theorem}
%\label{thm:universalAssociahedron}
For any reference triangulation~$\triangulation_\circ$ of $\polygon_\circ$, the orthogonal projection of the universal associahedron~$\UnivAsso[\polygon_\circ]{}$ on the coordinate subspace~$\R^{\triangulation_\circ}$ is the $\triangulation_\circ$-associahedron~$\Asso[\triangulation_\circ]{}$.
\end{theorem}

This extended abstract explains this result for arbitrary finite type cluster algebras.

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

\section{Finite type cluster algebras}
\label{sec:prerequisitesCA}

%%%%%%%%

\paragraph{Cluster algebras.}

We work in the ambient field~$\Q(x_1, \dots, x_n, p_1, \dots, p_m)$ of rational expressions in~$n+m$ variables with coefficients in~$\Q$ and denote by~$\Trop{m}$ its abelian multiplicative subgroup generated by the elements~$\{p_i\}_{i \in [m]}$.
Given~$p = \prod_{i \in [m]} p_i^{a_i} \in \Trop{m}$ we write
\(
\positiveExponents{p} \eqdef \prod_{i \in [m]} p_i^{\max(a_i,0)}
\)
and
\(
\negativeExponents{p} \eqdef \prod_{i \in [m]} p_i^{-\min(a_i,0)}
\)
so that~$p = \positiveExponents{p} \negativeExponents{p}^{-1}$.

\medskip
A \defn{seed}~$\seed$ is a triple~$(\B, \coefficients, \cluster)$ where
\begin{compactitem}
\item the \defn{exchange matrix}~$\B$ is an integer~$n \times n$ skew-symmetrizable matrix, \ie such that there exist a diagonal matrix~$\D$ with~$-\B\D = (\B\D)^T$,
\item the \defn{coefficient tuple}~$\coefficients$ is any subset of~$n$ elements of~$\Trop{m}$,
\item the \defn{cluster}~$\cluster$ is a set of \defn{cluster variables}, $n$~rational functions in the ambient field that are algebraically independent over~$\Q(p_1, \dots, p_m)$.
\end{compactitem}
To shorten our notation we think of rows and columns of~$\B$, as well as elements of~$\coefficients$, as being labelled by the elements of~$\cluster$: we write~$\B = (b_{xy})_{x,y \in \cluster}$ and~$\coefficients = \{p_x\}_{x \in \cluster}$.
Moreover we say that a cluster variable~$x$ (resp.~a coefficient~$p$) belongs to~$\seed = (\B, \coefficients, \cluster)$ to mean~$x \in \cluster$ (resp.~$p \in \coefficients$).

Given a seed~$\seed = (\B, \coefficients, \cluster)$ and a cluster variable~$x \in \seed$, we can construct a new seed~$\mu_x(\seed) = \seed' = (\B', \coefficients', \cluster')$ by \defn{mutation} in direction~$x$, where:
\begin{compactitem}
\item the new cluster $\cluster'$ is obtained from $\cluster$ by replacing $x$ with the cluster variable $x'$ defined by the following \defn{exchange relation}:
\[
x x' = \positiveExponents{p_x} \prod_{{y \in \cluster, \; b_{xy}  > 0}} y^{b_{xy}} + \negativeExponents{p_x} \prod_{{y \in \cluster, \; b_{xy}  <0}} y^{-b_{xy}}
\]
and leaving the remaining cluster variables unchanged so that $\cluster \ssm \{x\} = \cluster' \ssm \{x'\}$.

\item the row (resp.~column) of~$\B'$ indexed by~$x'$ is the negative of the row (resp.~column) of~$\B$ indexed by~$x$, while all other entries satisfy
\(
b'_{yz} = b_{yz} + \frac{1}{2}\big(|b_{yx}| b_{xz} + b_{yx}|b_{xz}|\big),
\)

\item the elements of the new coefficient tuple $\coefficients'$ are obtained by a related mutation rule.
\end{compactitem}
As mutations are involutions, they define an equivalence relation on the set of all seeds.

Fix a seed $\seed_\circ = (\B_\circ, \coefficients_\circ, \cluster_\circ)$ and call it \defn{initial}.
Up to  an automorphism of the ambient field we will assume that $\cluster_\circ = \{x_1,\dots,x_n\}$ and drop $\cluster_\circ$ from our notation.

\begin{definition}[{\cite[Definition~2.11]{FominZelevinsky-ClusterAlgebrasIV}}]
The (geometric type) \defn{cluster algebra} $\clusterAlgebra$ is the $\Z\Trop{m}$-subring of the ambient field generated by all the cluster variables in all the seeds mutationally equivalent to the initial seed $\seed_\circ$.
\end{definition}

The simplest possible choice of coefficient tuple in the initial seed, namely $m=0$ and  $\coefficients_\circ=\{1\}_{i\in[n]}$, gives rise to the \defn{ cluster algebra without coefficients}~$\coefficientFreeClusterAlgebra$.

\paragraph{Finite type.}

We only deal with cluster algebras of \defn{finite type} \ie cluster algebras having only a finite number of cluster variables.
Being of finite type is a property that depends only on the exchange matrix in the initial seed and not on the coefficient tuple.

The \defn{Cartan companion} of an exchange matrix $\B$ is the symmetrizable matrix $\A{\B}$ given by~$a_{xy} = 2$ if~$x = y$ and~$a_{xy} = -|b_{xy}|$ otherwise.

\begin{theorem}[{\cite[Theorem~1.4]{FominZelevinsky-ClusterAlgebrasII}}]
The cluster algebra $\clusterAlgebra$ is of finite type if and only~if there exists an exchange matrix $\B$ obtained by a sequence of mutations from $\B_\circ$ such that its Cartan companion is a Cartan matrix of finite type.
Moreover the type of $\A{\B}$ is determined~by~$B_\circ$.
\end{theorem}

In accordance with this statement, when talking about the \defn{(cluster) type} of $\clusterAlgebra$ or $\B_\circ$ we will refer to the Cartan type of $\A{\B}$.
We reiterate that the Cartan type of~$\A{\B_\circ}$ need not be finite: being of finite type is a property of the mutation class.

For a finite type cluster algebra~$\clusterAlgebra$, we will consider the root system of~$\A{\B_\circ}$.
To avoid any confusion later on let us state clearly the conventions we use here: for us simple roots~$\{\simpleRoot_x\}_{x \in \cluster_\circ}$ and fundamental weights~$\{\fundamentalWeight_x\}_{x \in \cluster_\circ}$ are two basis of the same vector space~$V$; the matrix relating them is the Cartan matrix $\A{\B_\circ}$.
Fundamental weights are the dual basis to simple coroots~$\{\simpleRoot^\vee_x\}_{x \in \cluster_\circ}$, while simple roots are the dual basis to fundamental coweights~$\{\fundamentalWeight^\vee_x\}_{x \in \cluster_\circ}$; coroots and coweights are two basis of the dual space~$V^\vee$ and they are related by the transpose of the Cartan matrix.

A finite type exchange matrix~$\B_\circ$ is said to be \defn{acyclic} if~$\A{\B_\circ}$ is itself a Cartan matrix of finite type and \defn{cyclic} otherwise.
An acyclic finite type exchange matrix is said to be \defn{bipartite} if each of its rows consists either of non-positive or non-negative entries.

\paragraph{Principal coefficients and $\b{g}$- and $\b{c}$-vectors.}

Among all the cluster algebras having a fixed initial exchange matrix, a central role is played by those with principal coefficients.

\begin{definition}[{\cite[Definition~3.1]{FominZelevinsky-ClusterAlgebrasIV}}]
A cluster algebra is said to have \defn{principal coefficients} (at the initial seed) if its ambient field is $\Q(x_1, \dots, x_n, p_1, \dots, p_n)$ and the initial coefficient tuple consists of the generators of $\Trop{n}$ \ie $\coefficients_\circ = \{p_i\}_{i \in [n]}$.
In this case we will write $\principalClusterAlgebra$ for $\clusterAlgebra[B_\circ][\{p_i\}_{i \in [n]}]$, and we reindex the generators~$\{p_i\}_{i \in [n]}$ of $\Trop{n}$ by~$\{p_x\}_{x \in \cluster_\circ}$.
\end{definition}

Cluster algebras with principal coefficients are $\Z^n$-graded (in the basis~$\{\omega_x\}_{x \in \cluster_\circ}$ of~$V$).
The degree function~$\deg(\B_\circ,\cdot)$ on $\principalClusterAlgebra$ is obtained by setting
\(
\deg(\B_\circ,  x) \eqdef \fundamentalWeight_x
\)
and
\(
\deg(\B_\circ, p_x) \eqdef \sum_{y \in \cluster_\circ} -b_{yx} \fundamentalWeight_y
\)
for any $x\in\cluster_\circ$.
This assignment makes all exchange relations and all cluster variables in~$\principalClusterAlgebra$ homogeneous~\cite{FominZelevinsky-ClusterAlgebrasIV} and it justifies the definition of the following family of integer vectors associated to cluster variables.

\begin{definition}[\cite{FominZelevinsky-ClusterAlgebrasIV}]
The \defn{$\b{g}$-vector}~$\gvector{\B_\circ}{x}$ of a cluster variable~$x \in \principalClusterAlgebra$ is its degree.
We denote by $\gvectors{\B_\circ}{\seed} \eqdef \set{\gvector{\B_\circ}{x}}{x \in \seed}$ the set of $\b{g}$-vectors of the cluster variable in the seed~$\seed$ of~$\principalClusterAlgebra$.
\end{definition}

The next definition gives another family of integer vectors, introduced implicitly in~\cite{FominZelevinsky-ClusterAlgebrasIV}, that are relevant in the structure of~$\principalClusterAlgebra$.

\begin{definition}
Given a seed~$\seed$ in~$\principalClusterAlgebra$, the \defn{$\b{c}$-vector} of a cluster variable $x \in \seed$ is the vector
\(
\cvector{\B_\circ}{\seed}{x} \eqdef \sum_{y \in \cluster_\circ} c_{yx} \, \simpleRoot_y
\)
of exponents of~$p_x = \prod_{y \in \cluster_\circ} (p_y)^{c_{yx}}$.
We denote by~$\cvectors{\B_\circ}{\seed} \eqdef \set{\cvector{\B_\circ}{\seed}{x}}{x \in \seed}$ the set of $\b{c}$-vectors of a seed~$\seed$.
\end{definition}

Our next task in this section is to discuss a duality relation in between $\b{c}$-vectors and $\b{g}$-vectors.
A first step is to recall the notion of the \defn{cluster complex} of $\clusterAlgebra$: it is the abstract simplicial complex whose vertices are the cluster variables of $\clusterAlgebra$ and whose facets are its clusters.
As it turns out, at least in the finite type cases, this complex is independent of the choice of coefficients, see~\cite[Theorem~1.13]{FominZelevinsky-ClusterAlgebrasII} and \cite[Conjecture~4.3]{FominZelevinsky-ClusterAlgebrasIV}.
In particular this means that, up to isomorphism, there is only one cluster complex for each finite type: the one associated to $\coefficientFreeClusterAlgebra$.
We will use this remark later on to relate cluster variables of different cluster algebras of the same finite type.
Note also that, again when $\clusterAlgebra$ is of finite type, the cluster complex is a \defn{pseudomanifold}~\cite{FominZelevinsky-ClusterAlgebrasII}.

For a skew-symmetrizable exchange matrix~$\B_\circ$, the matrix~$\B_\circ^\vee \eqdef -\B_\circ^T$ is still skew-symmetrizable.
The cluster algebras~$\principalClusterAlgebra$ and~$\principalClusterAlgebra[\B_\circ^\vee]$ can be thought as \defn{dual} to each other.
Indeed their types are Langlands dual of each other.
Moreover their cluster complexes are isomorphic: by performing the same sequence of mutations we can identify any cluster variable~$x$ of~$\principalClusterAlgebra$ with a cluster variable~$x^\vee$ of~$\principalClusterAlgebra[\B_\circ^\vee]$, and any seed $\seed$ in $\principalClusterAlgebra$ with a seed $\seed^\vee$ in~$\principalClusterAlgebra[\B_\circ^\vee]$.
More importantly the following crucial property holds.

\begin{theorem}[{\cite[Theorem~1.2]{NakanishiZelevinsky}}]
\label{thm:duality}
For any seed~$\seed$ of~$\principalClusterAlgebra$, let $\seed^\vee$ be its dual in $\principalClusterAlgebra[\B_\circ^\vee]$.
Then the set of $\b{g}$-vectors~$\gvector{\B_\circ}{\seed}$ and the set of $\b{c}$-vectors~$\cvectors{\B_\circ^\vee}{\seed^\vee}$ form dual bases, that is
\(
{\bigdotprod{\gvector{\B_\circ}{x}}{\cvector{\B_\circ^\vee}{\seed^\vee}{y^\vee}} = \delta_{x=y}}
\)
for any two cluster variables~$x,y \in \seed$.
\end{theorem}

In view of the above results, and since $\A{\B_\circ^\vee}=\A{\B_\circ}^T$, the $\b{c}$-vectors of a finite type cluster algebra $\principalClusterAlgebra[\B_\circ^\vee]$ can be understood as coroots for $\A{\B_\circ}$ so that the $\b{g}$-vectors of $\principalClusterAlgebra$ become weights.
This justify our choice to define $\b{g}$-vectors in the weight basis and $\b{c}$-vectors in the root basis.

\paragraph{Coefficient specialization and universal cluster algebra.}

We want to relate, within a given finite type, cluster algebras with different choices of coefficients.
Pick a finite type exchange matrix $\B_\circ$ and let $\clusterAlgebra\subset\Q(x_1,\dots,x_n,p_1,\dots,p_m)$ and $\clusterAlgebra[\B_\circ][\overline{\coefficients_\circ}]\subset\Q(\overline{x_1},\dots,\overline{x_n},\overline{p_1},\dots,\overline{p_\ell})$ be any two cluster algebras having~$\B_\circ$ as exchange matrix in their initial seed.
As we said, cluster variables and seeds in these two algebras are in bijection because their cluster complexes are isomorphic.
Let us write
\(
x \leftrightarrow \overline{x}
\)
and
\(
\seed \leftrightarrow \overline{\seed}
\)
for this bijection.
We will say that~$\clusterAlgebra[\B_\circ][\overline{\coefficients_\circ}]$ is obtained from~$\clusterAlgebra$ by a \defn{coefficient specialization} if there exist a map of abelian groups~$\eta:\Trop{m}\rightarrow\Trop{\ell}$ such that, for any~$p_x$ in some seed~$\seed$ of~$\clusterAlgebra$, we have
\(
\eta(\positiveExponents{p_x}) = \positiveExponents{\overline{p_{\overline{x}}}}
\)
and
\(
\eta(\negativeExponents{p_x}) = \negativeExponents{\overline{p_{\overline{x}}}}
\)
and which extends in a unique way to a map of algebras that satisfy
\(
\eta(x) = \overline{x}.
\)
Note that this is not the most general definition (see~\cite[Definition~12.1 and Proposition~12.2]{FominZelevinsky-ClusterAlgebrasIV}) but it will suffice here.
Armed with the notion of coefficient specialization we can now introduce the last kind of cluster algebra of finite type we will need.

\begin{definition}[{\cite[Definition~12.3 and Theorem~12.4]{FominZelevinsky-ClusterAlgebrasIV}}]
Pick a finite type exchange matrix $\B_\circ$.
The \defn{cluster algebra with universal coefficients} $\universalClusterAlgebra$ is the unique (up to canonical isomorphism) cluster algebra such that any other cluster algebra of the same type as $\B_\circ$ can be obtained from it by a unique coefficient specialization.
\end{definition}

Let us insist on the fact that, in view of the universal property it satisfies, $\universalClusterAlgebra$ depends only on the type of~$\B_\circ$ and not on the exchange matrix~$\B_\circ$ itself.
We keep~$\B_\circ$ in the notation only to fix an embedding into the ambient field.

Rather than proving the existence and explaining the details of how such a universal algebra is built, we will recall here one of its remarkable properties that follows directly from the $\b{g}$-vector recursion~\cite[Proposition~4.2\,(v)]{NakanishiZelevinsky} and that we will need later on.
Denote by $\clusterVariables$ the set of all cluster variables in $\universalClusterAlgebra$ and let $\{p[x]\}_{x\in\clusterVariables}$ be the generators of $\Trop{|\clusterVariables|}$.

\begin{theorem}[{\cite[Theorem~10.12]{Reading-UniversalCoefficients}}]
The cluster algebra $\universalClusterAlgebra$ can be realized over $\Trop{|\clusterVariables|}$.
The coefficient tuple $\coefficients=\{p_x\}_{x \in \cluster}$ at each seed $\seed=(\B,\coefficients,\cluster)$ of $\universalClusterAlgebra$ is given by the formula
\(
p_x = \prod_{y \in \clusterVariables} p[y]^{[\gvector{\B^T}{y^T};{x^T}]}
\)
where $[\b{v};x]$ is the $x$-th coefficient of a vector $\b{v}$ in the weight basis~$(\omega_x)_{x \in \cluster}$.
\end{theorem}

\begin{remark}
\label{rem:universalToPrincipal}
In view of this result, it is straightforward to produce the coefficient specialization morphism to get any cluster algebra with principal coefficients of type~$\B_\circ$ from $\universalClusterAlgebra$.
Namely, for any seed~$\seed_\star = (\B_\star, \coefficients_\star, \cluster_\star)$ of $\universalClusterAlgebra$, we obtain~$\principalClusterAlgebra[\B_\star]$ by evaluating to $1$ all the coefficients~$p[y]$ corresponding to cluster variables~$y$ not in $\seed_\star$.
\end{remark}

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

\section{Polyhedral geometry and fans}
\label{sec:prerequisitesFans}

A \defn{polyhedral cone} is a subset of the vector space~$V$ defined equivalently as the positive span of finitely many vectors or as the intersection of finitely many closed linear halfspaces.
We write~$\R_{\ge0}\b{\Lambda}$ for the positive span of a set~$\b{\Lambda}$ of vectors of~$V$.
The \defn{faces} of a cone~$C$ are the intersections of~$C$ with its supporting hyperplanes.
The $1$-dimensional (resp.~codimension~$1$) faces of~$C$ are called~\defn{rays} (resp.~\defn{facets}) of~$C$.
A cone is \defn{simplicial} if it is generated by a set of independent vectors.

A \defn{polyhedral fan} is a collection~$\Fan$ of polyhedral cones of~$V$ such that
\begin{compactitem}
\item if~$C \in \Fan$ and~$F$ is a face of~$C$, then~$F \in \Fan$,
\item the intersection of any two cones of~$\Fan$ is a face of both.
\end{compactitem}
A fan is \defn{simplicial} if all its cones are, and \defn{complete} if the union of its cones covers the ambient space~$V$.
For a simplicial fan~$\Fan$ with rays~$\cX$, the collection~$\set{X \subseteq \cX}{\R_{\ge0}X \in \Fan}$  of generating sets of the cones of~$\Fan$ defines a pseudomanifold.
The following statement characterizes which pseudomanifolds are complete simplicial fans.

\begin{proposition}
\label{prop:characterizationFan}
Consider a pseudomanifold~$\Delta$ with vertex set~$\cX$ and a set of vectors~$\{ \b{r}(x) \}_{x \in \cX}$ of~$V$.
For~$\cluster \in \Delta$, let~${\b{r}(\cluster) \eqdef \bigset{\b{r}(x)}{x \in \cluster}}$.
Then the collection of cones~${\bigset{\R_{\ge 0}\b{r}(\cluster)}{\cluster \in \Delta}}$ forms a complete simplicial fan if and~only~if
\begin{compactenum}
\item there exists a facet~$\cluster$ of~$\Delta$ such that~$\b{r}(\cluster)$ is a basis of~$V$ and the open cones~$\R_{> 0}\b{r}(\cluster)$ and~$\R_{> 0}\b{r}(\cluster')$ are disjoint for any facet~$\cluster'$ of~$\Delta$ distinct from~$\cluster$;
\item for any two adjacent facets~$\cluster, \cluster'$ of~$\Delta$ with~$\cluster \ssm \{x\} = \cluster' \ssm \{x'\}$, there is a linear dependence
\(
\gamma \, \b{r}(x) + \gamma' \, \b{r}(x') + \sum_{y \in \cluster \cap \cluster'} \delta_y \, \b{r}(y) = 0
\)
on~$\b{r}(\cluster \cup \cluster')$ where the coefficients~$\gamma$ and~$\gamma'$ have the same sign.
(When these conditions hold, these coefficients do not vanish and the linear dependence is unique up to rescaling.)
\end{compactenum}
\end{proposition}

A \defn{polytope} is a subset~$P$ of~$V^\vee$ defined equivalently as the convex hull of finitely many points or as a bounded intersection of finitely many closed affine halfspaces.
The \defn{faces} of~$P$ are the intersections of~$P$ with its supporting hyperplanes.
In particular, the dimension~$0$ (resp.~dimension~$1$, resp.~codimension~$1$) faces of~$P$ are called \defn{vertices} (resp.~\defn{edges}, resp.~\defn{facets}) of~$P$.
The (outer) \defn{normal cone} of a face~$F$ of~$P$ is the cone in $V$ generated by the outer normal vectors of the facets of~$P$ containing~$F$.
The (outer) \defn{normal fan} of~$P$ is the collection of the (outer) normal cones of all its faces.
We say that a complete polyhedral fan in~$V$ is \defn{polytopal} when it is the normal fan of a polytope in~$V^\vee$.
The following statement provides a characterization of polytopality of complete simplicial fans.

\begin{proposition}
\label{prop:characterizationPolytopalFan}
\label{prop:polytopalityFan}
Consider a pseudomanifold~$\Delta$ with vertex set~$\cX$ and a set of vectors~$\{ \b{r}(x) \}_{x \in \cX}$ of~$V$ such that~$\Fan \eqdef {\bigset{\R_{\ge 0}\b{r}(\cluster)}{\cluster \in \Delta}}$ forms a complete simplicial fan.
Assume that there exists a map~$\F: \cX \to \R_{> 0}$ such that for any two facets~$\cluster, \cluster'$ of~$\Delta$ with ${\cluster \ssm \{x\} = \cluster' \ssm \{x'\}}$, we have
\(
\gamma \, \F(x) + \gamma' \, \F(x') + \sum_y \delta_y \, \F(y) > 0,
\)
where
\(
\gamma \, \b{r}(x) + \gamma' \, \b{r}(x') + \sum_y \delta_y \, \b{r}(y) = 0
\)
is the unique (up to scaling) linear dependence with~$\gamma, \gamma' > 0$ between the rays of~${\b{r}(\cluster \cup \cluster')}$.
Then, $\Fan$ is the normal fan of the polytope given by
\(
\bigset{\b{v} \in V^\vee}{\dotprod{\b{r}(x)}{\b{v}} \le \F(x) \text{ for all } x \in \cX}.
\)
\end{proposition}

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

\section{The $\b{g}$-vector fan}
\label{sec:gvectorFan}

We first recast a well known fact concerning the cones spanned by the $\b{g}$-vectors of a any finite type cluster algebra with principal coefficients.

\begin{theorem}
\label{thm:gvectorFan}
For any finite type exchange matrix~$\B_\circ$, the collection of cones \\[.1cm]
\centerline{
$\gvectorFan \eqdef \bigset{\R_{\ge0} \gvectors{\B_\circ}{\seed}}{\seed \text{ seed of } \principalClusterAlgebra},$
} \\[.1cm]
together with all their faces, forms a complete simplicial fan, called the \defn{$\b{g}$-vector fan} of~$\B_\circ$.
\end{theorem}

There are several ways to deduce Theorem~\ref{thm:gvectorFan} from the literature.
One option is to use Proposition~\ref{prop:characterizationFan}, whose second condition is implied by the following description of the linear dependence between the $\b{g}$-vectors of two adjacent clusters, which is crucial~later.

\begin{lemma}
\label{lem:linearDependence}
For any finite type~exchange matrix~$\B_\circ$ and any adjacent seeds~${(\B, \coefficients, \cluster)}$, ${(\B', \coefficients', \cluster')}$ in $\principalClusterAlgebra$ with~$\cluster \ssm \{x\} = \cluster' \ssm \{x'\}$, the $\b{g}$-vectors of~$\cluster \cup \cluster'$ satisfy precisely one of the following two linear dependences \\[.3cm]
\centerline{
$\displaystyle \biggvector{\B_\circ}{x} + \biggvector{\B_\circ}{x'} = \!\!\!\!\!\!\!\! \sum_{{y \in \cluster \cap \cluster', \; b_{xy} < 0}} \!\!\!\!\!\!\!\! -b_{xy} \, \biggvector{\B_\circ}{y}
\quad\text{or}\quad
\biggvector{\B_\circ}{x} + \biggvector{\B_\circ}{x'} = \!\!\!\!\!\!\!\! \sum_{{y \in \cluster \cap \cluster', \; b_{xy} > 0}} \!\!\!\!\!\!\!\! b_{xy} \, \biggvector{\B_\circ}{y}.$
} \\[.2cm]
Note that which of the two possible linear dependences is satisfied by the $\b{g}$-vectors of~$\cluster \cup \cluster'$ depends on the initial exchange matrix~$\B_\circ$.
\end{lemma}

\begin{remark}
When the exchange matrix~$\B_\circ$ is acyclic, the $\b{g}$-vector fan is the Cambrian fan constructed by N.~Reading and D.~Speyer~\cite{ReadingSpeyer}.
Cyclic examples are shown in \fref{fig:gvectorFans}.
\end{remark}

\begin{figure}[h]
	\centerline{
	\begin{overpic}[width=.4\textwidth]{A3_fan}
	\put(-19,70){$\left[\begin{array}{@{}c@{\;}c@{\;}c@{}} 0 & -1 & 1 \\ 1 & 0 & -1 \\ -1 & 1 & 0 \end{array}\right]$}
	\end{overpic}
	\quad
	\begin{overpic}[width=.4\textwidth]{C3_fan}
	\put(81,70){$\left[\begin{array}{@{}c@{\;}c@{\;}c@{}} 0 & -1 & 2 \\ 1 & 0 & -2 \\ -1 & 1 & 0 \end{array}\right]$}
	\end{overpic}
	}
  \caption{The $\b{g}$-vector fan~$\gvectorFan$ for the type~$A_3$~(left) and type~$C_3$~(right) cyclic initial exchange matrices. To plot the figure, the $3$-dimensional fans are intersected with the unit sphere and stereographically projected to the plane from the pole~$(-1,-1,-1)$.}
	\label{fig:gvectorFans}
\end{figure}

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

\section{Polytopality}
\label{sec:polytopality}

In this section, we show that the $\b{g}$-vector fan~$\gvectorFan$ is polytopal for any finite type exchange matrix~$\B_\circ$.
As mentioned in the introduction, this result was previously known for acyclic finite type~exchange matrices~\cite{HohlwegLangeThomas}.
We first consider some convenient functions which will be used later in Theorem~\ref{thm:polytopality} to lift the $\b{g}$-vector fan.
The existence of such functions will be discussed in Proposition~\ref{prop:existenceExchangeSubmodularFunctions}.

\begin{definition}
\label{def:exchangeSubmodularFunction}
A positive function~$\F$ on the cluster variables of~$\clusterAlgebra$ is \defn{exchange submodular} if, for any adjacent seeds~$(\B, \coefficients, \cluster)$ and~$(\B', \coefficients', \cluster')$ with~$\cluster \ssm \{x\} = \cluster' \ssm \{x'\}$, it satisfies
\[
\F(x) + \F(x') > \max \Big( \sum_{{y \in \cluster \cap \cluster', \; b_{xy} < 0}} -b_{xy} \, \F(y) \;,  \sum_{{y \in \cluster \cap \cluster', \; b_{xy} > 0}} b_{xy} \, \F(y) \Big).
\]
\end{definition}

%\begin{definition}
%\label{def:pointHyperplane}
%Let~$\F$ be a positive function on the cluster variables of~$\principalClusterAlgebra$ we define:
%\begin{compactenum}[(i)]
%\item a point
%\(
%\bigpoint{\B_\circ}{\seed}{\F} \eqdef \sum_{x \in \seed} \F(x) \, \bigcvector{\B_\circ^\vee}{\seed^\vee}{x^\vee} \; \in V^\vee
%\)
%for each seed~$\seed$ of~$\principalClusterAlgebra$,
%\item a halfspace~$\HS{\B_\circ}{x}{\F} \eqdef \set{\b{v} \in V^\vee}{\dotprod{\biggvector{\B_\circ}{x}}{\b{v}} \le \F(x)}$ for each cluster variable~$x$ of~$\principalClusterAlgebra$.
%\end{compactenum}
%\end{definition}

The following statement is our central result.
%We refer again to Proposition~\ref{prop:existenceExchangeSubmodularFunctions} for the existence of exchange submodular functions.

\begin{theorem}
\label{thm:polytopality}
For any finite type~exchange matrix~$\B_\circ$ and exchange submodular function~$\F$, the $\b{g}$-vector fan~$\gvectorFan$ is the normal fan of the \defn{$\B_\circ$-associahedron}~$\Asso{\F}$ defined equivalently~as
\begin{compactenum}[(i)]
\item the convex hull of the points~$\bigpoint{\B_\circ}{\seed}{\F} \eqdef \sum_{x \in \seed} \F(x) \, \bigcvector{\B_\circ^\vee}{\seed^\vee}{x^\vee}$ for all seeds~$\seed$ of~$\principalClusterAlgebra$, or
\item the intersection of the halfspaces~$\HS{\B_\circ}{x}{\F} \eqdef \set{\b{v} \in V^\vee}{\dotprod{\biggvector{\B_\circ}{x}}{\b{v}} \le \F(x)}$ for all cluster variables~$x$ of~$\principalClusterAlgebra$.
\end{compactenum}
\end{theorem}

Our next step is to discuss the existence of exchange submodular functions for any finite type cluster algebra with principal coefficients.
The important observation here is that the definition of exchange submodular function does not involve in any way the coefficients of $\principalClusterAlgebra$ so that it suffices to construct one in the coefficient free cases.
Indeed, if $\F$ is exchange submodular for $\coefficientFreeClusterAlgebra$, and $\eta$ is the coefficient specialization morphism given by
\[
  \begin{array}{rccc}
    \eta: & \principalClusterAlgebra & \longrightarrow & \coefficientFreeClusterAlgebra\\
          & p_i                      & \longmapsto     & 1
  \end{array}
\]
one gets the desired map by setting
\(
  \F(x) \eqdef \F(\eta(x))
\)
for any cluster variable $x$ of $\principalClusterAlgebra$.

Recall that, up to an obvious automorphism of the ambient field, there exists a unique cluster algebra without coefficients for each given finite type~\cite{FominZelevinsky-ClusterAlgebrasIV}.
We can therefore, without loss of generality, assume that $\B_\circ$ is
bipartite and directly deduce our result from
\cite[Proposition~8.3]{Stella} obtained as an easy consequence of \cite[Lemma~2.4]{ChapotonFominZelevinsky} which we recast here in our current setting.

When~$\B_\circ$ is acyclic, the Weyl group of~$\A{\B_\circ}$ is finite and has a longest element~$\wo$.
A point~$\lambda^\vee \eqdef \sum_{x \in \cluster_\circ} \lambda^\vee_x \, \fundamentalWeight^\vee_x$ in the interior of the fundamental Weyl chamber of~$\A{\B^\vee_\circ}$ (that is to say $\lambda^\vee_x > 0$ for all $x \in \cluster_\circ$) is \defn{fairly balanced} if~$\wo(\lambda^\vee) = -\lambda^\vee$.

\begin{proposition}
\label{prop:existenceExchangeSubmodularFunctions}
Let $\coefficientFreeClusterAlgebra$ be any finite type cluster algebra without coefficients and assume that $\B_\circ$ is bipartite.
To each fairly balanced point~$\lambda^\vee$ corresponds an exchange submodular function $\F_{\lambda^\vee}$ on $\coefficientFreeClusterAlgebra$.
\end{proposition}
 
A particular example of fairly balanced point is the point
\(
\rho^\vee \eqdef \sum_{x \in \cluster_\circ} \fundamentalWeight^\vee_x.
\)
Note that~$\rho^\vee$ is both the sum of the fundamental coweights and the half sum of all positive coroots of the root system of finite type~$\A{\B_\circ}$.
In particular~$\F_{\rho^\vee}$ is the \defn{half compatibility sum} of~$x$, \ie the half sum of the compatibility degrees
\(
\F_{\rho^\vee}(x) \eqdef \frac{1}{2} \sum_{y \ne x} \compatibilityDegree{y}{x}
\)
over all cluster variables distinct from~$x$.
The point $\rho^\vee$ is particularly relevant in representation theory and its role in this context has already been observed in \cite[Remark~1.6]{ChapotonFominZelevinsky}.
We call \defn{balanced $\B_\circ$-associahedron} and denote by~$\Asso{}$ the~$\B_\circ$-associahedron~$\Asso{\F_{\rho^\vee}}$ for the exchange submodular function~$\F_{\rho^\vee}$.

\begin{remark}
When~$\B_\circ$ is acyclic, the $\B_\circ$-associahedron~$\Asso{}$ was already constructed in \cite{HohlwegLangeThomas}.
It is then obtained by deleting inequalities from the facet description of the permutahedron of the Coxeter group of type~$\A{\B_\circ}$.
This requires the fact that the Coxeter arrangement refines the Cambrian fan~\cite{ReadingSpeyer}.
Similar properties still hold for any type~$A$ initial seed: on the one hand, the $\b{g}$-vector fan is refined by the arrangement of hyperplanes normal to the $\b{c}$-vectors of~$\principalClusterAlgebra$; on the other hand, the $\B_\circ$-associahedron is obtained by deleting inequalities from the facet description of the zonotope obtained as the Minkowski sum of all $\b{c}$-vectors of~$\principalClusterAlgebra$.
Although the fan refinement still holds for all the other finite types, the $\B_\circ$-associahedron in general cannot be obtained by deleting inequalities in the facet description of a zonotope.
\end{remark}

\begin{figure}
	\centerline{$\vcenter{\hbox{\includegraphics[scale=.65]{A3_asso}}}$ \qquad $\vcenter{\hbox{\includegraphics[scale=.65]{C3_asso}}}$}
	\caption{The associahedra~$\Asso{}$ for the type~$A_3$~(left) and type~$C_3$~(right) cyclic initial exchange matrices whose $\b{g}$-vector fans are depicted in \fref{fig:gvectorFans}.}
	\label{fig:associahedra}
\end{figure}

We sum up by restating our main result.

\begin{corollary}
\label{coro:polytopalitygvectorFan}
For any finite type exchange matrix~$\B_\circ$, the $\b{g}$-vector fan~$\gvectorFan$ is polytopal.
\end{corollary}

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

\section{Universal associahedron}
\label{sec:universalAssociahedron}

For each initial exchange matrix~$\B_\circ$ of a given type, we constructed in Section~\ref{sec:polytopality} a generalized associahedron~$\Asso{\F}$ by lifting the $\b{g}$-vector fan using an exchange submodular function~$\F$ on the cluster variables of~$\principalClusterAlgebra$.
As already observed though, the function~$\F$ is independent of the coefficients of~$\principalClusterAlgebra$, so that all $\b{g}$-vector fans can be lifted with the same function~$\F$.
This motivates the definition of a universal associahedron.

Consider the finite type cluster algebra~$\universalClusterAlgebra$ with universal coefficients, and let $\clusterVariables$ denote its set of cluster variables.
Consider a $|\clusterVariables|$-dimensional vector space~$U$ with basis~$\{\beta_x\}_{x \in \clusterVariables}$ and its dual space~$U^\vee$ with basis~$\{\beta^\vee_{x^\vee}\}_{x^\vee \in \clusterVariables[\B_\circ^\vee]}$. As before, the cluster variables of~$\universalClusterAlgebra$ and~$\universalClusterAlgebra[\B_\circ^\vee]$ are related by~$x \leftrightarrow x^\vee$.
For~${\cluster \subseteq \clusterVariables}$, we denote by~$\coordSubspace{\cluster}$ the coordinate subspace of~$U$ spanned by~$\{\beta_x\}_{x \in \cluster}$.

Given a seed~$\seed$ in~$\universalClusterAlgebra$, the \defn{$\b{u}$-vector} of a cluster variable $x \in \seed$ is the vector
\(
\uvector{\B_\circ}{\seed}{x} \eqdef \sum_{y \in \clusterVariables} u_{yx} \, \beta_y 
\)
of exponents of~$p_x = \prod_{y \in \clusterVariables} (p[y])^{u_{yx}}$.
Remark~\ref{rem:universalToPrincipal} then reformulates in terms of $\b{u}$- and $\b{c}$-vectors as follows.
Choose a seed~${\seed_\star = (\B_\star, \coefficients_\star, \cluster_\star)}$ in~$\universalClusterAlgebra$ that you want to make initial.
Then, for any cluster variable~$x$ in a seed~$\seed$, the $\b{c}$-vector~$\cvector{\B_\star}{\seed}{x}$ is the orthogonal projection of the $\b{u}$-vector~$\uvector{\B_\circ}{\seed}{x}$ on the coordinate subspace~$\coordSubspace{\cluster_\star}$.
(Here and elsewhere we identify $\coordSubspace{\cluster_\star}$ with $V$ and $\coordSubspace{\cluster_\star^\vee}$ with $V^\vee$ in the obvious way.)
%
We are now ready to define the universal associahedron.

\begin{definition}
\label{def:universalAssociahedron}
For any finite type exchange matrix~$\B_\circ$ and any exchange submodular function~$\F$, the \defn{universal $\B_\circ$-associahedron}~$\UnivAsso{\F} \subseteq U^\vee$ is the convex hull of the points
\(
\Univbigpoint{\B_\circ}{\seed}{\F} \eqdef \sum_{x \in \seed} \F(x) \, \biguvector{\B_\circ^\vee}{\seed^\vee}{x^\vee}
\)
for all seeds~$\seed$~of~$\universalClusterAlgebra$.
\end{definition}

Note that~$\UnivAsso{\F}$ does not depend on~$\B_\circ$ but only on its cluster type.
We keep~$\B_\circ$ in the notation to fix the indexing.
Our interest in~$\UnivAsso{\F}$ comes from the following.

\begin{theorem}
\label{thm:universalAssociahedron}
Fix a finite type exchange matrix~$\B_\circ$ and an exchange submodular function~$\F$.
For any seed~$(\B_\star, \coefficients_\star, \cluster_\star)$ of $\universalClusterAlgebra$, the orthogonal projection of the universal associahedron~$\UnivAsso{\F}$ on the coordinate subspace~$\coordSubspace{\cluster_\star^\vee}$ of~$U^\vee$ spanned by~$\{\beta^\vee_{x^\vee}\}_{x^\vee \in \cluster^\vee_\star}$ is the $\B_\star$-associahedron~$\Asso[\B_\star]{\F}$.
\end{theorem}

\begin{remark}
Consider the normal fan~$\Fan$ of the universal $\B_\circ$-associahedron~$\UnivAsso{\F}$.
Then for any seed~$\seed_\star = (\B_\star, \coefficients_\star, \cluster_\star)$ in~$\universalClusterAlgebra$, the section of~$\Fan$ by the coordinate subspace~$\coordSubspace{\cluster_\star}$ of~$U$ spanned by~$\{\beta_x\}_{x \in \cluster_\star}$ is the $\b{g}$-vector fan~$\gvectorFan[\B_\star]$.
We therefore call \defn{universal $\b{g}$-vector fan} the normal fan~$\UnivgvectorFan$ of the universal $\B_\circ$-associahedron~$\UnivAsso{}$.
\end{remark}

As an immediate consequence of Theorem~\ref{thm:universalAssociahedron}, we obtain that the vertices of the universal associahedron~$\UnivAsso{\F}$ are precisely the points~$\Univpoint{\B_\circ}{\seed}{\F}$ for all seeds~$\seed$ of~$\universalClusterAlgebra$, and that the mutation graph of the cluster algebra~$\universalClusterAlgebra$ is a subgraph of the graph of~$\UnivAsso{\F}$. However, this inclusion is strict in general.

We conclude with three observations on the universal $\B_\circ$-associahedron~$\UnivAsso{\F}$ obtained by computer experiment:
\begin{compactitem}
\item Although \apriori{} defined in~$U^\vee$, $\UnivAsso{\F}$ seems to be of codimension~$1$. 
\item In general~$\UnivAsso{\F}$ is neither simple nor simplicial. Table~\ref{table:universalAssociahedron} presents some statistics for the number of vertices per facet and facets per vertex in type~$A_n$ for~$n \in [4]$.
\item The face lattice (and thus the $f$-vector) of~$\UnivAsso{\F}$ seems independent of~$\F$.

\begin{table}
	\centerline{
	\begin{tabular}{c|c|c|c|c|c|c}
    	$n$
		& ambient dim. 
		& dim. 
		& \# vertices 
		& \# facets & \# vertices / facet
		& \# facets / vertex \\
		\hline
		$1$ & $2$  & $1$  & $2$  & $2$    & $1$                   & $1$                       \\
		$2$ & $5$  & $4$  & $5$  & $5$    & $4$                   & $4$                       \\
		$3$ & $9$  & $8$  & $14$ & $60$   & $9 \le \cdot \le 10$  & $30 \le \cdot \le 42$     \\
		$4$ & $14$ & $13$ & $42$ & $8960$ & $14 \le \cdot \le 28$ & $3463 \le \cdot \le 4244$
	\end{tabular}}
	\caption{Some statistics for the universal associahedron of type~$A_n$ for~$n \in [4]$.}
	\label{table:universalAssociahedron}
\end{table}
\end{compactitem}


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