Matthew Ellison

Let \(\mathcal{K}\) be a finite pure simplicial \(d\)-complex, with oriented facets \(\{F_i\}\), which is boundaryless in the sense that \(\sum \partial F_i = 0\). We call such a \(\mathcal{K}\) an admissible \(d\)-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\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}(\mathcal{K})\) and \(V_\mathbb{Z}(\mathcal{K})\) 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}(\mathcal{K})\) and \(V_\mathbb{Q}(\mathcal{K})\) 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.

For finite abstract simplicial complex \(\Sigma\), initial realization \(\alpha\) in \(\mathbb{E}^d\), and desired edge lengths \(L\), we give practical sufficient conditions for the existence of a non-self-intersecting perturbation of \(\alpha\) realizing the lengths \(L\). We provide software to verify these conditions by computer and optionally assist in the creation of an initial realization from abstract simplicial data. Applications include proving the existence of a planar embedding of a graph with specified edge lengths or proving the existence of polyhedra (or higher-dimensional polytopes) with specified edge lengths.