# K-classes for matroids and equivariant localization

Alex Fink¹ and David Speyer²†

¹North Carolina State University, NC, USA

²University of Michigan, MI, USA

**Abstract.** To every matroid, we associate a class in the K-theory of the Grassmannian. We study this class using the method of equivariant localization. In particular, we provide a geometric interpretation of the Tutte polynomial. We also extend results of the second author concerning the behavior of such classes under direct sum, series and parallel connection and two-sum; these results were previously only established for realizable matroids, and their earlier proofs were more difficult.

**Résumé.** À chaque matroïde, nous associons une classe dans la K-théorie de la grassmannienne. Nous étudions cette classe en utilisant la méthode de localisation équivariante. En particulier, nous fournissons une interprétation géométrique du polynôme de Tutte. Nous étendons également les résultats du second auteur concernant le comportement de ces classes pour la somme directe, les connexions série et parallèle et la 2-somme; ces résultats n'ont été déjà établis que pour les matroïdes réalisables, et leurs preuves précédentes étaient plus difficiles.

**Keywords:** matroid, Tutte polynomial, K-theory, equivariant localization, Grassmannian

## 1 Introduction

Let $H_1, H_2, \dots, H_n$ be a collection of hyperplanes through the origin in $\mathbb{C}^d$. The study of such hyperplane arrangements is a major field of research, resting on the border between algebraic geometry and combinatorics. There are two natural objects associated to a hyperplane arrangement.

The first is the **matroid** of the hyperplane arrangement, which can be thought of as encoding the combinatorial structure of the arrangement.

The second, which captures the geometric structure of the arrangement, is a point in the Grassmannian $G(d, n)$. There is ambiguity in the choice of this point; it is only determined up to the action of an $n$-dimensional torus on $G(d, n)$. So more precisely, to any hyperplane arrangement, we associate an orbit in $G(d, n)$ for this torus action. It is technically more convenient to work with the closure of this orbit. In [19], the second author suggested that the K-class of this orbit could give rise to useful invariants of matroids, thus exploiting the geometric structure to study the combinatorial one. In this paper, we continue that project.

<footnote>†Supported by a Research Fellowship from the Clay Mathematics Institute.</footnote>

<footnote>○ The full version of this paper is arXiv:1004.2403.</footnote>
One of our main results, Theorem 1.1, is a formula for the Tutte polynomial, the most famous of matroid invariants, in terms of the K-class of Y. The other, Theorem 1.2, relates it to the invariants of [19]. In addition, we rewrite all of the K-theoretic definitions in terms of moment graphs, as [19] also began to do. This makes our theory purely combinatorial and in principle completely computable. Many results which were shown for realizable matroids in [19] are now extended to all matroids.

We review the definitions of these invariants now; the necessary K-theoretic definitions will be given in the following section. Let M be a rank d matroid on the ground set [n], and let $\rho_M$ be the rank function of M. The rank generating function of M is

$$r_M(u, v) := \sum_{S \subset [n]} u^{d - \rho_M(S)} v^{|S| - \rho_M(S)}.$$

The Tutte polynomial is defined by $t_M(z, w) = r_M(z - 1, w - 1)$. See [3] for background on the Tutte polynomial, including several alternate definitions. Let $h_M(s)$ be the invariant defined in [19], which we introduce after Lemma 3.3.

Given integers $0 < d_1 < \dots < d_s < n$, let $\mathcal{F}\ell(d_1, \dots, d_s; n)$ be the partial flag manifold of flags of dimensions $(d_1, \dots, d_s)$. For instance, $\mathcal{F}\ell(d; n) = G(d, n)$.

We will be concerned with the maps

$$\pi_d : \mathcal{F}\ell(1, d, n-1; n) \to G(d, n), \quad \pi_{1(n-1)} : \mathcal{F}\ell(1, d, n-1; n) \to G(1, n) \times G(n-1, n) \quad (1)$$

given respectively by forgetting the 1 and $(n-1)$-planes, and as the product of maps forgetting the 1 and $d$-planes and the $d$ and $(n-1)$-planes. Note that $\pi_{1(n-1)}$ factors through the hypersurface $\mathcal{F}\ell(1, n-1; n)$ in $G(1, n) \times G(n-1, n) \cong \mathbb{P}^{n-1} \times \mathbb{P}^{n-1}$.

Let $T$ be the torus $(\mathbb{C}^*)^n$, which acts on the spaces in (1) in an obvious way. Let $x$ be a point of $G(d, n)$, $M$ the corresponding matroid, and $\overline{Tx}$ the closure of the $T$ orbit through $x$. Let $Y$ be the class of the structure sheaf of $\overline{Tx}$ in $K^0(G(d, n))$. Write $K^0(\mathbb{P}^{n-1} \times \mathbb{P}^{n-1}) = \mathbb{Q}[\alpha, \beta]/(\alpha^n, \beta^n)$, where $\alpha$ and $\beta$ are the structure sheaves of hyperplanes.

**Theorem 1.1** With the above notations,

$$(\pi_{1(n-1)})_* \pi_d^*(Y \cdot [\mathcal{O}(1)]) = t_M(\alpha, \beta)$$

where $t_M$ is the Tutte polynomial.

The constant term of $t_M$ is zero; this corresponds to the fact that $\pi_{1(n-1)}$ is not surjective onto $\mathbb{P}^{n-1} \times \mathbb{P}^{n-1}$ but, rather, has image lying in $\mathcal{F}\ell(1, n-1; n)$. The linear term of Tutte is $(\alpha + \beta)$ times the beta invariant of $M$, corresponding to the fact that the map $\pi_d^{-1}(\overline{Tx}) \to \mathcal{F}\ell(1, n-1; n)$ is finite of degree the beta invariant.

