2024/04/01 by Matthew Ellison, Ellison, Matthew · 1 citation
Computer Science · Engineering · Mathematics · #52-08 #52C05 #52C07 #55U10 #68W25 #90C05 #90C10 #Algebraic Topology (math.AT) #Combinatorics (math.CO) #Digital Image Processing Techniques #F.2.2 #FOS: Mathematics #Finite Group Theory Research #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2404.01279
openalex publication_date 2024/04/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let K be a finite pure simplicial d-complex, with oriented facets \Fi\, which is boundaryless in the sense that ∑∂ Fi=0. We call such a K an admissible d-complex. Given an admissible d-complex, one can ask for the smallest collection \Ti\ of oriented (d+1)-simplices on the vertices of K which decomposes K in the sense that ∑ ∂ Ti = K. Let the minimum size of such a collection be V_ℤ(K), and let V_ℚ(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_ℚ and V_ℤ are both additive under disjoint union and connected sum along a d-simplex. The remainder of the paper explores integrality gaps between V_ℤ and V_ℚ 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.