Minkowski complexes and convex threshold dimension. (English) Zbl 1366.05075
Summary: For a collection of convex bodies \(P_1, \ldots, P_n \subset \mathbb{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 V. Chvátal and P. L. Hammer [Ann. Discrete Math. 1, 145–162 (1977; Zbl 0384.90091)] regarding forbidden subgraphs of threshold graphs. We also show that convexity is crucial this context.
Keywords:
Minkowski sum; Minkowski complexes; threshold complexes; convex threshold dimension; discrete mixed volumeCitations:
Zbl 0384.90091References:
| [1] | Bihan, F., Irrational mixed decomposition and sharp fewnomial bounds for tropical polynomial systems, Discrete Comput. Geom., 55, 907-933 (2016) · Zbl 1375.14210 |
| [2] | Chvátal, V.; Hammer, P. L., Aggregation of inequalities in integer programming, (Studies in Integer Programming, Proc. Workshop. Studies in Integer Programming, Proc. Workshop, Bonn, 1975. Studies in Integer Programming, Proc. Workshop. Studies in Integer Programming, Proc. Workshop, Bonn, 1975, Ann. Discrete Math., vol. 1 (1977), North-Holland: North-Holland Amsterdam), 145-162 · Zbl 0384.90091 |
| [3] | Edelman, P. H.; Gvozdeva, T.; Slinko, A., Simplicial complexes obtained from qualitative probability orders, SIAM J. Discrete Math., 27, 1820-1843 (2013) · Zbl 1290.05162 |
| [4] | Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs, Comput. Sci. Appl. Math. (1980), Academic Press [Harcourt Brace Jovanovich, Publishers]: Academic Press [Harcourt Brace Jovanovich, Publishers] New York-London-Toronto, Ont., with a foreword by Claude Berge · Zbl 0541.05054 |
| [5] | Jochemko, K.; Sanyal, R., Combinatorial mixed valuations (May 2016), preprint, 17 pages |
| [6] | Kalai, G., Algebraic shifting, (Computational Commutative Algebra and Combinatorics. Computational Commutative Algebra and Combinatorics, Osaka, 1999. Computational Commutative Algebra and Combinatorics. Computational Commutative Algebra and Combinatorics, Osaka, 1999, Adv. Stud. Pure Math., vol. 33 (2002), Math. Soc. Japan: Math. Soc. Japan Tokyo), 121-163 · Zbl 1034.57021 |
| [7] | Klivans, C. J., Threshold graphs, shifted complexes, and graphical complexes, Discrete Math., 307, 2591-2597 (2007) · Zbl 1127.05086 |
| [8] | Pakianathan, J.; Winfree, T., Threshold complexes and connections to number theory, Turkish J. Math., 37, 511-539 (2013) · Zbl 1283.55006 |
| [9] | Reiterman, J.; Rödl, V.; Šiňajová, E.; Tuma, M., Threshold hypergraphs, Discrete Math., 54, 193-200 (1985) · Zbl 0564.05043 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
