polyhedral combinatorics Polyhedral combinatorics is a branch of mathematics, within combinatorics and discrete geometry, that studies the problems of counting and describing the faces of convex polyhedra and higher-dimensional convex polytopes. Research in polyhedral comb ...

, the hypersimplex

\Delta_

is a

convex polytope A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the n-dimensional Euclidean space \mathbb^n. Most texts. use the term "polytope" for a bounded convex polytope, and the wo ...

that generalizes the

simplex In geometry, a simplex (plural: simplexes or simplices) is a generalization of the notion of a triangle or tetrahedron to arbitrary dimensions. The simplex is so-named because it represents the simplest possible polytope in any given dimension. ...

. It is determined by two integers

d

and

k

, and is defined as the

convex hull In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space ...

of the

d

-dimensional vectors whose coefficients consist of

k

ones and

d-k

zeros. Equivalently,

\Delta_

can be obtained by slicing the

d

-dimensional unit

hypercube In geometry, a hypercube is an ''n''-dimensional analogue of a square () and a cube (). It is a closed, compact, convex figure whose 1- skeleton consists of groups of opposite parallel line segments aligned in each of the space's dimensions, ...

,1 d

with the

hyperplane In geometry, a hyperplane is a subspace whose dimension is one less than that of its ''ambient space''. For example, if a space is 3-dimensional then its hyperplanes are the 2-dimensional planes, while if the space is 2-dimensional, its hyper ...

of equation

x_1+\cdots+x_d=k

and, for this reason, it is a

(d-1)

-dimensional polytope when

0 . .

Properties

The number of vertices of

\Delta_

\tbinom d k

. The graph formed by the vertices and edges of the hypersimplex

\Delta_

is the Johnson graph

J(d,k)

Alternative constructions

An alternative construction (for

k\leq

) is to take the convex hull of all

(d-1)

-dimensional

(0,1)

-vectors that have either

k-1

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_

is also the

matroid polytope In mathematics, a matroid polytope, also called a matroid basis polytope (or basis matroid polytope) to distinguish it from other polytopes derived from a matroid, is a polytope constructed via the bases of a matroid. Given a matroid M, the matroid ...

for a

uniform matroid In mathematics, a uniform matroid is a matroid in which the independent sets are exactly the sets containing at most ''r'' elements, for some fixed integer ''r''. An alternative definition is that every permutation of the elements is a symmetry. ...

with

d

elements and rank

k

Examples

The hypersimplex

\Delta_

is a

(d-1)

-simplex (and therefore, it has

d

vertices). The hypersimplex

\Delta_

is an

octahedron In geometry, an octahedron (plural: octahedra, octahedrons) is a polyhedron with eight faces. The term is most commonly used to refer to the regular octahedron, a Platonic solid composed of eight equilateral triangles, four of which meet at ea ...

, and the hypersimplex

\Delta_

is a

rectified 5-cell In four-dimensional geometry, the rectified 5-cell is a uniform 4-polytope composed of 5 regular tetrahedral and 5 regular octahedral cells. Each edge has one tetrahedron and two octahedra. Each vertex has two tetrahedra and three octahedra. In t ...

. Generally, the hypersimplex,

\Delta_

, corresponds to a

uniform polytope In geometry, a uniform polytope of dimension three or higher is a vertex-transitive polytope bounded by uniform facets. The uniform polytopes in two dimensions are the regular polygons (the definition is different in 2 dimensions to exclude vert ...

, 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.

History

The hypersimplices were first studied and named in the computation of

characteristic class In mathematics, a characteristic class is a way of associating to each principal bundle of ''X'' a cohomology class of ''X''. The cohomology class measures the extent the bundle is "twisted" and whether it possesses sections. Characteristic classes ...

es (an important topic in

algebraic topology Algebraic topology is a branch of mathematics that uses tools from abstract algebra to study topological spaces. The basic goal is to find algebraic invariant (mathematics), invariants that classification theorem, classify topological spaces up t ...

), by ..

Properties

Alternative constructions

Examples

History

References

Further reading