- Title
- The excess degree of a polytope
- Creator
- Pineda-Villavicencio, Guillermo; Ugon, Julien; Yost, David
- Date
- 2018
- Type
- Text; Journal article
- Identifier
- http://researchonline.federation.edu.au/vital/access/HandleResolver/1959.17/166732
- Identifier
- vital:13474
- Identifier
-
https://doi.org/10.1137/17M1131994
- Identifier
- ISBN:0895-4801
- Abstract
- We define the excess degree \xi (P) of a d-polytope P as 2f1 - df0, where f0 and f1 denote 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 ot = 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 f0 vertices and f1 edges, are determined.
- Publisher
- Society for Industrial and Applied Mathematics Publications
- Relation
- SIAM Journal on Discrete Mathematics Vol. 32, no. 3 (2018), p. 2011-2046, http://purl.org/au-research/grants/arc/DP180100602
- Rights
- Copyright © 2018 Society for Industrial and Applied Mathematics.
- Rights
- Open Access
- Rights
- This metadata is freely available under a CCO license
- Subject
- 0101 Pure Mathematics; 0802 Computation Theory and Mathematics; Excess degree; F-vector; Minkowski decomposability; Polytope; Polytope graph
- Full Text
- Reviewed
- Hits: 1807
- Visitors: 2017
- Downloads: 264
| Thumbnail | File | Description | Size | Format | |||
|---|---|---|---|---|---|---|---|
| View Details Download | SOURCE1 | Published version | 630 KB | Adobe Acrobat PDF | View Details Download |