%% 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[submission]{FPSAC2019}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

\articlenumber{104}
\addbibresource{104.bib}

%% note that the class file already loads {amsmath, amsthm, amssymb}

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

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

\newcommand{\lk}{{\mathrm{lk}}}
\newcommand{\st}{\mathrm{st}}
\newcommand{\FF}{ \ensuremath{\mathbb{F}}}
\newcommand{\NN}{ \ensuremath{\mathbb{N}}}
\newcommand{\ZZ}{ \ensuremath{\mathbb{Z}}}
\newcommand{\CC}{ \ensuremath{\mathbb{C}}}
\newcommand{\RR}{ \ensuremath{\mathbb{R}}}
\newcommand{\QQ}{ \ensuremath{\mathbb{Q}}}
\newcommand{\PP}{\mathbb{P}}

\usepackage{lipsum}
\usepackage{MnSymbol}
%\usepackage{cleveref}

%% define your title in the usual way
\title[Balanced triangulations on few vertices and an implementation of cross-flips]{Balanced triangulations on few vertices and an implementation of cross-flips}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author[Lorenzo Venturello]{Lorenzo Venturello\thanks{\href{lorenzo.venturello@uni-osnabrueck.de}{lorenzo.venturello@uni-osnabrueck.de}. The author was supported by the German Research Council DFG GRK-1916.}}

