On Dantzig figures from lexicographic orders

Abstract

We consider two families of \(d\)-polytopes defined as convex hulls of initial subsets for the graded lexicographic (grlex) and graded reverse lexicographic (grevlex) orders on \(\mathbb{Z}^{d}_{\geq 0}\). Our considerations are motivated by the nice properties of the lex polytopes which were studied in relation to optimization problems. We show that the grlex and grevlex polytopes are non-simple Dantzig figures which are not combinatorially equivalent but have the same number of vertices, \(\mathcal{O}(d^{2})\). In fact, we provide an explicit description of the vertices and the facets for both families and show the basic properties of their graphs such as the radius, diameter, existence of Hamiltonian circuits, and chromatic number. The diameter is no more than 3. Moreover, we prove that the graph of the grlex polytope, which has \(\mathcal{O}(d^{2})\) vertices of degree \(d\), has edge expansion 1.