**Theorem 1.2** Also with the above notations,

$$(\pi_{1(n-1)})_* \pi_d^*(Y) = h_M(\alpha + \beta - \alpha\beta)$$

where $h_M$ is the polynomial from [19].

## 1.1 Notation

We write $[n]$ for $\{1, 2, \dots, n\}$. For any set $S$, we write $\binom{S}{k}$ for the set of k-element subsets of $S$.
## 1.2 Acknowledgments

We are grateful to David Ben-Zvi, Megumi Harada, Allen Knutson and Sam Payne for providing us with references about and insights into equivariant K-theory. This paper's full version was finished while the authors visited the American Institute of Mathematics and we are grateful to that institution for the many helpful conversations they fostered.

# 2 Background on K-theory

In this section, we will introduce the requisite background on K-theory, emphasizing equivariant methods and localization. Our treatment here adopts a geometric focus.

We reassure combinatorial readers<sup>(i)</sup> that the computations can be carried out in a purely combinatorial setting, via *moment graphs*. We recommend [9] as a reference for the use of moment graphs in equivariant cohomology, which is extremely similar to the K-theory setup. In short, it is possible to read Theorem 2.6 as constructing the ring $K_T^0(X)$ as certain functions on graphs $\Gamma$ whose vertices (the T-fixed points) are elements of a free abelian group $\mathrm{Char}(T)$, and whose edges (the one dimensional orbits) are labelled with the minimal lattice vectors in the respective directions (associated characters); no further geometry is necessary. The operations in K-theory rings that conclude Section 2.3 can also be carried out using these graphs.

## 2.1 Groundwork

If $V$ is a finite dimensional representation of $T$, the Hilbert series of $V$ is the sum

$$ \mathrm{hilb}(V) := \sum_{\chi \in \mathrm{Char}(T)} \dim \mathrm{Hom}(\chi, V) \cdot \chi $$

in $\mathbb{Z}[\mathrm{Char}(T)]$. If $V$ isn't finite dimensional, but $\mathrm{Hom}(\chi, V)$ is for every character $\chi$, then we can still consider this as a formal sum.

Here is one example of particular interest: let $W$ be a finite dimensional representation of $T$ with character $\sum \chi_i$. Suppose that all of the $\chi_i$ lie in an open half space in $\mathrm{Char}(T) \otimes \mathbb{R}$; if this condition holds, we say that $W$ is *contracting*. Then the Hilbert series of $\mathrm{Sym}(W)$, defined as a formal power series, represents the rational function $1/(1-\chi_1)\cdots(1-\chi_r)$. If $M$ is a finitely generated $\mathrm{Sym}(W)$ module, then the Hilbert series of $M$ will likewise represent an element of $\mathrm{Frac}(\mathbb{Z}[\mathrm{Char}(T)])$ [16, Theorem 8.20].

Sign conventions are potentially confusing. Here are ours: if a group $G$ acts on a ring $A$, we let $G$ act on $\mathrm{Spec} A$ by $g(a) = (g^{-1})^*a$. This definition is necessary in order to make sure that both actions are *left* actions. In examples where $T$ acts on various partial flag varieties, our convention is that $T$ acts on $\mathbb{A}^n$ by the characters $t_1^{-1}, \dots, t_n^{-1}$. Grassmannians, and other partial flag varieties, are flags of *subspaces*, not quotient spaces, and $T$ acts on them by acting on the subobjects of $\mathbb{A}^n$. The advantage of this convention is that, for any ample line bundle $L$ on $\mathcal{F}\ell(n)$, the action on $\int^T L$ will be by nonnegative powers of the $t_i$, i.e. the equivariant K-class of $\int^T L$ will be a polynomial.

## 2.2 Definition of $K^0$ and $K_T^0$

If $X$ is any algebraic variety, then $K_0(X)$ denotes the free abelian group generated by isomorphism classes of coherent sheaves on $X$, subject to the relation $[A] + [C] = [B]$ whenever there is a short exact

<footnote>(i) Section 2.4 of the full paper is dedicated to this audience, in case our small reassurance here is insufficient.</footnote>
sequence $0 \to A \to B \to C \to 0$. The subspace generated by the classes of vector bundles is denoted $K^0(X)$. If $X$ is smooth, as all the spaces we deal with will be, the inclusion $K^0(X) \hookrightarrow K_0(X)$ is an equality. (See [18, Proposition 2.1] for this fact, and its equivariant generalization.)

We put a ring structure on $K^0(X)$, generated by the relations $[E][F] = [E \otimes F]$ for any vector bundles $E$ and $F$ on $X$. The group $K_0(X)$ is a module for $K^0(X)$, with multiplication given by $[E][F] = [E \otimes F]$ where $E$ is a vector bundle and $F$ a coherent sheaf.

For any map $f : X \to Y$, there is a pull back map $f^* : K^0(Y) \to K^0(X)$ given by $f^*[E] = [f^*E]$. This is a ring homomorphism. If $f : X \to Y$ is a proper map, there is also a pushforward map $f_* : K_0(X) \to K_0(Y)$ given by

$$f_*[E] = \sum (-1)^i [R^i f_*E].$$

These two maps are related by the projection formula, which asserts that

$$f_*((f^*[E])[F]) = [E]f_*[F]. \qquad (2)$$

That is, $f_*$ is a $K^0(Y)$-module homomorphism, if $K^0(X)$ has the module structure induced by $f^*$.

We always have a map from $X$ to a point. We denote the pushforward along this map by $\int$, or by $\int_X$, by analogy with de Rham cohomology. Notice that $K_0(pt) = K^0(pt) = \mathbb{Z}$, and $\int[E]$ is the holomorphic Euler characteristic of the sheaf $E$.

