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

%% note that the class file already loads {amsmath, amsthm, amssymb}
%%--PACKAGES-----------------------------------------------------
%\usepackage{lipsum}
\usepackage{mathtools}
\usepackage{xcolor}
\usepackage{url}
\usepackage[colorlinks=true]{hyperref}


%%--OTHER ENVIRONMENTS-------------------------------------------
\newtheorem{lemma}{Lemma}[section]
\newtheorem{theorem}[lemma]{Theorem}
\newtheorem{corollary}[lemma]{Corollary}
\newtheorem{proposition}[lemma]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[lemma]{Definition}
\newtheorem{conjecture}[lemma]{Conjecture}
\newtheorem{algorithm}[lemma]{Algorithm}
\newtheorem{question}[lemma]{Question}
\newtheorem{problem}[lemma]{Problem}
\newtheorem{claim}[lemma]{Claim}
\newtheorem{example*}[lemma]{Example}
\newtheorem{remark}[lemma]{Remark}
\newtheorem{assumption}[lemma]{Assumption}
\theoremstyle{remark}

\makeatletter
\newtheorem*{rep@theorem}{\rep@title}
\newcommand{\newreptheorem}[2]{%
\newenvironment{rep#1}[1]{%
%\def\rep@title{{\bf #2 \ref{##1}}}%
\def\rep@title{{\bf \cref{##1}}}%
\begin{rep@theorem}}%
{\end{rep@theorem}}}
\makeatother
\newreptheorem{theorem}{Theorem}

\DeclareRobustCommand{\qedify}[1]{%
  \ifmmode \quad\hbox{#1}
  \else
    \leavevmode\unskip\penalty9999 \hbox{}\nobreak\hfill
    \quad\hbox{#1}%
  \fi
}
\newenvironment{example}{\begin{example*}\pushQED{\qedify{$\diamondsuit$}}}{\popQED\end{example*}}


%%--MATH---------------------------------------------------------
\newcommand{\K}{\ensuremath{\Bbbk}} 
\newcommand{\Rbar}{\ensuremath{\overline{\mathbb R}}}
\newcommand{\Rx}{\Rbar[\mathbf x]}
\newcommand{\Bx}{\mathbb{B}[\mathbf{x}]}
\newcommand{\R}{R}

\newcommand{\M}{\mathcal{M}}
\newcommand{\I}{\mathcal{I}}
\newcommand{\C}{\mathcal{C}}
\newcommand{\D}{\mathcal{D}}
\newcommand{\V}{\mathcal{V}}
\newcommand{\B}{\mathcal{B}}
\newcommand{\F}{\mathcal{F}}
\newcommand{\G}{\mathcal{G}}

\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\BB}{\mathbb{B}}

\newcommand{\bfx}{\mathbf{x}}
\newcommand{\bfy}{\mathbf{y}}
\newcommand{\bfz}{\mathbf{z}}
\newcommand{\bfu}{\mathbf{u}}
\newcommand{\bfv}{\mathbf{v}}
\newcommand{\bfw}{\mathbf{w}}
\newcommand{\bfe}{\mathbf{e}}
\newcommand{\bfzero}{\mathbf{0}}
\newcommand{\rk}{\operatorname{rk}}
\newcommand{\gr}{\operatorname{gr}}
\newcommand{\one}{\mathbf{1}}
\newcommand{\sat}{\mathrm{sat}}

\newcommand{\comment}[1]{}

\DeclareMathOperator{\inn}{in}
\DeclareMathOperator{\codim}{codim}
\DeclareMathOperator{\rank}{rank}
\DeclareMathOperator{\val}{val}
\DeclareMathOperator{\trop}{trop}
\DeclareMathOperator{\supp}{supp}
%\DeclareMathOperator{\sat}{sat}
\DeclareMathOperator{\spann}{span}
\DeclareMathOperator{\aff}{aff}
\DeclareMathOperator{\cone}{cone}
\DeclareMathOperator{\relint}{relint}
\DeclareMathOperator{\starr}{star}
\DeclareMathOperator{\mon}{Mon}
\DeclareMathOperator{\mond}{{\mon_d}}
\DeclareMathOperator{\monld}{{\mon_{\leq d}}}
\DeclareMathOperator{\GL}{GL}
\DeclareMathOperator{\st}{st}


%tropical operations
\makeatletter
\newcommand{\superimpose}[2]{{\ooalign{$#1\@firstoftwo#2$\cr\hfil$#1\@secondoftwo#2$\hfil\cr}}}
\makeatother
\newcommand{\ttimes}{\hspace{0.3mm}{\mathpalette\superimpose{{\circ}{\cdot}}}\hspace{0.3mm}}
\newcommand{\tplus}{\oplus}






%% define your title in the usual way
\title{Tropical ideals do not realise all Bergman fans}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Jan Draisma\thanks{\href{mailto:jan.draisma@math.unibe.ch}{jan.draisma@math.unibe.ch}. JD was partially supported by the Vici grant Stabilisation in Algebra and Geometry from the Netherlands Organisation for Scientific Research (NWO).}\addressmark{1}
\and Felipe Rinc\'on\thanks{\href{mailto:f.rincon@qmul.ac.uk}{f.rincon@qmul.ac.uk}. FR was partially supported by the Research Council of Norway grant 239968/F20.}\addressmark{2}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Mathematisches Institut, Universität Bern, Switzerland. \\ \addressmark{2}School of Mathematical Sciences, Queen Mary University of London, United Kingdom.}

%% 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{Tropical ideals are combinatorial objects that abstract the possible collections of subsets arising as the supports of all polynomials in an ideal. 
Every tropical ideal has an associated
tropical variety: a finite polyhedral complex equipped with positive
integral weights on its maximal cells. This leads to the realisability
question, ubiquitous in tropical geometry, of which weighted polyhedral
complexes arise in this manner. Using work of Las Vergnas on the
non-existence of tensor products of matroids, we prove that there is no
tropical ideal whose variety is the Bergman fan of the direct sum of the
V\'amos matroid and the uniform matroid of rank two on three elements,
and in which all maximal cones have weight one.
}

\resumetitle{R\'esum\'e}
%% put your French abstract here, or comment this out if you don't have one
\resume{
Les id\'eaux tropicaux sont des objets combinatoires qui font abstraction des collections possibles de sous-ensembles constituant les supports de tous les polyn\^omes d'un id\'eal. 
Chaque id\'eal tropical a une vari\'et\'e tropicale associ\'ee: un complexe poly\'edrique fini \'equip\'e de pond\'erations int\'egrales positives sur ses cellules maximales. 
Ceci conduit \`a la question de la r\'ealisabilit\'e, omnipr\'esente en g\'eom\'etrie tropicale, de laquelle des complexes polyh\'edriques pond\'er\'es se pr\'esentent de cette mani\`ere. 
En utilisant les travaux de Las Vergnas sur la non-existence de produits tensoriels de matro\"ides, 
nous prouvons qu'il n'existe pas d'id\'eal tropical dont la vari\'et\'e est l'\'eventail de Bergman de la somme directe du matro\"ide de V\'amos et du matro\"ide uniforme de rang deux sur trois \'el\'ements, 
et dans lesquels tous les c\^ones maximaux ont un poids un.
}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{tropical geometry, tropical variety, tropical ideal, realisability, matroid.}

%% 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, style=alphabetic]{biblatex}
%\addbibresource{bibsubmission.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}

An ideal in a polynomial ring over a field with the trivial valuation
%with a non-Archimedean valuation 
gives rise to a polyhedral fan called its tropical variety, by taking all weight
vectors whose initial ideals do not contain a monomial.
% or, equivalently, after taking an appropriate field extension \cite[Theorem 4.2]{Draisma06a}, by applying the coordinate-wise valuation to all points in the zero set of the ideal.  
In the middle of this construction sits a
{\em tropical ideal}, obtained by recording the supports of all polynomials
in the ideal. This tropical ideal is a purely combinatorial object, 
%in that it does not know about the field or the valuation, 
and it contains more information than the tropical variety itself. For these
reasons, tropical ideals, axiomatised in \cite{MR}, were proposed as
the correct combinatorial/algebraic structures on which to build a theory of
tropical schemes. 

Concretely, if $K$ is an infinite field, a classical ideal $J \subseteq K[x_1,\dots,x_n]$ gives rise to the tropical ideal
\[I = \trop(J) \coloneqq \{ \supp(F) : F \in J \} \subseteq 2^{\NN^n},\]
where the support $\supp(F)$ of a polynomial 
$F = \sum_{\bfu \in \NN^n} c_\bfu \bfx^\bfu \in K[x_1,\dots,x_n]$
is given by $\supp(F) \coloneqq \{ \bfu \in \NN^n : c_\bfu \neq 0 \}$. 
A tropical ideal arising in this way is called {\em realisable} (over the field $K$). 

In general, a (possibly non-realisable) {\em tropical ideal} in the variables $x_1, \dots, x_n$ is a non-empty collection $I$ of finite subsets of $\NN^n$ satisfying the following conditions:
\begin{itemize}
\item If $S,T \in I$ then $S \cup T \in I$. 
\item If $S \in I$ then $S + \bfe_i := \{ \bfv +\bfe_i : \bfv \in S \} \in I$ for any $1 \leq i \leq n$, where $\{\bfe_1, \dots, \bfe_n\}$ denotes the standard basis of $\ZZ^n$.
\item {\em Monomial elimination axiom:} If $S, T \in I$ and $\bfu \in S \cap T$ then there is $U \in I$ such that $S \Delta T \subseteq U \subseteq (S \cup T) \setminus \{\bfu\}$, where $\Delta$ denotes symmetric difference. 
\end{itemize}
Tropical ideals are in this way combinatorial abstractions of the possible collections of subsets of $\NN^n$ that arise as the supports of all polynomials in a fixed ideal over a field.
As described below, the monomial elimination axiom is basically an instance of the cycle elimination axiom for matroids.
While `most' tropical ideals are expected to be non-realisable, there are essentially very few examples known so far of non-realisable tropical ideals---one of them, for instance, can be found in \cite[Example 2.8]{MR}.

Generalising the notion of tropical variety for a classical ideal, the {\em variety} of an arbitrary tropical ideal $I$ is  defined to be
\[V(I) \coloneqq \{\bfx \in \RR^n : \forall S \in I, \text{ the minimum }\min_{\bfu \in S} (\bfx \cdot \bfu) \text{ is attained by at least two terms} \}.\] 

Tropical ideals turn out to have very nice algebraic and geometric properties. It was proved in \cite{MR} that tropical ideals, while not finitely generated
as ideals--nor in any sense that we know of!---have a rational
Hilbert series, satisfy the ascending chain condition and the weak Nullstellensatz, and have
varieties that are finite weighted polyhedral fans. This leads to
the following realisability question.

\begin{question} \label{que:Realisability}
Which weighted polyhedral fans are the variety of some tropical
ideal?
\end{question}

When the tropical ideal records the supports of the polynomials in a classical prime ideal $J$, then the tropical variety is a pure-dimensional and balanced polyhedral fan \cite[Theorem 3.3.5]{Maclagan15}. Conversely, 
the question of which balanced polyhedral
complexes are realised by classical ideals has received much attention,
especially in the case of curves (see, e.g., \cites{Speyer14, Brugalle15,
Birkmeyer17}). But for general tropical ideals, very little is known
about \cref{que:Realisability}: no natural algebraic
criterion that ensures that the variety is pure-dimensional is known,
nor has their top-dimensional part been proved to be balanced. In fact,
until recently we had no intuition as to whether tropical ideals are flexible enough that they can realise basically any balanced polyhedral fan, or rather
more rigid, like algebraic varieties. In view of the following theorem,
we now lean towards the latter intuition.

\begin{reptheorem}{thm:main}
There exists no tropical ideal whose tropical variety is the Bergman fan of the direct sum of the V\'amos matroid
$V_8$ and the uniform matroid $U_{2,3}$ of rank two on three elements, with all maximal cones having weight $1$.
\end{reptheorem}

We believe that this theorem marks the beginning of an interesting
research programme, which, in addition to the pureness and balancing questions
mentioned above, asks which tropical ideals define algebraic matroids on the set of variables, and which matroids are, in this sense, tropically algebraic---see \cref{prob:matroidal} and \cref{que:algebraic}.

%\medskip
%\noindent {\bf Acknowledgements.} Both authors would like to thank the Mittag-Leffler Institute for their hospitality during the Spring 2018 program, when this paper was conceived. In addition, FR would like to thank the Discrete Mathematics/Geometry Group at TU Berlin and the ICERM Institute for their hospitality while these results were written.
%

\section{Definitions and basic results} \label{sec:Basics}

In this section we review the basic definitions of tropical linear spaces and tropical ideals. We will work in the general context of the full tropical semifield (corresponding to fields with a general non-Archimedean valuation), but all these notions can be specialised to the case of the Boolean semifield, as it was presented in the introduction. 

Consider the tropical semifield $(\Rbar:=\RR \cup \{\infty\},\tplus,
\ttimes)$ with $\tplus:=\min$ and $\ttimes:=+$. Let $R$ be a sub-semifield
of $\Rbar$. The example most relevant to us is the Boolean semifield $\BB:=\{0,\infty\}$,
which is not only a sub-semifield but also a quotient of $\Rbar$.

\begin{definition}\label{def:tropicallinearspace}
Let $N$ be a finite set. 
A set $L \subseteq R^N$ is a {\bf tropical linear space} if it is an
$R$-submodule (i.e., $(\infty,\ldots,\infty) \in L$ and $f,g \in L, c
\in R \Rightarrow (c \ttimes f) \oplus g \in L$) and if, moreover, $L$
satisfies the following elimination axiom: for $i \in N$ and $f,g \in L$
with $f_i=g_i \neq \infty$, there exists an $h \in L$ with $h_i=\infty$
and $h_j \geq f_j \tplus g_j$ for all $j \in N$, with equality whenever $f_j
\neq g_j$. The $\Rbar$-submodule $L_{\Rbar}$ of $\Rbar^N$ generated by $L$
is a tropical linear space in $\Rbar^N$, and has the structure of a finite polyhedral complex;
we denote its dimension as such by $\dim L$.
\end{definition}

If $K$ is a field equipped with a 
non-Archimedean valuation onto $R$ and if $V \subseteq K^N$ is a linear
subspace, then the image of $V$ under the coordinate-wise valuation is
a tropical linear space in $R^N$, but not
all tropical linear spaces arise in this manner. Tropical linear spaces
are well-studied objects in tropical geometry and matroid theory: the
definition above is equivalent to that of \cite{Speyer04}, except that
we allow some coordinates to be $\infty$. A tropical linear
space $L$ gives rise to a matroid $M(L)$ in which the independent sets
are those subsets $A \subseteq N$ for which 
%the projection $\pi_A(L) \subseteq R^A$ of $L$ onto the coordinates indexed by $A$ is equal to $R^A$.%%DUAL STATEMENT
$L \cap (R^A \times
\{\infty\}^{N\setminus A})=\{\infty\}^N$, and $L$ is the set of {\bf vectors}
($R$-linear combinations of valuated circuits) of a {\bf valuated matroid}
on $M(L)$ \cite{Murota01}. With this setup, $\dim L=|N|-\rk (M(L))$. We will freely alternate
between these different characterisations of tropical linear spaces.

Set $\NN:=\{0,1,2,\ldots\}$, and let $n \in \NN$. Denote by $R[x_1,
\dots,x_n]$ the semiring of polynomials in the variables $x_1,\dots,x_n$
with coefficients in $R$. We
write $\mond$ and $\monld$ for the set of monomials in $x_1,\ldots,x_n$
of degree equal to $d$ and at most $d$, respectively, and we identify a polynomial
in $R[x_1,\ldots,x_n]$ of degree at most $d$ with its coefficient
vector in $R^{\monld}$.

\begin{definition}\label{d:tropicalidealprojective}
A subset $I \subseteq R[x_1,\dots,x_n]$ is a {\bf tropical ideal}
if $x_i \ttimes I \subseteq I$ for all $i=1,\ldots,n$ and if for each $d
\in \NN$ the set $I_{\leq d} \coloneqq \{ f \in I : \deg(f) \leq d\}$ is
a tropical linear space in $R^{\monld}$. If $I$ is homogeneous, then the latter condition is equivalent to the
condition that for each $d$ the set $I_d$ of homogeneous polynomials in
$I$ of degree $d$ is a tropical linear space in $R^{\mond}$.

By \cref{def:tropicallinearspace}, $I$ is a tropical ideal if and only if $I$ is an ideal of $R[x_1,\dots,x_n]$ satisfying the following monomial elimination axiom:

\vspace{1mm}
\parbox[center][][c]{0.95\textwidth}
{
$\bullet$ For any $f, g \in I_{\leq d}$ and any monomial 
$\mathbf{x}^{\mathbf{u}}$ for which 
$[f]_{\mathbf{x}^{\mathbf{u}}} = [g]_{\mathbf{x}^{\mathbf{u}}} \neq \infty$,
there exists $h \in I_{\leq d}$ such that
$[h]_{\mathbf{x}^{\mathbf{u}}} = \infty$ and $[h]_{\mathbf{x}^{\mathbf{v}}} 
\geq \min( [f]_{\mathbf{x}^{\mathbf{v}}}, [g]_{\mathbf{x}^{\mathbf{v}}})$ 
for all monomials $\mathbf{x}^{\mathbf{v}}$, with the equality holding
whenever $[f]_{\mathbf{x}^{\mathbf{v}}} \neq [g]_{\mathbf{x}^{\mathbf{v}}}$.}

\vspace{1mm}
\noindent Here we use the notation $[f]_{\mathbf{x}^{\mathbf{u}}}$ to denote
the coefficient of the monomial $\mathbf{x}^{\mathbf{u}}$ in the tropical 
polynomial $f$.
\end{definition}

There is a natural notion of tropical ideals living in the Laurent polynomial semiring 
$R[x_1^{\pm 1},\ldots,x_n^{\pm 1}]$ that we will also use, and
if $I$ is a tropical ideal in $R[x_1,\ldots,x_n]$ then the set
$I' := \{f/\bfx^{\bfu} \mid f \in I, \bfu \in \NN^n\}$ is a tropical ideal
in $R[x_1^{\pm 1},\ldots,x_n^{\pm 1}]$. 

\comment{
The {\bf support} of a polynomial $f = \bigoplus a_{\mathbf{u}}
\ttimes \mathbf{x}^{\mathbf{u}}$ is
\[
\supp(f) \coloneqq \{\mathbf{u} \in \mathbb N^n: a_{\mathbf{u}} \neq \infty\}. 
\]
Let $\monld$ be the set of monomials of degree at most $d$ in the variables
$x_1,\dots,x_n$. We will identify a polynomial 
in $\Rbar[x_1,\dots,x_n]$ whose support is contained in $\monld$ with its vector of coefficients in $\Rbar^{\monld}$. 
In this way, if $\M$ is a valuated matroid on the ground set $\monld$,
vectors of $\M$ can be thought of as polynomials in 
$\Rbar[x_1, \dotsc, x_n]$ of degree at most $d$.
\note{define valuated matroids}
}

Tropical ideals were introduced by Maclagan and Rinc\'on in
\cite{MR} as a framework for developing algebraic foundations for tropical
geometry. Tropical ideals are much better behaved than general ideals
of the polynomial semiring $R[x_1,\dots,x_n]$, as we explain below.

\begin{definition}
For $\bfw \in \RR^n$ and $f=\bigoplus_{\bfu}
c_\bfu \ttimes \bfx^\bfu \in R[x_1,\ldots,x_n]$, define the {\bf initial part}
of $f$ relative to $\bfw$ as
\[ \inn_\bfw(f):=\bigoplus_{\bfu \,:\, c_\bfu+\bfu \cdot \bfw=f(\bfw)
} \bfx^{\bfu} \quad \in \BB[x_1,\ldots,x_n]. \]
For a tropical ideal $I$ define the its {\bf initial ideal} relative to $\bfw$ as
\[\inn_\bfw I:=\langle \inn_\bfw f \mid f \in I \rangle_\BB.\] 
\end{definition}

Note that in this paper we only consider weights $\bfw$ in $\RR^n$, not in $\Rbar^n$ as in
\cite{MR}. In other words, we do geometry only inside the tropical torus. 

\begin{definition}
The {\bf Hilbert function} of a tropical ideal $I \subseteq
R[x_1,\ldots,x_n]$ is the map $H_I:\NN \to \NN$ given by $d \mapsto
\binom{n+d}{d}-\dim I_{\leq d}$.
\end{definition}

Note that, as usual in commutative algebra, the Hilbert function
measures the codimension of $I_{\leq d}$ in its ambient space
$R^{\monld}$.  A homogeneous variant of this Hilbert function applies
only to homogeneous ideals and measures the codimension of $I_d$ in
$R^{\mond}$. The Hilbert function of a not necessarily homogeneous
ideal $I$ in $R[x_1,\ldots,x_n]$ 
equals the homogeneous Hilbert function of its homogenisation
in $R[x_0,\ldots,x_n]$.

The following is a special case of \cite[Corollary
3.6]{MR}.  

\begin{theorem} \label{thm:Inn}
For a homogeneous tropical ideal $I \subseteq R[x_1,\ldots,x_n]$ and
any $\bfw \in \RR^n$, $\inn_\bfw I \subseteq \BB[x_1,\ldots,x_n]$ is a homogeneous tropical ideal,
and $H_{\inn_\bfw I} = H_I$. 
\end{theorem}

\cref{thm:Inn} allows one to pass to monomial initial ideals and show that
the Hilbert function $H_I(d)$ of a homogeneous tropical ideal $I$
becomes a polynomial in $d$ for sufficiently large $d$, and also that homogeneous tropical
ideals satisfy the ascending chain condition. Via homogenisation, one
sees that both statements also hold for tropical ideals that are not homogeneous 
(but, as in the classical setting, the theorem does not apply directly,
since for instance, when $n=1$, $\inn_{(1)}(0 \oplus x_1)=0$ generates an
ideal---the entire semiring---with a smaller Hilbert function than any
tropical ideal containing $0 \oplus x_1$ but not $0$).

Furthermore, Maclagan and Rinc\'on prove that tropical ideals have
tropical varieties that are finite polyhedral complexes \cite[Theorem 5.11]{MR}.

\begin{theorem}
If $I \subseteq R[x_1,\dots,x_n]$ is a tropical ideal then its
(tropical) {\bf variety}
\[V(I) \coloneqq \{ \bfw \in \RR^n : \inn_\bfw I 
\text{ contains no monomial} \}\]
is the support of a finite polyhedral complex.
\end{theorem}

Indeed, if $I$ is homogeneous, they show that the sets of $\bfw$
where $\inn_\bfw I$ is constant form the relatively open polyhedra of
a polyhedral complex with support $\RR^n$ called the {\bf Gr\"obner
complex} of $I$, and that the cells where $\inn_\bfw I$ contains
no monomial form a subcomplex with support $V(I)$. By homogeneity,
all cells then contain in their lineality space the linear span of the all-ones vector $\one$. 
In the case where $I \subseteq R[x_1,\ldots,x_n]$ is not necessarily homogeneous, let $I^h$ be its
homogenisation in $R[x_0,x_1,\ldots,x_n]$. Then $\bfw \mapsto (0,\bfw)$
is a bijection between $V(I)$ and the intersection of $V(I^h)$ with the
zeroth coordinate hyperplane, and we give $V(I)$ the corresponding
polyhedral complex structure. 

The variety of a tropical ideal comes equipped with positive integral
weights on its maximal polyhedra; this is inspired by \cite[Lemma
3.4.7]{Maclagan15} and studied more in depth in \cite{MR2}.

\begin{definition}\label{def:multiplicity}
Let $I \subseteq R[x_1,\dots,x_n]$ be a tropical ideal, let
$\sigma$ be a maximal polyhedron of $V(I)$, and
let $\bfw$ be in the relative interior of $\sigma$. The {\bf
multiplicity} of $\sigma$ in $V(I)$ is defined as follows.  First, let $I' \subseteq
R[x_1^{\pm 1},\ldots,x_n^{\pm 1}]$ be the (tropical) ideal in the
Laurent polynomial ring generated by $I$. After an automorphism
of the Laurent polynomial ring given by $\bfx^\bfu \mapsto \bfx^{A\bfu}$
with $A \in \GL_n(\ZZ)$, we can assume that the affine span of $\sigma$
is a translate of $\spann(\bfe_1,\dots,\bfe_d)$ for some $d$. In this
case, by \cite{MR2}, the tropical ideal $J \coloneqq \inn_{\bfw}(I')
\cap \BB[x_{d+1}, \dots, x_{n}]$ is zero-dimensional, i.e., $H_J(e)$
is a constant for $e \gg 0$. The multiplicity of $\sigma$ is defined to be 
equal to this constant, called the degree of $J$.
\end{definition}

\begin{remark} \label{re:Mult}
A slightly more coordinate-free version of \cref{def:multiplicity}
is the following. Consider the linear span of $\sigma$, defined as 
\[ \spann(\sigma) := \RR_{\geq 0} \{ \bfv - \bfv' \mid \bfv, \bfv' \in \sigma \}. \] 
Let $S \subseteq \BB[x_1^{\pm 1},\ldots,x_n^{\pm 1}]$ be
the sub-semiring spanned by monomials $\bfx^\bfu$ of $\bfw$-weight $\bfw \cdot \bfu$ 
equal to zero for all $\bfw \in \spann(\sigma)$. 
Then $S$ itself is isomorphic to a Laurent polynomial semiring in $n-d$ variables. The
multiplicity of $\sigma$ is the degree of the zero-dimensional ideal
$\inn_\bfw (I') \cap S$.
%
%Assume that
%$\bfw \in \sigma$ is very generic in the following sense: the $\QQ$-span
%of the entries of $\bfw$, modulo the $\QQ$-space spanned by the finitely
%many real numbers appearing as right-hand sides in the definition of
%the polyhedron $\sigma$, has $\QQ$-dimension equal to $d:=\dim_\RR
%\sigma$. Let $S \subseteq \BB[x_1^{\pm 1},\ldots,x_n^{\pm 1}]$ be
%the sub-semiring spanned by monomials of $\bfw$-weight zero. Then $S$
%itself is isomorphic to a Laurent polynomial ring in $n-d$ variables. The
%multiplicity of $\sigma$ is the degree of the zero-dimensional ideal
%$\inn_\bfw I' \cap S$.
\end{remark}

We will need the following results.

\begin{lemma} \label{lm:Saturation}
Let $I$ be a tropical ideal in $R[x_1,\ldots,x_n]$. Denote by $I'$
the ideal generated by $I$ in $R[x_1^{\pm 1},\ldots,x_n^{\pm n}]$,
and set $I^\sat:=I' \cap R[x_1,\ldots,x_n]$. Then $I^\sat \supseteq I$
is a tropical ideal, and $V(I^\sat)=
V(I)$ as weighted polyhedral complexes.
\end{lemma}

We call $I^\sat$ the {\bf saturation} of $I$ with respect to $m:=x_1
\cdots x_n$, and we call $I$ {\bf saturated} with respect to $m$
if $I^\sat=I$.

\begin{proof}
That $I^\sat$ is a tropical ideal containing $I$ is straightforward from
the definition. Since $I^\sat \supseteq I$ we have $V(I^\sat) \subseteq
V(I)$.  Conversely, let $\bfw \in V(I)$ and $f \in I^\sat$. Then $\bfx^\bfu
\ttimes f \in I$ for some $\bfu \in \NN^n$, hence $\inn_\bfw (\bfx^\bfu \ttimes f)$
is not a monomial, and therefore neither is $\inn_\bfw f$.  This shows that $V(I) =
V(I^\sat)$. That the multiplicities are the same follows from the fact
that the multiplicities in $V(I)$ are defined using $I'$.
\end{proof}

If $\Sigma$ is a polyhedral complex in $\RR^n$ and $\sigma$ is a polyhedron in $\Sigma$,
the {\bf star} $\starr_\sigma \Sigma$ of $\Sigma$ at $\sigma$ is a weighted polyhedral fan, whose cones are
indexed by the cones $\tau$ of $\Sigma$ containing $\sigma$. The cone indexed by such $\tau$ is
\[\overline \tau := \RR_{\geq 0} \{ \bfv - \bfw \mid \bfv \in \tau \text{ and } \bfw \in \sigma \},\]
with weight equal to the weight of $\tau$ in $\Sigma$. 

The following is a result from \cite{MR2}. 

\begin{proposition} \label{prop:Initial}
Let $I$ be a tropical ideal in $R[x_1,\ldots,x_n]$, $\sigma$ be a
polyhedron in $V(I)$, and $\bfw$ be in the relative
interior of $\sigma$. Then $\inn_\bfw I \subseteq \BB[x_1,\ldots,x_n]$
is homogeneous with respect to every vector $\bfv \in \spann(\sigma)$, and 
$V(\inn_\bfw I)=\starr_\bfw V(I)$
as weighted polyhedral complexes.
\end{proposition}

\section{The independence complex of a tropical ideal}

\begin{definition}
Let $I \subseteq R[x_1,\dots,x_n]$ be a tropical ideal. The {\bf
independence complex} of $I$ is the simplicial complex
\begin{equation}\label{eq:indepalgebraic}
\I(I) \coloneqq \{ A \subseteq \{1,\dots,n\} : I \cap R[x_i : i \in  A] = \{\infty \} \}.
\end{equation}
When $\I(I)$ is the collection of independent sets of a matroid $M$,
we will say that $I$ is a {\bf matroidal tropical ideal}, and that $M$
is its associated {\bf algebraic matroid}.
\end{definition}

The independence complex of a tropical ideal $I$ can be recovered from
its variety $V(I)$, at least if $R=\Rbar$.

\begin{proposition} \label{pro:Independence}
	If $I \subseteq \Rbar[x_1,\dots,x_n]$ is a tropical ideal then
	\begin{equation}\label{eq:indepgeometric}
	\I(I) = \{ A \subseteq \{1,\dots,n\} : \pi_A(V(I)) = \RR^A \},
	\end{equation}
	where $\pi_A \colon \RR^n \to \RR^A$ is the coordinate projection onto the coordinates indexed by $A$. In particular, the independence complex $\I(I)$ depends only on the variety $V(I)$.
\end{proposition}
\begin{proof}
	Let $A \subseteq \{1,\dots,n\}$. If $A \notin \I(I)$ then there exists $f \in I
	\cap \Rbar[x_i : i \in A]$
	such that $f \neq \infty$, and $V(I) \subseteq V(f)$. We then have 
	$\pi_A(V(I)) \subseteq \pi_A(V(f)) \subsetneq \RR^A$, as claimed.
	For the reverse inclusion, suppose that $\pi_A(V(I)) \subsetneq \RR^A$, and let 
	$\bfw \in \RR^A \setminus \pi_A(V(I))$. For any polynomial $f \in
	\Rbar[x_1,\dotsc,x_n]$, denote
	by $f|_\bfw$ the polynomial in $\Rbar[x_i : i \notin A]$ obtained by specializing each variable
	$x_i$ with $i \in A$ to $w_i \in \RR$. Consider the ideal $I|_\bfw \subseteq
	\Rbar[x_i : i \notin A]$
	defined as $I|_\bfw \coloneqq \{ f|_\bfw : f \in I \}$. By \cite{MR2}, the ideal
	$I|_\bfw$ is a tropical ideal. Moreover, we must have $V(I|_\bfw) = \emptyset$, as any point $\bfv \in V(I|_\bfw)$
	would lift to the point $(\bfv, \bfw) \in V(I)$, contradicting that $\bfw \notin \pi_A(V(I))$.
	By the weak Nullstellensatz \cite[Corollary 5.17]{MR}, the tropical ideal $I|_\bfw$ must contain
	the constant polynomial $0$. But then $0 = f|_\bfw$ for some $f \in I$, which in particular implies
	that $f \in I \cap \Rbar[x_i : i \in A]$ and $f \neq \infty$. 
\end{proof}

Recall that the Hilbert function $H_I(e)$ of a tropical ideal $I \subseteq \Rbar[x_1,\dots,x_n]$ eventually agrees with a polynomial in $e$, called the {\bf Hilbert polynomial} of $I$ \cite[Proposition 3.8]{MR}. The {\bf dimension} $\dim(I)$ of $I$ is defined as the degree of its Hilbert polynomial.

\begin{corollary}
	For any tropical ideal $I$ we have
	\[\dim \I(I) + 1 = \dim V(I) = \dim I.\]
\end{corollary}
\begin{proof}
	From \eqref{eq:indepgeometric} it is clear that $\dim V(I) \geq \dim\I(I)+1$. Now, if $V(I)$ contains a polyhedron $\sigma$ of dimension $d$ then there is some coordinate projection $\pi_A(\sigma)$ that is $d$-dimensional, and thus from \eqref{eq:indepalgebraic} we see that $A \in \I(I)$ and thus $\dim \I(I) + 1 \geq d$. This shows that $\dim \I(I) + 1 = \dim V(I)$. The equality $\dim V(I) = \dim I$ is proved in \cite{MR2}.
\end{proof}

In the classical setting, primality of an ideal implies matroidality. 
We have no idea about a similarly appealing sufficient condition
for matroidality of general tropical ideals.

\begin{example}\label{ex:matroidal}
	If $J \subseteq K[x_1,\dotsc,x_n]$ is a prime ideal, where $K$ is a
	field with a non-Archimedean valuation, then $\trop(J)$ is a matroidal tropical ideal.
	Its associated algebraic matroid is the matroid that captures algebraic independence
	among the coordinate functions $x_1, \dots, x_n$ in the field of fractions of $K[x_1,\dots,x_n]/J$. 
\end{example}

\begin{problem}\label{prob:matroidal}
Find algebraic conditions on a tropical ideal that imply matroidality.
\end{problem}

As shown in \cref{ex:matroidal}, any (classically) algebraic matroid is the algebraic matroid of a tropical ideal.
However, in principle, it is possible that the class of matroids that are ``tropically algebraic'' is strictly larger than the usual class of algebraic matroids. 

\begin{question}\label{que:algebraic}
Which matroids arise as the algebraic matroid of a tropical ideal?
\end{question}



\section{Not every Bergman fan is the variety of a tropical ideal}

We now prove that not every balanced polyhedral complex can be
obtained as the variety of a tropical ideal. Our counterexample will in
fact be the Bergman fan of a matroid; see \cite{Ardila06} for details.

\begin{definition}
Let $M$ be a loopless matroid of rank $d$ on the ground set $\{1,\dots,n\}$. 
The {\bf Bergman fan} $\B(M)$ of $M$ is the pure $d$-dimensional polyhedral fan in $\RR^n$ 
consisting of the cones of the form 
\[\sigma_\F \coloneqq  \cone(\bfe_{F_1},\bfe_{F_2},\dotsc,\bfe_{F_k}) + \RR \!\cdot\! 
\bfe_{\{1,\dotsc, n\}}\] where 
$\F = \{\emptyset \subsetneq F_1 \subsetneq F_2 \subsetneq \dotsb \subsetneq F_k 
\subsetneq \{1,\dotsc, n\}\}$ is a chain of flats in 
the lattice of flats $\mathcal L(M)$ of $M$, and where $\bfe_S$ stands
for the sum of the standard basis vectors $\bfe_i$ with $i$ running
through $S$. 
The Bergman fan of any matroid is given the structure of a balanced polyhedral complex 
by defining the multiplicity of each maximal cone to be equal to 1.
\end{definition}

Bergman fans of matroids are the tropical linear spaces (more specifically, their part inside the torus $\RR^n$) that correspond to valuated matroids where the basis valuations all take values in $\BB$.

Let $U_{2,3}$ be the uniform matroid of rank 2 on the ground set $\{1,2,3\}$,
and let $V_8$ be the V\'amos matroid (of rank 4 on 8 elements). The following
is our main result.

\begin{theorem}\label{thm:main}
There is no tropical ideal $I \subseteq \Rbar[x_1, \dots, x_3, y_1, \dots,
y_8]$ such that $V(I)$ is equal to $\B(U_{2,3} \oplus V_8)$ as weighted polyhedral complexes, even up to common refinement.
\end{theorem}

Note that we do not require the polyhedral structure on $V(I)$
coming from the Gr\"obner complex of the homogenisation of $I$ to be equal
to the fan structure on the Bergman fan described above.

To prove the theorem, in addition to the fundamental results from
\cref{sec:Basics}, we will need results relating $V(I)$
to $H_I$ for any tropical ideal $I$.

\begin{lemma} \label{lm:Intersection}
Let $L,L' \subseteq R^N$ be tropical linear spaces. If $\dim L +
\dim L'>|N|$, then $L \cap L' \neq \{(\infty,\ldots,\infty)\}$. 
\end{lemma}
\begin{proof}
The notion of stable intersection for tropical linear spaces was 
studied by Speyer in \cite{Speyer04} when the underlying matroids of both
tropical linear spaces were uniform matroids, and later generalized by
Mundinger \cite{Mundinger} for arbitrary tropical linear spaces in $R^N$.
The stable intersection $L \cap_{\st} L'$ is a tropical linear space 
contained in both $L$ and $L'$, and it has dimension a least
$\dim L + \dim L' - |N| > 0$, which implies the desired result.
\end{proof}

\begin{proposition}\label{pro:lowerbound}
Let $I \subseteq R[x_1,\dots,x_n]$ be a tropical ideal. 
If the independence complex $\I(I)$ contains a subset $A$ of size $r$, then
$H_I(d) \geq \binom{r+d}{d}$ for all $d \in \NN$.
\end{proposition}

\begin{proof}
The space $R[x_i:i \in A]_{\leq d}$ is a tropical linear space
in $R^{\monld}$ of dimension $\binom{r+d}{d}$ and, by assumption,
it does not intersect $I_{\leq d}$.  Hence by \cref{lm:Intersection},
$\dim I_{\leq d} \leq \binom{n+d}{d} - \binom{r+d}{d}$, and therefore
$H_I(d) \geq \binom{r+d}{d}$. 
\end{proof}

\begin{proposition}\label{pro:upperbound}
Let $I \subsetneq R[x_1,\dots,x_n]$ be a tropical ideal, and set
$r:=H_I(1)-1$. Then $H_I(d) \leq \binom{r+d}{d}$ for all $d \in \NN$. 
\end{proposition}

\begin{proof}
Let $I^h \subseteq R[x_0,\ldots,x_n]$ be the homogenisation
of $I$. Then $\dim (I^h)_d=\dim I_{\leq d}$ for all $d \in \NN$, and in
particular $\dim (I^h)_1=\dim I_{\leq 1}=n+1-H_I(1)=n-r$. Moreover,
by applying \cref{thm:Inn} with a sufficiently general weight vector $\bfw$, 
the Hilbert function of $I^h$ is also that of
some monomial ideal $J$. We find that $J$ contains precisely $n-r$ of the
$n+1$ variables $x_0,\ldots,x_n$, and therefore all their multiples. 
This implies that $\dim
J_d \geq \binom{n+d}{d}-\binom{r+d}{d}$, where the last term counts
monomials in the remaining $r+1$ variables of degree $d$. 
We then have
\[ \textstyle H_I(d)=\binom{n+d}{d}-\dim I_{\leq d}=\binom{n+d}{d}-\dim J_d
\leq \binom{n+d}{d}-\binom{n+d}{d}+\binom{r+d}{d}, \]
as desired.
\end{proof}

The following proposition shows that the algebraic matroid of a Bergman fan $\B(M)$ (as in \cref{pro:Independence}) is equal to the matroid $M$.

\begin{proposition}[{\cite[Lemma 3]{Yu}}]\label{pro:complex}
The independence complex of the Bergman fan $\B(M)$ of a loopless
matroid $M$ is the same as the independence complex of $M$.
\end{proposition}

We now present a key step towards proving our main result.

\begin{proposition}\label{pro:degree1}
Let $M$ be a loopless matroid on the ground set $\{1,\dots,n\}$. 
Suppose $J \subseteq \BB[x_1,\dots,x_n]$ is a homogeneous tropical ideal,
saturated with respect to $x_1 \cdots x_n$, whose variety $V(J)$ has a
common refinement, as weighted polyhedral complexes, with the Bergman
fan $\B(M)$ (with weight 1 in all its
maximal cones).  Then the matroid $M(J_1)$ is equal to $M$, under the
identification $x_i \leftrightarrow i$ of ground sets.
\end{proposition}

\begin{proof}
Let $B = \{b_1, \dots, b_d\}$ be a basis of $M$. For $0 \leq i \leq
d$, consider the flat $F_i$ of $M$ obtained as the closure of the set
$\{b_1, \dots, b_i\}$, and let $\sigma$ be the maximal cone of $\B(M)$
corresponding to the chain of flats $\emptyset = F_0 \subsetneq F_1
\subsetneq \dots \subsetneq F_{d-1} \subsetneq F_d = \{1,\dots,n\}$.
Let $\tau \subseteq \sigma$ be a maximal cone in a common refinement of both $V(J)$ and $\B(M)$.
The linear span $\spann(\tau) = \spann(\sigma)$ consists of all vectors 
$\bfw \in \RR^n$ for which $w_i = w_j$ whenever $\{i, j\} \subseteq F_k\setminus F_{k-1}$ for some $k=1,\ldots,d$.
%and let $\bfw$
%be a point in the relative interior of $\sigma$ such that $\sigma$ locally
%around $\bfw$ agrees with a maximal polyhedron in $V(J)$.  Then $\bfw$
%is a constant $c_i$ on $F_i\setminus F_{i-1}$ for all $i=1,\ldots,d$, 
%and $c_1>c_2>\ldots>c_d$. We assume, furthermore, that there are no
%$\QQ$-linear relations among the $c_i$---we may do so by replacing $\bfw$
%by a nearby point, since the definition of multiplicities in $V(J)$ is
%invariant under this replacement. 
A monomial $\bfx^\bfu$ in $\BB[x_1^{\pm 1},\dots,x_n^{\pm 1}]$ has
$\bfw$-weight equal to zero for all such $\bfw$ 
if and only if for every $k$ we have
$\sum_{i \in F_k \setminus F_{k-1}} u_i = 0$. As in
\cref{re:Mult}, let $S$ be the subsemiring of $\BB[x_1^{\pm 1},\dots,x_n^{\pm 1}]$
consisting of all polynomials involving only such monomials, 
and let $J'$ be the (tropical) ideal in
$\BB[x_1^{\pm 1},\ldots,x_n^{\pm 1}]$ generated by $J$.

Take $\bfv$ to be a vector in the relative interior of $\tau$.
Since $\tau$ has multiplicity $1$ in $V(J)$, 
$\inn_\bfv(J') \cap S$ is zero-dimensional of degree $1$, and contains no monomials. 
Hence for any pair of distinct monomials $\bfx^\bfu,
\bfx^{\bfu'}$ in $S$, $\inn_{\bfv} (J') \cap S$ contains the binomial
$\bfx^\bfu \tplus \bfx^{\bfu'}$. In particular, if $\{i \neq j\} \subseteq F_k \setminus F_{k-1}$
for some $k$ then $0 \oplus x_i^{-1} x_j \in \inn_\bfv(J')
\cap S$, and thus $x_i \tplus x_j \in \inn_\bfv(J')$.
As $J$ is homogeneous and saturated with respect to $x_1
\cdots x_n$, this implies that there is a polynomial of the form $x_i \tplus x_j \tplus f$
in $J_1$ where $f$ is a sum of variables all contained in
$F_{k-1}$. 
It follows that $x_i$ is in the closure of $F_{k-1} \cup \{x_j\}$ in the matroid $M(J_1)$.
We conclude that $\{b_1, \dots, b_d\}$ is a generating set in the matroid $M(J_1)$, 
and thus $\rank(M(J_1)) \leq \rank(M)$. 
Now, the tropical prevariety cut out by the linear polynomials in $J$ is equal to $\B(M(J_1))$, so we have 
$\B(M(J_1)) \supseteq V(J) = \B(M)$. It follows from \cite[Lemma 7.4]{Rincon} that 
$\B(M(J_1)) = \B(M)$, and thus $M(J_1) = M$, completing the proof.
\end{proof}

We conclude with the proof of the main theorem.

\begin{proof}[Proof of \cref{thm:main}]
Suppose that such an $I$ exists, and denote $M:=U_{2,3} \oplus V_8$. Let
$\sigma$ be a polyhedron in $V(I)$ whose affine span is $\RR \cdot \one$ (which is contained in the lineality space of $\B(M)$), %%% B(M) has more lineality
and let $\bfw$ be in the relative
interior of $\sigma$.  Set $J' := \inn_\bfw I  \subseteq \BB[x_1, \dots, x_3,
y_1, \dots, y_8]$.  By \cref{prop:Initial}, the tropical ideal $J'$ is homogeneous (with respect to $\one$) and has variety $V(J') = \starr_\bfw V(I)$,
which is equal to $\B(M)$ up to common refinement. 
Consider the homogeneous ideal $J := (J')^\sat$. By \cref{lm:Saturation}, we have that $V(J)$ is also equal to $\B(M)$ up to common refinement, and so by \cref{pro:degree1}, $M(J_1)$ is equal
to $M$.  Since $\rk M=6$, we find that $H_J(1)=1+6=7$ and thus, by
\cref{pro:upperbound}, $H_J(d) \leq \binom{6+d}{d}$ for
all $d$.
On the other hand, since $V(J) = \B(M)$, by \cref{pro:complex,pro:Independence} the tropical ideal $J$ is matroidal, with associated
algebraic matroid $M = U_{2,3} \oplus V_8$. Hence, by \cref{pro:lowerbound} we have $H_J(d) \geq \binom{6+d}{d}$. We conclude that
$H_J(d)=\binom{6+d}{d}$. 

Denote $Q:=M(J_2)$. The matroid $Q$ has rank 
$H_J(2)-H_J(1) = 21$ on the ground set $S_1 \sqcup S_2 \sqcup S_3$ where $S_1:=\{x_i x_j \mid
1 \leq i \leq j \leq 3 \}$, $S_2:=\{y_i y_j \mid 1 \leq i \leq j \leq
8\}$, and $S_3:=\{x_i y_j \mid 1\leq i \leq 3, 1\leq j \leq 8\}$. The restriction
$Q|{S_1}$ is spanned by all products of
two elements in a basis of $M(J_1)|{\{x_1,x_2,x_3\}}$, hence has rank
at most $\binom{2+1}{2}=3$.  Similarly, the restriction $Q|{S_2}$ has
rank at most $\binom{4+1}{2}=10$. Hence $Q|{S_3}$ has rank at least
$21-3-10=8$. 

Since $J$ is saturated, for each $1\leq i \leq 3$, multiplication by $x_i$
yields an isomorphism between the matroid
$M(J_1)|{\{y_1,\ldots,y_8\}} \cong V_8$ and the restriction of $Q$ to
$x_i \cdot \{y_1,\ldots,y_8\} \subseteq S_3$. 
Similarly, for each $1\leq j \leq 8$, the restriction of
$Q$ to $y_j \cdot \{x_1,\dots,x_3\}$ is isomorphic to $U_{2,3}$. Hence
$Q|{S_3}$ is a quasi-product of $U_{2,3}$ and $V_8$ in
the sense of \cite{Vergnas81}. But the
main result of \cite{Vergnas81} shows that such a quasi-product has
rank at most $7$, a contradiction. 
\end{proof}

%% \acknowledgements{\lipsum[20]}

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