Neighborly polytope

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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 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=\lfloor d/2 \rfloor. If we exclude simplices, this is the maximum possible k: in fact, every polytope that is k-neighborly for some k\ge 1 + \lfloor d/2 \rfloor is a simplex.[1]

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 (tt2, ..., td) in d-dimensional space are automatically neighborly. Theodore Motzkin conjectured that all neighborly polytopes are combinatorially equivalent to cyclic polytopes.[2] 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.[3]

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.[4]

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} \le \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=\lfloor d/2\rfloor and final term of the sum should be halved if d is even.[5] According to the upper bound theorem of McMullen (1970),[6] 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 imples 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.[7]

References[edit]

  1. ^ Grünbaum, Branko (2003), Kaibel, Volker; Klee, Victor; Ziegler, Günter M., eds., Convex Polytopes, Graduate Texts in Mathematics 221 (2nd ed.), Springer-Verlag, p. 123, ISBN 0-387-00424-6 .
  2. ^ Gale, David (1963), "Neighborly and cyclic polytopes", in Klee, Victor, Convexity, Seattle, 1961, Symposia in Pure Mathematics 7, American Mathematical Society, pp. 225–233, ISBN 978-0-8218-1407-9 .
  3. ^ Shermer, Ido (1982), "Neighborly polytopes", Israel Journal of Mathematics 43 (4): 291–311, 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, doi:10.1073/pnas.0502258102 .
  5. ^ Ziegler, Günter M. (1995), Lectures on Polytopes, Graduate Texts in Mathematics 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: 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 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.