If $T$ is a torus acting on $X$, then we can form the analogous constructions using $T$-equivariant vector bundles and sheaves. These are denoted $K_T^0(X)$ and $K_T^0(X)$. Writing $\mathrm{Char}(T)$ for the lattice of characters, $\mathrm{Hom}(T, \mathbb{C}^*)$, we have $K_T^0(pt) = K_T^0(pt) = \mathbb{Z}[\mathrm{Char}(T)]$. Explicitly, a $T$-equivariant sheaf on $pt$ is simply a vector space with a $T$-action, and the corresponding element of $\mathbb{Z}[\mathrm{Char}(T)]$ is the character. We write $[E]^T$ for the class of the sheaf $E$ in $K_T^0(X)$.

## 2.3 Localization

The results in this section are well known to experts, but it seems difficult to find a reference that records them all in one place. The reader may want to compare the description of equivariant cohomology in [13].

Here we will be only concerned with $K_0^T(X)$ for extremely nice spaces $X$ — in fact, only partial flag manifolds and products thereof. All of these spaces are **equivariantly formal** spaces, meaning that their $K$-theory can be described using the method of **equivariant localization**, which we now explain. We will gradually add niceness hypotheses on $X$ as we need them.

**Condition 2.1** Let $X$ be a smooth projective variety with an action of a torus $T$.

Writing $X^T$ for the subvariety of $T$-fixed points, we have a restriction map

$$K_T^0(X) \to K_T^0(X^T) \cong K^0(X^T) \otimes K_T^0(pt).$$

**Theorem 2.2 ([18, Theorem 3.2], see also [12, Theorem A.4] and [21, Corollary 5.11])** In the presence of Condition 2.1, the restriction map $K_T^0(X) \to K_T^0(X^T)$ is an injection.

If we have Condition 2.1 and

**Condition 2.3** $X$ has finitely many $T$-fixed points,
then $K_T^0(X^T)$ is simply the ring of functions from $X^T$ to $K_T^0(\text{pt})$.

Let $x$ be a fixed point of the torus action on $X$, so we have a restriction map $K_T^0(X) \to K_T^0(x) \cong K_T^0(\text{pt})$. It is important to understand how this map is explicitly computed. For $\xi \in K_T^0(X)$, we write $\xi(x)$ for the image of $\xi$ in $K_T^0(x)$.

In all of our examples, there will exist a $T$-equivariant neighborhood $U$ of $x$ isomorphic to a contracting $T$-representation on $\mathbb{A}^n$. Let $\chi_1, \dots, \chi_N$ be the characters by which $T$ acts on $U$. Let $E$ be a $T$-equivariant coherent sheaf on $U$, corresponding to a graded, finitely generated $\mathcal{O}(U)$-module $M$. Then the Hilbert series of $M$ lies in $\text{Frac}(\mathbb{Z}[\text{Char}(T)])$; it is a rational function of the form $k(E)/\prod(1 - \chi_i^{-1})$ for some polynomial $k(E)$ in $\mathbb{Z}[\text{Char}(T)]$.

**Theorem 2.4** If $U$ is an open neighborhood of $x$ as above then $K_T^0(U) \cong K_T^0(\text{pt})$. With the above notations, $[E]^T(x) = k(E)$.

In particular, if $E$ is a vector bundle on $U$, and $T$ acts on the fiber over $x$ with character $\sum \eta_i$, then $[E]^T(x) = \sum \eta_i$.

We have now described, given a $T$-equivariant sheaf $E$ in $K_T^0(X)$, how to express it as a function from $X^T$ to $K_T^0(\text{pt})$. It will also be worthwhile to know, given a function from $X^T$ to $K_T^0(\text{pt})$, when it is in $K_T^0(X)$. For this, we need

**Condition 2.5** There are finitely many 1-dimensional $T$-orbits in $X$, each of which has closure isomorphic to $\mathbb{P}^1$ (and thus contains two $T$-fixed points).

**Theorem 2.6 ([21, Corollary 5.12], see also [12, Corollary A.5])** Assume conditions 2.1, 2.3 and 2.5. Let $f$ be a function from $X^T$ to $K_T^0(\text{pt})$. Then $f$ is of the form $\xi(\cdot)$ for some $\xi \in K_T^0(X)$ if and only if the following condition holds: For every one dimensional orbit, on which $T$ acts by character $\chi$ and for which $x$ and $y$ are the $T$-fixed points in the closure of the orbit, we have

$$f(x) \equiv f(y) \mod 1 - \chi.$$

**Example 2.7** Let's see what this theorem means for the Grassmannian $G(d, n)$. Here $K_T^0(\text{pt})$ is the ring of Laurent polynomials $\mathbb{Z}[t_1^{\pm}, t_2^{\pm}, \dots, t_n^{\pm}]$. The fixed points $G(d, n)^T$ are the linear spaces of the form $\text{Span}(e_i)_{i \in I}$ for $I \in \binom{[n]}{d}$. We will write this point as $x_I$ for $I \in \binom{[n]}{d}$. So an element of $K_T^0(G(d, n))$ is a function $f: \binom{[n]}{d} \to K_T^0(\text{pt})$ obeying certain conditions. What are those conditions? Each one-dimensional torus orbit joins $x_I$ to $x_J$ where $I = S \sqcup \{i\}$ and $J = S \sqcup \{j\}$ for some $S$ in $\binom{[n]}{d-1}$. Thus an element of $K_T^0(G(d, n))$ is a function $f: \binom{[n]}{d} \to K_T^0(\text{pt})$ such that

$$f(S \sqcup \{i\}) \equiv f(S \sqcup \{j\}) \mod 1 - t_i/t_j$$

