Minkowski complexes and convex threshold dimension

DOI10.1016/J.JCTA.2017.04.010MaRDI QIDQ2363363zbMATH OpenOpenAlexFDO

Authors Florian Frick, Raman Sanyal

Publication date 13 July 2017

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

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

zbMATH Keywords

Minkowski sumdiscrete mixed volumeconvex threshold dimensionMinkowski complexesthreshold complexes

Mathematics Subject Classification ID

Integer programming (90C10) Hypergraphs (05C65)

Abstract: For a collection of convex bodies $P_1,dots,P_{n}subsetmathbb{R}^d$ containing the origin, a Minkowski complex is given by those subsets whose Minkowski sum does not contain a fixed basepoint. Every simplicial complex can be realized as a Minkowski complex and for convex bodies on the real line, this recovers the class of threshold complexes. The purpose of this note is the study of the convex threshold dimension of a complex, that is, the smallest dimension in which it can be realized as a Minkowski complex. In particular, we show that the convex threshold dimension can be arbitrarily large. This is related to work of Chv'atal and Hammer (1977) regarding forbidden subgraphs of threshold graphs. We also show that convexity is crucial this context.

Recommendations

• On the exact maximum complexity of Minkowski sums of polytopes
• Geometry of cut-complexes and threshold logic
• A tight lower bound for convexly independent subsets of the Minkowski sums of planar point sets
• Minkowski complexity of sets: an easy lower bound
• Minkowski's theorem for arbitrary convex sets

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3598234 (Why is no real title available?)
• scientific article; zbMATH DE number 1795862 (Why is no real title available?)
• Irrational mixed decomposition and sharp fewnomial bounds for tropical polynomial systems
• Simplicial complexes obtained from qualitative probability orders
• Threshold complexes and connections to number theory
• Threshold graphs, shifted complexes, and graphical complexes
• Threshold hypergraphs

Cited in

(1)

• Minkowski complexity of sets: an easy lower bound

This page was built for publication: Minkowski complexes and convex threshold dimension

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