  


On Dantzig figures from lexicographic orders
Akshay Gupte (agupteclemson.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 nonsimple 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 Modify/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  