Primitive zonotopes

Abstract: We introduce and study a family of polytopes which can be seen as a generalization of the permutahedron of type

B_{d}

. We highlight connections with the largest possible diameter of the convex hull of a set of points in dimension

d

whose coordinates are integers between

0

and

k

, and with the computational complexity of multicriteria matroid optimization.

Review text

The authors introduce the notion of a \textit{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.

Recommendations

Cites work

Cited in

(17)

Describes a project that uses

Uses Software

OEIS

This page was built for publication: Primitive zonotopes

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