Optimization Online


On Dantzig figures from lexicographic orders

Akshay Gupte (agupte***at***clemson.edu)
Svetlana Poznanovic (spoznan***at***clemson.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/2016
Entry Accepted: 12/20/2016
Entry Last Modified: 02/03/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society