Hypersimplex

Standard hypersimplices in ${ℝ}^3$

File:2D-simplex.svg	File:2D-hypersimplex 011.png
${\Delta }_{3,1}$ Hyperplane: $x+y+z=1$	${\Delta }_{3,2}$ Hyperplane: $x+y+z=2$

In polyhedral combinatorics, the hypersimplex ${\Delta }_{d,k}$ is a convex polytope that generalizes the simplex. It is determined by two integers $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. Equivalently, ${\Delta }_{d,k}$ can be obtained by slicing the $d$-dimensional unit hypercube $[0,1{]}^d$ with the hyperplane of equation $x_1+\cdots +x_d=k$ and, for this reason, it is a $(d-1)$-dimensional polytope when $0<k<d$.

Properties

The number of vertices of ${\Delta }_{d,k}$ is $(\genfrac{}{}{0ex}{}{d}{k})$. The vertex-edge graph of the hypersimplex ${\Delta }_{d,k}$ is the Johnson graph $J(d,k)$.

Alternative constructions

An alternative construction (for $0<k<d$) is to take the convex hull of all $(d-1)$-dimensional $(0,1)$-vectors that have either $k-1$ or $k$ nonzero coordinates. This has the advantage of operating in a space that is the same dimension as the resulting polytope, but the disadvantage that the polytope it produces is less symmetric (although combinatorially equivalent to the result of the other construction).

The hypersimplex ${\Delta }_{d,k}$ is also the matroid polytope for a uniform matroid with $d$ elements and rank $k$.

Examples

The hypersimplex ${\Delta }_{d,1}$ is a $(d-1)$-simplex (and therefore, it has $d$ vertices). The hypersimplex ${\Delta }_{4,2}$ is an octahedron, and the hypersimplex ${\Delta }_{5,2}$ is a rectified 5-cell.

Generally, the hypersimplex, ${\Delta }_{d,k}$, corresponds to a uniform polytope, being the $(k-1)$-rectified $(d-1)$-dimensional simplex, with vertices positioned at the center of all the $(k-1)$-dimensional faces of a $(d-1)$-dimensional simplex.

Examples (d = 3...6)

Name	Equilateral triangle	Tetrahedron (3-simplex)	Octahedron	5-cell (4-simplex)	Rectified 5-cell	5-simplex	Rectified 5-simplex	Birectified 5-simplex
Δd,k = (d,k) = (d,d − k)	(3,1) (3,2)	(4,1) (4,3)	(4,2)	(5,1) (5,4)	(5,2) (5,3)	(6,1) (6,5)	(6,2) (6,4)	(6,3)
Vertices $(\genfrac{}{}{0ex}{}{d}{k})$	3	4	6	5	10	6	15	20
d-coordinates	(0,0,1) (0,1,1)	(0,0,0,1) (0,1,1,1)	(0,0,1,1)	(0,0,0,0,1) (0,1,1,1,1)	(0,0,0,1,1) (0,0,1,1,1)	(0,0,0,0,0,1) (0,1,1,1,1,1)	(0,0,0,0,1,1) (0,0,1,1,1,1)	(0,0,0,1,1,1)
Image	File:Regular triangle.svg	File:Uniform polyhedron-33-t0.svg	File:Uniform polyhedron-33-t1.svg	File:Schlegel wireframe 5-cell.png	File:Schlegel half-solid rectified 5-cell.png
Graphs	File:2-simplex t0.svg J(3,1) = K2	File:3-simplex t0.svg J(4,1) = K3	File:3-cube t2.svg J(4,2) = T(6,3)	File:4-simplex t0.svg J(5,1) = K4	File:4-simplex t1.svg J(5,2)	File:5-simplex t0.svg J(6,1) = K5	File:5-simplex t1 A4.svg J(6,2)	File:5-simplex t2 A4.svg J(6,3)
Coxeter diagrams	File:CDel node 1.pngFile:CDel 3.pngFile:CDel node.png File:CDel node.pngFile:CDel 3.pngFile:CDel node 1.png	File:CDel node 1.pngFile:CDel 3.pngFile:CDel node.pngFile:CDel 3.pngFile:CDel node.png File:CDel node.pngFile:CDel 3.pngFile:CDel node.pngFile:CDel 3.pngFile:CDel node 1.png	File:CDel node.pngFile:CDel 3.pngFile:CDel node 1.pngFile:CDel 3.pngFile:CDel node.png	File:CDel node 1.pngFile:CDel 3.pngFile:CDel node.pngFile:CDel 3.pngFile:CDel node.pngFile:CDel 3.pngFile:CDel node.png File:CDel node.pngFile:CDel 3.pngFile:CDel node.pngFile:CDel 3.pngFile:CDel node.pngFile:CDel 3.pngFile:CDel node 1.png	File:CDel node.pngFile:CDel 3.pngFile:CDel node 1.pngFile:CDel 3.pngFile:CDel node.pngFile:CDel 3.pngFile:CDel node.png File:CDel node.pngFile:CDel 3.pngFile:CDel node.pngFile:CDel 3.pngFile:CDel node 1.pngFile:CDel 3.pngFile:CDel node.png	File:CDel node 1.pngFile:CDel 3.pngFile:CDel node.pngFile:CDel 3.pngFile:CDel node.pngFile:CDel 3.pngFile:CDel node.pngFile:CDel 3.pngFile:CDel node.png File:CDel node.pngFile:CDel 3.pngFile:CDel node.pngFile:CDel 3.pngFile:CDel node.pngFile:CDel 3.pngFile:CDel node.pngFile:CDel 3.pngFile:CDel node 1.png	File:CDel node.pngFile:CDel 3.pngFile:CDel node 1.pngFile:CDel 3.pngFile:CDel node.pngFile:CDel 3.pngFile:CDel node.pngFile:CDel 3.pngFile:CDel node.png File:CDel node.pngFile:CDel 3.pngFile:CDel node.pngFile:CDel 3.pngFile:CDel node.pngFile:CDel 3.pngFile:CDel node 1.pngFile:CDel 3.pngFile:CDel node.png	File:CDel node.pngFile:CDel 3.pngFile:CDel node.pngFile:CDel 3.pngFile:CDel node 1.pngFile:CDel 3.pngFile:CDel node.pngFile:CDel 3.pngFile:CDel node.png
Schläfli symbols	{3} = r{3}	{3,3} = 2r{3,3}	r{3,3} = {3,4}	{3,3,3} = 3r{3,3,3}	r{3,3,3} = 2r{3,3,3}	{3,3,3,3} = 4r{3,3,3,3}	r{3,3,3,3} = 3r{3,3,3,3}	2r{3,3,3,3}
Facets	{ }	{3}		{3,3}	{3,3}, {3,4}	{3,3,3}	{3,3,3}, r{3,3,3}	r{3,3,3}

History

The hypersimplices were first studied and named in the computation of characteristic classes (an important topic in algebraic topology), by Gabrièlov, Gelʹfand & Losik (1975).

Further reading

• .