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

William Y.C. Chen and Peter L. Guo

  Abstract:   Let Qn denote the n-dimensional hypercube with the vertex set Vn = {0, 1}n. A 0/1-polytope of Qn is a convex hull of a subset of Vn. 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 completed the enumeration of equivalence classes of full-dimensional 0/1-polytopes for Q4, Q5, and those of Q6 up to 12 vertices. In this paper, we present a method to compute the number of equivalence classes of full-dimensional 0/1-polytopes of Qn with more than 2n-3 vertices. As an application, we finish the counting of equivalence classes of full-dimensional 0/1-polytopes of Q6 with more than 12 vertices.

  AMS Classification:  05A15, 52A20, 52B12, 05C25.


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

  Download:   pdf   

Return