An O(n3) sized external representation of a factorial faceted, factorial extreme point polytope
Abstract
Define polytope Cn as the convex hull of all n by n permutation matrices, less the n by n identity permutation matrix. Cn has n!-1 extrema and is known to be a factorial faceted polytope from earlier work. Cn is now shown to possess an O(n3 ) external representation, an improvement over its existing O(n4 ) formulation discovered in earlier thesis work. In fact, Cn is shown to be the convex hull of an O(n) sized set of polytopes, each polytope having an O(n2) sized external representation. Hence this paper further promotes the concept of representing a polytope as the convex hull of 'just the right subset of polytopes', proposed in earlier research involving cubes. These ideas may also be useful in attempts to gain more understanding of the seemingly intangible P =? NP boundary.
