Abstract:   Let Q_n denote the n-dimensional hypercube with vertex set V_n = {0, 1}ⁿ. 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₄ and Q₅ with any given number of vertices and those of Q₆ 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₆, we can compute F₆(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₆.

 AMS Classification:  05A15, 52B05

 Keywords:  full-dimensional 0/1-polytope, symmetry, hyperplane, Pólya theory

 Download:   pdf