Neighborly polytope

In geometry and polyhedral combinatorics, a Template:Mvar-neighborly polytope is a convex polytope in which every set of Template:Mvar or fewer vertices forms a face. For instance, a 2-neighborly polytope is a polytope in which every pair of vertices is connected by an edge, forming a complete graph. 2-neighborly polytopes with more than four vertices may exist only in spaces of four or more dimensions, and in general a Template:Mvar-neighborly polytope (other than a simplex) requires a dimension of Template:Math or more. A Template:Mvar-simplex is Template:Mvar-neighborly. A polytope is said to be neighborly, without specifying Template:Mvar, if it is Template:Mvar-neighborly for Template:Math. If we exclude simplices, this is the maximum possible Template:Mvar: in fact, every polytope that is Template:Mvar-neighborly for some Template:Math is a simplex.

In a Template:Mvar-neighborly polytope with Template:Math, every 2-face must be a triangle, and in a Template:Mvar-neighborly polytope with Template:Math, every 3-face must be a tetrahedron. More generally, in any Template:Mvar-neighborly polytope, all faces of dimension less than Template:Mvar are simplices.

The cyclic polytopes formed as the convex hulls of finite sets of points on the moment curve Template:Math in Template:Mvar-dimensional space are automatically neighborly. Theodore Motzkin conjectured that all neighborly polytopes are combinatorially equivalent to cyclic polytopes. However, contrary to this conjecture, there are many neighborly polytopes that are not cyclic: the number of combinatorially distinct neighborly polytopes grows superexponentially, both in the number of vertices of the polytope and in the dimension.

The convex hull of a set of random points, drawn from a Gaussian distribution with the number of points proportional to the dimension, is with high probability Template:Mvar-neighborly for a value Template:Mvar that is also proportional to the dimension.

The number of faces of all dimensions of a neighborly polytope in an even number of dimensions is determined solely from its dimension and its number of vertices by the Dehn–Sommerville equations: the number of Template:Mvar-dimensional faces, Template:Mvar, satisfies the inequality

$f_{k-1}\le \sum _{i=0}^{d/2}{}^{*}((\genfrac{}{}{0ex}{}{d-i}{k-i})+(\genfrac{}{}{0ex}{}{i}{k-d+i}))(\genfrac{}{}{0ex}{}{n-d-1+i}{i}),$

where the asterisk means that the sums ends at Template:Math and final term of the sum should be halved if Template:Mvar is even. According to the upper bound theorem of Template:Harvtxt, neighborly polytopes achieve the maximum possible number of faces of any Template:Mvar-vertex Template:Mvar-dimensional convex polytope.

A generalized version of the happy ending problem applies to higher-dimensional point sets, and implies that for every dimension Template:Mvar and every Template:Math there exists a number Template:Math with the property that every Template:Mvar points in general position in Template:Mvar-dimensional space contain a subset of Template:Mvar points that form the vertices of a neighborly polytope.