A decomposition of 2-weak vertex-packing polytopes
type: Item
instance of: scholarly article
title: A decomposition of 2-weak vertex-packing polytopes
zbMATH Open document ID: 0813.52009
DOI: 10.1007/BF02574393
author: Einar Steingrímsson
published in: Discrete \& Computational Geometry
publication date: 1995-05-29T00:00:00Z
full work available at URL: https://eudml.org/doc/131343
review text: Let \(G\) be a loopless graph with \(d\) vertices. The 2-weak vertex-packing polytope \(W(G)\) of \(G\) (which is interesting from the viewpoint of linear programming) is defined by \[ x_ i\leq 1, \quad 0\leq x_ i, \quad 1\leq i\leq d, \qquad x_ i+x_ j\leq 1, \quad \text{ if \((i,j)\) is an edge of }G. \] By a dilation of \(W(G)\) with ratio 2, leading to the polytope \(P(G)\), the author obtains various results on this class of polytopes. For example, he shows ways for computing the \(h\)-vector of \(P(G)\) as a descent statistic on a subset of the hyperoctahedral group determined by \(G\), and he also gives a recursive formula for the computation of this \(h\)-vector, being descended to those facets of \(P(G)\) which lie in the boundary of the corresponding dilated unit \(d\)-cube. A simplified version of this recursion yields a simple recursive formula for the volume computation with respect to \(P(G)\).
reviewed by: Horst Martini
Mathematics Subject Classification ID: 52B05
Mathematics Subject Classification ID: 90C05
zbMATH DE Number: 698612
zbMATH Keywords: simplicial complex
zbMATH Keywords: Ehrhart polynomials
zbMATH Keywords: 2-weak vertex-packing polytope
zbMATH Keywords: linear programming
zbMATH Keywords: \(h\)-vector
zbMATH Keywords: volume computation
MaRDI profile type: Publication
cites work: Lattice points in lattice polytopes
cites work: Shellable and Cohen-Macaulay Partially Ordered Sets
cites work: Q4860774
cites work: On certain polytopes associated with graphs
cites work: The maximum numbers of faces of a convex polytope
cites work: Q3827224
cites work: On the facial structure of set packing polyhedra
cites work: Signed permutation statistics
cites work: Decompositions of Rational Convex Polytopes
cites work: Q3748279
cites work: Two poset polytopes
cites work: Q3797807
cites work: Permutation statistics of indexed permutations
OpenAlex ID: W2115110298
Recommended article: Equidecomposable and weakly neighborly polytopes
Recommended article: Vertex decompositions of two-dimensional complexes and graphs
Recommended article: Obstructions to weak decomposability for simplicial polytopes
Recommended article: Decompositions of two-dimensional simplicial complexes
Recommended article: A polyhedral study of the generalized vertex packing problem
Recommended article: Edge decompositions and rooted packings of graphs
Recommended article: An Improvement in the Two-packing Bound Related to Vizing's Conjecture
Recommended article: A Structural Lemma in 2-Dimensional Packing, and Its Implications on Approximability
Recommended article: Packing \(d\)-degenerate graphs
Recommended article: Decomposability of polytopes
description: scientific article; zbMATH DE number 698612