%% 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[finalversion]{FPSAC2024}
\articlenumber{92}
%% 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}

%\newtheorem{thm}{Theorem}
%\newtheorem{lem}{Lemma}

\newtheorem{thrm}{Theorem}[section]
\newtheorem{lem}[thrm]{Lemma}
\newtheorem{prop}[thrm]{Proposition}
\newtheorem{cor}[thrm]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[thrm]{Definition}
\newtheorem{remark}[thrm]{Remark}
\newtheorem{example}[thrm]{Example}
\numberwithin{equation}{section}

\newcommand{\M}{{M}}
\newcommand{\B}{\mathrm{B}}
\newcommand{\U}{{U}}
\newcommand{\Gr}{\mathrm{Gr}}
\newcommand{\BC}{\mathrm{BC}}
\newcommand{\csm}{\mathrm{csm}}

\newcommand{\bb}{\mathbb}
\newcommand{\mc}{\mathcal}

\DeclareMathOperator{\vspan}{span}
\DeclareMathOperator{\aff}{aff}
\DeclareMathOperator{\conv}{conv}
\DeclareMathOperator{\lin}{lin}
\DeclareMathOperator{\verti}{verti}


\usepackage{lipsum}
\usepackage{amsfonts,amssymb,amsmath,amsthm,mathtools,comment} % usual
\usepackage{url} % url
\usepackage{enumitem} % optional argument for enumerate
\urlstyle{sf}
\usepackage{stmaryrd,color}
\usepackage{multicol}

%% define your title in the usual way

\title{A Regular Unimodular Triangulation of the Matroid Base Polytope}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Spencer Backman\thanks{\href{mailto:sbackman@uvm.edu}{sbackman@uvm.edu}}\addressmark{1} %Spencer Backman was supported by a Simons Collaboration Gift \# 854037 and an NSF Grant (DMS-2246967)}
\and Gaku Liu\thanks{\href{mailto:gakuliu@uw.edu}{gakuliu@uw.edu}}\addressmark{2} }

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics and Statistics, University of Vermont, Burlington, Vermont, USA \\ \addressmark{2}Department of Mathematics, University of Washington, Seattle, Washington, USA}

%% put the date of submission here
\received{November 15, 2023}

%% 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{We produce the first regular unimodular triangulation of an arbitrary matroid base polytope.  We then extend our triangulation to integral generalized permutahedra. Prior to this work it was unknown whether each matroid base polytope admitted a unimodular cover.}

%% 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{matroid, polytope, triangulation}

%% 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; i.e., [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{sample.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}

Despite considerable interest, very little is known about triangulations of matroid base polytopes.  There are a few motivations for wanting to have nice triangulations of matroid base polytopes.  The first motivation comes from White's conjecture whose weakest version states that the toric ideal of a matroid base polytope is quadratically generated \cite{white1977basis}\cite{lason2014toric}.  Herzog and Hibi asked whether the toric ideal of every matroid base polytope has a quadratic Gr\"obner basis \cite{herzog2002discrete}.  It follows by a result of Sturmfels \cite{sturmfels1996grobner} combined with an observation of Ohsugi and Hibi \cite{ohsugi1999toric} that the existence of a quadratic Gr\"obner basis is equivalent to the existence of a quadratic triangulation, i.e. a regular unimodular flag triangulation.  The existence of a quadratic triangulation is known for base sortable matroids, e.g.  positroids \cite{stanley1977eulerian,sturmfels1996grobner,blum2001base, lam2007alcoved, lam2018alcoved}. For transversal matroids, a result of Conca \cite{conca2007linear} establishes that the toric ring is Koszul, which is stronger than quadratic generation of the toric ideal but weaker than a quadratic triangulation.

The second motivation comes from Ehrhart theory.  A formula for the volume of a matroid base polytope was calculated by Ardila--Doker--Benedetti \cite{ardila2010matroid}, but no formula is currently known which is cancellation free, i.e. involves no subtraction.  If a polytope  $P$ admits a unimodular triangulation $\mc T$, then the volume of $P$ is equal to the number of maximal simplices in $\mc T$.  The volume of a polytope occurs as the leading coefficient of the Ehrhart polynomial. Several researchers have investigated Ehrhart polynomials for matroid base polytopes \cite{castillo2018berline}\cite{jochemko2022generalized} \cite{ferroni2022ehrhart} largely motivated by the conjecture of De Loera--Haws--K\"oppe \cite{de2009ehrhart}  that matroid base polytopes are Ehrhart positive---this conjecture was recently disproven by Ferroni \cite{ferroni2022matroids}, but various other questions about these polynomials remain open.  The volume of a polytope $P$ is also given by the evaluation of the $h^*$-polynomial at 1.  Another conjecture by De Loera--Haws--K\"oppe, which remains open, is that the $h^*$-vectors of matroid base polytopes are unimodal \cite{de2009ehrhart}.  Ferroni further conjectures that the $h^*$-polynomial of a matroid polytope (more generally an integral generalized permutahedron) is real-rooted \cite{ferroni2022ehrhart,ferroni2022minimalmatroids}.  It has been conjectured that if a polytope $P$ has the integer decomposition property (is IDP), then $P$ has a unimodal $h^\ast$-vector \cite{schepers2013unimodality}, and it is known that every matroid base polytope is IDP \cite{herzog2002discrete}.   We note that the property of admitting a unimodular triangulation is strictly stronger than the property of being IDP \cite{bruns1999normality}.  We refer the reader to \cite{ferroni2023examples} for a comprehensive survey of results in this area.  It is known that the $h^*$-vector of a polytope is equal to the $h$-vector of any unimodular triangulation of the polytope \cite{stanley1980decompositions}\cite{betke1985lattice}, thus one might hope that such a triangulation could shed some light on this conjecture.

A natural question which sits in between these various results and conjectures is whether each matroid base polytope admits a (not necessarily flag) regular unimodular triangulation.  That the matroid base polytope admits a (not necessarily regular) unimodular triangulation was conjectured by Haws in their 2009 thesis \cite{haws2009matroid}.  In this paper we give an affirmative answer to this question by providing a regular unimodular triangulation of an arbitrary matroid base polytope.  We then apply this result to produce a regular unimodular triangulation of an arbitrary integral generalized permutahedron, and explain how this gives a regular unimodular triangulation of the matroid independence polytope.  We emphasize that prior to this work it was unknown whether every matroid base polytope admitted a unimodular cover (this was also conjectured by Haws \cite{haws2009matroid}) let alone a unimodular triangulation.  Our construction produces many different triangulations, but at the time of writing we do not know if any of them are flag.  We invite other researchers to try their hand at applying our triangulation to the topics above.  See Remark \ref{whiteproblem}.


\section{Preliminaries}
We recommend the following texts for an introduction to matroids \cite{Oxley2011matroid}, polytope theory \cite{ziegler2012lectures}, and triangulations \cite{de2010triangulations}\cite{haase2021existence}.  Let $[n]$ denote the set of integers $\{1,\dots,n\}$.  Given $S \subseteq [n]$ we will employ the notation  $x_S := \sum_{i \in S} x_i$.  We identify $\{0,1\}^n$ with the collection of all subsets of $[n]$.  We denote the standard basis vectors for $\mathbb{R}^n$ by $e_i$ for $1\leq i\leq n$. 

\begin{definition}
    A \emph{matroid} is a pair $M =(E,\mathcal{B})$ where $E$ is a finite set called the \emph{ground set}, and $\mathcal{B}$ is a nonempty collection of subsets of $E$ called the \emph{bases} which satisfy the following basis exchange condition:

    \begin{itemize}
        \item For any $B_1,B_2 \in \mathcal{B}$ and $x \in B_1\setminus B_2$, there exists some $y \in B_2 \setminus B_1$ such that $(B_1 \setminus \{x\}) \cup \{y\} \in \mathcal{B}$.
    \end{itemize}

A set $I\subseteq E$ is \emph{independent} if there exists some basis $B \in \mc B$ such that $I \subseteq B$.  The collection of independent sets is denoted $\mc I$.  The \emph{rank} of a set $S \subseteq E$, written $r(S)$, is the maximum cardinality of an independent set contained in $S$.
\end{definition}

Matroid independence  polytopes and the matroid base polytopes were introduced by Edmonds \cite{edmonds2003submodular}.

\begin{definition}
    Given a matroid $M$ on ground set $E = [n]$, the \emph{matroid base polytope} $P_M$ is the convex hull of the indicator vectors for the bases of $M$, and the \emph{matroid independence polytope} $P_{\mc I}$ is the convex hull of the indicator vectors of the independent sets.  More explicitly, given $S\subseteq E$, we define the indicator vector $\chi_S \in \mathbb{R}^n$ by
\[ \chi_S(i)=
  \begin{cases} 
      1 & i \in S \\
      0 & i \notin S
      \end{cases} \]
Thus $P_M = \conv\{\chi_B: B \in \mc B\}$ and $P_{\mc I}= \conv\{\chi_I: I \in \mc I\}$.

\end{definition}

The matroid base polytope is the distinguished face of the matroid independence polytope where the sum of the coordinates is maximized.  The matroid independence polytope will be discussed at the end of this article (see Corollary \ref{indep}).

Gelfand--Goresky--MacPherson--Serganova uncovered a connection between matroid base polytopes and the geometry of the Grassmannian \cite{gelfand1987combinatorial}.   They showed that torus orbit closure of a linear space $L$  in the Grassmannian is a normal toric variety whose weight polytope is the matroid base polytope $P_{M(L)}$, where $M(L)$ is the matroid determined by $L$.  See Katz \cite{katz2016matroid} for an overview of this story.  By standard toric theory, our regular unimodular triangulation of $P_M$ gives a projective Crepant resolution of the toric variety associated to the cone over a matroid base polytope.

Matroid bases polytopes allow for a polytopal characterization of matroids.

\begin{thrm}\label{gelmat} \cite{edmonds2003submodular}\cite{gelfand1987combinatorial}
A polytope $P$ is a matroid base polytope for some matroid $M$ if and only if $P$ is a 0-1 polytope whose edge directions are of the form $e_i-e_j$.
\end{thrm}

Polymatroids are a generalization of matroids described by monotonic submodular fuctions taking values in the nonnegative reals.  Their base polytopes are equivalent by translation to the generalized permutahedra of Postnikov \cite{postnikov2009permutohedra}.  See \cite{ardila2020coxeter} for a careful treatment of the following definition. 

\begin{definition}\label{genper}
    A \emph{generalized permutahedron} $P \subseteq \mathbb{R}^n$ is a polytope defined by any one of the following equivalent conditions:

    \begin{enumerate}
        \item \label{cond1} The edge directions for $P$ are all of the form $e_i-e_j$,
        \item\label{cond2} The normal fan of $P$ is a coarsening of the braid arrangement,
        \item\label{cond3}$P$ is defined by inequalities $x_S \leq f(S)$ where $f:\{0,1\}^n\rightarrow \mathbb{R}$ is a submodular function, together with a single equation $x_{[n]} =f([n])$.
    \end{enumerate}
\end{definition}

An \emph{integral generalized permutahedron} $P$ is a generalized permutahedron whose vertices have integer coordinates.  The following is well-known, and follows from the unimodularity of the set of primitive ray generators of each chamber in the braid arrangement.

\begin{lem}\label{permint}
Let $P$ be a generalized permutahedron determined by a submodular function $f$ as in condition (\ref{cond3}) of Definition \ref{genper}.  If $f$ is an integer-valued function then $P$ is an integral generalized permutahedron.  Moreover, if $P$ is an integral generalized permutahedron then $f$ may be chosen to be integer-valued.
\end{lem}

In our proof, we will use condition (\ref{cond2}) from Definition \ref{genper} as this allows us to describe the affine span of a face of a matroid base polytope.

\begin{lem}\label{flag}
Let $P$ be an integral generalized permutahedron and $\aff(P)$ its affine span. Then

    \[\aff(P) = \bigcap_{i=1}^j \{ x_{S_i} = b_i \}
\]
for some flag of subsets $\emptyset = S_0 \subsetneq S_1 \subsetneq \dots \subsetneq S_j = [n]$ and some $b_i \in \bb Z$.
\end{lem}
  
We note that when $P$ is a matroid base polytope, the $b_i$ in the lemma above is equal to the rank of the set $S_i$ viewed as a subset of the ground set of the matroid. 

\begin{definition}



    A \emph{subdivision} of a polytope $P$ is a collection of polytopes $\mathcal{S} = \{P_1, \ldots, P_k\}$ such that
    
    \begin{enumerate}
        \item $\bigcup_{i=1}^k P_i =P$ 
        \item for each $P_i \in \mathcal{S}$ and $F$ a face of $P_i$, there exists some $j$ such that $F=P_j$ 
        \item for any $i$ and $j$ with $1\leq i,j \leq k$, the intersection $P_i\cap P_j$ is a face of both $P_i$ and $P_j.$
        
    \end{enumerate}

A maximal polytope in $\mathcal{S}$ is a \emph{cell} of $\mathcal{S}$.
\end{definition}
\begin{definition}
    A \emph{triangulation} of a polytope $P$ is a subdivision $\mathcal{T} = \{T_1, \ldots, T_k\}$ of $P$ such that each polytope $T_i$ is a simplex.
\end{definition}

\begin{definition}
    Let $P \subset \bb R^n$ be a polytope and $S$ a finite subset of $P$ containing the vertices of $P$. Given a function $f : S \to \bb R$, the subdivision \emph{induced} by $f$ is the subdivision of $P$ formed by projecting the lower faces of the polytope
    \[
    \conv\{ (x,f(x)) : x \in S \} \subset \bb R^{n+1}.
    \]    
    A subdivision is \emph{regular} if it is induced by some function $f$.
\end{definition}

Given a set $S \subseteq \bb R^n$, let $\aff(S)$ denote the affine span of $S$. Let $\lin(S)$ denote the linear subspace of $\bb R^n$ with the same dimension and parallel to $\aff(S)$.

%Let $\vec{A}$ denote the unique linear subspace such that $A = x + \vec{A}$ for some $x \in \bb R^n$. Similarly, given an affine sublattice $L \subseteq \bb Z^n$, let $\vec{L}$ denote the unique sublattice of $\bb Z^n$ such that $L = x + \vec{L}$ for some $x \in \bb Z^n$.   Given $S\subset \mathbb{R}^n$ we let $\aff(S)$ denote the affine span of $S$.

\begin{definition}
    A lattice simplex $T$ is \emph{unimodular} if it has normalized volume 1.  Equivalently, if $T$ has vertices $v_0,\ldots, v_n \in \mathbb{Z}^n$, then $T$ is unimodular whenever a maximal linearly independent set of edge vectors $\{v_i-v_j\}$ form a lattice basis for  $\lin(T) \cap \mathbb{Z}^n$.  
\end{definition}



\begin{definition}
    The \emph{resonance arrangement} $\mathcal{A}_n$ is the hyperplane arrangement in $\mathbb{R}^n$ consisting of all hyperplanes $H_S =\{x \in \mathbb{R}^n: x_S = 0\}$ where $\emptyset \subsetneq S\subseteq [n]$.
\end{definition}

For an introduction to the resonance arrangement (also called the \emph{all subsets arrangement}) we refer the reader to \cite{kuhne2023universality}.  A \emph{flat} of a hyperplane arrangement $\mathcal{H}$ is an intersection of hyperplanes in $\mathcal{H}$.

\begin{definition}\label{generic}
    We say that an affine functional $\ell:\mathbb{R}^n\rightarrow \mathbb{R}$ is \emph{generic} if it is non constant on each positive dimensional flat of the resonance arrangement.
   


\end{definition}

We note that a generic point $p$ on the $n$-th moment curve
\[
C_n = \{(t, t^2, \ldots, t^{n}): t \in \mathbb{R}\}
\]
produces a generic linear functional $x \mapsto \langle x,p \rangle$.




\section{A deletion-contraction triangulation}

In this section we establish the main result of this paper. 

\begin{thrm}\label{main}
Every matroid base polytope has a regular unimodular triangulation.
\end{thrm}

Before providing a proof, we briefly give some context for our construction.  Two fundamental operations on a matroid are the deletion and contraction of an element, and many important constructions in matroid theory proceed by an inductive appeal to these operations.  If $e$ is a loop or coloop, then the matroid base polytope $P_M$ is translation equivalent to $P_{M/e}$ and $P_{M\setminus e}$.   If $e$ is neither a loop nor a coloop then $P_M$ is the convex hull of $P_{M/e}$ and $P_{M\setminus e}$.  In this way, our recursive construction fits into the paradigm of deletion-contraction. 

Let $M=(E,\mathcal{B})$ be a matroid with ground set $E=[n]$, and $P_M \subset \bb R^n$ its matroid base polytope. We will use $\verti(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 \ge 2$.  Let $P_0$ and $P_1$ be the polytopes in $\bb 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 : \verti(P_0) \to \bb R$ and $f_1 : \verti(P_1) \to \bb R$ be functions which induce these triangulations. Let $\ell_0, \ell_1 : \bb R^{n-1} \to \bb R$ be affine functionals such that $\ell_0 - \ell_1$ is generic.  Let $\epsilon>0$ be sufficiently small, and define $f : \verti(P_M) \to \bb R$ to be the function
\[
f(x) = \begin{dcases*}
\ell_0(x_2,\dots,x_n) + \epsilon f_0(x_2,\dots,x_n) & if $x_1 = 0$ \\
\ell_1(x_2,\dots,x_n) + \epsilon f_1(x_2,\dots,x_n) & if $x_1 = 1$.
\end{dcases*}
\]
In our full paper \cite{backmanliu2023}, we prove that $f$ induces a unimodular triangulation of $P_M$.

The following theorem is  more explicit version of Theorem~\ref{main}.


\begin{thrm} \label{functiondesc}
Let $P \in \bb R^n$ be a matroid base polytope. For each string $s \in \bigsqcup_{k=1}^{n-1} \{0,1\}^k$, let $\ell_s : \bb R^{n-|s|} \to \bb R$ be an affine functional, where $|s|$ is the length of $s$. Assume that $\ell_{s'0} - \ell_{s'1}$ is generic for all strings $s'$. Then for $1 \gg \epsilon_1 \gg \epsilon_2 \gg \dots \gg \epsilon_{n-1} > 0$, the function $f : \verti(P) \to \bb R$ defined by
\[
f(x) = \sum_{k=1}^{n-1} \epsilon_k \ell_{x_1 \dots x_k}(x_{k+1},\dots,x_n)
\]
induces a regular unimodular triangulation on $P_M$.
\end{thrm}

\begin{proof}
This is obtained by unwinding the induction in the proof of Theorem~\ref{main}. 
\end{proof}


We now explain how to extend our triangulation to all integral generalized permutahedra.

\begin{cor}
Every integral generalized permutahedron has a regular unimodular triangulation.
\end{cor}

\begin{proof}
Let $P \in \bb 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 \le x_k \le R \text{ for all } 1 \le k \le n \}$. It is known that dicing $P$ by the hyperplanes $\{x_k = c\}$ where $c$ and $k$ are integers with $1 \le k \le n$ and $0 \le c \le R$ gives a regular integral subdivision $\mc X$ of $P$, and every cell of the subdivision is a translation of a matroid base polytope\footnote{\,This can be verified by appealing to the submodularity description of generalized permutahedra, Lemma \ref{permint}, and Theorem \ref{gelmat}.}. Let $g : P \cap \bb Z^n \to \bb R$ be a function which induces $\mc X$.


For each $s \in \bigsqcup_{k=1}^{n-1} \{0,\dots,R\}^k$, choose an affine functional $\ell_s : \bb R^{n-|s|} \to \bb R$ so that $\ell_{s'i} - \ell_{s'(i+1)}$ is generic for all strings $s'$ and integers $i$. For $1 \gg \epsilon_1 \gg \epsilon_2 \gg \dots \gg \epsilon_{n-1} > 0$, define the function $f : P \cap \bb Z^n \to \bb R$ by
\[
f(x) = g(x) + \sum_{k=1}^{n-1} \epsilon_k \ell_{x_1 \dots x_k}(x_{k+1},\dots,x_n).
\]

Then $f$ induces a subdivision of $P$ which refines $\mc X$. Moreover, by Theorem~\ref{functiondesc}, the restriction of $f$ to each cell of $\mc X$ induces a unimodular triangulation.
\end{proof}


\begin{cor}\label{indep}
    Every matroid independence polytope has a regular unimodular triangulation.
\end{cor}

\begin{proof}
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\footnote{\,It is implicit in \cite{ardila2013lifted} 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.
\end{proof}


\begin{example}\label{mainexample}
    
We provide an example of our triangulation for the cycle matroid of the complete graph $K_4$. Let $\verti(K_4) = \{v_0,v_1,v_2,v_3\}$.  To simplify notation we denote the edges of $K_4$ by integers:  $$v_0v_1=0,\, v_1v_2=1,\, v_0v_1=2,\, v_1v_3=3,\, v_0v_3=4,\, v_2v_3=5.$$ The bases are in the following order:
\begin{multicols}{3}
\begin{enumerate}\addtocounter{enumi}{-1}
\item \{0 1 3\}
\item \{1 2 3\}
\item \{1 3 4\}
\item \{0 1 4\}
\item \{0 1 5\}
\item \{1 2 5\}
\item \{1 4 5\}
\item \{1 2 4\}
\item \{0 2 4\}
\item \{2 3 4\}
\item \{0 2 3\}
\item \{0 2 5\}
\item \{2 3 5\}
\item \{0 3 5\}
\item \{3 4 5\}
\item \{0 4 5\}
\end{enumerate}
\end{multicols}



We take the height function described in Theorem \ref{functiondesc} as follows:  if $s$ is a string ending is 0, the function $\ell_s$ is 0. If a string ends in 1, and the string has length $k$, the function $\ell_s= (-3^{n-k-1}, -3^{n-k-2},\ldots,1)$. The cells of the associated triangulation are

\begin{multicols}{3}
\noindent \{3 7 8 9 12 14\}\\
\{3 5 7 8 12 14\}\\
\{3 5 6 7 8 14\}\\
\{3 5 8 11 12 14\}\\
\{3 5 6 8 11 14\}\\
\{3 4 6 11 14 15\}\\
\{3 4 5 6 11 14\}\\
\{3 4 5 11 12 14\}\\
\{3 6 8 11 14 15\}\\
\{0 3 8 11 14 15\}\\
\{0 3 4 5 11 12\}\\
\{0 3 4 5 12 14\}\\
\{0 3 4 11 12 14\}\\
\{0 3 4 5 6 14\}\\
\{0 3 4 11 14 15\}\\
\{0 4 11 12 13 14\}\\
\{0 4 11 13 14 15\}\\
\{0 3 5 8 11 12\}\\
\{0 3 8 11 12 14\}\\
\{0 3 5 6 7 14\}\\
\{0 10 11 12 13 14\}\\
\{0 8 10 11 14 15\}\\
\{0 8 10 11 12 14\}\\
\{0 8 9 10 12 14\}\\
\{0 10 11 13 14 15\}\\
\{0 3 5 7 12 14\}\\
\{0 3 5 7 8 12\}\\
\{0 2 3 6 7 14\}\\
\{0 2 3 7 9 14\}\\
\{0 1 7 9 10 12\}\\
\{0 1 5 7 10 12\}\\
\{0 5 8 10 11 12\}\\
\{0 7 8 9 10 12\}\\
\{0 5 7 8 10 12\}\\
\{0 1 2 6 7 14\}\\
\{0 1 2 7 9 14\}\\
\{0 1 7 9 12 14\}\\
\{0 1 5 7 12 14\}\\
\{0 1 5 6 7 14\}\\
\{0 3 7 9 12 14\}\\
\{0 3 8 9 12 14\}\\
\{0 3 7 8 9 12\}.
\end{multicols}


\end{example}

\begin{remark}\label{whiteproblem}
The authors, Matt Larson, and Sam Payne attempted to apply the construction of this article to produce quadratic triangulations of graphic matroid base polytopes, i.e. spanning tree polytopes.  We convinced ourselves that it not possible to do so using only $\ell_s$ above which are exponential.  We welcome others to attempt to apply our triangulation to White's conjecture.
\end{remark}


\acknowledgements{
The authors would like to thank the University of Vermont, the University of Washington, and the Simons Center for Geometry and Physics Workshop ``Combinatorics and Geometry of Convex Polyhedra" for excellent working conditions where part of this work was completed.  The authors thank Mateusz Michalek for noting some typos in an earlier draft of this work, to Luis Ferroni for providing further references, to Matt Larson for providing example \ref{mainexample}, and to Sam Payne for suggesting a simplification of proof of the main theorem.  The first author was supported by a Simons Collaboration Gift \# 854037 and an NSF Grant (DMS-2246967).}
%% 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}
