Lower bounds and integrality gaps in simplicial decomposition

Let K be a finite pure simplicial d-complex, with oriented facets ᵢ\, which is boundaryless in the sense that ∑∂ Fᵢ=0. We call such a K an admissible d-complex. Given an admissible d-complex, one can ask for the smallest collection ᵢ\ of oriented $(d+1)$-simplices on the vertices of K which decomposes K in the sense that ∑ ∂ Tᵢ = K. Let the minimum size of such a collection be VZ(K), and let VQ(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 VQ and VZ are both additive under disjoint union and connected sum along a d-simplex. The remainder of the paper explores integrality gaps between VZ and VQ 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.