%% 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[revision]{FPSAC2019}

\articlenumber{45}
\addbibresource{45.bib}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

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

%packages
\usepackage{amsxtra, amscd, amsfonts}
\usepackage{mathrsfs}
\usepackage[all]{xy}
\usepackage{graphicx}
\usepackage{comment}
\usepackage{url}
\usepackage{color}

\usepackage{lipsum}

%theorem environments
\theoremstyle{definition}
\newtheorem{cor}[subsection]{Corollary}
\newtheorem{lem}[subsection]{Lemma}
\newtheorem{prop}[subsection]{Proposition}
\newtheorem{thm}[subsection]{Theorem}
\newtheorem{defn}[subsection]{Definition}
\newtheorem{eg}[subsection]{Example}
\newtheorem{rem}[subsection]{Remark}
\newtheorem{obs}[subsection]{Observation}
\newtheorem{ques}[subsection]{Question}
\newtheorem{conj}[subsection]{Conjecture}
\newtheorem{exer}{Exercise}


%letters
\newcommand{\QQ}{\mathbb Q}
\newcommand{\RR}{\mathbb R}
\newcommand{\CC}{\mathbb C}
\newcommand{\PP}{\mathbb P}
\newcommand{\ZZ}{\mathbb Z}


%% define your title in the usual way
\title{Divisors on matroids and their volumes}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Christopher Eur\thanks{\href{mailto:ceur@math.berkeley.edu}{ceur@math.berkeley.edu}}}

%% then use \addressmark to match authors to institutions here
\address{Department of Mathematics, University of California, Berkeley.}

%% 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{The classical volume polynomial in algebraic geometry measures the degrees of ample (and nef) divisors on a smooth projective variety. We introduce an analogous volume polynomial for matroids, give a complete combinatorial formula, and show that it is a valuation under matroid polytope subdivisions. For a realizable matroid, we thus obtain an explicit formula for the classical volume polynomial of the associated wonderful compactification; in particular, we obtain another formula for volumes of generalized permutohedra.  We then introduce a new invariant called the shifted rank-volume of a matroid as a particular specialization of its volume polynomial, and discuss its algebro-geometric and combinatorial properties in connection to graded linear series on blow-ups of projective spaces.}

%% put your French abstract here, or comment this out if you don't have one
%\resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{matroids, Chow rings, volume polynomials, Newton-Okounkov bodies, generalized permutohedra}

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

Recent intersection theoretic approach to matroids has led to the resolution of the long-standing conjecture of Rota on the log-concavity of the coefficients of chromatic polynomials, first proven for graphs by Huh in \cite{Huh12}, for realizable matroids in \cite{HK12}, and for general matroids by Adiprasito, Huh, and Katz in \cite{AHK18}.  Among the key tools in \cite{Huh12, HK12} for establishing log-concavity is the Teissier-Khovanskii inequality for intersection numbers of nef divisors on smooth projective varieties, which can be understood as a phenomenon of convexity:  The Newton-Okounkov body $\Delta(D)$ of a nef divisor $D$ is a convex body whose volume is the self-intersection number of $D$, and its existence reduces the Teissier-Khovanskii inequality to the Brunn-Minkowski inequality for volumes of convex bodies.

For general matroids, a combinatorial version of Teissier-Khovanskii inequality is proven in \cite{AHK18} by establishing Hodge theory analogues for the Chow ring of a matroid \emph{without} explicit use of convex bodies.  Noting that matroids can be considered as tropical linear varieties (see \cite{AK06}), the results of \cite{AHK18} suggest an existence for an analogue of Newton-Okounkov bodies for tropical linear varieties, and perhaps tropical varieties in general.  Our results here can be seen as a first step towards such a direction with various ramifications to both algebraic geometry and combinatorics of matroids.

The volume polynomial in classical algebraic geometry measures the self-intersection number of a nef divisor on a smooth projective variety, or equivalently the volume of its Newton-Okounkov body.  In essence, it is defined by choosing a presentation of the cohomology ring of the variety; here we define analogously the volume polynomial $VP_M$ for a matroid $M$.

Let $M$ be a matroid of rank $r = d+1$ on a ground set $E$ with lattice of flats $\mathscr L_M$, and denote $\overline{\mathscr L_M} := \mathscr L_M\setminus\{\emptyset, E\}$.  The Chow ring of a matroid defined below plays the role of the cohomology ring of a smooth projective variety of dimension $d$.

