Equivalence Classes of Full-Dimensional 0/1-Polytopes with Many Vertices
William Y.C. Chen and Peter L. Guo
Abstract: Let Q_{n} denote the n-dimensional hypercube with vertex set V_{n} = {0, 1}^{n}. A 0/1-polytope of Q_{n} is the convex hull of a subset of V_{n}. This paper is concerned with the enumeration of equivalence classes of full-dimensional 0/1-polytopes under the symmetries of the hypercube. With the aid of a computer program, Aichholzer obtained the number of equivalence classes of full-dimensional 0/1-polytopes of Q_{4} and Q_{5} with any given number of vertices and those of Q_{6} up to 12 vertices. Let F_{n}(k) denote the number of equivalence classes of full-dimensional 0/1-polytopes of Q_{n} with k vertices. We present a method to compute F_{n}(k) for k > 2n-2. Let A_{n}(k) denote the number of equivalence classes of 0/1-polytopes of Q_{n} with k vertices, and let H_{n}(k) denote the number of equivalence classes of 0/1-polytopes of Q_{n} with k vertices that are not full-dimensional. So we have A_{n}(k) = F_{n}(k)+H_{n}(k). It is known that A_{n}(k) can be computed by using the cycle index of the hyperoctahedral group.We showthat for k > 2n-2, H_{n}(k) can be determined by the number of equivalence classes of 0/1-polytopes with k vertices that are contained in every hyperplane spanned by a subset of V_{n}. We also find a way to compute H_{n}(k) when k is close to 2n-2. For the case of Q_{6}, we can compute F_{6}(k) for k > 12. Together with the computation of Aichholzer, we reach a complete solution to the enumeration of equivalence classes of full-dimensional 0/1-polytopes of Q_{6}. AMS Classification: 05A15, 52B05 Keywords: full-dimensional 0/1-polytope, symmetry, hyperplane, Pólya theory Download: pdf |