Minkowski complexes and convex threshold dimension

DOI10.1016/J.JCTA.2017.04.010zbMATH Open1366.05075arXiv1607.07814OpenAlexW2964191901MaRDI QIDQ2363363FDOQ2363363

Authors: Florian Frick, Raman Sanyal 

Publication date: 13 July 2017

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

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.

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

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

zbMATH Keywords

Minkowski sumdiscrete mixed volumeconvex threshold dimensionMinkowski complexesthreshold complexes

Mathematics Subject Classification ID

Integer programming (90C10) Hypergraphs (05C65)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Irrational mixed decomposition and sharp fewnomial bounds for tropical polynomial systems
• Threshold complexes and connections to number theory
• Threshold hypergraphs
• Simplicial complexes obtained from qualitative probability orders
• Threshold graphs, shifted complexes, and graphical complexes

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)