\begin{defn}
The \textbf{Chow ring} of a simple matroid $M$ is the graded ring
$$A^\bullet(M):=\frac{ \RR[x_F : F\in \overline{\mathscr L_M}] }{ \langle x_Fx_{F'} \ | \ F,F' \textnormal{ incomparable}\rangle + \langle \sum_{F\ni i}x_F - \sum_{G\ni j} x_G \ | \ i,j\in E\rangle }$$
\end{defn}

In analogy with Chow rings in algebraic geometry, we call elements of $A^1(M)$ \textbf{divisors} on a matroid $M$.  Like the cohomology rings of smooth manifolds, each graded piece $A^i(M)$ of the Chow ring $A^\bullet(M)$ is a finite dimensional $\RR$-vector space and is nonzero only for $0\leq i \leq d$.  It satisfies Poincar\'e duality, with the degree map
$$\begin{array}{cl}
\deg_M: A^{d}(M) \overset \sim \to \RR \quad & \textnormal{ where }\deg_M(x_{F_1}x_{F_2}\cdots x_{F_d}) = 1\\
& \textnormal{ for every maximal chain } F_1\subsetneq \cdots \subsetneq F_d \textnormal{ in }  \overline{\mathscr L_M}.
\end{array}$$

Given a graded algebra $R$ with such Poincar\'e duality property, a standard procedure of Macaulay's inverse system in commutative algebra then provides a way to encode $R$ by a single polynomial called the cogenerator from which $R$ can be recovered (see \cref{cogen}).

\newtheorem*{defn:volpoldefn}{\cref{volpoldefn}}
\begin{defn:volpoldefn}
Let $M$ be a matroid of rank $r = d+1$.  The \textbf{volume polynomial} $VP_M(\underline t) \in \RR[t_F : F\in \overline{\mathscr L_M}]$ is the cogenerator of $A^\bullet(M)$.
\end{defn:volpoldefn}

When $M$ is realizable, $VP_M$ agrees with the classical volume polynomial of the wonderful compactification $Y_M$ of the complement of the associated hyperplane arrangement  $\mathcal A_M$ of $M$.  While $VP_M$ is initially defined purely algebraically, we prove a completely combinatorial formula for $VP_M$, which follows from our first main theorem on the intersection numbers of divisors on a matroid.

\newtheorem*{thm:main}{\cref{main}}
\begin{thm:main}
Let $M = (E, \mathcal B)$ be a matroid, $\emptyset = F_0 \subsetneq F_1 \subsetneq \cdots \subsetneq F_k \subsetneq F_{k+1} = E$ a chain of flats in $\mathscr L_M$ of ranks $r_i := \operatorname{rk} F_i$, and $d_1, \ldots, d_k$ be positive integers such that $\sum_i d_i = d := \operatorname{rk} M - 1$.  Denote by $\widetilde d_i := \sum_{j=0}^i d_j$ (where $d_0 := 0$).  Then
$$\deg_M(x_{F_1}^{d_1}\cdots x_{F_k}^{d_k}) = (-1)^{d-k} \prod_{i = 1}^{k}{d_i -1 \choose \widetilde d_i - r_i}\mu^{\widetilde d_i - r_i}(M|F_{i+1}/F_i)$$
where $\mu^i(N)$ denotes the $i$-th unsigned coefficient of the reduced characteristic polynomial $\overline{\chi}_N(t) = \mu^0(N) t^{\operatorname{rk} N-1} - \mu^1(N) t^{\operatorname{rk}N-2} + \cdots \pm \mu^{\operatorname{rk}N-1}(N)$ of a matroid $N$.
\end{thm:main}

\newtheorem*{cor:regdim}{\cref{volpol}}
\begin{cor:regdim}
 Let the notations be as above.  The coefficient of $t_{F_1}^{d_1}\cdots t_{F_k}^{d_k}$ in $VP_M(\underline t)$ is
$$(-1)^{d-k}{d \choose d_1, \ldots, d_k} \prod_{i = 1}^{k} {d_i - 1 \choose \widetilde d_i -r_i} \mu^{\widetilde d_i - r_i}(M|F_{i+1}/F_i).$$
\end{cor:regdim}

We give two immediate applications of the formula for the volume polynomial.  The first is an explicit formula in \cref{volGP} for the volumes of generalized permutohedra, adding to the ones given by Postnikov in \cite{Pos09}.  The second is to show that taking the Chow ring of a matroid respects the ``type $A$" structure of matroids.  More precisely,

\newtheorem*{prop:val}{\cref{val}}
\begin{prop:val}
Consider $VP_M(\underline t)$ as a polynomial in $\RR[t_S : S\in 2^E]$.  Then the map $M\mapsto  VP_M \in \RR[t_S : S\in 2^E]$ is a matroid valuation in the sense of \cite{AFR10}.
\end{prop:val}

\medskip
While the volume polynomial $VP_M$ has the same information as the Chow ring $A(M)$ of a matroid, it lends itself more naturally as an invariant of a matroid than the Chow ring.  That $M\mapsto VP_M$ is a valuation already illustrates this effect.  Moreover, any natural specialization of $VP_M$ defines an invariant of a matroid.  We present here one such example coming from the rank function of a matroid.

\newtheorem*{defn:voldefn}{\cref{voldefn}}
\begin{defn:voldefn}
Define the \textbf{shifted rank-volume} of a matroid $M$ to be
$$\operatorname{shRVol}(M) := VP_M(t_F := \operatorname{rk} F) = \deg_M\Big(\sum_{F\in \overline{\mathscr L_M}} (\operatorname{rk} F)x_F\Big)^{\operatorname{rk} M-1}.$$
\end{defn:voldefn}

The shifted rank-volume of a matroid seems to be a genuinely new invariant, as it is unrelated to classical invariants such as the Tutte polynomial or the volume of the matroid polytope; see \cref{volrel}.  It seems to measure how close the matroid is to the uniform matroid.

\newtheorem*{thm:realmax}{\cref{realmax}}
\begin{thm:realmax}
Let $M$ be a realizable matroid of rank $r$ on $n$ elements.  Then 
$$\operatorname{shRVol}(M) \leq \operatorname{shRVol}(U_{r,n}) = (n-r)^{r-1} \quad \textnormal{with equality iff $M=U_{r,n}$}.$$
\end{thm:realmax}

The proof of \cref{realmax} is algebro-geometric in nature, involving counting sections of line bundles.  In a subsequent work we give a proof for arbitrary matroids \cite{BES19}, but it is not a combinatorial reflection of such algebro-geometric approach.  This naturally leads to asking whether there exist an analogue of the theory of Newton-Okounkov bodies for linear tropical varieties.

\medskip
This is an extended abstract for the author's full paper \cite{Eur18}.  Worked-out examples and codes can be found at \url{https://math.berkeley.edu/~ceur/research.html}.

\proof[Notations] $|S|$ denotes the cardinality of a (finite) set $S$.  We use $k$ for a field, which we always assume algebraically closed, and a variety is an integral separated scheme over a field $k$.  A binomial coefficient ${n \choose m}$ is understood to be zero if $m<0$ or $m>n$.


\section{Preliminaries}

\subsection*{Wonderful compactifications and Chow rings of matroids}   See \cite{Oxl11} for a general reference on matroids.  For accounts tailored towards Chow ring of matroids, we recommend \cite{Bak18}.

\medskip
For a matroid $M$ on a ground set $E$ of rank $r = d+1$, denote by $\mathscr L_M$ the lattice of flats, and $\overline {\mathscr L_M} := \mathscr L\setminus\{\emptyset, E\}$\footnote{As the notions we discuss will only depend on $\mathscr L_M$, we assume for simplicity that $M$ is simple.}.   An open interval in a lattice $\mathscr L$ is denoted $(\ell_1, \ell_2) = \{\ell \in \mathscr L  \ | \ \ell_1 < \ell < \ell_2\}$.  Let $\chi_M(t)$ be the characteristic polynomial of $M$, then its \textbf{reduced characteristic polynomial} is $\overline\chi_M(t) := \chi_M(t) / (t-1)$.

If the matroid $M$ matroid is realizable, say as vectors $\{v_i\}_{i\in E}$ spanning a $k$-vector space $V$, denote by $\mathcal A_M = \{H_i\}_{i\in E}$ the associated hyperplane arrangement in $\PP(V^*)$ where $H_i := \{f\in \PP(V^*): f(v_i) = 0\}$.  A flat $F$ of rank $c$ in $M$ correspond to a $c$-codimensional linear space $H_F := \{f\in \PP(V^*) : f(v_i) = 0 \ \forall i\in F\}$.  The \textbf{wonderful compactification} $Y_M$ is  then obtained by consecutively blowing-up (strict transforms of) $\{H_F\}_{F\in \overline{\mathscr L_M}}$ in $\PP(V^*)$ starting with $H_F$ with highest $\operatorname{rk} F$.  $Y_M$ is a compactification of the hyperplane arrangement complement $C(\mathcal A_M) = \PP(V^*)\setminus \mathcal A_M$ whose boundary $Y_M\setminus C(\mathcal A_M)$ consists of the exceptional divisors $\widetilde H_F$, which have simple-normal-crossings.  See \cite{DCP95} for the original construction, or \cite{Fei05} for a survey written for combinatorialists.  The intersection theory of the boundary divisors of $Y_M$ is encoded in the matroid (\cite[Theorem 5.12]{AHK18}), which leads to the definition of the Chow ring of an arbitrary matroid (not necessarily realizable), first appearing in \cite{FY04} and further studied in \cite{AHK18}.

\begin{defn}
The \textbf{Chow ring} of a (simple) matroid $M$ is the graded ring
$$A^\bullet(M):=\frac{ \RR[x_F : F\in \overline{\mathscr L_M}] }{ \langle x_Fx_{F'} \ | \ F,F' \textnormal{ incomparable}\rangle + \langle \sum_{F\ni i}x_F - \sum_{G\ni j} x_G \ | \ i,j\in E\rangle }.$$
We call elements of $A^1(M)$ \textbf{divisors} on $M$.
\end{defn}

Recently in \cite{AHK18}, the ring $A^\bullet(M)$ has been shown to satisfy the whole K\"ahler package---Poincar\'e duality, hard Lefschetz property, and Hodge-Riemann relations.  For our purposes, we only need the Poincar\'e duality.

\begin{prop}\cite[\S5.10]{AHK18} The Chow ring $A^\bullet(M)$ of a matroid $M$ of rank $r = d+1$ is a finite graded $\RR$-algebra satisfying:  (i) there exists a linear isomorphism $\deg_M: A^d(M) \to \RR$ uniquely determined by the property that $\deg_M(x_{F_1}x_{F_2}\cdots x_{F_d}) = 1$ for every maximal chain $F_1\subsetneq \cdots \subsetneq F_d$ in $\overline{\mathscr L_M}$, and (ii) the pairings $A^i(M) \times A^{d-i}(M) \to A^d(M) \overset{\deg}{\simeq}\RR$ are non-degenerate.
\end{prop} 

\subsection*{Volumes of divisors and cogenerators} For a general reference on intersection theory, see \cite{EH16}.  Here we follow the survey \cite{ELM+05}.

\medskip
Let $X$ be a $d$-dimensional smooth projective variety over an algebraically closed field $k$, and let $A^\bullet(X)$ be its Chow ring and denote by $\deg_X$ or $\int_X$ the degree map $A^d(X) \to \ZZ$ sending a class of a closed point to 1.  For a Cartier divisor $D$ on $X$, the \textbf{volume} of $D$ is defined as
$$\operatorname{vol}(D) := \lim_{t\to \infty} \frac{h^0(X,\mathscr O(tD))}{t^d/d!}.$$
In other words, denoting by $R(D)_\bullet := \bigoplus_{t\geq 0} H^0(X,tD)$ the \textbf{section ring} of $D$, the volume measures the asymptotics of $\frac{\dim_k R(D)_t}{t^d/d!}$ as $t\to \infty$.

By standard relation between Hilbert polynomials and intersection multiplicities, volume of a very ample divisor $D$ is the degree of $X$ under the embedding given by $D$.  can be geometrically interpreted as follows: If $m>0$ is such that $mD$ is very ample, then for general divisors $E_1, \ldots, E_d$ in the complete linear system $|mD|$ we have $\operatorname{vol}(D) = \frac{1}{m^d} \deg_X[E_1\cap E_2 \cap \cdots \cap E_d]$.  That is, $\operatorname{vol}(D) = \int_X (c_1(D))^d$ if $D$ is ample.

The volume of a divisor depends only on its numerical equivalence class.  Thus, letting $N^1(X)$ be the group divisors modulo numerical equivalence generated by $\{\xi_1, \ldots, \xi_r\}$ and $\operatorname{Nef}(X)\subset N^1(X)_\RR$ the nef cone, the map $\operatorname{vol}: \operatorname{Nef}(X) \to \RR$ defines the \textbf{volume polynomial} $VP_X\in \RR[t_1, \ldots, t_r]$ where 
$$VP_X(t_1, \ldots, t_r) = \operatorname{vol}(t_1\xi_1+\cdots + t_r\xi_r) \quad \textnormal{whenever $t_1\xi_1+ \cdots + t_r\xi_r\in \operatorname{Nef}(X)$}.$$

\begin{rem}
The volume of a divisor $D$ can be realized as a volume of convex body $\Delta(D)$ called the \textbf{Newton-Okounkov body} of $D$.  For background on Newton-Okounkov bodies, see \cite{LM09} for a more geometric perspective with applications to big divisors and N\'eron-Severi groups, and \cite{KK12} for an approach using semigroups and with a view towards generalized Kushnirenko-Bernstein theorem.
\end{rem}

Macaulay's inverse system provide a purely algebraic approach to the notion of volume polynomial as the cogenerator of a graded ring with Poincar\'e duality.

\begin{prop}\cite[\S13.4.7]{CLS11} \label{cogen}
Suppose a graded finite $k$-algebra $A = \bigoplus_{i=0}^d A_i$ satisfies: (i) $A$ is generated in $A_1$ with $A_0 = k$, (ii) there exists a $k$-linear isomorphism $\deg: A_d \to k$, and (iii) $A_i \times A_{d-i} \to A_d \overset{deg}\simeq k$ is a non-degenerate pairing.  Let $x_1, \ldots, x_n$ generate $A_1$, so that $A \simeq k[\underline x]/I$ for some ideal $I$. Then there exists $P\in k[t_1, \ldots, t_n]$ such that
$$I = \{f\in k[\underline x] \ | \ f(\frac{\partial}{\partial{t_1}}, \ldots, \frac{\partial}{\partial{t_n}})\cdot P = 0\}.$$  Up to scaling by an element of $k$, this \textbf{cogenerator} $P$ is
$$P = \deg\big( (t_1x_1 + \cdots + t_nx_n)^d\big)$$
where we extend $\deg: A_d\to k$ to $A_d[t_1, \ldots, t_n] \to k[t_1, \ldots, t_n]$.
\end{prop}


\section{The volume polynomial of a matroid}

As the Chow ring $A^\bullet(M)_\RR$ of a matroid satisfies Poincar\'e duality, that is, the conditions of \cref{cogen}, we can define its cogenerator.

\begin{defn}\label{volpoldefn}
Let $M$ be a matroid of rank $r = d+1$.  The \textbf{volume polynomial} $VP_M \in \RR[t_F : F\in \overline{\mathscr L_M}]$ is the cogenerator of $A^\bullet(M)_\RR$, where $VP_M$ is normalized so that the coefficient of any monomial $t_{F_1}t_{F_2}\cdots t_{F_d}$ corresponding to a maximal chain of flats in $\mathscr L_M$ is $d!$.

Equivalently, observe that via \cref{cogen} the volume polynomial is $VP_M = \deg_M( (\sum_{F\in \overline{\mathscr L_M}} x_F t_F)^d)$ (where $\deg_M:A^d(M)\to \RR$ is extended to $A^d[t_F\textnormal{'s}]\to \RR[t_F\textnormal{'s}]$).
\end{defn}

The coefficient of $t_{F_1}^{d_1}\cdots t_{F_k}^{d_k}$ for $d_1 + \cdots d_k = d = \operatorname{rk} M -1$ in the volume polynomial $VP_M$ is ${d \choose d_1, \ldots, d_k}\deg_M(x_{F_1}^{d_1}\cdots x_{F_k}^{d_k})$.  Thus, the knowing the volume polynomial amounts to knowing all the intersection numbers $\deg_M(x_{F_1}^{d_1}\cdots x_{F_k}^{d_k})$.  Our main theorem is the combinatorial formula for all the intersection numbers.

\begin{thm}\label{main} Let $M = (E, \mathcal B)$ be a matroid, $\emptyset = F_0 \subsetneq F_1 \subsetneq \cdots \subsetneq F_k \subsetneq F_{k+1} = E$ a chain of flats in $\mathscr L_M$ of ranks $r_i := \operatorname{rk} F_i$, and $d_1, \ldots, d_k$ be positive integers such that $\sum_i d_i = d := \operatorname{rk} M - 1$.  Denote by $\widetilde d_i := \sum_{j=0}^i d_j$ (where $d_0 := 0$).  Then
$$\deg(x_{F_1}^{d_1}\cdots x_{F_k}^{d_k}) = (-1)^{d-k} \prod_{i = 1}^{k}{d_i -1 \choose \widetilde d_i - r_i}\mu^{\widetilde d_i - r_i}(M|F_{i+1}/F_i)$$
where $\mu^i(N)$ is the $i$-th unsigned coefficient of the reduced characteristic polynomial $\overline{\chi}_N(t) = \mu^0(N) t^{\operatorname{rk} N-1} - \mu^1(N) t^{\operatorname{rk}N-2} + \cdots +(-1)^{\operatorname{rk}(N)-1} \mu^{\operatorname{rk}N-1}(N)$ of a matroid $N$.
\end{thm}

\begin{cor}\label{volpol} Let the notations be as above.  The coefficient of $t_{F_1}^{d_1}\cdots t_{F_k}^{d_k}$ in $\operatorname{VP}_M(\underline t)$ is
$$(-1)^{d-k}{d \choose d_1, \ldots, d_k} \prod_{i = 1}^{k} {d_i - 1 \choose \widetilde d_i -r_i} \mu^{\widetilde d_i - r_i}(M|F_{i+1}/F_i).$$
\end{cor}

\begin{rem}[$\overline{\mathcal M_{0,n}}$] When $M$ is realizable, $VP_M$ agrees with the classical volume polynomial of the wonderful compactification $Y_M$.  In particular, when $M = M(K_{n-1})$ is the matroid of the complete graph on $n-1$ vertices, its wonderful compactification $Y_M$ is the Deligne-Mumford space $\overline{\mathcal M_{0,n}}$ of rational curves with $n$ marked points (\cite[\S 6.4]{MS15}).  The numerical cones of $\overline{\mathcal M_{0,n}}$ are believed to be complicated, as $\overline{\mathcal M_{0,n}}$ is not a Mori dream space in general (\cite{GK16}).  Nevertheless, our combinatorial formula for the volume polynomial allows for computation of the volume of any divisor in its nef cone.
\end{rem}

\begin{rem}[Computation] 
Computing $VP_M$ via \cref{cogen} alone via Gr\"obner bases quickly becomes infeasible as the matroid becomes larger.  For example, $M(K_6)$ has 203 flats, so that the Chow ring $A(M)$ has 201 variables.
\end{rem}

The proof of \cref{main} consists broadly of three steps.  First, via the geometry of the Bergman fan of a matroid, one deduces the following key lemma.

\begin{lem}\label{submult}Let $M = (E, \mathcal B)$ be a matroid, $\mathscr F: \emptyset = F_0 \subsetneq F_1 \subsetneq \cdots \subsetneq F_k \subsetneq F_{k+1} = E$ a chain of flats in $\mathscr L_M$.  Write $x_{\mathscr F}$ for $x_{F_1}x_{F_2} \cdots x_{F_k}$.  Then for any $1\leq i \leq k$, we have
$$ x_{\mathscr F}\cdot x_{F_i} = x_{\mathscr F}\cdot (-1)\left( \sum_{F\in (F_i, F_{i+1})}\frac{|F_{i+1}\setminus F|}{|F_{i+1} \setminus F_i|}x_F + \sum_{F\in (F_{i-1}, F_i)} \frac{|F\setminus F_{i-1}|}{|F_i \setminus F_{i-1}|}x_F \right)$$
\end{lem}

The second step involves using this to expand $x_{F_1}^{d_1} \cdots x_{F_k}^{d_k}$ into square-free monomials.  In doing so, one comes across the following quantity.

\begin{defn}
For $M$ a loopless matroid on a ground set $E$ of rank $d+1$ and $-1\leq i \leq d+1$, define $\gamma(M,i)$ as follows.  For $i=-1, d+1$, define $\gamma(M,-1) = -1$ and $\gamma(M, d+1) = 0$; for $0\leq i \leq d$, define
$$ \gamma(M, i) := \sum_{\mathscr G \in \mathscr L_M^{\leq i}} (-1) \left(-\frac{|G_1\setminus G_0|}{|G_1|} \right)\left(-\frac{|G_2\setminus G_1|}{|G_2|} \right)\cdots \left(-\frac{|G_{i+1}\setminus G_i|}{|G_{i+1}|} \right)$$
where $\mathscr L_M^{\leq i}$ consists of chains of flats $\mathscr G: \emptyset = G_0 \subsetneq G_1 \subsetneq \cdots \subsetneq G_i\subsetneq G_{i+1} = E$ such that $\operatorname{rk} G_j= j$ for $j=0,\ldots, i$.
\end{defn}

Lastly, one relates these quantities $\gamma(M,i)$ to the characteristic polynomial via Weisner's theorem \cite[\S3.9]{Sta12} and the cover-partition axiom for flats of a matroid.

\begin{prop} \label{gamma} $\overline \chi_M(t) = \sum_{i=0}^d \gamma(M,i)t^{d-i}$ for a loopless matroid $M$ of rank $r=d+1$. \end{prop}

\section{First applications of the volume polynomial}

We give some first applications of the volume polynomial of a matroid.  In this section, we always set the ground set of a matroid to be $[n] := \{1, \ldots, n\}$ for some $n$.

\subsection*{Volumes of generalized permutohedra}

A \textbf{generalized permutohedron} $P$ is obtained by sliding the facets of the permutohedron.  More precisely, for a submodular function $z_{(\cdot)}: 2^{[n]} \to \RR$ (where $[n]\supset I \mapsto z_I$) on the boolean lattice $\mathscr L_{U_{n,n}}$, we define
$$P(\underline z) := \{ (\underline x) \in \RR^n \ | \ \sum_{i\in [n]} x_i = z_{[n]}, \ \sum_{i\in I} x_i \leq z_I \ \forall I\subset [n]\}$$
which is a polytope of dimension at most $n-1$ in $\RR^n$.  It is characterized by the property that every edge is parallel to $e_i - e_j$ for some $i\neq j \in [n]$.

The Bergman fan $\Sigma_{A_{n-1}}$ of $U_{n,n}$ is the normal fan of the permutohedron, whose rays correspond to subsets of $[n]$.  As nef torus invariant divisors on the toric variety $X_{\Sigma_{A_{n-1}}}$ exactly correspond to submodular functions with $z_\emptyset = z_{[n]} = 0$, combining \cref{volpol} and well-known results from toric geometry on volumes of torus invariant divisors (\cite[\S13.4.3]{CLS11}) gives us:

\begin{prop}\label{volGP}
Let $z_{(\cdot )}: I \mapsto z_I\in \RR$ be a submodular function such that $z_\emptyset = z_{[n]} =0$, then the volume of the generalized permutohedron $P(\underline z)$ is
$$(n-1)! \operatorname{Vol} P(\underline z) = \sum_{I_\bullet, \underline d} (-1)^{d-k} {d \choose d_1, \ldots, d_k}\prod_{i=1}^k {d_i -1 \choose \widetilde d_i - |I_i|} {|I_{i+1}| - |I_i| - 1 \choose \widetilde d_i - |I_i|}z_{I_i}$$
where the summation is over chains $\emptyset \subsetneq I_1 \subsetneq \cdots \subsetneq I_k\subsetneq I_{k+1} = [n]$ and $\underline d = (d_1, \ldots, d_k)$ such that $\sum d_i = n-1$ and $\widetilde d_j:= \sum_{i=1}^j d_i$.
\end{prop}

Postnikov computed the volumes of generalized permutohedra that can be expressed as Minkowski sums of standard simplices (\cite[Corollary 9.4]{Pos09}).  Note that our formula above imposes no such restriction.  It was not clear to the author how one recovers \cref{volGP} from \cite[Corollary 9.4]{Pos09} or vice versa.

\subsection*{Valuativeness of the volume polynomial}  While the volume polynomial $VP_M$ has the same information as the Chow ring $A(M)$, it lends itself more naturally as a valuation on a matroid when viewed as a map $M\mapsto VP_M \in \RR[t_S : S\in 2^{[n]}]$.   In this subsection, we illustrate this by showing that $M \mapsto VP_M$ is a valuation under matroid polytope subdivisions, which is a statement that does not make sense for $M \mapsto A(M)$.


\medskip
We first give a brief sketch of matroid polytopes and matroid valuations; for more on matroid valuations, we point to \cite{AFR10}.  Given a matroid $M$ on $[n]$ of rank $r$ with bases $\mathcal B$, its \textbf{matroid polytope} is defined as 
$$\Delta(M) := \operatorname{Conv}(e_B  = \sum_{i\in B} e_i\ | \ B\in \mathcal B)\subset \RR^n$$
where $e_S := \sum_{i\in S} e_i$ for $S\subset [n]$ and $e_i$'s are the standard basis of $\RR^n$.  Its vertices are the indicator vectors for the bases of $M$, and it follows from a theorem of Gelfand, Goresky, MacPherson, and Serganova that the faces of $\Delta(M)$ are also matroid polytopes (\cite{GGMS87}).   A \textbf{matroid subdivision} $\mathcal S$ of a matroid polytope $\Delta$ is a polyhedral subdivision $\mathcal S: \Delta = \bigsqcup_i \Delta(M_i)$ such that each $\Delta(M_i)$ is a matroid polytope of some matroid $M_i$ (necessarily of rank $r$ on with ground set $[n]$). Denote by $\operatorname{Int}(\mathcal S)$ the faces of $\Delta(M_i)$'s that is not contained in the boundary of $\Delta(M)$.  It is often of interest to see whether a valuation on matroids behave well via inclusion-exclusion with respect to matroid subdivisions:

\begin{defn}
Let $R$ be an abelian group, and let $\mathcal M := \bigcup_{n\geq 0} \{\textnormal{matroids on ground set $[n]$}\}$ be the set of all matroids.  A map $\varphi: \mathcal M \to R$ is a \textbf{matroid valuation} (or is \textbf{valuative}) if for any $M\in \mathcal M$ and a matroid subdivision $\mathcal S: \Delta(M) = \bigsqcup_i \Delta(M_i)$ one has
$$\varphi(M) = \sum_{Q \in \operatorname{Int}(\mathcal S)} (-1)^{\dim \Delta(M) - \dim Q}\varphi(M_i).$$
\end{defn}

Many interesting functions on matroids are matroid valuations, for example the Tutte polynomial (\cite[Corollary 5.7]{AFR10}).  The formula in \cref{volpol}, combined with Hopf algebra structure for matroids (see \cite{AA17}), allows one to prove that volume polynomial of a matroid is also a matroid valuation.

\begin{prop}\label{val}
$M\mapsto VP_M(t) \in \RR[t_S : S\in 2^{[n]}]$ is a matroid valuation.
\end{prop}

That the matroid volume polynomial behaves well with respect to matroid polytope subdivisions suggests that there may be a generalization of Chow ring of matroids to Coxeter matroids of arbitrary Lie type (where matroids are the type $A$ case).  For Coxeter matroids see \cite{BGW03}.


\section{The shifted rank-volume of a matroid}

Let $M = (E,\mathcal B)$ be a matroid.  Following \cite{AHK18}, a (strictly) submodular function $c_{(\cdot)}: 2^E \to \RR$ gives a \emph{combinatorially nef (ample)} divisor $D = \sum_{F\in \overline{\mathscr L_M}} c_Fx_F \in A^1(M)_\RR$.  For realizable matroids, if the divisor $D\in A^1(M)_\RR$ is combinatorially nef (ample) then as an element of $A^1(Y_M)_\RR$ the divisor $D$ is nef (ample) in the classical sense.  As the rank function is a distinguished submodular function of a matroid\footnote{Technically one should impose $c_\emptyset = c_E = 0$ for the submodular function $c$, which the rank function does not satisfy (as most often $\operatorname{rk}(E) > 0$).  This turns out not to be an issue here, but is the reason for the modifier ``shifted" in the following definition.}, we define the following notions.

\begin{defn}\label{voldefn}
For a matroid $M$, define its \textbf{shifted rank-divisor} to be \linebreak $D_M := \sum_{F\in \overline{\mathscr L_M}} (\operatorname{rk} F) x_F,$ and define the \textbf{shifted rank-volume of a matroid} $M$ to be the volume of its shifted rank-divisor:
$$\operatorname{shRVol}(M) := \deg\Big(\sum_{F\in \overline{\mathscr L_M}} (\operatorname{rk} F)x_F\Big)^{\operatorname{rk} M-1}.$$
\end{defn}

A slight modification of the proof of \cref{val} implies that the shifted rank-volume of a matroid is a valuative invariant.

\begin{cor}
The map $M\mapsto \operatorname{shRVol}(M)$ is a matroid valuation.
\end{cor}

We do not know of a purely combinatorial meaning of the shifted rank-volume of a matroid.  In fact, it seems to be a genuinely new invariant of a matroid.

\begin{rem}[Relation to other invariants, or lack thereof] \label{volrel}  We point to \verb+Eur_DivMatVol.m2+ that can be found at \url{https://math.berkeley.edu/~ceur/research.html} for computations supporting the statements below.

\begin{itemize}
\item Same Tutte polynomial does not imply same $\operatorname{shRVol}$, and vice versa.  The two graphs in Figure 2 of \cite{CLP15} have the same Tutte polynomial but their matroids are not isomorphic; their shifted rank-volumes are 1533457 and 1534702.  There are many examples of matroids with same $\operatorname{shRVol}$ but with different Tutte polynomials.
\item Same volume of the matroid polytope does not imply same $\operatorname{shRVol}$, and vice versa.
\end{itemize}

\end{rem}

The following theorem shows that the shifted rank-volume seems to measure how close the matroid is to the uniform matroids.

\begin{thm}\label{realmax}
Let $M$ be a realizable matroid of rank $r$ on $n$ elements.  Then 
$$\operatorname{shRVol}(M) \leq \operatorname{shRVol}(U_{r,n}) = n^{r-1} \quad \textnormal{with equality iff $M = U_{r,n}$}.$$
\end{thm}

\begin{proof}  As $Y_M$ is constructed as consecutive blow-ups of $\PP^{r-1}$, let $\pi: Y_M \to \PP^{r-1}$ be the blow-down map and let $\widetilde H = \pi^*(c_1(\mathscr O_{\PP^{r-1}}(1)))$ be the pullback of the hyperplane class.  Then the key observation is
$$D_M = n\widetilde H - \sum_{\operatorname{rk} F > 2} (|F| -\operatorname{rk}_M F)x_F.$$
Noting that $|F| -\operatorname{rk}_M F \geq 0$, we have that $D_M = D - E$ where $D = n\widetilde H$ is a nef divisor and $E = \sum_{\operatorname{rk} F > 2} (|F| -\operatorname{rk}_M F)x_F$ is an effective divisor.  Then the proof of the inequality then reduces to an almost trivial statement in algebraic geometry that $H^0(m(D-E)) \subset H^0(mD)$ for all $m\geq0$ (or equivalently that $\Delta(D-E)\subset \Delta(D)$).

For the remainder of the statement, note that $\bigoplus_{m\geq 0}H^0(m(n\widetilde H - E))$ is a graded linear series on $\PP^{r-1}$ of degree $n$ hypersurfaces vanishing at certain loci dictated by $E$, where $E = 0$ exactly when $M = U_{r,n}$.  Thus, one concludes that $\operatorname{shRVol}(U_{r,n}) =$ (degree of Veronese embedding by $\mathscr O_{\PP^{r-1}}(n)) = n^{r-1}$ and that among realizable matroids the maximum $n^{r-1}$ is achieved \emph{uniquely by $U_{r,n}$}.
\end{proof}

\medskip
There is no analogue of counting sections $H^0(D)$ of a divisor $D$ in the purely combinatorial setting of matroids or more generally in tropical geometry.  As a result, the proof of the inequality in \cref{realmax} for arbitrary matroids given in a subsequent work \cite{BES19} is not a combinatorial reflection of the algebro-geometric proof for realizable matroids given above, and the validity of the statement that the maximum is achieved uniquely by the uniform matroid remains unclear.  This thus further begs the question of whether there is a notion of Newton-Okounkov bodies for matroids, a.k.a.\ tropical linear varieties.





\acknowledgements{The author would like to thank Bernd Sturmfels for suggesting this problem, Justin Chen for many helpful discussions and his Macaulay2 matroids package \cite{Che19}, Alex Fink for generously providing the sketch of the proof for valuativeness of the volume polynomial, and Federico Ardila for inspiring the author to pursue this direction of research.  The author is also grateful for helpful conversations with David Eisenbud, June Huh, Vic Reiner, Botong Wang, and Mengyuan Zhang.}

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way

\sloppy
\printbibliography
\fussy


\end{document}