for all $S \in \binom{[n]}{d-1}$ and $i, j \in [n] \setminus S$.

We now describe how to compute tensor products, pushforwards and pullbacks in the localization description. The first two are simple: tensor product corresponds to multiplication in the ring of functions, and pullback to pullback of functions. The formula for pushforward is somewhat more complex, and is more conveniently stated in terms of multi-graded Hilbert series. If $\text{hilb}(E_x)$ is the multi-graded Hilbert series of the stalk $E_x$, then

$$\text{hilb}(\pi_*(E)_y) = \sum_{x \in X^T, \pi(x)=y} \text{hilb}(E_x) \quad (3)$$
This yields a formula for $(\pi_*[E]^T)(y)$ by Theorem 2.4. The special case of this formula for pushforward to a point,

$$ \int_X^T [E]^T = \sum_{x \in X^T} \mathrm{hilb}(E_x), \qquad (4) $$

is more prominent in the literature than the general result; see for example [18, Section 4].

Finally, we describe the relation between ordinary and $T$-equivariant $K$-theories. There is a map from equivariant $K$-theory to ordinary $K$-theory by forgetting the $T$-action. In particular, the map $K_T^0(\mathrm{pt}) \to K^0(\mathrm{pt}) = \mathbb{Z}$ just sends every character of $T$ to 1. In this way, $\mathbb{Z}$ becomes a $K_T^0(\mathrm{pt})$-module. Thus, for any space $X$ with a $T$-action, we get a map $K_T^0(X) \otimes_{K_T^0(\mathrm{pt})} \mathbb{Z} \to K^0(X)$. All we will need is that this map exists, but in fact given Condition 2.1 it is an isomorphism [15, Theorem 4.3].

## 3 Matroids and Grassmannians

Let $\mathbb{E}$ be a finite set (the ground set), which we will usually take to be $[n]$. For $I \subseteq \mathbb{E}$, we write $e_I$ for the vector $\sum_{i \in I} e_i$ in $\mathbb{Z}^\mathbb{E}$. Let $M$ be a collection of $d$-element subsets of $\mathbb{E}$. Let $\mathrm{Poly}(M)$ be the convex hull of the vectors $e_I$, as $I$ runs through $M$. The collection $M$ is called a matroid if it obeys any of a number of equivalent conditions (see [17] for these, and [5] for motivation). Our favorite is due to Edmonds:

**Theorem 3.1 ([7]; see also [8, Theorem 4.1])** $M$ is a matroid if and only if $M$ is nonempty and every edge of $\mathrm{Poly}(M)$ is in the direction $e_i - e_j$ for some $i$ and $j \in \mathbb{E}$.

We now explain the connection between matroids and Grassmannians. We assume basic familiarity with Grassmannians (see [16, Chapter 14] for background). Given a point $x$ in $G(d, n)$, the set of $I$ for which the Plücker coordinate $p_I(x)$ is nonzero forms a matroid, which we denote $\mathrm{Mat}(x)$. (A matroid of this form is called realizable.) Let $T$ be the torus $(\mathbb{C}^*)^n$, which acts on $G(d, n)$ in the obvious way, so that $p_I(tx) = t^{e_I}p_I(x)$ for $t \in T$. Clearly, $\mathrm{Mat}(tx) = \mathrm{Mat}(x)$ for any $t \in T$.

We now discuss how we will bring $K$-theory into the picture. Consider the torus orbit closure $\overline{Tx}$. The orbit $Tx$ is a translate (by $x$) of the image of the monomial map given by the set of characters $\{t^{-e_I} : p_I(x) \neq 0\}$. Essentially by definition, $\overline{Tx}$ is the toric variety associated to the polytope $\mathrm{Poly}(\mathrm{Mat}(x))$ (see [4, Section 5], and [22] regarding normality). In the appendix to [19], the second author checked that the class of the structure sheaf of $\overline{Tx}$ in $K_T^0(G(d, n))$ depends only on $\mathrm{Mat}(x)$, and gave the following natural way to define a class $y(M)$ in $K_T^0(G(d, n))$ for any matroid $M$ of rank $d$ on $[n]$, nonrealizable matroids included.

For a polyhedron $P$ and a point $v \in P$, define $\mathrm{Cone}_v(P)$ to be the positive real span of all vectors of the form $u - v$, with $u \in P$; if $v$ is not in $P$, define $\mathrm{Cone}_v(P) = \emptyset$. Let $M \subseteq \begin{bmatrix} [n] \\ d \end{bmatrix}$ be a matroid. We will abbreviate $\mathrm{Cone}_{e_I}(\mathrm{Poly}(M))$ by $\mathrm{Cone}_I(M)$. For a pointed rational polyhedron $C$ in $\mathbb{R}^n$, define $\mathrm{hilb}(C)$ to be the Hilbert series

$$ \mathrm{hilb}(C) := \sum_{a \in C \cap \mathbb{Z}^n} t^a. $$

This is a rational function with denominator dividing $\prod_{i \in I} \prod_{j \notin I} (1 - t_i^{-1} t_j)$ [20, Theorem 4.6.11]. We define the class $y(M)$ in $K_T^0(G(d, n))$ by

$$ y(M)(x_I) := \mathrm{hilb}(\mathrm{Cone}_I(M)) \prod_{i \in I} \prod_{j \notin I} (1 - t_i^{-1} t_j), $$
Note that hilb(Cone$_I(M)) = 0$ for $I \notin M$.

