Equivalence Classes of Full-Dimensional $$0/1$$ 0 / 1 -Polytopes with Many Vertices

Autor: Peter L. Guo, William Y. C. Chen
Rok vydání: 2014
Předmět:
Zdroj: Discrete & Computational Geometry. 52:630-662
ISSN: 1432-0444
0179-5376
DOI: 10.1007/s00454-014-9630-5
Popis: Let $$Q_n$$Qn denote the $$n$$n-dimensional hypercube with vertex set $$V_n=\{0,1\}^n$$Vn={0,1}n. A $$0/1$$0/1-polytope of $$Q_n$$Qn is the convex hull of a subset of $$V_n$$Vn. This paper is concerned with the enumeration of equivalence classes of full-dimensional $$0/1$$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$$0/1-polytopes of $$Q_4$$Q4 and $$Q_5$$Q5 with any given number of vertices and those of $$Q_6$$Q6 up to 12 vertices. Let $$F_n(k)$$Fn(k) denote the number of equivalence classes of full-dimensional 0/1-polytopes of $$Q_n$$Qn with $$k$$k vertices. We present a method to compute $$F_n(k)$$Fn(k) for $$k>2^{n-2}$$k>2n-2. Let $$A_n(k)$$An(k) denote the number of equivalence classes of $$0/1$$0/1-polytopes of $$Q_n$$Qn with $$k$$k vertices, and let $$H_n(k)$$Hn(k) denote the number of equivalence classes of $$0/1$$0/1-polytopes of $$Q_n$$Qn with $$k$$k vertices that are not full-dimensional. So we have $$A_n(k)= F_n(k)+ H_n(k)$$An(k)=Fn(k)+Hn(k). It is known that $$A_n(k)$$An(k) can be computed by using the cycle index of the hyperoctahedral group. We show that for $$k>2^{n-2}$$k>2n-2, $$H_n(k)$$Hn(k) can be determined by the number of equivalence classes of $$0/1$$0/1-polytopes with $$k$$k vertices that are contained in every hyperplane spanned by a subset of $$V_n$$Vn. We also find a way to compute $$H_n(k)$$Hn(k) when $$k$$k is close to $$2^{n-2}$$2n-2. For the case of $$Q_6$$Q6, we can compute $$F_6(k)$$F6(k) for $$k>12$$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$$Q6.
Databáze: OpenAIRE
Externí odkaz: