A Regular Unimodular Triangulation of the Matroid Base Polytope

Let $M=(E,\mathcal{B})$ be a matroid with ground set $E=[n]$, and $P_{M}\subset\mathbb{R}^{n}$ its matroid base polytope. We will use $\operatorname{vert}(P_{M})$ to denote the vertices of $P_{M}$. We show $P_{M}$ has a unimodular triangulation by induction on $n$. If $n=1$, then $P_{M}$ is a point and we are done.

Assume $n\geq 2$. Let $P_{0}$ and $P_{1}$ be the polytopes in $\mathbb{R}^{n-1}$ such that $P_{0}\times\{0\}=P_{M}\cap\{x_{1}=0\}$ and $P_{1}\times\{1\}=P_{M}\cap\{x_{1}=1\}$. Note that $P_{0}$ or $P_{1}$ may be empty, which occurs if 1 is a loop or coloop. If $P_{0}$ is nonempty then it is the matroid base polytope of $M\setminus 1$, and if $P_{1}$ is nonempty then it is the matroid base polytope of $M/1$.

By the inductive hypothesis, $P_{0}$ and $P_{1}$ have regular unimodular triangulations. (We assume an empty polytope has a regular unimodular triangulation induced by a function with empty domain.) Let $f_{0}:\operatorname{vert}(P_{0})\to\mathbb{R}$ and $f_{1}:\operatorname{vert}(P_{1})\to\mathbb{R}$ be functions which induce these triangulations. Let $\ell_{0},\ell_{1}:\mathbb{R}^{n-1}\to\mathbb{R}$ be affine functionals such that $\ell_{0}-\ell_{1}$ is generic. Let $\epsilon>0$ be sufficiently small, and define $f:\operatorname{vert}(P_{M})\to\mathbb{R}$ to be the function

We claim that $f$ induces a unimodular triangulation of $P_{M}$¹¹1That the subdivision induced by $f$ is independent of $\epsilon$ for $\epsilon$ sufficiently small is guaranteed by the existence of the secondary fan of $P_{M}$.. We will need the following lemmas.

We say that two linear subspaces $V$, $W$ of $\mathbb{R}^{n}$ are independent if $V\cap W=\emptyset$. We say that two rational linear subspaces $V$, $W$ of $\mathbb{R}^{n}$ are complementary if $(V\cap\mathbb{Z}^{n})+(W\cap\mathbb{Z}^{n})=(V+W)\cap\mathbb{Z}^{n}$. Equivalently, $V$ and $W$ are complementary if there exist $A\subset(V\cap\mathbb{Z}^{n})$ and $B\subset(W\cap\mathbb{Z}^{n})$ such that $A\cup B$ generates $(V+W)\cap\mathbb{Z}^{n}$ over the integers.

We warn the reader that $P$ and $Q$ in the following lemma will not correspond to $P_{0}$ and $P_{1}$.

We now return to the main proof. If either $P_{0}$ or $P_{1}$ is empty, then $f$ induces a unimodular triangulation on $P_{M}$ by the definition of $f_{0}$ and $f_{1}$. Thus, assume $P_{0}$ and $P_{1}$ are not empty. Let $g:\operatorname{vert}(P)\to\mathbb{R}$ be the function

Let $\mathcal{S}$ be the subdivision of $P_{M}$ induced by $g$. Since $g$ is affine on $P_{0}$ and $P_{1}$, it must be that $P_{0},P_{1}\in\mathcal{S}$. Hence every cell of $\mathcal{S}$ is of the form $\operatorname{conv}(F_{0}\times\{0\}\cup F_{1}\times\{1\})$, where $F_{0}$ and $F_{1}$ are faces of $P_{0}$ and $P_{1}$, respectively.

We claim that because $\ell_{0}-\ell_{1}$ is generic, $\operatorname{lin}(F_{0})$ and $\operatorname{lin}(F_{1})$ are independent. Note that the function $g$ and the function

differ by an affine function on $\mathbb{R}^{n}$, and therefore they induce the same subdivision on $P$. Moreover, $0-(\ell_{1}-\ell_{0})=\ell_{0}-\ell_{1}$. Therefore, by replacing $g$ with $g^{\prime}$, we may assume $\ell_{0}=0$.

Let $A_{0}=\operatorname{aff}(F_{0})$ and $A_{1}=\operatorname{aff}(F_{1})$ and suppose that $\operatorname{lin}(A_{0})$ and $\operatorname{lin}(A_{1})$ are not independent. Then $L=\operatorname{lin}(A_{0})\cap\operatorname{lin}(A_{1})$ is a positive dimensional linear space, and by Lemma 2.6 it is a flat in the resonance arrangement. Furthermore, $x_{0}+L\subset A_{0}$ and $x_{1}+L\subset A_{1}$ for some $x_{0}$, $x_{1}\in\mathbb{Z}^{n-1}$. Now, let $\tilde{g}:\mathbb{R}^{n}\to\mathbb{R}$ be an affine function which agrees with $g$ on $\operatorname{conv}(F_{0}\times\{0\}\cup F_{1}\times\{1\})$. (This exists by the assumption that $\operatorname{conv}(F_{0}\times\{0\}\cup F_{1}\times\{1\})$ is a cell in the subdivision induced by $g$.) Since $\ell_{0}=0$, we have that $\tilde{g}$ is 0 on $A_{0}\times\{0\}$, and hence it is 0 on $(x_{0}+L)\times\{0\}\subset A_{0}\times\{0\}$. Since $\tilde{g}$ is affine, it is therefore constant on $(x_{1}+L)\times\{1\}$. Since $(x_{1}+L)\times\{1\}\subset A_{1}\times\{1\}$, it follows that $\ell_{1}$ is constant on $x_{1}+L$, and hence it is constant on $L$. This contradicts the assumption that $\ell_{0}-\ell_{1}$ is non-constant on positive dimensional flats of the resonance arrangement. Thus $\operatorname{lin}(F_{0})$ and $\operatorname{lin}(F_{1})$ are independent. Each face of a matroid base polytope is a matroid base polytope, hence by Lemma 3.3, $\operatorname{lin}(F_{0})$ and $\operatorname{lin}(F_{1})$ are complementary.