To motivate this definition, suppose $M$ is of the form $\mathrm{Mat}(x)$ for some $x \in G(d, n)$. For $I$ in $M$, the toric variety $\overline{Tx}$ is isomorphic near $x_I$ to $\mathrm{Spec} \mathbb{C}[\mathrm{Cone}_I(M) \cap \mathbb{Z}^n]$. In particular, the Hilbert series of the structure sheaf of $\overline{Tx}$ near $x_I$ is hilb(Cone$_I(M))$. So in this situation $y(M)$ is exactly the $T$-equivariant class of the structure sheaf of $\overline{Tx}$.

**Proposition 3.2** *Whether or not $M$ is realizable, the function $y(M)$ from $G(d, n)^T$ to $K_T^0(\mathrm{pt})$ defines a class in $K_T^0(G(d, n))$.*

This follows from the following, more general, polyhedral result.

**Lemma 3.3** Let $P$ be a lattice polytope in $\mathbb{R}^n$ and let $u$ and $v$ be vertices of $P$ connected by an edge of $P$. Let $e$ be the minimal lattice vector along the edge pointing from $u$ to $v$, with $v = u + ke$. Then hilb(Cone$_e(P)) + hilb(Cone_v(P))$ is a rational function whose denominator is not divisible by $1 - t^e$.

Having defined $y(M)$, we can give the definition of $h_M(s)$ from [19]. Let $i$ be an index between 1 and $d$. Choose a line $\ell$ in $n$-space and an $n-i$ plane $M$ containing $\ell$. Let $\Omega_i \subset G(d, n)$ be the Schubert cell of those $d$-planes $L$ such that $\ell \subset L$ and $L+M$ is contained in a hyperplane. If $i > d$, we define $\Omega_i$ to be $\Omega_d$. $h_M(s)$ is defined by

$$ \frac{h_M(s)}{1-s} = \sum_{i=1}^{\infty} \int_{G(d,n)} y(M)[\mathcal{O}_{\Omega_i}]s^i.$$

**Example 3.4** We work through these definitions for the case of a matroid in $G(2, 4)$, namely $M = \{13, 14, 23, 24, 34\}$. This $M$ is realizable, arising as $\mathrm{Mat}(x)$ when for instance $x$ is the rowspan of $\begin{pmatrix} 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 \end{pmatrix}$, with Plücker coordinates $(p_{12}, p_{13}, p_{14}, p_{23}, p_{24}, p_{34}) = (0, 1, 1, 1, 1, -1)$.

Computing $y(M)$ entails finding the Hilbert functions hilb(Cone$_I(M))$ for each $I \in M$. We leave the reader to find these and confirm that $y(M)$ is sent under the localization map of Theorem 2.2 to

$$ (0, 1 - t_2 t_3^{-1}, 1 - t_2 t_4^{-1}, 1 - t_1 t_3^{-1}, 1 - t_1 t_4^{-1}, 1 - t_1 t_2 t_3^{-1} t_4^{-1}), $$

ordering the coordinates lexicographically. We see that this satisfies the congruences in Theorem 2.6.

## 3.1 Valuations

A subdivision of a polyhedron $P$ is a polyhedral complex $\mathcal{D}$ with $|\mathcal{D}| = P$. We use the names $P_1, \dots, P_k$ for the facets of a typical subdivision $\mathcal{D}$ of $P$, and for $J \subseteq [k]$ nonempty we write $P_J = \bigcap_{j \in J} P_j$, which is a face of $\mathcal{D}$. We also put $P_\emptyset = P$. Let $\mathcal{P}$ be a set of polyhedra (for us, the set of matroid polytopes), and $A$ an abelian group. We say that a function $f: \mathcal{P} \to A$ is a **valuation** (or is **valuative**) if, for any subdivision such that $P_J \in \mathcal{P}$ for all $J \subseteq [k]$, we have

$$ \sum_{J \subseteq [k]} (-1)^{|J|} f(P_J) = 0. $$

For example, one valuation of fundamental importance to the theory is the function $1(\cdot)$ mapping each polytope $P$ to its characteristic function. Namely, $1(P)$ is the function $V \to \mathbb{Z}$ which takes the value 1 on $P$ and 0 on $V \setminus P$. Also, many important functions of matroids, including the Tutte polynomial, are valuations.
We discuss how valuations arise from K-theory. Let D be a subdivision of matroid polytopes, with facets $P_1, \dots, P_k$, and let $P_J = \text{Poly}(M_J)$. From the definition of $y(M)$ it is not hard to show

**Proposition 3.5** *The function $y$ is a valuation of matroids.*

That is, we have a linear relation of K-theory classes

$$ \sum_{J \subseteq [k]} (-1)^{|J|} y(M_J) = 0. \qquad (5) $$

As a corollary, any function built using K-theory, for example the functions in our main theorems, is a valuation.

Theorem 1.5a of [6] asserts that the group of valuative matroid invariants is free of rank $\binom{n}{d}$. The group $K^0(G(d, n))$ is also free of rank $\binom{n}{d}$. This gives rise to the hope that every valuative matroid invariant might factor through $M \mapsto y(M)$, i.e. that every matroid valuation might come from K-theory. This hope is quite false, however. The reason is that no torus orbit closure can have dimension greater than that of $T$, namely $n-1$. Therefore, $\int y(M)[E]$ vanishes whenever $E$ is supported in codimension $n$ or greater. This imposes nontrivial linear constraints on $y(M)$, so the classes $y(M)$ span a proper subspace of $K^0(G(d, n))$. The reader may check that for $(d, n) = (2, 4)$, an explicit valuative invariant not extending to a linear function on $K^0(G(d, n))$ is $z$ given by $z(M)$ is 1 if $\text{Poly}(M)$ contains $(1/2, 1/2, 1/2, 1/2)$ and 0 otherwise.

# 4 A fundamental lemma

