%% 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{99}
\addbibresource{99.bib}

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

\newtheorem{theorem}{Theorem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{prueba}[theorem]{Proof}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}
\newtheorem{algorithm}[theorem]{Algorithm}

\newcommand{\PS}{\mathrm{PS}}
\newcommand{\BB}{\mathcal{B}}
\newcommand{\CC}{\mathcal{C}}
\newcommand{\EE}{\mathcal{E}}
\newcommand{\FF}{\mathcal{F}}
\newcommand{\II}{\mathcal{I}}
\newcommand{\MM}{\mathcal{M}}
\newcommand{\NN}{\mathcal{N}}
\newcommand{\LL}{\mathcal{L}}
\newcommand{\OO}{\mathcal{O}}
\newcommand{\QQ}{\mathcal{Q}}

\newcommand\preceqdot{\mathrel{\ooalign{$\preceq$\cr
  \hidewidth\raise0.225ex\hbox{$\cdot\mkern0.5mu$}\cr}}}

%% define your title in the usual way
\title[Matroids with prescribed topology]{Finiteness theorems for matroid complexes with prescribed topology}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Federico Castillo\addressmark{1} \and Jos\'e Alejandro Samper\addressmark{2}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}University of Kansas \\ \addressmark{2}University of Miami\\}

%% 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{It is known that there are finitely many simplicial complexes (up to isomorphism) with a given number of vertices. Translating to the language of $h$-vectors, there are finitely many simplicial complexes of bounded dimension with $h_1=k$ for any natural number $k$. In this paper we study the question at the other end of the $h$-vector: given $d$ and $k$ there are only finitely many $d-1$-dimensional independence complexes, broken circuit complexes, and order complexes of geometric lattices (without coloops) with $h_d = k$. This suggests new upper/lower bound programs for these types of simplicial complexes.}

