×
Deza, Antoine; Manoussakis, George; Onn, Shmuel

Primitive zonotopes. (English) Zbl 1406.52029

Discrete Comput. Geom. 60, No. 1, 27-39 (2018).
The authors introduce the notion of a primitive zonotope: a zonotope generated by the primitive integer vectors of \(q\)-norm \(\leq p\), that is, \[ Z_q(d, p) := \left\{ \lambda_v v : \, v \in \mathbb{Z}^d, \;\|v\|_q \leq p, \;\gcd(v) = 1, \;v \succ 0, \;0 \leq \lambda_v \leq 1 \right\} . \] Here \(\succ\) denotes the lexicographic order, i.e., \(v \succ 0\) means that the first nonzero entry of \(v\) is positive. These polytopes are interesting because they have a large symmetry group, a large diameter, and many vertices relative to their grid embedding size. The authors derive several properties of primitive zonotopes, including lower bounds for their diameters and connections to the computational complexity of multicriteria matroid optimization.
Reviewer: Matthias Beck (San Francisco)

Cited in 3 Reviews
Cited in 14 Documents

MSC:

52B20 Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry)

Keywords:

primitive zonotope; lattice polytope; matroid optimization; polytope diameter; primitive integer vector

Software:

OEIS
Cite Review PDF
Full Text: DOI arXiv

Online Encyclopedia of Integer Sequences:

Number of comparative probability orderings on all subsets of n elements that can arise by assigning a probability distribution to the individual elements.
Number of generalized retarded functions in quantum field theory.
Largest diameter of a lattice polygon.

References:

[1] Acketa, DM; Žunić, JD, On the maximal number of edges of convex digital polygons included into an \(m× {m}\)-grid, J. Comb. Theory Ser. A, 69, 358-368, (1995) · Zbl 0815.68112 · doi:10.1016/0097-3165(95)90058-6
[2] Allamigeon, X., Benchimol, P., Gaubert, S., Joswig, M.: Long and winding central paths. arXiv:1405.4161 (2014) · Zbl 1316.52021
[3] Balog, A., Bárány, I.: On the convex hull of the integer points in a disc. In: Goodman, J.E., et al. (eds.) Proceedings of the Seventh Annual Symposium on Computational Geometry (SCG’91), pp. 162-165. ACM, New York (1991)
[4] Berge, C.: Graphes, 3rd edn. Gauthier-Villars, Paris (1983) · Zbl 0531.05031
[5] Bonifas, N; Summa, M; Eisenbrand, F; Hähnle, N; Niemeier, M, On sub-determinants and the diameter of polyhedra, Discrete Comput. Geom., 52, 102-115, (2014) · Zbl 1310.52013 · doi:10.1007/s00454-014-9601-x
[6] Borgwardt, S., De Loera, J.A., Finhold, E.: The diameters of network-flow polytopes satisfy the Hirsch conjecture. arXiv:1603.00325 (2016) · Zbl 1386.52008
[7] Pia, A; Michini, C, On the diameter of lattice polytopes, Discrete Comput. Geom., 55, 681-687, (2016) · Zbl 1342.52014 · doi:10.1007/s00454-016-9762-x
[8] Deza, A., Pournin, L.: Improved bounds on the diameter of lattice polytopes. arXiv:1610.00341 (2016) · Zbl 1399.52024
[9] Eppstein, D, Zonohedra and zonotopes, Math. Educ. Res., 5, 15-21, (1996)
[10] Fukuda, K.: Lecture: Polyhedral Computation. http://www-oldurls.inf.ethz.ch/personal/fukudak/lect/pclect/notes2015/ (2015) · Zbl 1297.90087
[11] Gritzmann, P; Sturmfels, B, Minkowski addition of polytopes: complexity and applications to Gröbner bases, SIAM J. Discrete Math., 6, 246-269, (1993) · Zbl 0798.68157 · doi:10.1137/0406019
[12] Grünbaum, B.: Convex Polytopes. Graduate Texts in Mathematics, vol. 221, 2nd edn. Springer, New York (2003) · Zbl 1024.52001 · doi:10.1007/978-1-4613-0019-9
[13] Hardy, G.H., Wright, E.M.: An Introduction to the Theory of Numbers, 5th edn. Clarendon Press, New York (1979) · Zbl 0423.10001
[14] Humphreys, J.E.: Reflection Groups and Coxeter Groups. Cambridge Studies in Advanced Mathematics, vol. 29. Cambridge University Press, Cambridge (1990) · Zbl 0725.20028 · doi:10.1017/CBO9780511623646
[15] Kalai, G; Kleitman, DJ, A quasi-polynomial bound for the diameter of graphs of polyhedra, Bull. Am. Math. Soc., 26, 315-316, (1992) · Zbl 0751.52006 · doi:10.1090/S0273-0979-1992-00285-9
[16] Kleinschmidt, P; Onn, S, On the diameter of convex polytopes, Discrete Math., 102, 75-77, (1992) · Zbl 0762.52004 · doi:10.1016/0012-365X(92)90349-K
[17] Melamed, M; Onn, S, Convex integer optimization by constantly many linear counterparts, Linear Algebra Appl., 447, 88-109, (2014) · Zbl 1297.90087 · doi:10.1016/j.laa.2014.01.007
[18] Naddef, D, The Hirsch conjecture is true for \((0,1)\)-polytopes, Math. Program., 45, 109-110, (1989) · Zbl 0684.90071 · doi:10.1007/BF01589099
[19] Onn, S.: Nonlinear Discrete Optimization. Zurich Lectures in Advanced Mathematics. European Mathematical Society, Zürich (2010) · Zbl 1219.90003 · doi:10.4171/093
[20] Onn, S; Rothblum, UG, Convex combinatorial optimization, Discrete Comput. Geom., 32, 549-566, (2004) · Zbl 1179.90289 · doi:10.1007/s00454-004-1138-y
[21] Santos, F, A counterexample to the Hirsch conjecture, Ann. Math., 176, 383-412, (2012) · Zbl 1252.52007 · doi:10.4007/annals.2012.176.1.7
[22] Sloane, N. (ed.): The on-line encyclopedia of integer sequences. https://oeis.org · Zbl 1044.11108
[23] Soprunov, I; Soprunova, J, Eventual quasi-linearity of the Minkowski length, Eur. J. Comb., 58, 110-117, (2016) · Zbl 1347.52014 · doi:10.1016/j.ejc.2016.05.009
[24] Sukegawa, N.: Improving bounds on the diameter of a polyhedron in high dimensions. arXiv:1604.04039 (2016) · Zbl 1370.52019
[25] Thiele, T.: Extremalprobleme für Punktmengen. Diplomarbeit, Freie Universität Berlin (1991)
[26] Todd, MJ, An improved Kalai-kleitman bound for the diameter of a polyhedron, SIAM J. Discrete Math., 28, 1944-1947, (2014) · Zbl 1316.52021 · doi:10.1137/140962310
[27] Ziegler, G.M.: Lectures on Polytopes. Graduate Texts in Mathematics, vol. 152. Springer, New York (1995) · Zbl 0823.52002 · doi:10.1007/978-1-4613-8431-1
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.