Polytopes close to being simple

DOI10.1007/S00454-018-00053-YMaRDI QIDQ2189745zbMATH OpenOpenAlexWikidataFDO

Authors Guillermo Pineda-Villavicencio, Julien Ugon, David Yost

Publication date 16 June 2020

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

\(k\)-skeletonreconstructibility from graphssimple polytope

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Special polytopes (linear programming, centrally symmetric, etc.) (52B12)

Abstract: It is known that polytopes with at most two nonsimple vertices are reconstructible from their graphs, and that $d$-polytopes with at most $d-2$ nonsimple vertices are reconstructible from their 2-skeletons. Here we close the gap between 2 and $d-2$, showing that certain polytopes with more than two nonsimple vertices are reconstructible from their graphs. In particular, we prove that reconstructibility from graphs also holds for $d$-polytopes with $d+k$ vertices and at most $d-k+3$ nonsimple vertices, provided $kge5$. For $kle4$, the same conclusion holds under a slightly stronger assumption. Another measure of deviation from simplicity is the {it excess degree} of a polytope, defined as $xi(P):=2f_1-d{f}_0$, where $f_k$ denotes the number of $k$-dimensional faces of the polytope. Simple polytopes are those with excess zero. We prove that polytopes with excess at most $d-1$ are reconstructible from their graphs, and this is best possible. An interesting intermediate result is that $d$-polytopes with less than $2d$ vertices, and at most $d-1$ nonsimple vertices, are necessarily pyramids.

Recommendations

• On simple polytopes
• scientific article; zbMATH DE number 3992330
• The almost simple cubical polytopes
• On polytopes that are simple at the edges
• On the faces of simple polytopes
• scientific article; zbMATH DE number 1368684
• Polytopes
• Simple 0/1-polytopes

Cites work

• A simple way to tell a simple polytope from its graph
• Complete enumeration of small realizable oriented matroids
• Convex Polytopes
• Decomposable convex polyhedra
• scientific article; zbMATH DE number 1538126 (Why is no real title available?)
• scientific article; zbMATH DE number 3804333 (Why is no real title available?)
• scientific article; zbMATH DE number 2107521 (Why is no real title available?)
• Lower bound theorems for general polytopes
• More indecomposable polyhedra
• On the graph structure of convex polyhedra in n-space
• On the reconstruction of polytopes
• polymake: a framework for analyzing convex polytopes
• Puzzles and polytope isomorphisms
• The excess degree of a polytope

Cited in

(10)

• A family of easy polyhedra
• Simplest polymetric geometries
• On the reconstruction of polytopes
• Minimum number of edges of polytopes with \(2d+2\) vertices
• The excess degree of a polytope
• The lower bound theorem for d-polytopes with 2d+1 vertices
• Reconstructibility of matroid polytopes
• On the faces of simple polytopes
• Reconstructing simplicial polytopes from their graphs and affine 2-stresses
• Polytopes with low excess degree

Describes a project that uses

Uses Software

• polymake

This page was built for publication: Polytopes close to being simple

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