近隣多面体

幾何学と多面体組合せ論において、 $k$ 近傍多面体とは、 $k$ 個以下の頂点のすべての集合が面を形成する凸多面体です。たとえば、 2 近傍多面体とは、すべての頂点のペアが辺で接続され、完全グラフを形成する多面体です。 5 つ以上の頂点を持つ 2 近傍多面体は、4 次元以上の空間にのみ存在し、一般に $k近傍多面体 ($ 単体以外) には $2$ $k$ 以上の次元が必要です。 $d単体は$ $d$ 近傍です。 $k$ $= ⌊$ $d$ $⁄$ $2$ $⌋$ に対して $k$ 近傍である場合、 $k$ を指定せずに多面体は近傍であると言われます。単体を除けば、これが $k$ の最大値です。実際、ある $k$ $\geq 1 + ⌊$ $d$ $⁄$ $2$ $⌋に対して$ $k$ 近傍となる多面体はすべて単体です。^[1] $.mw-parser-output .frac{white-space:nowrap}.mw-parser-output .frac .num,.mw-parser-output .frac .den{font-size:80%;line-height:0;vertical-align:super}.mw-parser-output .frac .den{vertical-align:sub}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}$

$k$ $\geq 3の$ $k$ 近傍多面体では、すべての 2 面は三角形でなければならず、 $k$ $\geq 4の$ $k$ 近傍多面体では、すべての 3 面は四面体でなければなりません。より一般的には、任意の $k近傍多面体において、$ $k$ 未満の次元のすべての面は単体です。

$d$ 次元空間のモーメント曲線 $($ $t$ $,$ $t$ $2$ $, \dots,$ $t$ $d$ $)$ 上の有限点集合の凸包として形成される巡回多面体は、自動的に隣接多面体となる。セオドア・モツキンは、すべての隣接多面体は巡回多面体と組合せ的に同値であると予想した。 ^[2]しかし、この予想に反して、巡回ではない隣接多面体も多数存在する。組合せ的に異なる隣接多面体の数は、多面体の頂点数と次元の両方で超指数関数的に増加する。^[3]

次元に比例する点の数を持つガウス分布から抽出されたランダムな点の集合の凸包は、次元に比例する値 $kに対して高い確率で$ $k近傍になります。$ ^[4]

偶数次元の近傍多面体のすべての次元の面の数は、デーン・ゾンマービル方程式によってその次元と頂点の数のみから決定される。k次元 $の$ 面の数 $f k$ は、不等式を満たす。

f_{k-1}\leq \sum _{i=0}^{d/2}{}^{*}\left({\binom {di}{ki}}+{\binom {i }{k-d+i}}\right){\binom {nd-1+i}{i}},

ここでアスタリスクは、和が $i = ⌊ d ⁄ 2 ⌋で終了し、$ $d$ が偶数の場合は和の最終項が半分になることを意味します。 ^{[5] McMullen（1970）の}上界定理によれば、^{[6]近隣多面体は、任意の} $n$ 頂点 $d$ 次元凸多面体の面の最大可能数を実現します。

ハッピーエンド問題の一般化版は高次元の点集合に適用され、あらゆる次元 $d$ とあらゆる $n > d$ $に対して、 d$ 次元空間の一般的な位置にあるすべての $m$ 個の点には、近傍多面体の頂点を形成する $n$ 個の点のサブセットが含まれるという性質を持つ数 $m (d, n)が存在することを意味します。$ ^[7]

参考文献

^ グリュンバウム、ブランコ(2003)、カイベル、フォルカー;ヴィクトル・クレー; Ziegler、Günter M. (編)、Convex Polytopes、Graduate Texts in Mathematics、vol. 221 (第 2 版)、Springer-Verlag、p. 123、ISBN 0-387-00424-6。
^ ゲイル、デイビッド(1963)、「近隣多面体と巡回多面体」、クリー、ビクター(編)、凸性、シアトル、1961、純粋数学シンポジウム、第 7 巻、アメリカ数学会、pp. 225–233、ISBN 978-0-8218-1407-9。
^ シェマー、イド（1982）、「近隣多面体」、イスラエル数学ジャーナル、43（4）：291–314、doi：10.1007 / BF02761235。
^ Donoho, David L. ; Tanner, Jared (2005)、「高次元におけるランダム投影単体の近傍性」、米国科学アカデミー紀要、102 (27): 9452–9457、doi : 10.1073/pnas.0502258102、PMC 1172250、PMID 15972808 。
^ ジーグラー、ギュンター・M. (1995)、多面体に関する講義、数学の大学院テキスト、第152巻、シュプリンガー・フェアラーク、pp. 254–258、ISBN 0-387-94365-X。
^ マクマレン、ピーター（1970）、「凸多面体の面の最大数」、Mathematika、17（2）：179–184、doi：10.1112 / S0025579300002850。
^ グリュンバウム、ブランコ(2003)、カイベル、フォルカー;ヴィクトル・クレー; Ziegler、Günter M. (編)、Convex Polytopes、Graduate Texts in Mathematics、vol. 221 (第 2 版)、Springer-Verlag、p. 126、ISBN 0-387-00424-6グリュンバウムは、この結果における重要な補題である、 $d + 3点のすべての集合には$ $(d + 2)$ 頂点の巡回多面体の頂点が含まれているという補題を、ミカ・パールズに帰している。

[1] グリュンバウム、ブランコ(2003)、カイベル、フォルカー;ヴィクトル・クレー; Ziegler、Günter M. (編)、Convex Polytopes、Graduate Texts in Mathematics、vol. 221 (第 2 版)、Springer-Verlag、p. 123、ISBN 0-387-00424-6。

[2] ゲイル、デイビッド(1963)、「近隣多面体と巡回多面体」、クリー、ビクター(編)、凸性、シアトル、1961、純粋数学シンポジウム、第 7 巻、アメリカ数学会、pp. 225–233、ISBN 978-0-8218-1407-9。

[3] シェマー、イド（1982）、「近隣多面体」、イスラエル数学ジャーナル、43（4）：291–314、doi：10.1007 / BF02761235。

[4] Donoho, David L. ; Tanner, Jared (2005)、「高次元におけるランダム投影単体の近傍性」、米国科学アカデミー紀要、102 (27): 9452–9457、doi : 10.1073/pnas.0502258102、PMC 1172250、PMID 15972808 。

[5] ジーグラー、ギュンター・M. (1995)、多面体に関する講義、数学の大学院テキスト、第152巻、シュプリンガー・フェアラーク、pp. 254–258、ISBN 0-387-94365-X。

[6] マクマレン、ピーター（1970）、「凸多面体の面の最大数」、Mathematika、17（2）：179–184、doi：10.1112 / S0025579300002850。

[7] グリュンバウム、ブランコ(2003)、カイベル、フォルカー;ヴィクトル・クレー; Ziegler、Günter M. (編)、Convex Polytopes、Graduate Texts in Mathematics、vol. 221 (第 2 版)、Springer-Verlag、p. 126、ISBN 0-387-00424-6グリュンバウムは、この結果における重要な補題である、 $d + 3点のすべての集合には$ $(d + 2)$ 頂点の巡回多面体の頂点が含まれているという補題を、ミカ・パールズに帰している。