The excess degree of a polytope

Pineda-Villavicencio, Guillermo, Ugon, Julien and Yost, David 2018, The excess degree of a polytope, SIAM journal on discrete mathematics, vol. 32, no. 3, pp. 2011-2046, doi: 10.1137/17M1131994.

Attached Files
Name Description MIMEType Size Downloads

Title The excess degree of a polytope
Author(s) Pineda-Villavicencio, Guillermo
Ugon, JulienORCID iD for Ugon, Julien
Yost, David
Journal name SIAM journal on discrete mathematics
Volume number 32
Issue number 3
Start page 2011
End page 2046
Total pages 36
Publisher Society for Industrial and Applied Mathematics
Place of publication Philadelphia, Pa.
Publication date 2018
ISSN 0895-4801
Summary © 2018 Society for Industrial and Applied Mathematics. We define the excess degree \xi (P) of a d-polytope P as 2f1 - df0, where f0and f1denote the number of vertices and edges, respectively. This parameter measures how much P deviates from being simple. It turns out that the excess degree of a d-polytope does not take every natural number: the smallest possible values are 0 and d - 2, and the value d - 1 only occurs when d = 3 or 5. On the other hand, for fixed d, the number of values not taken by the excess degree is finite if d is odd, and the number of even values not taken by the excess degree is finite if d is even. The excess degree is then applied in three different settings. First, it is used to show that polytopes with small excess (i.e., \xi (P) < d) have a very particular structure: provided d \not = 5, either there is a unique nonsimple vertex, or every nonsimple vertex has degree d + 1. This implies that such polytopes behave in a similar manner to simple polytopes in terms of Minkowski decomposability: they are either decomposable or pyramidal, and their duals are always indecomposable. Second, we characterize completely the decomposable d-polytopes with 2d + 1 vertices (up to combinatorial equivalence). Third, all pairs (f0, f1), for which there exists a 5-polytope with f0vertices and f1 edges, are determined.
Language eng
DOI 10.1137/17M1131994
Field of Research 0101 Pure Mathematics
0802 Computation Theory And Mathematics
HERDC Research category C1 Refereed article in a scholarly journal
Copyright notice ©2018, Society for Industrial and Applied Mathematics
Persistent URL

Connect to link resolver
Unless expressly stated otherwise, the copyright for items in DRO is owned by the author, with all rights reserved.

Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 3 times in TR Web of Science
Scopus Citation Count Cited 5 times in Scopus
Google Scholar Search Google Scholar
Access Statistics: 88 Abstract Views, 0 File Downloads  -  Detailed Statistics
Created: Fri, 26 Oct 2018, 14:29:18 EST

Every reasonable effort has been made to ensure that permission has been obtained for items included in DRO. If you believe that your rights have been infringed by this repository, please contact