Recall from section 1 the maps $\pi_d : \mathcal{F}\ell(1, d, n-1; n) \to G(d, n)$ and $\pi_{1(n-1)} : \mathcal{F}\ell(1, d, n-1; n) \to \mathbb{P}^{n-1} \times \mathbb{P}^{n-1}$, and the notations $\alpha$ and $\beta$ for the hyperplane classes in $K^0(\mathbb{P}^{n-1} \times \mathbb{P}^{n-1})$. Over $G(d, n)$, we have the tautological exact sequence

$$ 0 \to S \to \mathbb{C}^n \to Q \to 0. \qquad (6) $$

Over each point of $G(d, n)$, the fiber of $S$ is the corresponding $d$-dimensional vector space.

The following lemma is central to the proofs of Theorems 1.1 and 1.2.

**Lemma 4.1** Given $[E] \in K^0(G(d, n))$, define a formal polynomial in $u$ and $v$ by

$$ R(u, v) := \int_{G(d,n)} [E] \sum [\wedge^p S] [\wedge^q (Q^\vee)] u^p v^q. \qquad (7) $$

Then

$$ (\pi_{1(n-1)})_* \pi_d^*[E] = R(\alpha - 1, \beta - 1). $$

We do not have an equivariant generalization of Lemma 4.1, relating classes in $K_T^0(G(d, n))$ to those in $K_T^0(\mathbb{P}^{n-1} \times \mathbb{P}^{n-1})$. However, Lemma 4.1 provides an alternate way to obtain equivariant versions of our main theorems.

By Lemma 4.1, the content of Theorem 1.1 is that

$$ \int y(M) \cdot [\mathcal{O}(1)] \cdot \sum_{p=0}^{d} \sum_{q=0}^{n-d} [\wedge^p S] [\wedge^q (Q^\vee)] u^p v^q = r_M(u, v). $$

In fact, something stronger is true.
**Theorem 4.2** In equivariant K-theory, we have

$$ \int \sum_{p=0}^{d} \sum_{q=0}^{n-d} y(M) [\mathcal{O}(1)]^T [\wedge^p S]^T [\wedge^q (Q^\vee)]^T u^p v^q = \sum_{S \subseteq [n]} t^{e_S} u^{d-\rho_M(S)} v^{|S|-\rho_M(S)}. \quad (8) $$

That is, the integral (8) is a generating function in $K_T^0(\mathrm{pt})[u, v]$ recording the subsets of $[n]$ which $r_M(u, v)$ enumerates.

**Question 4.3** Is there an equivariant version of Lemma 4.1 which provides a generating function in $K_T^0(\mathrm{pt})[u, v]$ for the bases of given activity, parallel to Theorem 4.2 for the rank generating function?

We do not obtain any enriched equivariant version of $h$ via Lemma 4.1.

**Lemma 4.4** In the setup of Theorem 1.2, $\int y(M)[\wedge^p S]^T [\wedge^q (Q^\vee)]^T \in \mathbb{Z}$ for any $p$ and $q$, and equals 0 when $p \neq q$.

**Example 4.5** We outline the computation of $t_M$ and $h_M$ for the matroid $M$ of Example 3.4. At a fixed point $x_I$, equivariant localisation of the summation in (7) yields

$$ s'_{I} := \sum_{P \subseteq I} \sum_{Q \subseteq J} t^{-e_{P}+e_{Q}} u^{|P|} v^{|Q|} = \prod_{i \in I} (1 + u t_i^{-1}) \prod_{j \in J} (1 + v t_j) $$

and the same sum multiplied by $\mathcal{O}(1)$ gives

$$ s_I := \sum_{P \subseteq I} \sum_{Q \subseteq J} t^{e_P + e_Q} u^{d - |P|} v^{|Q|} = \prod_{i \in I} (u + t_i) \prod_{j \in J} (1 + v t_j), $$

where $J = [n] \setminus I$. Define also

$$ h_I := \prod_{i \in I} \prod_{j \in J} (1 - t_i^{-1} t_j)^{-1}. $$

The reader or their computer algebra system may check that the $R(u, v)$ of Lemma 4.1 in the two cases is

$$ \sum_{I} s_I h_I y(M)(x_I) = 5 + 4u + 4v + u^2 + uv + v^2 $$

$$ \sum_{I} s'_{I} h_{I} y(M)(x_{I}) = 1 - uv $$

yielding $t_M(z, w) = w + z + w^2 + wz + z^2$ and $h_M(t) = t$.

# 5 Flipping cones

Let $f$ be a rational function in $\mathbb{Q}(z_1, z_2, \dots, z_n)$. It is possible that many different Laurent power series represent $f$ on different domains of convergence. This section discusses some implications of this phenomenon. By Lemma 4.1 and equivariant localization, the computations in our main results are reduced to manipulating sums of Hilbert series of certain infinite-dimensional $T$-representations. This section's results are of importance for gaining control over their coefficients.
The results can be thought of as generalizations of the relationships between the lattice point enumeration formulas of Brianchon-Gram, Brion and Lawrence-Varchenko [2]. We recommend [1] as a general introduction to generating functions for lattice points in cones.

Let $\mathcal{P}_n$ be the sub-vector space of real-valued functions on $\mathbb{Z}^n$ spanned by characteristic functions of lattice polytopes. If $P$ is a pointed polytope, then the sum $\sum_{e \in P} z^e$ converges somewhere, and the value it converges to is a rational function in $\mathbb{Q}(z_1, \dots, z_n)$ which we denote $\mathfrak{hilb}(P)$. It is a theorem of Lawrence [14], and later Khovanski-Pukhlikov [11], that $1(P) \mapsto \mathfrak{hilb}(P)$ extends to a linear map $\mathfrak{hilb}: \mathcal{P}_n \to \mathbb{Q}(z_1, \dots, z_n)$.

