geometry Geometry (; ) is, with arithmetic, one of the oldest branches of mathematics. It is concerned with properties of space such as the distance, shape, size, and relative position of figures. A mathematician who works in the field of geometry is c ...

and polyhedral combinatorics, a -neighborly polytope 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 ...

in which every set of or fewer vertices forms a

face The face is the front of an animal's head that features the eyes, nose and mouth, and through which animals express many of their emotions. The face is crucial for human identity, and damage such as scarring or developmental deformities may aff ...

. For instance, a 2-neighborly polytope is a polytope in which every pair of vertices is connected by an

edge Edge or EDGE may refer to: Technology Computing * Edge computing, a network load-balancing system * Edge device, an entry point to a computer network * Adobe Edge, a graphical development application * Microsoft Edge, a web browser developed by ...

, forming a

complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is ...

. 2-neighborly polytopes with more than four vertices may exist only in spaces of four or more dimensions, and in general a -neighborly polytope (other than a

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

) requires a dimension of or more. A -simplex is -neighborly. A polytope is said to be neighborly, without specifying , if it is -neighborly for . If we exclude simplices, this is the maximum possible : in fact, every polytope that is -neighborly for some is a simplex. In a -neighborly polytope with , every 2-face must be a triangle, and in a -neighborly polytope with , every 3-face must be a tetrahedron. More generally, in any -neighborly polytope, all faces of dimension less than are

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

. The cyclic polytopes formed as the convex hulls of finite sets of points on the moment curve in -dimensional space are automatically neighborly.

Theodore Motzkin Theodore Samuel Motzkin (26 March 1908 – 15 December 1970) was an Israeli-American mathematician. Biography Motzkin's father Leo Motzkin, a Ukrainian Jew, went to Berlin at the age of thirteen to study mathematics. He pursued university studi ...

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 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 a set of random points, drawn from a Gaussian distribution with the number of points proportional to the dimension, is with high probability -neighborly for a value 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 -dimensional faces, , satisfies the inequality :

f_ \le \sum_^ ^* \left( \binom+\binom \right) \binom,

where the asterisk means that the sums ends at and final term of the sum should be halved if is even. According to the

upper bound theorem In mathematics, the upper bound theorem states that cyclic polytopes have the largest possible number of faces among all convex polytopes with a given dimension and number of vertices. It is one of the central results of polyhedral combinatorics. O ...

of , neighborly polytopes achieve the maximum possible number of faces of any -vertex -dimensional convex polytope. A generalized version of the

happy ending problem In mathematics, the "happy ending problem" (so named by Paul Erdős because it led to the marriage of George Szekeres and Esther Klein) is the following statement: This was one of the original results that led to the development of Ramsey t ...

applies to higher-dimensional point sets, and implies that for every dimension and every there exists a number with the property that every points in

general position In algebraic geometry and computational geometry, general position is a notion of genericity for a set of points, or other geometric objects. It means the ''general case'' situation, as opposed to some more special or coincidental cases that ar ...

in -dimensional space contain a subset of points that form the vertices of a neighborly polytope.. Grünbaum attributes the key lemma in this result, that every set of points contains the vertices of a -vertex cyclic polytope, to Micha Perles.

References

{{reflist Polyhedral combinatorics