2025/12/08 by Pineda-Villavicencio, Guillermo, Wang, Jie
Computer Science · Business, Management and Accounting · #Computational Geometry and Mesh Generation #Facility Location and Emergency Management #Complexity and Algorithms in Graphs
paper · doi:10.48550/arxiv.2512.07456
We prove a lower bound theorem for the number of k-faces (1≤ k≤ d-2) in a d-dimensional polytope P (or d-polytope) with up to 3d-1 vertices. Previous lower bound theorems for d-polytopes with few vertices concern those with at most 2d vertices, 2d+1 vertices, and 2d+2 vertices. If P has exactly d+2 facets and 2d+ℓ vertices (ℓ≥ 1), the lower bound is tight for certain combinations of d and ℓ. When P has at least d+3 facets and 2d+ℓ vertices (ℓ≥ 1), the lower bound remains tight up to ℓ=d-1, and equality for some 1≤ k≤ d-2 is attained only when P has precisely d+3 facets. We exhibit at least one minimiser for each number of vertices between 2d+1 and 3d-1, including two distinct minimisers with 2d+2 vertices and three with 3d-2 vertices.