**Lemma 5.1** The vector space $\mathcal{P}_n$ is spanned by the classes of simplicial cones.

Let $\zeta := (\zeta_1, \zeta_2, \dots, \zeta_n)$ be a basis for $\mathbb{R}^n$, which is given the standard inner product. Define an order $<_{\zeta}$ on $\mathbb{Q}^n$ by $x <_{\zeta} y$ if, for some index $i$, we have $\langle \zeta_1, x \rangle = \langle \zeta_1, y \rangle$, $\langle \zeta_2, x \rangle = \langle \zeta_2, y \rangle$, ..., $\langle \zeta_{i-1}, x \rangle = \langle \zeta_{i-1}, y \rangle$ and $\langle \zeta_i, x \rangle < \langle \zeta_i, y \rangle$. (In fact we lose no strength in our applications if we reduce to the case of a single vector $\zeta$, but the freedom to use a tuple of vectors with integer entries is convenient.)

We'll say that a polytope $P$ is $\zeta$-pointed if, for every $a \in \mathbb{R}^n$, the intersection $P \cap \{e : e <_{\zeta} a\}$ is bounded. We'll say that an element in $\mathcal{P}_n$ is $\zeta$-pointed if it is supported on a finite union of $\zeta$-pointed polytopes. Let $\mathcal{P}_n^\zeta$ be the vector space of $\zeta$-pointed elements in $\mathcal{P}_n$.

**Lemma 5.2** The restriction of $\mathfrak{hilb}$ to $\mathcal{P}_n^\zeta$ is injective.

**Corollary 5.3** Suppose that we have functions $f_1, f_2, \dots, f_r, g_1, g_2, \dots, g_s$ in $\mathcal{P}_n^\zeta$ and scalars $a_1, \dots, a_r, b_1, \dots, b_s$ such that $\sum a_i \mathfrak{hilb}(f_i) = \sum b_j \mathfrak{hilb}(g_j)$. Let $e$ be any lattice point in $\mathbb{Z}^n$. Then $\sum a_i f_i(e) = \sum b_j g_j(e)$.

The next lemma, in the case of a single $\zeta$, is the main result of [10].

**Lemma 5.4** Let $\zeta = (\zeta_1, \dots, \zeta_n)$ be as above. For every $f \in \mathcal{P}_n$, there is a unique $f^\zeta \in \mathcal{P}_n^\zeta$ such that $\mathfrak{hilb}(f) = \mathfrak{hilb}(f^\zeta)$. The map $f \mapsto f^\zeta$ is linear.

For example $\sum_{i \ge 0} z^i$ and $-\sum_{i < 0} z^i$ both converge to $1/(1-z)$, on different domains, and correspond to $\{x : x \ge 0\}$ and $\{x : x < 0\}$. In general, if $C$ is a simplicial cone, $1(C)^\zeta$ can be computed by "flipping" defining inequalities in this sense, and possibly negating.

**Lemma 5.5** Let $C$ be a pointed cone with vertex at $w$. Then $1(C)^\zeta$ is contained in the half space $\{x : \langle \zeta_1, x \rangle \ge \langle \zeta_1, w \rangle\}$. Furthermore, if $C$ is not contained in $\{x : \langle \zeta_1, x \rangle \ge \langle \zeta_1, w \rangle\}$, then $1(C)^\zeta$ is in the open half space $\{x : \langle \zeta_1, x \rangle > \langle \zeta_1, w \rangle\}$.

**Corollary 5.6** Let $C_i$ be a finite sequence of pointed cones in $\mathbb{R}^n$, with the vertex of $C_i$ at $w_i$. Let $a_i$ be a finite sequence of scalars. Suppose that we know $\sum a_i \mathfrak{hilb}(C_i)$ is a Laurent polynomial. Then its Newton polytope is contained in the convex hull of the $w_i$.

# 6 Geometric interpretations of matroid operations

Our techniques give combinatorial proofs a number of facts about the behavior of $h_M$ under standard matroid operations, originally proved geometrically in [19]. Before stating them, we introduce slightly more general polynomials for which they hold. Following section 4, we define

$$F_M^{m,T}(u, v) := \int y(M)[\mathcal{O}(m)]^T \sum_{p,q} [\wedge^p S]^T [\wedge^q (Q^\vee)]^T u^p v^q.$$
Its nonequivariant counterpart $F_M^m(u, v)$ is the unique polynomial, of degree $\le n$ in $u$ and $v$, such that

$$F_M^m(\mathcal{O}(1,0), \mathcal{O}(0,1)) = (\pi_{1(n-1)})_* \pi_d^*([\mathcal{O}(m)]y(M)). \qquad (9)$$

We have seen that $F_M^{0,T}(u, v) = h_M(1 - uv)$, that $F_M^{1,T}(u, v)$ and $F_M^1(u, v)$ are the weighted and un-weighted rank generating functions, and that $F_M^1(u - 1, v - 1)$ is the Tutte polynomial. The entire collection of $F_M^{m,T}$ can be seen as a generalization of the Ehrhart polynomial of $\text{Poly}(M)$. Specifically, $F_M^m(0, 0) = \#(m \cdot \text{Poly}(M) \cap \mathbb{Z}^n)$ for $m \ge 0$.

We denote the matroid dual to $M$ by $M^*$. Given matroids $M_1$ and $M_2$ on respective ground sets $E_1$ and $E_2$, we denote their direct sum by $M_1 \oplus M_2$. For $i_k \in E_k$, there are three further standard matroid operations that join $M_1$ and $M_2$ together after identifying $i_1 = i_2$: they are the series connection $M_{\text{ser}}$, the parallel connection $M_{\text{par}}$, and the two-sum $M_{2\text{sum}}$.

