Conductivity of transparency

2013-01-09T13:15:16Z

130.104.205.193: /* Examples */

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 [[vertex (geometry)|vertices]] is connected by an [[edge (geometry)|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 2''k'' or more. A [[simplex|''d''-simplex]] is ''d''-neighborly. A polytope is said to be neighborly, without specifying ''k'', if it is ''k''-neighborly for <math>k=\lfloor d/2 \rfloor</math>. If we exclude simplices, this is the maximum possible ''k'': in fact, every polytope that is ''k''-neighborly for some ''<math>k\ge 1 + \lfloor d/2 \rfloor</math>'' is a simplex.<ref>{{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=123}}.</ref>

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 [[simplex|simplices]].

The [[cyclic polytope]]s formed as the convex hulls of finite sets of points on the [[moment curve]] (''t'', ''t''2, ..., ''t''''d'') in ''d''-dimensional space are automatically neighborly. [[Theodore Motzkin]] conjectured that all neighborly polytopes are combinatorially equivalent to cyclic polytopes.<ref>{{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}}.</ref> 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.<ref>{{citation
| last = Shermer | first = Ido
| doi = 10.1007/BF02761235
| issue = 4
| journal = Israel Journal of Mathematics
| pages = 291–311
| title = Neighborly polytopes
| volume = 43
| year = 1982}}.</ref>

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.<ref>{{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}}.</ref>

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

:<math>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},</math>

where the asterisk means that the sums ends at <math>i=\lfloor d/2\rfloor</math> and final term of the sum should be halved if ''d'' is even.<ref>{{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}}.</ref> According to the [[upper bound theorem]] of {{harvtxt|McMullen|1970}},<ref>{{citation
| last = McMullen | first = Peter
| journal = Mathematika
| pages = 179–184
| title = The maximum numbers of faces of a convex polytope
| volume = 17
| year = 1970
| doi=10.1112/S0025579300002850}}.</ref> 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.<ref>{{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 ''d'' + 3 points contains the vertices of a (''d'' + 2)-vertex cyclic polytope, to Micha Perles.</ref>

==References==
{{reflist}}

[[Category:Polyhedral combinatorics]]

formulasearchengine - User contributions [en]

Conductivity of transparency