Misplaced Pages

Neighborly polytope

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Convex polytope where all sets of ≤ k vertices form a face

In geometry and polyhedral combinatorics, a k-neighborly polytope is a convex polytope in which every set of k 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 k-neighborly polytope (other than a simplex) requires a dimension of 2k or more. A d-simplex is d-neighborly. A polytope is said to be neighborly, without specifying k, if it is k-neighborly for k = ⌊d⁄2⌋. If we exclude simplices, this is the maximum possible k: in fact, every polytope that is k-neighborly for some k ≥ 1 + ⌊d⁄2⌋ is a simplex.

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

The cyclic polytopes formed as the convex hulls of finite sets of points on the moment curve (t, t, …, t) in d-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 k-neighborly for a value k 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 k-dimensional faces, fk, satisfies the inequality

f k − 1 ≤ ∑ i = 0 d / 2 ∗ ( ( d − i k − i ) + ( i k − d + i ) ) ( n − d − 1 + i i ) , {\displaystyle f_{k-1}\leq \sum _{i=0}^{d/2}{}^{*}\left({\binom {d-i}{k-i}}+{\binom {i}{k-d+i}}\right){\binom {n-d-1+i}{i}},}

where the asterisk means that the sums ends at i = ⌊d⁄2⌋ and final term of the sum should be halved if d is even. According to the upper bound theorem of McMullen (1970), neighborly polytopes achieve the maximum possible number of faces of any n-vertex d-dimensional convex polytope.

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

References

  1. Grünbaum, Branko (2003), Kaibel, Volker; Klee, Victor; Ziegler, Günter M. (eds.), Convex Polytopes, Graduate Texts in Mathematics, vol. 221 (2nd ed.), Springer-Verlag, p. 123, ISBN 0-387-00424-6.
  2. Gale, David (1963), "Neighborly and cyclic polytopes", in Klee, Victor (ed.), Convexity, Seattle, 1961, Symposia in Pure Mathematics, vol. 7, American Mathematical Society, pp. 225–233, ISBN 978-0-8218-1407-9.
  3. Shemer, Ido (1982), "Neighborly polytopes", Israel Journal of Mathematics, 43 (4): 291–314, doi:10.1007/BF02761235.
  4. Donoho, David L.; Tanner, Jared (2005), "Neighborliness of randomly projected simplices in high dimensions", Proceedings of the National Academy of Sciences of the United States of America, 102 (27): 9452–9457, Bibcode:2005PNAS..102.9452D, doi:10.1073/pnas.0502258102, PMC 1172250, PMID 15972808.
  5. Ziegler, Günter M. (1995), Lectures on Polytopes, Graduate Texts in Mathematics, vol. 152, Springer-Verlag, pp. 254–258, ISBN 0-387-94365-X.
  6. McMullen, Peter (1970), "The maximum numbers of faces of a convex polytope", Mathematika, 17 (2): 179–184, doi:10.1112/S0025579300002850.
  7. Grünbaum, Branko (2003), Kaibel, Volker; Klee, Victor; Ziegler, Günter M. (eds.), Convex Polytopes, Graduate Texts in Mathematics, vol. 221 (2nd ed.), Springer-Verlag, p. 126, ISBN 0-387-00424-6. Grünbaum attributes the key lemma in this result, that every set of d + 3 points contains the vertices of a (d + 2)-vertex cyclic polytope, to Micha Perles.
Category: