Lower bounds and integrality gaps in simplicial decomposition

Let $\mathcal{K}$ be a finite pure simplicial $d$-complex, with oriented facets $\{F_i\}$, which is boundaryless in the sense that $\sum \mathrm{\partial }{F}_i=0$. We call such a $\mathcal{K}$ an $\mathit{\text{admissible}}d\mathit{\text{-complex}}$. Given an admissible $d$-complex, one can ask for the smallest collection $\{T_i\}$ of oriented $(d+1)$-simplices on the vertices of $\mathcal{K}$ which decomposes $\mathcal{K}$ in the sense that $\sum \mathrm{\partial }{T}_i=\mathcal{K}$. Let the minimum size of such a collection be $V_{\mathbb{Z}}(\mathcal{K})$, and let $V_{\mathbb{Q}}(\mathcal{K})$ be the relaxed analog where fractional $(d+1)$-simplices may be used. We explain how these quantities may be computed via integer and linear programming, and show how lower bounds may be obtained by exploiting LP-duality. We then prove that $V_{\mathbb{Q}}$ and $V_{\mathbb{Z}}$ are both additive under disjoint union and connected sum along a $d$-simplex. The remainder of the paper explores integrality gaps between $V_{\mathbb{Z}}$ and $V_{\mathbb{Q}}$ in dimension 1, where we share what we believe is the simplest admissible complex with an integrality gap; and in dimension 2, where we collect some results on integrality gaps for triangulations of the 2-sphere for a companion paper with Zili Wang and Peter Doyle.