Equivalence Classes of Full-Dimensional 0/1-Polytopes with Many Vertices
Preprint
Abstract
Let $Q_n$ denote the $n$-dimensional hypercube with the vertex set $V_n=\{0,1}^n$. A 0/1-polytope of $Q_n$ is a 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 completed the enumeration of equivalence classes of full-dimensional 0/1-polytopes for $Q_4$, $Q_5$, and those of $Q_6$ 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 $Q_n$ with more than $2^{n-3}$ vertices. As an application, we finish the counting of equivalence classes of full-dimensional 0/1-polytopes of $Q_6$ with more than 12 vertices.
Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- Revlex-initial 0/1-polytopesJournal of Combinatorial Theory, Series A, 2006
- What is known about unit cubesBulletin of the American Mathematical Society, 2005
- On 0-1 Polytopes with Many FacetsAdvances in Mathematics, 2001
- Upper Bounds on the Maximal Number of Facets of 0/1-PolytopesEuropean Journal of Combinatorics, 2000
- All 0–1 polytopes are traveling salesman polytopesCombinatorica, 1996
- Classifying Hyperplanes in HypercubesSIAM Journal on Discrete Mathematics, 1996
- On the Size of Weights for Threshold GatesSIAM Journal on Discrete Mathematics, 1994
- Induced Cycle Structures of the Hyperoctahedral GroupSIAM Journal on Discrete Mathematics, 1993
- Derangements on the n-cubeDiscrete Mathematics, 1993
- On the cycle index of a product of permutation groupsJournal of Combinatorial Theory, 1968