\resumetitle{Resumen}
%% put your French abstract here, or comment this out if you don't have one
\resume{Es conocido que hay finitos complejos simpliciales (m\'odulo isomorfismo) con un n\'umero de vertices fijo. En el lenguage de $h$-vectores, hay finitos complejos simpliciales que satisfacen $h_1=k$ para $k$ fijo. En esta nota estudiamos la pregunta al extremo opuesto del $h$-vector: dados $d$ y $k$ hay finitos complejos de independencia, complejos de circuitos cortados, y complejos de orden, con dimension $d-1$ y $h_d=k$. Esto sugiere nuevos programas para determinar cotas inferiores y superiores para estos tipos de complejos.}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Matroids, broken circuit complexes, geometric lattices.}

%% 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{BIBLIO.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}

This paper aims to present a new approach to the study of matroids from the perspective of the topology of various simplicial complexes. In the survey \cite{bjorner}, Bj\"orner presented the story of three complexes associated to a matroid: the independence complex, the broken circuit complex, and the order complex of its lattice of flats. We introduce a program that aims to study, for each of the three associated complexes, all matroids whose complex has a fixed homotopy type.

%To understand the various aspects of the topology of the aforementioned complexes we start by recalling that they are all shellable and hence homotopy equivalent to the wedge of some finite number of equidimensional spheres. The homotopy type is then completely determined by two parameters, the dimension and the Euler characteristic.


The program is cast in the language of $h$-numbers, and their equivalent relatives $f$-numbers. These invariants have been extensively studied and are the subject of widely celebrated new results and old conjectures. For instance, the recent resolution of the Rota-Herron-Welsh conjecture by Adiprasito, Huh and Katz \cite{AHK} can be interpreted as a set of inequalities on $f$-vectors of broken circuit complexes. Other recent breakthroughs include the proof, by Ardila, Denham and Huh \cite{Ardila-slides}, that the $h$-vector of any broken circuit complex is log concave, and the solutions of Br\"and\'en-Huh \cite{BH} and Anari-Lui-Oreis Gharan-Vinzant \cite{ALOV} of the strongest version of Mason's conjecture for $f$-vectors of independence complexes. 

From the work of Chari \cite{Chari} (for independence complexes), Nyman and Swartz \cite{EdNym} (for order complexes of geometric lattices), and Juhnke-Kubitzke and Van Dihn \cite{Martina} (for broken circuit complexes) we now know that the $h$-vector in all these cases is \emph{flawless}. In terms of the entries it says that if $h= (h_0, \dots h_s)$ is the $h$-vector of a complex, with $h_s\neq 0$ and  $\delta = \lfloor \frac s2 \rfloor$, then $h_0 \le h_1 \le \dots \le h_\delta$. and $h_i \le h_{s-i}$ for $i\le \delta$. 

%The $h$-vector of any simplicial complex remains fixed when coned: the extra dimension gets a zero. Independence and broken circuit complexes are special in the sense that that if they $d-1$-dimensional and not cones,   then $h_d\neq 0$. Order complexes of geometric lattices are never contractible and shellable, so $h_d\neq 0$ in all cases. 

If $i<d$ and the $h$-vector is flawless, then $h_i \ge h_1= f_0-d$, where $f_0$ is the number of vertices. It follows that, after fixing $k$ and $d$, the number of (isomorphism types of) complexes of rank $d$ with $h_i=k$ and no cone vertices is finite. This is however, far away from the case if we consider $h_d$ instead: the $g$-theorem \cite[Theorem 1.1 Section III]{greenbook} implies that the $h$-vector of the boundary of any $(d-1)$-dimensional simplicial polytope is flawless and has $h_d=1$. 

Surprisingly for independence complexes, broken circuit complexes, and geometric lattices, the restriction for $h_d$ still implies finiteness. 

\subsection{Independence complexes}

%Perhaps the most intriguing conjecture about matroid $h$-vectors is due to Stanley~\cite{Stanley77}. It posits that the $h$-vector of a matroid independence complex is a pure $O$-sequence. This means that, given one such $h$-vector $(h_0, \dots, h_d$), there is a finite collection of monomials $\mathcal S$ satisfying the following three properties: \begin{enumerate}\item[i.]  $\mathcal S$ is closed under divisibility, 
%\item [ii.] $\mathcal S$ has $h_i$ monomials of degree $i$, and
%\item[iii.] Every monomial in $\mathcal S$ divides a monomial of degree $d$ in $\mathcal S$. 
%\end{enumerate}
%Of this three conditions, the third is the toughest to achieve. It follows from the results in \cite{Stanley77} that $\mathcal S$ can be constructed satisfying the other two conditions. The proof yields a collection of inequalities satisfied by the entries of the $h$-vectors. However $h$-vector families are much smaller in all our three cases, than  the family of $h$-vectors satisfying conditions [i.] and [ii.], i.e. the class Cohen-Macaulay simplicial complexes. The third property is perhaps an attempt to capture this for matroid independence complex. It is the combinatorial analogue of a result in the realm of commutative algebra: the Artinian reduction of the Stanley-Reisner ring (over any field) of the independence complex of a matroid is level \cite[Theorem 3.4 Section III]{greenbook}. 
%
%Among enumerative consequences of [iii.] is that $h_1$ is bounded above in terms of $h_d$: all monomials of degree one divide one monomial of degree $d$, thus $h_1 \le dh_d$. 
%This in turn, would yield a finiteness result that is the starting point of this paper: we don't need Stanley's conjecture to obtain much better bounds than the prediction of this conjecture. The consequences of such a statement are strong. 
\begin{theorem}\label{thm:main} Let $d,k$ be positive integers. There are finitely many isomorphism classes of loopless rank $d$ matroids $M$ whose independence complex satisfies $h_d(\II(M))=k$. 
\end{theorem}
This result should be surprising at first sight. However, it is a natural consequence of several results that exist in the literature, some dating back to 1980. 

\cref{thm:main} implies that there are upper bounds on all $h$-numbers in terms of $h_d$. On the other hand, lower bounds exist from the fact that the $h$-vector is an $O$-sequence. Thus it seems reasonable to launch a program to understand extremal matroids for upper and lower bounds for matroid independence complexes with fixed rank and topology. 
%
%Notice that a similar program for simplicial polytopes in terms of vertices and dimension has been widely successful: it leads to the stories of neighborly and stacked polytopes. On the other hand its counterpart for matroids based in rank and the number of vertices does not say much. For example, all upper bounds are achieved trivially by uniform matroids. 

%In contrast, by using the top $h$-number instead, the upper bound analogue has a non-trivial maximizer and restricting to the classes of simple and connected matroids changes the problem drastically. For lower bounds, uniform matroids are entrywise minimizers but only for certain values of $h_d$ (namely, in the case $k=\binom{s}{d-1}$). (and speculate about the behavior of minimizers for other values of $h_d$. )

Another natural path to follow is trying to estimate the size of the set $\Psi_{d,k}$ of all isomorphism classes of loopless matroids of rank $d$ with $h_d=k$. It is a priori not clear that such a set is not empty, but we provide several examples in each class. Furthermore, we provide non-trivial upper and lower bounds for the cardinality of $|\Psi_{d,1}|$. In particular, we extend a result of Chari, who showed that $|\Psi_{d,1}| = p(d)$, the number of integer partitions of $d$. 

\begin{theorem}\label{thm:ref} Let $d,k>0$ and let $T_{d,k}$ be the number of matroids of rank at most $d$ with at most $k$ bases. Then \[2^dkT_{d,k}\ge |\Psi_{d,k}| \ge |\Psi_{d,1}| = p(d).\]
\end{theorem}

The bounds above are far from tight. Nonetheless we expect the asymptotics to be close to the upper bound. It is not even clear that the cardinality of $\Psi_{d,k}$ increases as $d$ or $k$ increase. Furthermore, restricting to the subset $\Sigma_{d,k}$ of $\Psi_{d,k}$ that consists of simple matroids one observes the following:  $|\Sigma_{2,1}| = 1 > 0 = |\Sigma_{2,2}|$. Hence a different behavior in the case of simple matroids is expected.  

\subsection{Broken circuit complexes}

A natural question that follows after studying independence complexes is that of broken circuit complexes. They arise naturally in the study of hyperplane arrangements and are a meaningful generalization of matroids: every matroid is a reduced broken circuit complex. 

\begin{theorem}\label{thm:nbc}
Let $d,k$ be positive integers. The number of isomorphism classes of simple connected, rank $d$ ordered matroids $M$ whose reduced broken circuit complex satisfies $h_{d-1}(\overline{BC_<(M)})=k$ is finite. %The nbc complex of such matroids are exactly the ones that are homotopy equivalent to a wedge of $k$ copies of $\mathbb{S}^{d-2}$. 
\end{theorem}

%It turns out that they are shellable, and their face numbers are coefficients of the characteristic polynomial. Thus the Rota-Herron-Welsh conjecture concerns those numbers. 

It is known that $h$-vectors of broken circuit complexes properly contain the $h$-vectors of matroids (see \cite{greenbook}). The real reason for the difference is not fully understood. There are examples of broken circuit complexes whose $h$-vector is not a pure $O$-sequence and others which do not admit convex ear decompositions. However, numerical inequalities known to be satisfied by $h$-vectors of matroids are also known to hold for broken circuit complexes after the recent work of Ardila, Denham and Huh. 
%After a few remarks about the nbc complex, we conjecture that the analogue of Theorem~\ref{thm:main} holds for nbc complexes too, and speculate about how the proof looks like. In particular, adapting the proofs using $PS$-spheres and balls is not possible due to arguments of Swartz, which motivates a detailed consideration of the proof using the internal order. As a motivation, we show that nbc bases form an order ideal of the poset, which seems to connect to one of the proofs for matroids. 
\subsection{Geometric lattices}
Interest in geometric lattices has flourished significantly in the last two decades due to their connection with tropical geometry. They are connected to tropical linear spaces via the Bergman fan of $M$. After after intersecting the fan with a unit sphere, the remaining cellular complex is triangulated a geometric realization of the order complex of the lattice of flats of $M$. See for instance \cite{Ardila-Klivans}. It is also crucial in the study of the Chow ring of a matroid and its Hodge structure \cite{AHK}. Even more, Huh and Wang \cite{Huh-Wang} recently proved Dowling's top heavy conjecture for representable geometric lattices: a theorem on numerical invariants of the lattice, by studying again elements of Hodge theory. It is therefore desirable to get a better grasp of aforementioned invariants from a different point of view, which as a way to complement the new results.

Hidden in one of the exercises in \cite[Problem 100.(d) Ch. 3 ]{EC1} is the following result: the number of isomorphism classes of simple, loop and coloop free matroids whose geometric lattice is homotopy equivalent to a wedge of $k$ spheres (independently of dimension!) is finite. This is much stronger than the result for independence complexes and can be expressed in terms of Euler characteristics, M\"obius functions or the top non-zero $h$-number of the order complex of the proper part of the lattice. Even though the result is stated in Stanley's book, there seems to be no published proof. 


\begin{theorem}\label{thm:flats}
Let $d,k$ be positive integers. The number of isomorphism classes of simple matroids $M$ of rank $d$ whose geometric lattice, $\LL(M)$, satisfies $|\mu(\LL(M))|=k$ is finite. Furthermore if we restrict to coloopless matroids, we can drop the rank condition.
\end{theorem}
%One proof of the above mentioned result and a sketch of weaker rank dependent result are included, mainly because their flavor is similar to that of independence complexes and it looks like the techniques can be improved to obtain additional structural properties that complement and deepen Stanley's result. Several new questions are posed and a similar upper an lower bound program is proposed. In this case many other invariants are relevant. 



\section{Definitions and notation}
This section is devoted to defining, summarizing and relating various aspects of matroid theory that appear in the arguments of this paper. See \cite{greenbook} for more detailed definitions.

\subsection{Simplicial complexes} A simplicial complex $\Delta$ is a collection of subsets of a finite set $E$ that is closed under inclusion. Any simplicial complex admits a geometric realization, a topological space whose different aspects (geometric and topological) encode the information about the complex. The topology of a simplicial complex refers to the topology of its geometric realization. Throughout this paper we use reduced simplicial homology with rational coefficients. 

%Elements of a simplicial complex $\Delta$ are called faces. The complex $\Delta$ is said to be \emph{pure} if all its maximal faces have the same cardinality. For a subset $A$ of the base set of $\Delta$ (also known as the ground set or vertex set), let $\Delta|_A$ be the complex consisting of the faces of $\Delta$ contained in $A$. The complex $\Delta|_A$ is said to be an \emph{induced} subcomplex of $\Delta$. The \emph{dimension} of a face of a complex is one less than its cardinality and the dimension of a complex is the maximal dimension of its faces. The $f$-vector $(f_{-1}, f_0, f_1, \dots , f_{d-1})$ of a simplicial complex $\Delta$ is the enumerator of faces by dimension, i.e., $f_k$ denotes the number of $k$-dimensional faces of $\Delta$. The $h$-vector of a complex $\Delta$ is a vector that carries the exact same information as the $f$-vector. It is defined as the vector of coefficients of the $h$-polynomial $h(\Delta, t) = \sum_{i=0}^d h_it^i = \sum_{i=0}^d f_{i-1}t^i(1-t)^{d-i}$. We refer the readers to \cite{greenbook} for details and undefined terminology.

Let $\Delta_1$ and $\Delta_2$ be simplicial complexes on disjoint ground sets $E_1$ and $E_2$, the join $\Delta_1*\Delta_2$ is the complex on the ground set $E_1\cup E_2$ whose faces are unions of faces of $\Delta_1$ and $\Delta_2$.  Joins of several complexes are defined in the natural straightforward way. The join of  two spheres is again  a sphere and the join of a sphere and a ball yields another ball. A simplicial complex $\Delta$ is said to be \emph{join irreducible} if it is not equal to the join of two non-trivial subcomplexes. 

\subsection{PS ear decompositions.}
The \emph{full $d$-simplex} $\Gamma_d$ is the simplicial complex whose faces are all the subsets of a set with $d+1$ elements: it is homeomorphic to a $d$-dimensional ball. The \emph{boundary of the $d$-simplex} $\hat \Gamma_d$ is the set of proper subsets of a set with $d+1$ elements: it is homeomorphic to a $(d-1)$-sphere.
A \emph{$\PS$-sphere} is a join of boundaries of simplices $\hat\Gamma_{d_1}\ast \hat\Gamma_{d_2}\ast\dots \ast\hat\Gamma_{d_k}$. It is homeomorphic to a sphere of dimension $d_1+d_2+\dots +d_k -1$. 
\begin{lemma}\label{lem:hmax}
Let $\Delta$ be any $\PS$-sphere of dimension $d-1$. For every $1\le i \le d$, the following inequality holds: \begin{equation}h_i(\Delta)\leq \binom{d}{i}.\end{equation}
Consequently, $f_{d-1}(\Delta)\leq 2^d$.
\end{lemma}
\begin{proof}
The join operation on simplicial complexes has the effect of multiplying the respective $h$-polynomials. We have that $h(\hat\Gamma_d,t)=1+t+\cdots+t^{d}$, and $h(\hat\Gamma_1^{d},t)=(1+t)^{d}$, where $\hat\Gamma_1^{d}$ is the join of $d$ boundaries of segments.
This implies that, coefficient by coefficient, we have $h(\hat\Gamma_d,t)\leq h(\hat\Gamma_1^{d},t)$.

For a general $\PS$-sphere we have 
$h(\hat\Gamma_{d_1}\ast \hat\Gamma_{d_2}\ast\dots \ast\hat\Gamma_{d_k}, t) = h(\hat\Gamma_{d_1},t)h(\hat\Gamma_{d_2},t)\cdots h(\hat\Gamma_{d_k}, t)\leq h(\hat\Gamma_1^{d_1},t)h(\hat\Gamma_{1}^{d_2},t)\cdots h(\hat\Gamma_{1}^{d_k}, t)=h(\hat\Gamma_1^d,t)$, where $d=d_1+\cdots+d_k$, showing the inequality we wanted. The combinatorially unique maximizer is $\hat\Gamma_1^d$ and it is equal to $\partial \Diamond_d$, the boundary of a $d$-dimensional crosspolytope.\end{proof}

A $\PS$-ball is a complex of the form $\Sigma * \Gamma_\ell$, where $\Sigma$ is a PS-sphere. This is a cone over $\hat\Sigma$ with apex the whole ball $\Gamma_\ell$.
The (topological) boundary of such a PS-ball is the PS-sphere $\Sigma\ast\hat\Gamma_{\ell}$. Notice that, unless $\ell =0$, the vertices of a PS-ball are all in the boundary. In the special case $\ell = 0$ the PS ball has one interior vertex. 

\begin{definition}\label{def:ear}
Let $\Delta$ be a simplicial complex and $K\cong\Sigma * \Gamma_\ell$ a PS-ball with $\dim(\Delta)=\dim(K)$ and such that $ \Delta \cap K = \partial K $. The complex $\Delta'=\Delta\cup K$ is said to be obtained from $\Delta$ by \emph{attaching a $\PS$ ear}.
\end{definition}

\begin{lemma}\label{lem:hvectorear}
Under the conditions of \cref{def:ear} above we have the following relation of $h$-polynomials:
\[
h(\Delta',t) = h(\Delta,t)+t^{l+1}h(\partial K, t).
\]
\end{lemma}
\begin{proof}
This is the polynomial version of Lemma 3 \cite{Chari} together with the Dehn-Sommerville relations for simplicial spheres. 
\end{proof}

\begin{definition}A $(d-1)$-dimensional simplicial complex $\Delta$ is said to be $\PS$-ear decomposable if there is $k\ge 0$ and a sequence $\Delta_0 \subset \Delta_1 \subset \dots \subset \Delta_k = \Delta$ of complexes, such $\Delta_0$ is a PS-sphere and for $0 \le j \le k-1$ the complex $\Delta_{j+1}$ is obtained from $\Delta_{j}$ by attaching a PS-ear. 
\end{definition}
\begin{remark}\label{rem:ear}
Each time we attach an ear the top Betti number goes up by one and hence if we attach $k-1$ PS ears, the resulting complex has $|\tilde\chi(\Delta)|=k$.
\end{remark}

\subsection{Matroids}
A \emph{matroid} is a pair $M=(E,r)$, where $E$ is a finite set and $r:2^E\to\mathbb{Z}$ is a function on subsets of $E$ that is nonnegative, nondecreasing, and submodular.
%\begin{itemize}
%\item[R1] $0\leq r(A)\leq |A|$ for all subsets $A\subset E$.
%\item[R2] $r(B)\leq r(A)$ whenever $B\subset A$.
%\item[R3] $r(A\cap B)+r(A\cup B)\leq r(A)+r(B)$ for any two subsets $A,B\subset E$.
%\end{itemize}
An \emph{independent set} $I\subset E$ is a subset such that $r(I)=|I|$. Independent sets form a simplicial complex denoted by $\II(M)$. A matroid is said to be \emph{connected}, if $\II(M)$ is join irreducible. Maximal independent sets are called \emph{bases} and we denote the set of bases of matroid $\BB(M)$. Minimally dependent (that is, not independent) sets are called \emph{circuits}. %An element $x$ is called a \emph{loop} if $r(x)=0$. A matroid is said to be loopless if it has no loops. All matroids that we consider in this paper are loop free. An element $x$ is called a \emph{coloop} if $r(E-x)< r(E)$, i.e it is contained in every basis. A matroid without coloops is said to be \emph{coloop free}. A \emph{simple} matroid is a matroid with $r(A)=|A|$ whenever $|A|\leq 2$.

A \emph{flat} is a subset $F\subset E$ such that $r(F)<r(F\cup\{x\})$ for any $x\notin F$. If we have a total order $<$ on $E$, a \emph{broken circuit} is a circuit with its smallest element removed. A basis is called an \emph{nbc basis} if it does not contain any broken circuit.


An \emph{ordered matroid} $(M,<)$ is a matroid together with an ordering on its ground set. Given an ordered matroid $M$, a basis $B$ and $b\in B$, say that $b$ is \emph{internally passive} if there is $b'<b$ such that $(B\backslash\{b\})\cup\{b'\} \in \BB(M)$, i.e., it can be replaced by a smaller element to obtain another basis of $M$. The set of all internally passive elements of a basis $B$ is denoted by $IP(B)$ and it is called the internally passive set of $B$. 

%Let $\text{Int}_<(M)$ to be the poset on $\BB(M)$ with the order given by inclusion of internally passive sets. $\text{Int}_<(M)$ is a graded poset with $h_i(\II(M))$ elements of rank $i$. After attaching a maximum element it becomes a graded lattice \cite[Theorem 3.4]{LasV}. As  set system of $E$, $\text{Int}_<(M)$ enjoys the structure of a greedoid \cite{dawson} and \cite[Ex. 7.5]{bjorner}. 

In the paper \cite{bjorner} Bjorner studies three simplicial complexes associated with a matroid $M$. The first one is the independence complex defined above. The other two are defined here: 

\begin{definition}
Let $M=(E,r)$ be a matroid of rank $d$, i.e., $r(E)=d$. We define the following complexes:
\begin{itemize}
\item The \textbf{broken circuit complex} $BC_<(M)$, whenever $(M,<)$ is an ordered matroid, consists of the ground set $E$ with faces given by sets that do not contain broken circuits.
\item The \textbf{order complex of the lattice of flats} $\LL(M)$ is the order complex of poset given by flats of $M$ ordered by inclusion (see the precise definitions below).
\end{itemize}
All of these complexes have dimension $d-1$.
\end{definition}

In \cite{bjorner} it is shown that all three complexes are \emph{shellable}, a concept we will not define but only state the consequence we need.  A shellable simplicial complex $\Delta$ of dimension $d-1$ is homotopy equivalent to the wedge product of $k$ spheres of dimension $d-1$, where $k=h_d(\Delta)=|\tilde\chi(\Delta)|$. Hence, its homotopy type depends on just two parameters: $\dim(\Delta)$ and $\tilde\chi(\Delta)$ (or alternatively $h_d(\Delta)$).

%\begin{definition}[Graphical matroids]
%Given a graph $G=(V,E)$, we can define a matroid $M(G)$ on the edge set, $E$, by letting the rank of a subset $A\subset E$ be the size of the largest forest contained in the subgraph induced by $A$. Equivalently, we can define the circuits to be the cycles. 
%\end{definition}

%\begin{remark}\label{rem:maximizer}
%Notice that the maximizer of Lemma \ref{lem:hmax}, $\partial\Diamond_d$, is in fact the independence complex of the graphical matroid given by a path of length $d$ with each edge doubled. See Figure \ref{fig:max}.
%\begin{figure}[h]
%\centering
%\includegraphics{snakesimple.eps}
%\caption{Graph whose graphical matroid has independent complex equal to $\partial \Diamond_4$}\label{fig:max}
%\end{figure}
%\end{remark}

%\begin{example}\label{ex:uniform}
%Consider the graph $C_{d+1}$ given by a single $(d+1)$-cycle. In the matroid $M(C_{d+1})$ any \emph{proper} subset of $E$ is independent, so the independence complex is $\hat{\Gamma}_d$.
%\end{example}


The broken circuit complex turns out to be a cone over a non-contractible space: the number of cone points equals the number of connected components of the matroid as shown in \cite{bjorner}. The {\bf reduced} broken circuit complex $\overline{BC}_<(M)$ is the complex that results from removing the cone points of the broken circuit complex. For simplicity we only work with connected matroids, i.e matroids whose independence complex cannot be decomposed as a join of two non-trivial complexes. 

The following theorem provides one topological difference between independence and broken circuit complexes. Indeed, it follows from the work of Swartz \cite{swartz} that it is \emph{false} for broken circuit complexes.

\begin{theorem}[{\cite[Theorem 3]{Chari}}] \label{thm:chari}
For any matroid $M$, the independence complex $\II(M)$ is PS-ear decomposable. 
\end{theorem}




\subsection{Geometric lattices}

For any matroid $M$ we have a partially ordered set (by inclusion) on the set of flats. These posets are characterized by certain extra properties, they are precisely the \emph{geometric lattices}. %We need some more terminology. 

%Let $\mathbb{P}$ be a finite poset. We will always assume that there is a unique smallest element $\hat{0}$ and a unique maximal element $\hat{1}$. We say that $x$ covers $y$, denoted $y\preceqdot x$, if $y\preceq x$ and there is no $z$ such that $y\preceq z\preceq x$. An \emph{atom} is an element $x$ such that $\hat{0}\preceqdot x$. We usually represent a poset through its Hasse diagram, i.e., by drawing an edge between two elements whenever one covers the other.
%
%Given two elements $x,y$ we denote by $x\vee y$ their \emph{join}, an element such that $x\preceq z$ and $y\preceq z$ imply $x\vee y\preceq z$. Dually we can define $x\wedge y$ as the \emph{meet}. These operations are binary but associative so it makes sense to talk about the meet or join of any finite subset.
%\begin{definition}
%A poset $L$ is a geometric lattice if it satisfies the following conditions
%\begin{enumerate}
%\item It is graded.
%\item Its rank function $r$ is semimodular, i.e for every $x,y\in L$ the following inequality holds:
% \begin{equation*}r(x\vee y)+r(x\wedge y)\leq r(x)+r(y).\end{equation*}
%\item It is atomistic, i.e., every element is the join of a set of atoms.
%\end{enumerate}
%\end{definition}

%For notational purposes we declare $r(\hat{0})=-1$, so that for instance the atoms have rank equal to zero. 
\begin{theorem}
Assigning the poset $\LL(M)$ to each matroid $M$ induces a one-to-one correspondence between geometric lattices and simple matroids. 
\end{theorem}

Every poset $\mathbb{P}$ gives a simplicial complex $\OO(\mathbb{P})$, called the order complex of $\mathbb{P}$, in the following way: Its elements are the elements of $\mathbb{P}$ and the faces are the chains ordered by inclusion.
As mentioned before, the order complex of a geometric lattice $L$ is shellable.
%We close this section by providing a description of $\tilde\chi(\OO(L))$ following \cite{bjorner}.
%
%Let $m$ be the number of atoms in $L$ and choose an arbitrary bijection between atoms and $[m]$ so we can label atoms with positive integers. Let $E(L)$ be the set of edges of the Haase diagram. Define a labelling $\lambda: E(L)\longrightarrow \mathbb{Z}$ as follows: if $y\preceqdot x$ then $\lambda(y,x)$ equals the smallest atom $a$ such that $a\preceq x$ but $a\not\preceq y$. A \emph{descending chain} is a chain $\hat{0}=x_0\preceqdot x_1\preceqdot\cdots\preceqdot x_r=\hat{1}$, such that $\lambda(x_{i-1},x_{i})>\lambda(x_{i},x_{i+1})$ for $1\leq i\leq r-1$.
%
%\begin{proposition}\cite[Proposition~7.6.4 ]{bjorner}
%Let $L$ be a geometric lattice. We have that $|\tilde\chi(\OO(L))|=|\mu(\hat{0},\hat{1})|$, the m\"obius function, and this quantity is also equal to the number of descending chains. 
%\end{proposition}






\section{Independence Complexes}

This section is devoted to various proofs of \cref{thm:main}. Quite surprisingly the result is a simple consequence of several standard (yet deep) theorems in matroid theory. 

\begin{definition}
Let $\Psi_{d,k}$ be the set of all isomorphism classes of \emph{loopless} matroids $M$ such that $\dim(\II(M))=d-1$ and $|\tilde\chi(\II(M))|=k$.
\end{definition}
%Each of the following proofs sheds a light on different aspects of $\Psi_{d,k}$. We begin with a proof using some theorems of \cite{bjorner}. These seem to be the oldest family of results that actually suggest the property for matroids. 

%\begin{proof}[First proof of Theorem \ref{thm:main}] Let $M$ be a loopless matroid of rank $d$. By Theorem 7.8.4 and Corollary 7.8.5 in \cite{bjorner}, there is a basis for the homology group $H_{d-1}(\II(M))$ consisting of cycles whose supports are the facets of PS-spheres; furthermore every basis of the complex is in the support of one such cycle. There are only finitely many $PS$-spheres and each $PS$-sphere has at most $2^d$ facets, thus the number of bases of $M$ is bounded above by $2^dh_d$. 
%\end{proof}
%\begin{remark}Notice that the previous bound is far from tight: bases are overcounted and an intricate inclusion/exclusion process is needed. Little is known about the types of spheres in the bases and how they intersect, so we believe it is unlikely to make this argument sharper. 
%
%Bj\"orner also shows \cite[Proposition~7.5.3]{bjorner} that if $M$ is connected and has no coloops, then $h_d \ge h_1$. The proof is inductive and uses the Tutte-Polynomial. It is not clear if this is in general tight, but it tells us that if we restrict to connected matroids, then the bounds are different: below we present examples of matroids with $h_1 = h_d + d -1$. 
%\end{remark}
\cref{thm:main} implies the existence of upper bounds for each entry of the $h$-vectors and $f$-vectors of a matroid in terms of its dimension and its Euler characteristic. We start by providing tight bounds. These bounds were first proved in Swartz \cite{superEd} with a complicated inductive argument. The advantage of our approach is that we can completely classify equality cases. 
\begin{theorem}\label{thm:hbound}
Let $M\in\Psi_{d,k}$ we have the following inequalities:
\begin{enumerate}
\item $h_i(\II(M)) \leq \binom{d}{i} + (k-1)\binom{d-1}{i-1},$ for $0\leq i\leq d$.
\item $f_i(\II(M)) \leq \binom{d}{i+1}2^{i+1} + (k-1)\binom{d-1}{i}2^{i},$ for $-1\leq i\leq d-1$.
\end{enumerate}
Furthermore, these inequalities are tight and equality holds only if $M$ is isomorphic to the matroid $V_{d,k}$ defined below.
\end{theorem}

\begin{proof}
We begin with the first part. We will use \cref{thm:chari}, i.e., the fact that $\II(M)$ is PS ear decomposable. To begin with, there is a unique $h$-vector maximizer among the PS spheres $\Delta_0$; namely it is the boundary of a $d$-dimensional crosspolytope and its $h$-vector is given by the binomial coefficients (\cref{lem:hmax}). By \cref{lem:hvectorear}, together with \cref{lem:hmax}, the way to attach a PS ear with maximal resulting $h$-vector is by attaching a PS ball whose boundary is isomorphic to $\partial\Diamond_{d-1}$. We now show that this maximal bound can be attained.

Set $\Delta_0$ to be $\partial\Diamond_d$. Fix a vertex $v\in\Delta_0$ and attach an ear using the PS ball $\Sigma\ast\Gamma_0$, where $\Sigma$ is the link of $v$ (which isomorphic to $\partial\Diamond_{d-1}$) and $\Gamma_0$ is just a single new vertex.  We can repeat this process $k$ times, always using the same link of the original vertex $v$. The simplicial complex obtained in this way is the independence complex of matroid. Our choice of $\Delta_0$ is the independence complex of the graphical matroid of a path with each edge doubled. Each ear attachment corresponds to adding parallel elements to a fixed edge. We denote this matroid by $V_{d,k}$.

The second part follows from the fact that $V_{d,k}$ also maximizes each entry of the $f$-vector. This is because the $f$-vector is a positive combination of the $h$-vector.
\end{proof}
\begin{figure}[h]
\centering
\includegraphics{snake.eps}
\caption{The graphical matroid $V_{4,7}$.}
\end{figure}

Now we can give another proof of \cref{thm:main}.

\begin{proof}[Proof of \cref{thm:main}]
We have $h_d(\II(M))=|\tilde\chi((\II(M)))|$, so \cref{thm:hbound} gives $f_0(\II(M))\leq 2d+h_d(\II(M))-1$. Fixing $h_d(\II(M))$ and $d$ bounds the number of vertices $(\II(M))$ can have, whence the result follows.
\end{proof}

In contrast to the case of the Upper Bound Theorem for spheres (see \cite{UBC}), $V_{d,k}$ is the unique maximizer up to isomorphism. However, $V_{d,k}$ is perhaps not very interesting from the matroid theoretic perspective (for instance lattice of flats of $V_{d,k}$ is the boolean lattice $B_d$). A relevant variant, which we expect to be harder, is the analogous question over the family of \textbf{simple} matroids.
\begin{question}What is the maximal value of $h_j(\II(M))$ for where $M$ ranges over all simple matroids of $\Psi_{d,k}$? Is there a single simple matroid that simultaneously maximizes all the $h$-vector entries? What if we further restrict to the class of simple connected matroids? 
\end{question}
In light of the above question, we notice that for simple matroids, the number of vertices is strictly less than $2d+ h_d(\II(M)) -1$ which is the tight upper bound for general matroids. 
\begin{corollary} If $M$ is a matroid with $f_0(\II(M)) = 2d+h_d(\II(M)) -1$, then $M$ is isomorphic to $V_{d,k}$. 
\end{corollary}
%We now present another proof of the main theorem that may be more suitable for studying the simple case and/or the broken circuit complexes.
%
%\begin{proof}[Third proof of Theorem \ref{thm:main}] Choose an order $<$ on the vertex set of $M$,  and consider the poset $\text{Int}_<(M)$. It is graded, the number of elements of degree $i$ is $h_i$ and all the maximal elements are of degree $d$ (since it is a greedoid or a graded lattice minus the top element). Since the elements of the posets are sets ordered by inclusion and graded by cardinality, the number of atoms is at most $d$ times the number of bases of rank $d$ in the poset, in terms of $h$-numbers it means that $h_1 \le dh_d$. 
%\end{proof}
%
%
%
%
%\begin{remark} The inequalities obtained from this method are far from tight (Theorem \ref{thm:hbound} gives the stronger inequality $h_1\leq d-1+h_d$). Indeed the equality case would need disjoint bases which cannot happen. The structural properties of $\text{Int}_<(M)$ are quite strong, but barely used. 
%\end{remark}


To finish, we present a proof of the main theorem which allows us to say something about the size of $\Psi_{d,k}$.
\begin{proof}[Second proof of \cref{thm:main}] Given a matroid $M$ and a basis $B$, Corollary~3.5  in \cite{SamKlee} shows that the $h$-polynomial of the independence complex of $M$ can be decomposed as: 
\[ h(\II,x) = \sum_{I} x^{|I|}h(\text{link}_\II(I)|_B, x).\]
The sum is taken over the independent sets $I$ of $M$ that are disjoint from $B$. Lemma~3.8 in \cite{SamKlee} shows that all maximal such $I$ under inclusion, i.e the bases of the induced matroid on $E\backslash B$, satisfy that $h_{d-|I|}(\text{link}_\II(I)|_B) \not= 0$. It follows that $h_d(M)$ is bounded below by the number of bases of $M|_{E-B}$. This implies that there are at most $k$ maximal bases. Together with the fact that the rank of the restriction is bounded above by $d$, this implies that the number of possible restrictions is finite. The missing independent sets consist of a subset of $B$ together with an element of the restriction, thus the number of matroids with $h_d = k$ is bounded above by $2^dkT_{d,k}$, where $T_{d,k}$ is the number of matroids of rank at most $d$ with at most $k$ bases. 
\end{proof}
%\begin{remark} The bounds are far from tight. First of all, it is to be expected that the larger the number of bases of $\Delta_{E\backslash B}$, the fewer ways there are to complete to a matroid. More careful analysis can be carried to replace the power of $2$, but basic asymptotics of binomial coefficients tell us that the replacement is still exponential. An estimate of $T_{d,k}$ is not known, but it seems like estimating it is more a more tractable problem. In particular, it is a simple consequence of the exchange axiom that the values stabilize for fixed $k$ and large values of $d$. 
%\end{remark}
In general, it follows from Chari's \cref{thm:chari} that $|\Psi_{d,1}| = p(d)$, the number of integer partitions of $d$. Consequently, the best kind of formula we can expect for the cardinality of $\Psi_{d,k}$ is asymptotic. It is unclear that the value of $\Psi_{d,k}$ is monotone in either of the parameters. At least the construction of $V_{d,k}$ shows that $\Psi_{d,k}\neq\emptyset$. Using the same ideas we can say a little more.
\begin{lemma}\label{lem:many}
$|\Psi_{d,1}| \le |\Psi_{d,k}|$ for every positive integer $d$
\end{lemma}
\begin{proof} Since every matroid in $\Psi_{d,1}$ is a PS-sphere, we can choose any vertex $v$ and replicate the construction of $V_{d,k}$ to get an inclusion $\Psi_{d,1}\to \Psi_{d,k}$.
\end{proof}

Notice that the previous argument is not strong enough to prove that $\Psi_{d,k} \le \Psi_{d,{k+1}}$ in general (if $d=1$ the number of all such matroids is one). In particular, it would be interesting to find a matroid operation that increases $h_d(\II(M))$ by one in general. The previous construction relies heavily on having a vertex of the independence complex whose link is a sphere. This is, presumably, almost never the case. 


\section{Broken Circuit complexes}
\cref{thm:nbc} is a natural extension of \cref{thm:main}.  The proof is a consequence of Theorem 5.4 in \cite{superEd}. Notice that if $M$ is a connected rank-$d$ simple matroid without coloops, then the upper bounds for $h_i$ in terms of $h_{d-1}$ coincide with the tight ones found for matroids.% The proof though, makes it hard to

Thus the numerical inequalities found for broken circuit complexes are not stronger than the ones found for matroids. However, the lack of flexibility of the approach leads to some potential differences: for instance, while the independence complex maximizer is unique, none of the arguments that apply to broken circuit complexes. In particular Swartz \cite{swartz} provided examples of broken circuit complexes such that the Artinian reduction of the Stanley-Reisner ring admits no $g$-element. This means that some broken complexes do not admit convex ear decompositions (even after increasing the family of allowable convex spheres and balls). As a result it follows that the proof using PS-ear decomposition cannot be extended, and the equality classification fails. 
  

An alternative approach, which is part of a current research project of the second author, comes from studying the $\text{Int}_<(M)$ poset when restricted to the facets of $BC_<(M)$. As evidence that an argument along these lines may be reasonable, we provide a new structural theorem about the subposet of $\text{Int}_<(M)$ that consists of nbc bases: it is an order ideal. By studying the structure of the subposet carefully we expect to be able to classify upper bounds and hopefully obtain significant quantitative differences between the two families of $h$-vectors. 

%\begin{theorem}\label{orderId} If $(M,<)$ is an ordered loopless matroid, then the nbc bases form an order ideal of $\text{Int}_<(M)$. 
%\end{theorem}
%This theorem is interesting on its own and provides, for example, evidence that broken circuit complexes play an important role in the theory of quasi-matroidal classes \cite{QS-stuff}. In order to prove it, we start with a lemma that provide us with the relationship between activities and broken circuits. 
%
%\begin{lemma} Let $(M,<)$ be an ordered matroid and let $C$ be a circuit whose corresponding broken circuit is $\hat C$. If $B$ is any basis with $\hat C \subseteq B$, then $\hat C \subseteq IP(B)$. Furthermore, $\hat C = IP(\hat B)$ for the smallest lexicographic basis $\hat B$ that contains $\hat C$. 
%\end{lemma} 
%\begin{proof} 
%Let $c$ be the element in $C\backslash \hat C$. Since $C\subseteq B\cup\{c\}$ any element $d\in \hat C$ can be replaced by $c$ to obtain a new basis. Since $\hat C$ is a broken circuit, we have $c<d$ and therefore $d\in IP(B)$ as desired. 
%
%If $\hat B$ is the smallest lexicographic basis containing $\hat C$ and $\hat C \subseteq IP(\hat B)$, then equality must hold since the lexicographic order is a shelling order with internally passive sets as restriction sets. 

%\end{proof}

%The lemma immediately implies Theorem~\ref{orderId}: broken circuits for an antichain in $\text{Int}_<(M)$ and the nbc bases are exactly the order ideals whose minimal non-elements are the broken circuits. 
%Finally we remark that there is no homology basis as in Bj\"orner's theorem. Thus the first proof of Theorem~\ref{thm:main} cannot be extended for broken circuit complexes. If $M$ is the ordered matroid of Example~\ref{ex:ed} , then the $h$-vector of the broken circuit complex is $(1,2,3,1)$. The top homology is one dimensional and its $h$-vector is not symmetric. If there is a sphere that covers the complex, then the bases of the two complexes would have to coincide, but that would make the $h$-vector symmetric by the Dehn-Sommerville equations. 

\section{Order complexes of geometric lattices.}

%We begin with a simple argument to show the weaker, rank dependent, part of Theorem \ref{thm:flats}. Let $a(L)$ be the number of atoms of $L$.
%\begin{theorem}\label{weakLattices}
%The number of geometric lattices $L$ with rank $d$ and $|\mu(L)|=k$ is finite.
%\end{theorem}
%\begin{proof}
%We will show that if a rank-$d$ geometric lattice $L$ satisfies $a(L)\geq (k+1)k^{d-1}$, then $|\mu(L)|>k$.
%
%We will proceed by induction on $d$. Let $L$ be a geometric lattice of rank $1$, then $|\mu(L)|=a(L)$, the number of atoms, and the base case follows.
%
%Notice that in general if there exist $k+2$ atoms such that their join lies in rank two, then by labeling them with the largest $k+2$ numbers, we can guarantee at least $k+1$ descending chains. So let us assume that no $k+2$ atoms have a join in rank two, i.e., every element in rank two is the join of at most $k+1$ atoms. Fix an atom $x$ and consider the interval $L^x=[x,\hat{1}]$. This interval is a geometric lattice on its own (it corresponds to the matroid obtained by contracting the flat $x$). The atoms of $L^x$ are in bijection with elements of rank two in $L$ above $x$, and as such, they give a partition of the set of atoms of $L$ (other than $x$) by looking at the atoms each of them cover. This means that $k\cdot a(L^x)>a(L)$. Since the rank of $L^x$ is $d-1$, by induction on rank we know that if $a(L)\geq (k+1)k^{d-1}$, then in $a(L^x)\geq (k+1)k^{d-2}$ and therefore there are more than $k$ descending chains. By labeling $x$ with the largest number we can extend each of these chains to descending chains in $L$ to guarantee that $|\mu(L)|>k$. 
%
%\end{proof}
%
%\begin{remark} It should be noted that Swartz and Nyman~\cite{EdNym} proved that the order complex of any geometric lattice admits a convex ear decomposition. This is a decomposition pretty similar to a PS-ear one, except that one is allowed to start with other spheres, and attach other balls (all convex). They use the convex ear decomposition to study flag $h$-numbers, which we intend to do from various points of view in an upcoming project. In their theorem, the combinatorial types of spheres and balls are also prescribed, but different. Another proof of Theorem~\ref{weakLattices} can be obtained this way, but we do not include it here as it would require many more definitions and all the ideas behind them are explained above.
%\end{remark}

A careful look at Exercise 100(d) in Chapter 3 of \cite{EC1} gives a much stronger result than an analogous of \cref{thm:main}. The level of the problem in the ranking [3-], but unlike most problems in the book, the solution is not written down. To the best of our knowledge, it is not anywhere in the literature, so we include it here for the sake of completeness. 
\begin{theorem}\label{thm:latticeStrong}
Fix a natural number $k$. There exist finitely many geometric lattices $L_1,\cdots,L_m$ such that if $L$ is any finite geometric lattice satisfying $|\tilde\chi(\OO(L))|=k$ then $L=L_i\times B_d$ for some $i,d$.
\end{theorem}
\begin{proof}
Notice that the simple matroid associated to $L\times B_d$ is the join of the matroid of $L$ with the full $d-1$-simplex $\Gamma_{d-1}$. Thus it suffices to show that there are finitely many simple coloop free matroids $M$ whose lattice of flats has Euler characteristic equal to $k$. 

Assume that $M$ is such a matroid and $L$ is the associated geometric lattice. By \cite[Proposition 7.4.5]{bjorner} the Euler characteristic of $\tilde\chi(\OO(L))$ equals the number of facets of $BC_<(M)$. And there are finitely many isomorphism classes of such broken circuit complexes with $k$ facets. 

Let $\Delta$ be one such broken circuit complex. We claim that only finitely many matroids can have $\Delta$ as a broken circuit complex. To prove this we will bound the number of vertices of the independence complex of any such matroid. Let $C_1, C_2, \dots C_s$ be the minimal nonfaces of $\Delta$, that is, the broken circuits of any potential matroid. Let $M$ be a simple ordered matroid that has $\Delta$ as a broken circuit complex. Assume that $C_i\cup x$ and $C_i\cup y$ are circuits of $M$. Pick an arbitrary $c\in C_i$. Note that by the circuit elimination axiom, the set $(C_i\cup\{x,y\})\backslash\{c\}$ is a nonface. Since $M$ is simple, $x<y$ are not parallel. Thus there is a circuit of $M$ containing $\{x,y\}$. Such a circuit has to be equal to $C_j\cup\{x\}$ for some $j$ or $C_j\cup\{z\}$ for some $j$ and some other $z$ in the groundset of $M$. In either case $y\in C_j$, and hence a vertex of $\Delta$. Hence the number of vertices of $M$ not in $\Delta$ that extend the broken circuit $C_j$ is at most one, which leads to the inequality $f_0(\II(M)) \le f_0(\Delta) +s$ as desired. 
\end{proof}

Note that one cannot drop the dimension assumption from \cref{thm:main}, since $$\tilde\chi(\II(U_{d,d+1})))=1$$ for every $d$, where $U_{d,d+1}$ is the uniform matroid of rank $d$ on $[d+1]$.


\acknowledgements{We thank Isabella Novik, Ed Swartz and Steven Klee for helpful conversations.}

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