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

, a -neighborly polytope is a convex polytope 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 b ...

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

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

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 In statistics, a normal distribution or Gaussian distribution is a type of continuous probability distribution for a real-valued random variable. The general form of its probability density function is : f(x) = \frac e^ The parameter \mu i ...

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

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