The excess degree of a polytope

DOI10.1137/17M1131994MaRDI QIDQ4579953zbMATH OpenOpenAlexWikidataFDO

Authors Guillermo Pineda-Villavicencio, Julien Ugon, David Yost

Publication date 10 August 2018

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1703.10702

zbMATH Keywords

\(f\)-vectorexcess degreeMinkowski decomposabilitypolytopepolytope graph

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) (n)-dimensional polytopes (52B11)

Abstract: We define the excess degree $xi(P)$ of a $d$-polytope $P$ as $2f_1-d{f}_0$, where $f_0$ and $f_1$ 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. It is used to show that polytopes with small excess (i.e. $xi(P)<d$) have a very particular structure: provided $de5$, 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. Secondly, we characterise completely the decomposable $d$-polytopes with $2d+1$ vertices (up to combinatorial equivalence). And thirdly all pairs $(f_0,f_1)$, for which there exists a 5-polytope with $f_0$ vertices and $f_1$ edges, are determined.

Recommendations

• Polytopes close to being simple
• Decomposability of polytopes and polyhedra
• More indecomposable polyhedra
• The lower bound theorem for d-polytopes with 2d+1 vertices
• Extremal edge polytopes

Cites work

• A proof of the lower bound conjecture for convex polytopes
• Convex Polytopes
• Decomposability of polytopes
• Decomposability of polytopes and polyhedra
• Decomposable convex polyhedra
• scientific article; zbMATH DE number 3633249 (Why is no real title available?)
• Indecomposable polytopes
• Irreducible convex sets
• Lectures on Polytopes
• More indecomposable polyhedra
• Polyhedra with 4 to 8 faces
• Polytope pairs and their relationship to linear programming
• Polytopes, graphs, and complexes
• Rigidity and the lower bound theorem. I
• The \(d\)-step conjecture for polyhedra of dimension \(d<6\)
• The Minimum Number of Facets of a Convex Polytope

Cited in

(13)

• On the reconstruction of polytopes
• Minimum number of edges of polytopes with \(2d+2\) vertices
• Characterizing face and flag vector pairs for polytopes
• Polytopes close to being simple
• Semi-algebraic sets of \(f\)-vectors
• The numbers of edges of 5-polytopes with a given number of vertices
• Lower bound theorems for general polytopes
• The lower bound theorem for d-polytopes with 2d+1 vertices
• Embedding divisor and semi-prime testability in f-vectors of polytopes
• Graphs, skeleta and reconstruction of polytopes
• Lower bound results for conditionally decomposable polytopes
• A lower bound theorem for d-polytopes with 2d+2 vertices
• Polytopes with low excess degree

This page was built for publication: The excess degree of a polytope

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4579953)