A decomposition of 2-weak vertex-packing polytopes
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)\).
scientific article; zbMATH DE number 698612
scientific article