Neighborly polytope
{{short description|Convex polytope where all sets of ≤ k vertices form a face}}
In geometry and polyhedral combinatorics, a {{mvar|k}}-neighborly polytope is a convex polytope in which every set of {{mvar|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 {{mvar|k}}-neighborly polytope (other than a simplex) requires a dimension of {{math|2k}} or more. A {{mvar|d}}-simplex is {{mvar|d}}-neighborly. A polytope is said to be neighborly, without specifying {{mvar|k}}, if it is {{mvar|k}}-neighborly for {{math|1=k = ⌊{{frac|d|2}}⌋}}. If we exclude simplices, this is the maximum possible {{mvar|k}}: in fact, every polytope that is {{mvar|k}}-neighborly for some {{math|k ≥ 1 + ⌊{{frac|d|2}}⌋}} is a simplex.{{citation
| last = Grünbaum | first = Branko | authorlink = Branko Grünbaum
| edition = 2nd
| editor1-last = Kaibel | editor1-first = Volker
| editor2-last = Klee | editor2-first = Victor | editor2-link = Victor Klee
| editor3-last = Ziegler | editor3-first = Günter M. | editor3-link = Günter M. Ziegler
| isbn = 0-387-00424-6
| publisher = Springer-Verlag
| series = Graduate Texts in Mathematics
| title = Convex Polytopes
| title-link = Convex Polytopes
| volume = 221
| year = 2003|page=123}}.
In a {{mvar|k}}-neighborly polytope with {{math|k ≥ 3}}, every 2-face must be a triangle, and in a {{mvar|k}}-neighborly polytope with {{math|k ≥ 4}}, every 3-face must be a tetrahedron. More generally, in any {{mvar|k}}-neighborly polytope, all faces of dimension less than {{mvar|k}} are simplices.
The cyclic polytopes formed as the convex hulls of finite sets of points on the moment curve {{math|(t, t{{sup|2}}, …, t{{sup|d}})}} in {{mvar|d}}-dimensional space are automatically neighborly. Theodore Motzkin conjectured that all neighborly polytopes are combinatorially equivalent to cyclic polytopes.{{citation
| last = Gale | first = David | author-link = David Gale
| contribution = Neighborly and cyclic polytopes
| editor-last = Klee | editor-first = Victor | editor-link = Victor Klee
| isbn = 978-0-8218-1407-9
| pages = 225–233
| publisher = American Mathematical Society
| series = Symposia in Pure Mathematics
| title = Convexity, Seattle, 1961
| volume = 7
| year = 1963}}. 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.{{citation
| last = Shemer | first = Ido
| doi = 10.1007/BF02761235
| issue = 4
| journal = Israel Journal of Mathematics
| pages = 291–314
| title = Neighborly polytopes
| volume = 43
| year = 1982
}}.
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 {{mvar|k}}-neighborly for a value {{mvar|k}} that is also proportional to the dimension.{{citation
| last1 = Donoho | first1 = David L. | author1-link = David Donoho
| last2 = Tanner | first2 = Jared
| doi = 10.1073/pnas.0502258102
| issue = 27
| journal = Proceedings of the National Academy of Sciences of the United States of America
| pages = 9452–9457
| title = Neighborliness of randomly projected simplices in high dimensions
| volume = 102
| year = 2005 | pmid=15972808 | pmc=1172250| doi-access = free | bibcode = 2005PNAS..102.9452D }}.
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 {{mvar|k}}-dimensional faces, {{mvar|f{{sub|k}}}}, satisfies the inequality
:
where the asterisk means that the sums ends at {{math|1=i = ⌊{{frac|d|2}}⌋}} and final term of the sum should be halved if {{mvar|d}} is even.{{citation
| last = Ziegler | first = Günter M. | author-link = Günter M. Ziegler
| isbn = 0-387-94365-X
| publisher = Springer-Verlag
| series = Graduate Texts in Mathematics
| title = Lectures on Polytopes
| volume = 152
| year = 1995
| pages = 254–258}}. According to the upper bound theorem of {{harvtxt|McMullen|1970}},{{citation
| last = McMullen | first = Peter
| journal = Mathematika
| pages = 179–184
| title = The maximum numbers of faces of a convex polytope
| volume = 17
| year = 1970
| issue = 2
| doi=10.1112/S0025579300002850
| doi-access =
}}. neighborly polytopes achieve the maximum possible number of faces of any {{mvar|n}}-vertex {{mvar|d}}-dimensional convex polytope.
A generalized version of the happy ending problem applies to higher-dimensional point sets, and implies that for every dimension {{mvar|d}} and every {{math|n > d}} there exists a number {{math|m(d,n)}} with the property that every {{mvar|m}} points in general position in {{mvar|d}}-dimensional space contain a subset of {{mvar|n}} points that form the vertices of a neighborly polytope.{{citation
| last = Grünbaum | first = Branko | authorlink = Branko Grünbaum
| edition = 2nd
| editor1-last = Kaibel | editor1-first = Volker
| editor2-last = Klee | editor2-first = Victor | editor2-link = Victor Klee
| editor3-last = Ziegler | editor3-first = Günter M. | editor3-link = Günter M. Ziegler
| isbn = 0-387-00424-6
| publisher = Springer-Verlag
| series = Graduate Texts in Mathematics
| title = Convex Polytopes
| volume = 221
| year = 2003|page=126}}. Grünbaum attributes the key lemma in this result, that every set of {{math|d + 3}} points contains the vertices of a {{math|(d + 2)}}-vertex cyclic polytope, to Micha Perles.
References
{{reflist}}