Now, let $\mathcal{T}$ be the subdivision of $P_{M}$ induced by $f$. Because $f$ is a perturbation of $g$, it follows that $\mathcal{T}$ refines $\mathcal{S}$. Furthermore, since $f$ restricted to $P_{0}\times\{0\}$ is an affine function plus $\epsilon f_{1}(x_{2},\dots,x_{n})$, the restriction of $\mathcal{T}$ to $P_{0}\times\{0\}$ is a unimodular triangulation. Similarly the restriction of $\mathcal{T}$ to $P_{1}\times\{1\}$ is a unimodualar triangulation. Let $T$ be a cell of $\mathcal{T}$, and let $S=\operatorname{conv}(F_{0}\times\{0\}\cup F_{1}\times\{1\})$ be a cell of $\mathcal{S}$ containing $T$. We have $T=\operatorname{conv}(T_{0}\times\{0\}\cup T_{1}\times\{1\})$, where $T_{i}$ is a unimodular simplex contained in $F_{i}$. Because $\operatorname{lin}(F_{0})$ and $\operatorname{lin}(F_{1})$ are independent, $\operatorname{lin}(T_{0})$ and $\operatorname{lin}(T_{1})$ are independent, hence $T$ is a simplex. Moreover, since $\operatorname{lin}(F_{0})$ and $\operatorname{lin}(F_{1})$ are complementary and independent, it follows by Lemma 3.2 that $\operatorname{lin}(T_{0})$ and $\operatorname{lin}(T_{1})$ are complementary. Thus we can form a basis $B$ of $(\operatorname{lin}(T_{0})+\operatorname{lin}(T_{1}))\cap\mathbb{Z}^{n-1}$ from maximal collections of linearly independent edge vectors of $T_{0}$ and $T_{1}$. Each edge vector of $T$ from a vertex in $T_{0}$ to a vertex in $T_{1}$ has first coordinate 1. We claim that we can add any such edge vector $v$ to $B$ to give a basis $B^{\prime}$ of $\operatorname{lin}(T)\cap\mathbb{Z}^{n}$. Given $x\in\operatorname{lin}(T)\cap\mathbb{Z}^{n}$ we explain that $x$ is in the integral span of $B^{\prime}$. We can subtract an integer multiple of $v$ from $x$ so that the first coordinate is zero. The resulting vector must be in $\operatorname{lin}(T_{0})+\operatorname{lin}(T_{1})$ and is integral, hence it is in the integral span of $B$. We conclude that $T$ is a unimodular simplex and $\mathcal{T}$ is a unimodular triangulation. ∎

This is obtained by unwinding the induction in the proof of Theorem 3.1. ∎

Let $P\in\mathbb{R}^{n}$ be an integral generalized permutahedron. By translating $P$ if necessary, we may assume without loss of generality that there is some positive integer $R$ such that $P\subset\{x:0\leq x_{k}\leq R\text{ for all }1\leq k\leq n\}$. It is known that dicing $P$ by the hyperplanes $\{x_{k}=c\}$ where $c$ and $k$ are integers with $1\leq k\leq n$ and $0\leq c\leq R$ gives a regular integral subdivision $\mathcal{X}$ of $P$, and every cell of the subdivision is a translation of a matroid base polytope³³3 This can be verified by appealing to the submodularity description of generalized permutahedra, Lemma 2.5, and Theorem 2.3.. Let $g:P\cap\mathbb{Z}^{n}\to\mathbb{R}$ be a function which induces $\mathcal{X}$.

For each $s\in\bigsqcup_{k=1}^{n-1}\{0,\dots,R\}^{k}$, choose an affine functional $\ell_{s}:\mathbb{R}^{n-|s|}\to\mathbb{R}$ so that $\ell_{s^{\prime}i}-\ell_{s^{\prime}(i+1)}$ is generic for all strings $s^{\prime}$ and integers $i$. For $1\gg\epsilon_{1}\gg\epsilon_{2}\gg\dots\gg\epsilon_{n-1}>0$, define the function $f:P\cap\mathbb{Z}^{n}\to\mathbb{R}$ by

Then $f$ induces a subdivision of $P$ which refines $\mathcal{X}$. Moreover, by Theorem 3.5, the restriction of $f$ to each cell of $\mathcal{X}$ induces a unimodular triangulation. ∎

Each matroid independence polytope $P_{\mathcal{I}}$ is unimodularily equivalent to an integral generalized permutahedron: given a point $v=(v_{1},\ldots v_{n})\in P_{\mathcal{I}}$, let $\psi(v)=(v_{0},v_{1},\dots v_{n})\in\mathbb{R}^{n+1}$, where $v_{0}=r(E)-\sum_{i=1}^{n}v_{i}$. The map $\psi$ is unimodular and its image is an integral generalized permutahedron⁴⁴4 It is implicit in [AD13] that the independence polytope is unimodularily equivalent to a generalized permutahedron.. We can apply our triangulation to $\psi(P_{\mathcal{I}})$ and then map this triangulation back to $P_{\mathcal{I}}$ to obtain a regular unimodular triangulation of the latter. ∎