%% then use \addressmark to match authors to institutions here
\address{Universit\"{a}t Osnabr\"{u}ck,
	Fakult\"{a}t f\"{u}r Mathematik,
	Albrechtstra\ss e 28a,
	49076 Osnabr\"{u}ck, Germany }
%% put the date of submission here
\received{13/11/2018}

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

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{A $d$-dimensional simplicial complex is \emph{balanced} if the underlying graph is $(d+1)$-colorable. We present an implementation of cross-flips, a set of local moves introduced by Izmestiev, Klee and Novik which connect any two PL-homeomorphic balanced combinatorial manifolds without boundary. As a result we exhibit a vertex-minimal balanced triangulation of the dunce hat and balanced triangulations of several surfaces and 3-manifolds on few vertices. In particular we obtain small balanced triangulations of the 3-sphere that are non-shellable or shellable but not vertex decomposable.}

\resumetitle{Sommario}
%% put your French abstract here, or comment this out if you don't have one
\resume{Un complesso simpliciale di dimensione $d$ si dice \emph{bilanciato} se il suo grafo \`{e} $(d+1)$-colorabile. In questo articolo presentiamo un'implementazione dei cross-flips, un insieme di trasformazioni locali introdotte da Izmestiev, Klee e Novik, sufficienti a connettere ogni due variet\`{a} combinatorie senza bordo che sono PL-omeomorfe. Come risultato presentiamo una triangolazione bilanciata minimale (rispetto al numero di vertici) del dunce hat e numerose triangolazioni bilanciate di superfici e 3-variet\`{a} con pochi vertici. In particolare otteniamo triangolazioni bilanciate con pochi vertici della 3-sfera che sono non-shellable e shellable ma non vertex decomposable. }

%% put your keywords here, or comment this out if you don't have them yet
\keywords{triangulation, balanced, combinatorial manifold, cross-flip}

%% 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,maxbibnames=9,doi=true,isbn=false,url=false]{biblatex}
%\addbibresource{bibliography.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

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



\section{Introduction}
A classical problem in combinatorial topology is to determine the minimum number of vertices that a triangulation of a fixed manifold can have. To study this and other related questions we can make use of \emph{bistellar flips}, a finite set of local moves which preserves the PL-homeomorphism type and suffices to connect any two \emph{combinatorial triangulations} of a given manifold (equivalently, triangulations of PL-manifolds without boundary).
In this article we focus on \emph{balanced} simplicial complexes, i.e., $d$-dimensional simplicial complexes whose underlying graphs are $(d+1)$-colorable in the classical graph-theoretic sense. Many questions and results for arbitrary triangulations have balanced analogs (see for instance \cite{IKN,JV,Juhnke:Murai:Novik:Sawaske,KN}), and in particular we can ask what is the minimum number of vertices that a balanced triangulation of a fixed manifold can have. 
In \cite{IKN} Izmestiev, Klee and Novik introduced a finite set of local moves called \emph{cross-flips}, which preserves balancedness, the PL-homeomorphism type, and suffices to connect any two balanced combinatorial triangulations of a manifold. We provide a computer program implemented in Sage \cite{sagemath} to search through the set of balanced triangulations of a manifold and we report several results in dimensions $2$ and $3$.
% In \Cref{surf_dunce} we present a vertex minimal balanced triangulation of $\mathbb{R}\mathbf{P}^{2}$, we list small balanced $f$-vectors of surfaces, and exhibit a balanced triangulation of the dunce hat on $11$ vertices. We devote \Cref{section_dunce} to the proof of its vertex minimality.  Next we list balanced triangulations of $3$-manifolds on few vertices. In particular we report a vertex minimal balanced triangulation of $\mathbb{R}\mathbf{P}^{3}$ on 16 vertices with interesting symmetries. Finally via results in knot theory we construct balanced 3-spheres on few vertices that are non-shellable and shellable but not vertex decomposable.   

The source code and the list of facets of all the simplicial complexes appearing in this paper are made available in \cite{GitRepo}, together with a short demo showing how to use program.

\acknowledgements{I would like to thank Martina Juhnke-Kubitzke for her constant support and precious help. I would also like to thank Isabella Novik and Hailun Zheng for helpful comments on a long version of this paper and Bruno Benedetti for pointing out the results in \cite{BeLu}. Finally I would like to thank Francesco Croce for his careful proofreading.
}

\section{Preliminaries}
An abstract simplicial complex $\Delta$ on $\left[ n\right]=\{1,\dots,n\}$ is \emph{pure} if all facets (i.e., inclusion maximal face) have the same dimension. A simplicial complex is uniquely determined by its facets: for elements $F_i\in2^{\left[ n\right] }$ we define the complex \emph{generated} by $\left\lbrace F_1,\dots,F_m\right\rbrace$ as $\left\langle F_1,\dots,F_m \right\rangle:=\left\lbrace F\in2^{\left[ n\right] } : F\subseteq F_i, \text{ for some }i=1,\dots, m  \right\rbrace$.
We denote with $f_i(\Delta)$ the number of faces of $\Delta$ of dimension $i$, and we collect them together in the \emph{$f$-vector} $f(\Delta)=(f_{-1}(\Delta),f_0(\Delta),\dots,f_{\dim(\Delta)}(\Delta))$.  Given two simplicial complexes $\Delta$ and $\Gamma$, their \emph{join} is defined as $\Delta*\Gamma:=\left\lbrace F\cup G: F\in\Delta, G\in\Gamma \right\rbrace$.
In particular for two vertices $i,j\notin\Delta$ the operations $\Delta*\left\langle \left\lbrace i\right\rbrace  \right\rangle$ and $\Delta*\left\langle \left\lbrace i\right\rbrace ,\left\lbrace j\right\rbrace  \right\rangle$ are the \emph{cone} and the \emph{suspension} over $\Delta$ respectively. To every face $F\in\Delta$ we associate  the simplicial complex $\lk_{\Delta}(F):=\left\lbrace G\in\Delta : F\cup G\in\Delta, F\cap G=\emptyset \right\rbrace$, called the \emph{link} of $\Delta$ at $F$. There is a canonical way to associate to an abstract simplicial complex $\Delta$ a topological space, denoted by $\left| \Delta\right|$, and given a topological space $X$ we say that a \emph{triangulation} of $X$ is any simplicial complex $\Delta$ such that $\left|\Delta \right|\cong X$. For example the complex $\partial\Delta_{d+1}:=\left\langle [d+2]\setminus\left\lbrace i\right\rbrace : i\in[d+2]\right\rangle $ is a standard triangulation of the $d$-sphere $S^{d}$. 
\begin{definition}
	A pure $d$-dimensional simplicial complex $\Delta$ is a \emph{combinatorial $d$-sphere} if $\left| \Delta\right| $ is PL-homeomor\-phic to $\left| \partial\Delta_{d+1}\right|$. A pure connected $d$-dimensional simplicial complex is a \emph{combinatorial $d$-manifold} if the link of each vertex is a combinatorial $(d-1)$-sphere. 
\end{definition}
A relaxation of the above definitions is the class of \emph{$\FF$-homology $d$-manifold}, that is a pure $d$-dimensional simplicial complex $\Delta$ such that the link of every nonempty face $F$ is an \emph{$\FF$-homology $(d-\dim(F)-1)$-sphere}, i.e., $\widetilde{H}_i(\lk_{\Delta}(F),\FF)\cong \widetilde{H}_i(S^{d-\dim(F)-1},\FF)$, for every $i$. In this paper we study a family of simplicial complexes with an additional combinatorial property, introduced by Stanley in \cite{St79}.
\begin{definition}
	A $d$-dimensional simplicial complex $\Delta$ on $[n]$ is \emph{balanced} if there is a map $\kappa:[n]\longrightarrow[d+1]$, such that $\kappa(i)\neq\kappa(j)$ for every $\left\lbrace i,j \right\rbrace\in\Delta$. 
\end{definition}
In other words $\Delta$ is balanced if the graph given by its vertices and edges is $(d+1)$-colorable in the classical graph-theoretic sense, and we often refer to the elements in $[d+1]$ as \emph{colors} and to the preimages of a color as \emph{color class}. Although a priori the map $\kappa$ is part of the data defining a balanced complex, in most of the families considered in this paper $\kappa$ is unique up to permutations of the colors. Again we turn our attention to balanced triangulations of interesting topological spaces. As a guiding example we consider the $d$-dimensional complex
$\partial\mathcal{C}_{d+1}:=\left\langle \left\lbrace 0\right\rbrace ,\left\lbrace v_0\right\rbrace \right\rangle*\dots*\left\langle \left\lbrace d\right\rbrace ,\left\lbrace v_d\right\rbrace \right\rangle$ on the set $\left\lbrace 0,\dots,d,v_0,\dots,v_d\right\rbrace $. This is indeed a balanced vertex minimal triangulation of $S^d$, and it is in particular isomorphic to the boundary of the $(d+1)$-dimensional \emph{cross-polytope}.
In general it is possible to turn any triangulation $\Delta$ of a topological space into a balanced one by considering its \emph{barycentric subdivision} $\text{Bd}(\Delta):=\left\lbrace \left\lbrace v_{F_1},\dots,v_{F_m} \right\rbrace : \emptyset\neq F_1\subsetneq\dots\subsetneq F_m, F_i\in\Delta \right\rbrace$. 
Still more generally, the order complex of a ranked poset is balanced, since the rank function gives the required coloring (see \cite{St79}).  
Among the many results on face enumeration that have been recently proved to have analogs in the balanced setting, we focus on a work of Izmestiev, Klee and Novik. In \cite{IKN} the authors specialize the theory of bistellar flips to the balanced settings by defining the following operation which preserves balancedness. Recall that a subcomplex $\Gamma$ of $\Delta\subseteq 2^{\left[ n\right]}$ is \emph{induced} if $\Gamma=\{F : F\in\Delta, F\subseteq W\}$, for some $W\subseteq\left[ n\right]$.
\begin{definition}\label{cross-flips}
	Let $\Delta$ be a pure $d$-dimensional simplicial complexes and let $\Phi\subseteq\Delta$ be an induced subcomplex that is a $d$-ball and that is isomorphic to a subcomplex of $\partial\mathcal{C}_{d+1}$. The operation
	$$\Delta\longmapsto\chi_{\Phi}(\Delta):=\left( \Delta\setminus\Phi\right)  \cup \left( \partial\mathcal{C}_{d+1}\setminus\Phi \right)$$
	is called a \emph{cross-flip} on $\Delta$.
\end{definition}
In \cite{IKN} the authors require the subcomplexes $\Phi$ and $\partial\mathcal{C}_{d+1}\setminus\Phi$ to be \emph{shellable} (see \Cref{section_decomposition} for a definition). In our work we instead restrict ourselves to a specific family of subcomplexes of $\partial\mathcal{C}_{d+1}$: For $0\leq i \leq d+1$ define
$$\Phi_i:=\begin{cases}
\left\langle \left\lbrace v_{0} \right\rbrace \right\rangle * \left\langle \left\lbrace i+1\right\rbrace ,\left\lbrace v_{i+1}\right\rbrace \right\rangle *\dots* \left\langle \left\lbrace d\right\rbrace ,\left\lbrace v_{d}\right\rbrace \right\rangle & \text{for } i=0, \\
\left\langle \left\lbrace 0,\dots,i-1,v_{i} \right\rbrace \right\rangle * \left\langle \left\lbrace i+1\right\rbrace ,\left\lbrace v_{i+1}\right\rbrace \right\rangle *\dots* \left\langle \left\lbrace d\right\rbrace ,\left\lbrace v_{d}\right\rbrace \right\rangle & \text{for } 1\leq i \leq d, \\
\left\langle \left\lbrace 0,\dots,d\right\rbrace \right\rangle
& \text{for } i = d+1,
\end{cases}$$
and let $\Phi_I:=\bigcup_{i\in I}\Phi_i$, for every $I\subseteq [d+1]$. It is not hard to see that those complexes are indeed shellable subcomplexes of the boundary of the $(d+1)$-dimensional cross-polytope. A cross-flip replacing a subcomplex $\Phi_I$ with its complement $\Phi_J$ (note that this family is closed under taking complements in $\partial\mathcal{C}_{d+1}$) is called a \emph{basic cross-flip}.
The basic cross-flip replacing $\Phi_{\left\lbrace 0\right\rbrace} $ with $\partial\mathcal{C}_{d+1}\setminus \Phi_{\left\lbrace 0\right\rbrace} \cong \Phi_{\left\lbrace 0\right\rbrace}$ is referred to as \emph{trivial flip}, because it does not affect the combinatorics, while every non-trivial basic cross-flips either increases or decreases the number of vertices. We refer to the former as \emph{up-flips} and to the latter as \emph{down-flips}. Moreover two distinct sets $I,J\subseteq[d+1]$, with $I\neq J$, might lead to isomorphic subcomplexes $\Phi_I\cong\Phi_J$, and certain basic cross-flips can be generated (i.e. written as composition) by some others. As an example, the two flips in the middle of \Cref{2_dim} can be obtained via a combination of the remaining four moves (we count the arrows separately). This issues, as well as a description of the possible $f$-vectors of the complexes $\Phi_I$, have been studied in \cite{JV}.
\begin{figure}[h]
	\centering
	\includegraphics[scale=0.8]{2_dim_cross_flips_three_row.pdf}
	\caption{All $6$ non-trivial basic cross-flips for $d=2$.}
	\label{2_dim}
\end{figure} 
\begin{theorem}\cite{JV}.\label{reducedCrossFlips}
	There are precisely $2^{d+1}-2$ non isomorphic non-trivial basic cross-flips in dimension $d$. Moreover $2^{d}$ of them suffice to generate all of them. 
\end{theorem}
%Every non trivial basic cross-flips	either increases or decreases the number of vertices. (see (\textbf{ref}) for a complete description of the $h$-vector of these complexes). We refer to the former as \emph{up flips} and to the latter as \emph{down flips}.
The interest in cross-flips, and in particular in basic cross-flips, relies on the following result by Izmestiev, Klee and Novik.
\begin{theorem}\cite{IKN}.\label{cross-flipsIKN}
	Let $\Delta$ and $\Gamma$ be balanced combinatorial $d$-manifolds. Then the following conditions are equivalent:
	\begin{itemize}
		\item $\Delta$ and $\Gamma$ are PL-homeomorphic;
		\item $\Delta$ and $\Gamma$ are connected by a sequence of cross-flips;
		\item $\Delta$ and $\Gamma$ are connected by a sequence of basic cross-flips.
	\end{itemize} 
\end{theorem}	 
Essentially \Cref{cross-flipsIKN} states that any two balanced PL-homeomorphic combinatorial manifolds can be transformed one into the other by a sequence of a finite number of flips. This serves as a motivation to develop an implementation of these moves, as it was done in the setting of bistellar flips by Bj\"{o}rner and Lutz in \cite{BjLu} with the software BISTELLAR. In particular our goal is to find balanced triangulations of a given manifold on few vertices, since taking barycentric subdivision typically yields complexes with a large vertex set.

\section{The implementation}
The main purpose of our implementation is to obtain small, possibly vertex-minimal, balanced triangulations of surfaces and 3-manifolds starting from the barycentric subdivision of a non-balanced triangulation, many of which can be found in the Manifold Page \cite{Lu}. We first establish some notation: a vertex $v\in\Delta$ is called \emph{removable} if there exists a down flip $\chi_{\Phi}$ such that $v\notin\chi_{\Phi}(\Delta)$. A balanced simplicial complex without removable vertices is called \emph{irreducible}. 
%\begin{remark}
	While a vertex-minimal balanced triangulation is clearly irreducible, the converse is not true. Indeed irreducible triangulations are quite frequent, and they can have a large vertex set, as shown in \Cref{bd_irreducible}.
%\end{remark} 
\begin{lemma}
	Let $\Delta$ be a pure $d$-dimensional balanced simplicial complex. If a vertex $v\in \Delta$ is removable then $f_0(\lk_{\Delta}(v))=2d$. 
\end{lemma}
\begin{proof}
	If the vertex $v$ is removable then there exists an induced subcomplex $\Gamma\subseteq\Delta$ that is isomorphic to an induced subcomplex of $\partial\mathcal{C}_{d+1}$, such that $\Gamma$ is a $d$-ball. Moreover $v$ lies in the interior of $\Gamma$, because vertices on the boundary are preserved. Since the link of a vertex in the interior of a balanced $d$-ball is a balanced $(d-1)$-sphere, and the only such subcomplex of $\partial\mathcal{C}_{d+1}$ is $\partial\mathcal{C}_{d}$, it follows that $\lk_{\Delta}{(v)}\cong\partial\mathcal{C}_{d}$ Hence $f_0(\lk_{\Delta}{(v)})=2d$. 
\end{proof}
\begin{corollary}\label{bd_irreducible}
	Let $\Delta$ be a combinatorial $d$-manifold, with $d\geq 3$. Then the barycentric subdivision $\text{Bd}(\Delta)$ is irreducible.
\end{corollary}
\begin{proof}
	For every vertex $v_F\in \text{Bd}(\Delta)$, corresponding to a $k$-face $F\in\Delta$ we have $\lk_{\text{Bd}(\Delta)}(v_F)\cong\text{Bd}(\partial\Delta_{k})*\text{Bd}(\lk_{\Delta}(F))$. Moreover, since $\lk_{\text{Bd}(\Delta)}(v_F)$ is a combinatorial $(d-k-1)$-sphere, it has at least $f_i(\partial\Delta_{d-k})$ many $i$-faces. Hence
	$$f_0(\lk_{\text{Bd}(\Delta)}(v_F))=2^{k+1}-2+\sum_{i=0}^{d-k-1}f_i(\lk_{\Delta}(F))\geq 2^{k+1}-2+\sum_{i=0}^{d-k-1}f_i(\partial\Delta_{d-k})= 2^{d-k+1}+2^{k+1}-4.$$
	For a fixed $d$ the last expression is minimized when $k=\frac{d}{2}$, and in that case we have $f_0(\lk_{\text{Bd}(\Delta)}(v_F))\geq 4\left( 2^{\frac{d}{2}}-1\right)$, which is strictly larger than $2d$, for $d\geq 3$. 
\end{proof}

The computation above shows that to reduce the barycentric subdivision of a combinatorial $3$-manifold we are forced to start with some up-flips and to first increase the number of vertices, before applying down-flips.
Our code meets two main challenges:
\begin{itemize}
	\item Problem 1. List all the flippable subcomplexes of any combinatorial type;
	\item Problem 2. Decide which type of move to apply and which subcomplex to flip. 
\end{itemize} 
For the first issue we reduce the problem to the one dimensional case, to employ structures and algorithms designed for graphs. We say that a pure strongly connected $d$-dimensional simplicial complex is a \emph{pseudomanifold} if every $(d-1)$-face is contained in exactly two facets.
\begin{definition}
	For a pure $d$-dimensional pseudomanifold $\Delta$ the \emph{dual graph} $G(\Delta)$ is the graph on vertex set $\left\lbrace F \in\Delta: \dim(F)=d\right\rbrace $ and with edge set $\left\lbrace \left\lbrace F_i,F_j\right\rbrace: \dim(F_i\cap F_j)=d-1  \right\rbrace$. 
\end{definition} 
Given a $d$-dimensional pseudomanifold $\Delta$ and a subcomplex $\Phi_{I}\subseteq\partial\mathcal{C}_{d+1}$ we first list all subgraphs of $G(\Delta)$ that are isomorphic to $G(\Phi_{I})$ (using an algorithm such as the VF2 algorithm \cite{CoFoSaVe}), from which we keep only those that correspond to an induced subcomplex. Moreover once a flip $\Delta\longmapsto\chi_{\Phi_I}(\Delta)=:\Delta'$ is performed we do not need to rerun the check on the entire complex to list all the flippable subcomplexes of $\Delta'$, but it suffices to update the list locally, by considering only the induced subcomplexes of $\Delta'$ that are not induced subcomplexes of $\Delta$. Even though this idea allows to deal with relatively large $3$-dimensional complexes, higher dimensions appear to be still out of reach.\\
For the second problem we propose and combine two naive strategies:
given a balanced pseudomanifold $\Delta$ we choose any flippable subcomplex $\Phi$ which maximizes both
\begin{itemize}
	\item $\displaystyle\left| \left\lbrace v\in\chi_{\Phi}(\Delta): f_0(\lk_{\chi_{\Phi}(\Delta)}(v))=2d\right\rbrace \right|$;
	\item  $\displaystyle\sum_{v\in\chi_{\Phi}(\Delta), \ \dim(v)=0}(f_0(\lk_{\chi_{\Phi}(\Delta)}(v)))^2$.  
\end{itemize} 
With the first condition we simply maximize the number of potentially removable vertices, while maximizing the sum of squares of the vertex degrees we force the new triangulation to have an inhomogeneous degree distribution, and hence some very poorly connected vertices. 

\section{Real projective plane, surfaces and the dunce hat}\label{surf_dunce}
\begin{figure}[h]
	\centering
	\includegraphics[scale=0.80]{Projective_balanced_nicer.pdf}
	\quad\quad\quad\quad\quad\quad\quad\quad
	\includegraphics[scale=0.80]{Projective_balanced_8_3.pdf}
	\caption{$\Delta^{\mathbb{R}\mathbf{P}^{2}}_{9}$ represented as the quotient of a disk in two different ways.}	\label{rp}
\end{figure}
The first complexes we consider are triangulations of compact $2$-manifolds. It is well known that in this case the number of vertices uniquely determines the remaining entries of the $f$-vector. In \Cref{tab:table3} we display the smallest known $f$-vector of balanced triangulations of some surfaces found via our program.
In particular we exhibit the unique vertex minimal balanced triangulation $\Delta^{\mathbb{R}\mathbf{P}^{2}}_{9}$ of the real projective plane. The $f$-vector is $f(\Delta^{\mathbb{R}\mathbf{P}^{2}}_{9})=(1,9,24,16)$. The non-balanced vertex-minimal triangulation has 6 vertices.
 
\begin{proposition}\label{rp2}
	The simplicial complex $\Delta^{\mathbb{R}\mathbf{P}^{2}}_{9}$ is a vertex-minimal balanced triangulation of the projective plane. Hence it minimizes every $f_i$.
\end{proposition}

\begin{proof}
	The claim follows from a result of Klee and Novik (\cite{KN}, Proposition 6.1) which states that any balanced triangulation of an homology $d$-manifold $\Delta$ that is not an homology $d$-sphere has at least three vertices in each color class.  
\end{proof}

\begin{table}[h!]
	\small
	
	\[\begin{array}{l|l|l|l|l}
	\left| \Delta\right|  & \text{Min }f(\Delta) &  f(\text{Bd}(\Delta)) & \text{Min. Balanced $f$ known} & \text{Notes} \\\hline
	S^2 & (1,4,6,4) &  (1,14,36,24) & (1,6,12,8)^* & \partial\mathcal{C}_{3}\\
	\mathbb{T} & (1,7,21,14) & (1,42,126,84) & (1,9,24,16)^* & \text{see \cite{KN}} \\
	\mathbb{T}^{\#2} & (1,10,36,24) & (1,70,216,144) & (1,12,42,28) &\\
	\mathbb{T}^{\#3} & (1,10,42,28) & (1,80,252,168) & (1,14,54,36)& \\
	\mathbb{T}^{\#4} & (1,11,51,34) & (1,96,306,204)  & (1,14,60,36)& \\
	\mathbb{T}^{\#5} & (1,12,60,40) & (1,112,360,240)  & (1,16,72,48)& \\
	\mathbb{R}\mathbf{P}^{2} & (1,6,15,10) & (1,31,90,60) & (1,9,24,16)^* & \Delta^{\mathbb{R}\mathbf{P}^{2}}_{9}\\
	(\mathbb{R}\mathbf{P}^{2})^{\#2} & (1,8,24,16) & (1,48,144,96) & (1,11,33,22) & \\
	(\mathbb{R}\mathbf{P}^{2})^{\#3} & (1,9,30,20) & (1,59,180,120) & (1,12,39,26) & \\
	(\mathbb{R}\mathbf{P}^{2})^{\#4} & (1,9,33,22) & (1,64,198,132) & (1,12,42,28) & \\
	(\mathbb{R}\mathbf{P}^{2})^{\#5} & (1,9,36,24) & (1,69,216,144) & (1,13,48,32) & \\
	\end{array}
	\]
	\caption{A table reporting some small $f$-vectors of balanced surfaces. The symbol "*" indicates that the $f$-vector is minimal. }
	\label{tab:table3}
\end{table}
The dunce hat is a topological space which exhibits interesting properties: it is contractible but non-collapsible, and it is Cohen-Macaulay (see \cite{Stanley-greenBook}) over any field but none of its triangulations are shellable (see \Cref{section_decomposition}). It can be visualized as a triangular disk whose edges are identified with a non-coherent orientation. \Cref{dunce} (left) depicts a balanced triangulation of the dunce hat $\Delta^{\text{DH}}$, with $f$-vector $f(\Delta^{\text{DH}})=(1,11,34,24)$. We prove that this is indeed the least number of vertices that a balanced triangulation of the dunce hat can have. For the rest of this section with \emph{singularity} of a triangulation of the dunce hat we indicate the $1$-dimensional subcomplex of faces whose links are not spheres, and denote the number of vertices in the singularity by $f_0^{\text{sing}}$.
Since the dunce hat is not a manifold the number of vertices of a triangulation does not uniquely determine the other face numbers, but its $f$-vector satisfies the following equations:
\begin{equation}\label{f_relations}
\begin{cases}
f_0-f_1+f_2=1\\
f_0^{\text{sing}}+2f_1-3f_2=0
\end{cases}.
\end{equation}
In particular it holds that $f_1=f_0^{\text{sing}}+3f_0-3$. We proceed now with a sequence of lemmas leading to \Cref{prop_dunce}, proving that the triangulation in \Cref{dunce} is indeed a balanced vertex-minimal triangulation of the dunce hat.

\begin{lemma}\label{at_least_2_per_class}
	Let $\Delta$ be a balanced $2$-dimensional Cohen-Macaulay complex that is not shellable. Then each color class contains at least two vertices. Moreover if every edge of $\Delta$ is contained in at least two triangles, then each color class contains at least three vertices.
\end{lemma}
\begin{proof}
	If there exists a color class containing only one vertex $v$ then $\Delta$ is a cone over the $1$-dimensional Cohen-Macaulay complex $\lk_{\Delta}(v)$. But since every $1$-dimensional Cohen-Macaulay complex is shellable, and since coning preserves shellability this implies that $\Delta$ is shellable.
	Assume that every edge of $\Delta$ is contained in at least two triangles. If there are only two vertices of color 1, then $\Delta$ is the suspension over the 1-dimensional complex $\Delta_{\left[23\right]}$ of all faces not containing color 1. $\Delta_{\left[23\right]}$ is Cohen-Macaulay (see \cite{Stanley-greenBook}) and 1-dimensional, and hence shellable. Since taking suspensions preserves shellability this yields a contradiction.
\end{proof}

We call a pair of vertices ${i,j}$ of $\Delta$ such that $\left\lbrace i,j\right\rbrace \notin \Delta$ and $\kappa(i)\neq\kappa(j)$ a \emph{bichromatic missing edge} of $\Delta$ .
\begin{lemma}\label{at_least_10}
	Let $\Delta$ be a balanced triangulation of the dunce hat. If $f_0^{\text{sing}}\geq 4$ then $f_0(\Delta)\geq 10$.  Let $m$ be the number of bichromatic missing edges of $\Delta$. If $f_0^{\text{sing}}+m\geq 7$ then $f_0(\Delta)\geq 11$.
\end{lemma}
\begin{proof}
	For any balanced $2$-dimensional simplicial complex $\Delta$ with $n_i$ vertices of color $i$ ($i=1,2,3$), the number of edges of $\Delta$ is the number of edges of the complete $3$-partite graph $K_{n_1,n_2,n_3}$, which equals $\left| E(K_{n_1,n_2,n_3})\right|=n_1n_2+n_1n_3+n_2n_3$, minus the number of missing bichromatic edges $m$. Hence using \eqref{f_relations} we obtain
	\begin{equation}\label{inequality_dunce}
	f_0^{\text{sing}}+3f_0(\Delta)-3=f_1(\Delta)= n_1n_2+n_1n_3+n_2n_3-m\leq \frac{f_0(\Delta)^2}{3}-m,
	\end{equation}
	where the last inequality follows by maximizing the function $n_1n_2+n_1n_3+n_2n_3$, under the constraint $\sum_{i=1}^{3}n_i=f_0(\Delta)$. Solving the inequality $f_0^{\text{sing}}+3f_0(\Delta)-3\leq \frac{f_0(\Delta)^2}{3}$ for $f_0(\Delta)$ yields
	$$f_0(\Delta)\geq\dfrac{9+\sqrt{81+12(f_0^{\text{sing}}+m)-36}}{2}.$$
	If we assume $f_0^{\text{sing}}\geq 4$ we obtain $f_0(\Delta)\geq 9,32$, for any $m\geq 0$.
	The second statement follows in the same way by imposing $f_0^{\text{sing}}+m\geq 7$, which yields $f_0(\Delta)\geq 10,18$.
\end{proof}
In order to prove that the minimum number of vertices for a balanced triangulation of the dunce hat is 11 it remains to show that no such simplicial complex exists with $f_0(\Delta)\leq11$ and $f_0^{\text{sing}}=3$, or $f_0(\Delta)=10$ and $f_0^{\text{sing}}\in\left\lbrace 3,4,5,6 \right\rbrace$. This is done by studying the possible configurations of colors in the singularity in each case. For the sake of brevity the proof is not reported here.

\begin{figure}[h]
	\centering
	\includegraphics[scale=0.58]{Dunce_11_nicer.pdf}
	\quad\quad\quad\quad\quad
	\includegraphics[scale=0.7]{link_RP3_v2_space.pdf}
	\caption{Minimal balanced triangulation $\Delta^{\text{DH}}$ of the dunce hat (left) and the (all isomorphic) vertex links of the triangulation $\Delta^{\mathbb{R}\mathbf{P}^{3}}_{16}$ (right). }
	\label{dunce}
\end{figure} 
\begin{theorem}\label{prop_dunce}
	The simplicial complex in \Cref{dunce} (left) is a vertex-minimal balanced triangulation of the dunce hat.
\end{theorem}
\begin{remark}
	We observe that the two simplicial complexes in this section are not order complexes of a ranked poset. In fact order complexes are \emph{flag} (i.e., their minimal non-faces are edges), while both $\Delta^{\mathbb{R}\mathbf{P}^{2}}_{9}$ and $\Delta^{\text{DH}}$ have missing triangles.
\end{remark}
%\begin{proof}
%	The claim follows combining \Cref{f0sing=3}, \Cref{at_least_10} and \Cref{no10}, which show that no such triangulation exists on less than 11 vertices, for any value of $f_0^{\text{sing}}$. 
%\end{proof}
\section{Real projective space and balanced $3$-manifolds}
In this section we report some interesting and small balanced triangulations of $3$-manifolds found using our computer program.
	
There exists a peculiar balanced triangulation $\Delta^{\mathbb{R}\mathbf{P}^{3}}_{16}$ of the real projective space with $f$-vector $f(\Delta^{\mathbb{R}\mathbf{P}^{3}}_{16})=(1,16,88,144,72)$. An interesting feature of this complex is its strong symmetry: it is \emph{centrally symmetric} (i.e., there is a free involution acting) and all the vertex links are isomorphic to the $2$-sphere in \Cref{dunce} (right). Since a result of Zheng \cite{Zh17} shows that any balanced triangulation of a \emph{lens space} $L(p,q)$ with $p>1$ has at least 4 vertices per color class, and $\mathbb{R}\mathbf{P}^{3}\cong L(2,1)$ we obtain the following.
	\begin{proposition}\label{lens_at_least_16}
		The simplicial complex $\Delta^{\mathbb{R}\mathbf{P}^{3}}_{16}$ is a vertex-minimal balanced triangulation of the real projective space.
	\end{proposition}
	In \Cref{tab:table2} we report the smallest known $f$-vectors of balanced triangulations for several $3$-manifolds, such as several lens spaces $L(p,q)$, connected sums, two additional spherical 3-manifolds called the octahedral space and the cube space, and the Poincar\'{e} homology $3$-sphere. The lists of facets of all the triangulations appearing in \Cref{tab:table2} can be found in \cite{GitRepo}. We point out that some of these triangulations were previously constructed, as referenced in the table. A classical theorem in topology by Edwards and Cannon (see e.g., \cite{Dav}) states that the $k$-fold suspension of any homology $d$-sphere is homeomorphic to $S^{d+k}$, even though it is not a combinatorial sphere. Since balancedness is preserved by taking suspensions we obtain a family of non-combinatorial balanced triangulations of $S^{d}$, for $d\geq 5$. 

	\begin{corollary}
		There exists a balanced non-combinatorial $5$-sphere with $f$-vector $(1,30,288,1132,\\
		106,1848,616)$. Moreover by taking further suspensions we obtain a balanced non-combinatorial $d$-sphere on $2d+20$ vertices, for every $d\geq 5$.
	\end{corollary}

	\begin{table}[h!]
		\small
		\[\begin{array}{l|l|l|l|l}
		\left| \Delta\right|  & \text{Min }f(\Delta) &  f(\text{Bd}(\Delta)) & \text{Min. Bal. $f$ obtained} & \text{Notes} \\\hline
		S^3 & (1,5,10,10,5) & (1,30, 150, 240, 120) & (1,8,24,32,16)^* & \partial\mathcal{C}_{4}\\
		S^2\times S^1 & (1,10,42,64,32) & (1,148,916,1536,768) & (1,14,64,100,50)^* & \text{see \cite{KN}}\\
		S^2\dtimes S^1 & (1,9,36,54,27) & (1,126,774,1296,648) & (1,12,54,84,42)^* & \text{see \cite{KN}}\\
		\mathbb{R}\mathbf{P}^{3} & (1,11,51,80,40) & (1, 182, 1142, 1920, 960) & (1, 16, 88, 144, 72)^* & \Delta^{\mathbb{R}\mathbf{P}^{3}}_{16}\\
		L(3,1) & (1,12,66,108,54) & (1, 240, 1536, 2592, 1296) & (1, 16, 96, 160, 80)^* & \text{see \cite{Zh17}}\\
		L(4,1) & (1,14,84,140,70) & (1, 308, 1988, 3360, 1680) & (1, 20, 132, 224, 112) &\\
		L(5,1) & (1,15,97,164,82) & (1, 358, 2326, 3936, 1968) & (1, 22, 152, 260, 130) &\\
		L(5,2) & (1,14,86,144,72) & (1, 316, 2044, 3456, 1728) & (1,20,132,224,112)&\\
		L(6,1) & (1,16,110,188,94) & (1,408,2664,4512,2256) & (1,24,176,304,152) & \\
		(S^2\times S^1)^{\#2} & (1,12,58,92,46) & (1, 208, 1312, 2208, 1104) & (1,16,84,136,68)& \\
		(S^2\dtimes S^1)^{\#2} & (1,12,58,92,46) & (1, 208, 1312, 2208, 1104) & (1,16,84,136,68)& \\
		(S^2\times S^1)\#\mathbb{R}\mathbf{P}^{3} & (1,14,73,118,59) & (1, 264, 1680, 2832, 1416) & (1,20,118,196,98) & \\
		(\mathbb{R}\mathbf{P}^{3})^{\#2} & (1,15,86,142,71) & (1,314,2018,3408,1704) & (1,21,137,232,116) & \\
		(S^2\times S^1)^{\#3} & (1,13,72,118,59) & (1,262,1678,2832,1416) & (1,20,118,196,98)& \\
		(S^2\dtimes S^1)^{\#3} & (1,13,72,118,59) & (1,262,1678,2832,1416) & (1,19,111,184,92)& \\
		S^1\times S^1\times S^1 & (1,15,105,180,90) & (1,390,2550,4320,2160) & (1,24,168,288,144)& \\
		\text{Oct. space} & (1,15,102,174,87) & (1,378,2466,4176,2088) & (1,24,168,288,144)& \\
		\text{Cube space} & (1,15,90,150,75) & (1,330,2130,3600,1800) & (1,23,157,268,134)& \\
		\text{Poincar\'{e}} & (1,16,106,180,90) & (1, 392, 2552, 4320, 2160) & (1, 26, 180, 308, 154) &\\
		\mathbb{R}\mathbf{P}^{2}\times S^1 & (1,14,84,140,70) & (1, 308, 1988, 3360, 1680) & (1, 24, 156, 264, 132) &\\
		\text{Triple-trefoil} & (1,18,143,250,125) & (1,536,3536,6000,3000) & (1, 28, 204, 352, 176) & \Delta^{3T}_{28}\\
		\text{Double-trefoil} & (1,16,108,184,92) & (1, 400, 2608, 4416, 2208) & (1, 22, 136, 228, 114) & \Delta^{2T}_{22}\\
		\end{array}
		\]
		\caption{A table reporting some small $f$-vectors of balanced $3$-manifolds. The symbol "*" indicates that the $f$-vector is componentwise minimal.}
		\label{tab:table2}
	\end{table}

	\subsection{Non-vertex decomposable and non-shellable balanced $3$-spheres}\label{section_decomposition}
	In this paragraph we exhibit two interesting balanced triangulations of the $3$-sphere, namely one that is shellable but not vertex decomposable and a second one which is not constructible, and hence not shellable. We start with some definitions.
	\begin{definition}
		Let $\Delta$ be a pure $d$-dimensional simplicial complex. We say that $\Delta$ is \emph{vertex decomposable} if $\Delta\cong\Delta_d:=2^{[d+1]}$ or there exists a vertex $v$ such that $\lk_{\Delta}(v)$ and $\Delta\setminus v:=\left\lbrace F\in\Delta: v\notin F \right\rbrace $ are vertex decomposable. $\Delta$ is \emph{shellable} if there exists an ordering $F_1,\dots,F_m$ of its facets such that the complex $\left\langle F_1,\dots,F_{i-1}\right\rangle \cap\left\langle F_i\right\rangle$ is pure and $(d-1)$-dimensional for every $1\leq i \leq m$.
		$\Delta$ is \emph{constructible} if $\Delta\cong\Delta_d$ or $\Delta=\Gamma_1\cup\Gamma_2$, where $\Gamma_1$, $\Gamma_2$ and $\Gamma_1\cap\Gamma_2$ are constructible, $\dim(\Gamma_1)=\dim(\Gamma_2)=d$ and $\dim(\Gamma_1\cap\Gamma_2)=d-1$. 
	\end{definition}
	It is well known that shellable complexes are constructible, and vertex decomposable complexes are shellable. Interestingly while there exist shellable $3$-spheres which are not vertex decomposable, the existence of constructible, but not shellable $3$-spheres is still open. In order to obtain interesting, possibly small balanced triangulations we again start from the barycentric subdivision of $3$-spheres with a sufficiently complicated knot embedded in their \emph{1-skeleta} (i.e., the subcomplex of all faces of dimension at most 1). In particular we turn our attention to the connected sum of $2$ or $3$ \emph{trefoil knots}, called a \emph{double-trefoil} and a \emph{triple-trefoil}. The reason for this choice is that in general the barycentric subdivision might turn non-shellable simplicial complexes into shellable ones, while complicated knot are obstructions to shellability which resist to the subdivision. We employ the following rephrasing of results by Ehrenborg and Hachimori (\cite{EhHa}), and Hachimori and Ziegler \cite{HaZi}.
	\begin{theorem}\cite{EhHa}, \cite{HaZi}.\label{knot_BZ}
		Let $\Delta$ be a triangulation of a $3$-sphere. If the 1-skeleton of $\Delta$ contains a double-trefoil knot on 6 edges then $\Delta$ is not vertex decomposable. If the 1-skeleton of $\Delta$ contains a triple-trefoil knot on 6 edges then $\Delta$ is not constructible (hence not shellable).
	\end{theorem}
	For an introduction to knot theory and a rigorous definition of complicatedness of knots we defer to a work of Benedetti and Lutz \cite{BeLu}, where triangulations of the $3$-sphere containing the double and triple-trefoil knot on 3 edges were constructed: the first has 16 vertices (see $S_{16,92}$ in \cite{BeLu}), while the second has 18 vertices ($S_{18,125}$). Using our computer program we take the barycentric subdivision of these two complexes and we reduce them only applying cross-flips preserving the subdivision of the knots, which consist of 6 vertices and 6 edges. More precisely we only allow flips of the form $\Delta\longmapsto\chi_{\Phi}(\Delta)$, where the interior of $\Phi$ does not contain any of the 6 edges of the knot. \Cref{knot_BZ} guarantees that in this way the obstructions for vertex decomposability and shellability are preserved, so as an output we obtain the following.
	\begin{proposition}
		There exist balanced triangulations of the $3$-sphere $\Delta^{2T}_{22}$ $\Delta^{3T}_{28}$, such that: $\Delta^{2T}_{22}$ is shellable, but not vertex decomposable, and $f(\Delta^{2T}_{22})=(1,22,136,228,114)$, while $\Delta^{3T}_{28}$ is non-constructible (hence non-shellable), and $f(\Delta^{3T}_{28})=(1,28,204,352,176)$.
	
	\end{proposition} 



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