A decomposition of 2-weak vertex-packing polytopes |
| |
Authors: | E Steingrímsson |
| |
Institution: | 1. Matematiska Institutionen CTH & GU, 412 96, G?teborg, Sweden
|
| |
Abstract: | The 2-weak vertex-packing polytope of a loopless graphG withd vertices is the subset of the unitd-cube satisfyingx
i
+x
j
≤1 for every edge (i,j) ofG. The dilation by 2 of this polytope is a polytope
with integral vertices. We triangulate
with lattice simplices of minimal volume and label the maximal simplices with elements of the hyperoctahedral groupB
d
. This labeling gives rise to a shelling of the triangulation
of
, where theh-vector of
(and the Ehrharth
*-vector of
can be computed as a descent statistic on a subset ofB
d
defined in terms ofG. A recursive way of computing theh-vector of
is also given, and a recursive formula for the volume of
.
This work was partially supported by grants from the Icelandic Council of Science and the Royal Swedish Academy of Sciences,
respectively. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|