**Theorem 6.1** We have

$$(a) \quad F_M^m(u, v) = F_{M^*}^m(v, u) \in \mathbb{Z}[u, v]$$

$$(b) \quad F_{M_1}^m F_{M_2}^m = F_{M_1 \oplus M_2}^m$$

$$(c) \quad F_{M_1 \oplus M_2}^m = (1 + v)F_{M_{\text{ser}}}^m + (1 + u)F_{M_{\text{par}}}^m - (1 + v)(1 + u)F_{M_{2\text{sum}}}^m$$

$$\text{In particular, } F_{M_{2\text{sum}}}^0 = F_{M_{\text{ser}}}^0 = F_{M_{\text{par}}}^0 = F_{M_1 \oplus M_2}^0 / (1 - uv).$$

The series, respectively parallel, extension of a matroid $M_1$ along $i_1$ is its series, respectively parallel, connection to the uniform matroid $U_{1,2}$. Two-sum with $U_{1,2}$ leaves $M_1$ unchanged. Since $h_{U_{1,2}} = 1 - uv$, Proposition 6.1(b,c) implies one of the most characteristic combinatorial properties of $h$ from [19].

**Corollary 6.2** The values of $h_M$ and $F_M^0$ are unchanged by series and parallel extensions.

## References

[1] Alexander Barvinok, *Integer Points in Polyhedra*, European Mathematical Society (2008).

[2] Matthias Beck, Christian Hasse and Frank Sottile, *Formulas of Brion, Lawrence, and Varchenko on rational generating functions for cones*, Math. Intelligencer **31** (2009), no. 1, 9–17.

[3] Thomas Brylawski and James Oxley, *The Tutte polynomial and its applications*, in *Matroid Applications*, Encyclopedia of Mathematics and its Applications **40**, ed. Neil White, Cambridge University Press (1992).

[4] David Cox, *Recent developments in toric geometry*, in *Algebraic geometry – Santa Cruz 1995*, 389–436, Proc. Sympos. Pure Math. **62**, part 2, Amer. Math. Soc. (1997).

[5] Henry Crapo, *Examples and Basic Concepts*, in *Theory of Matroids*, Encyclopedia of Mathematics and its Applications **26**, ed. Neil White, Cambridge University Press (1986).

[6] Harm Derksen and Alex Fink, *Valuative invariants for polymatroids*, Adv. in Math., in press, doi:10.1016/j.aim.2010.04.016.

[7] Jack Edmonds, *Submodular functions, matroids, and certain polyhedra*, in *Combinatorial Structures and Their Applications*, eds. Richard Guy, Haim Hanani, Norbert Sauer, Johanen Schonheim, Gordon and Breach, New York (1970), 69–87.
[8] Israel Gelfand, Mark Goresky, Robert MacPherson and Vera Serganova, *Combinatorial geometries, convex polyhedra, and Schubert cells*, Adv. in Math. **63** (1987), no. 3, 301–316.

[9] Victor Guillemin and Catalin Zara, *Equivariant de Rham Theory and Graphs*, Asian J. Math. **3** (1999), no. 1, 49–76.

[10] Christian Hasse, *Polar decomposition and Brion's theorem*, in *Integer Points in Polyhedra — Geometry, Number Theory, Algebra, Combinatorics*, Contemporary Mathematics **274** (2005), 91–99.

[11] Askold Khovanskii and Aleksandr Pukhlikov, *Integral transforms based on Euler characteristic and their applications*, Integral Transform. Spec. Funct. **1** (1993), no. 1, 19–26.

[12] Allen Knutson and Ioanid Rosu, Appendix to *Equivariant K-theory and Equivariant Cohomology*, Math. Z. **243** (1999), no. 3, 423–448.

[13] Allen Knutson and Terrence Tao, *Puzzles and (equivariant) cohomology of Grassmannians*, Duke Math. J. **119** (2003), no. 2, 221–260.

[14] Jim Lawrence, *Rational-function-valued valuations on polyhedra*, in *Discrete and computational geometry (New Brunswick, NJ, 1989/1990)*, 199–208, DIMACS Ser. Discrete Math. Theoret. Comput. Sci. **6**, Amer. Math. Soc. (1991).

[15] Alexander Merkur'ev, *Comparison of the equivariant and the standard K-theory of algebraic varieties*, Algebra i Analiz **9** (1997), no. 4, 175–214. Translation in St. Petersburg Math. J. **9** (1998), no. 4, 815–850.

[16] Ezra Miller and Bernd Sturmfels, *Combinatorial Commutative Algebra*, Graduate Texts in Mathematics **227**, Springer (2005).

[17] Giorgio Nicoletti and Neil White, *Axiom Systems*, in *Theory of Matroids*, Encyclopedia of Mathematics and its Applications **26**, ed. Neil White, Cambridge University Press (1986).

[18] Holger Andreas Nielsen, *Diagonalizably linearized coherent sheaves*, Bull. de la S. M. F. **102** (1974), 85–97.

[19] David Speyer, *A matroid invariant via the K-theory of the Grassmannian*, Adv. in Math. **221** (2009), no. 3, 882–913.

[20] Richard Stanley, *Enumerative Combinatorics: Volume I*, Cambridge University Press (1997).

[21] Gabriele Vezzosi and Angelo Vistoli, *Higher algebraic K-theory for actions of diagonalizable groups*, Invent. Math. **153** (2003), no. 1, 1–44.

[22] Neil White, *The basis monomial ring of a matroid*, Adv. in Math. **24** (1977), no. 3, 292–297.