Hypersimplex


In polyhedral combinatorics, a hypersimplex, Δd,k, is a convex polytope that generalizes the simplex. It is determined by two parameters d and k, and is defined as the convex hull of the d-dimensional vectors whose coefficients consist of k ones and d − k zeros. It forms a -dimensional polytope, because all of these vectors lie in a single -dimensional hyperplane.

Properties

The number of vertices in Δd,k is.
The graph formed by the vertices and edges of a hypersimplex Δd,k is the Johnson graph J.

Alternative constructions

An alternative construction is to take the convex hull of all -dimensional -vectors that have either or k nonzero coordinates. This has the advantage of operating in a space that is the same dimension as the resulting polytope, but the disadavantage that the polytope it produces is less symmetric.
A hypersimplex Δd,k is also the matroid polytope for a uniform matroid with d elements and rank k.

Examples

The hypersimplex with parameters is a -simplex, with d vertices.
The hypersimplex with parameters is an octahedron, and the hypersimplex with parameters is a rectified 5-cell.
Generally, every -hypersimplex, Δd,k, corresponds to a uniform polytope, being the -rectified -simplex, with vertices positioned in the centers of all -face elements of a -simplex.

History

The hypersimplices were first studied and named in the computation of characteristic classes, by.