- On Dantzig figures from lexicographic orders Akshay Gupte (agupteclemson.edu) Svetlana Poznanovic (spoznanclemson.edu) 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. Keywords: grlex, grevlex, polytope, Dantzig figure, diameter Category 1: Combinatorial Optimization (Polyhedra ) Category 2: Integer Programming Citation: submitted Download: [PDF]Entry Submitted: 12/19/2016Entry Accepted: 12/20/2016Entry Last Modified: 02/03/2017Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.