多面体組合せ論

多面体組合せ論は、組合せ論と離散幾何学の範囲内の数学の分野であり、凸多面体と高次元凸多面体の面を数えたり記述したりする問題を研究します。

多面体組合せ論の研究は、2つの異なる分野に分かれます。この分野の数学者は、多面体の組合せ論を研究します。たとえば、任意の多面体または多面体の特定の重要なサブクラスにおける高次元の頂点、辺、面の数の関係を記述する不等式を求めたり、接続性や直径（任意の頂点から他の頂点に到達するために必要なステップ数）など、多面体のその他の組合せ特性を研究したりします。さらに、多くのコンピューター科学者は、整数計画問題から生じる特定の多面体（特に、頂点が超立方体のサブセットである0-1多面体）の面の正確な記述に関する研究を表すために「多面体組合せ論」というフレーズを使用します。

凸多面体Pの面は、Pと閉半空間Hとの交差として定義され、 Hの境界にはPの内点が含まれない。面の次元はこの包の次元である。0 次元の面は頂点そのものであり、1 次元の面 (辺 と呼ばれる)は頂点のペアを結ぶ線分である。この定義には、空集合と多面体P全体も面として含まれることに注意されたい。P自体が次元d を持つ場合、次元d − 1 を持つPの面はPのファセット と呼ばれ、次元d − 2を持つ面は尾根 と呼ばれる。^[1] Pの面は包含によって部分的に順序付けられ、最上位要素としてP自身を持ち、最下位要素として空集合を 持つ面格子を形成する。

多面体組合せ論における重要なツールは、多面体のƒ ベクトル^[2]である。これはベクトル ( f ₀ , f ₁ , ..., f _{d  − 1} ) であり、f _{i は}多面体のi次元特徴の数である。たとえば、立方体には8 つの頂点、12 の辺、6 つの面があるため、その ƒ ベクトルは (8,12,6) である。双対多面体には、同じ数字が逆の順序で並んだ ƒ ベクトルがある。したがって、たとえば、立方体の双対である正八面体の ƒ ベクトルは (6,12,8) である。配置行列には、正多面体の f ベクトルが対角要素として含まれる。

拡張ƒ ベクトルは、 ƒ ベクトルの両端に 1 を連結して形成され、面格子のすべてのレベルにあるオブジェクトの数を数えます。ベクトルの左側では、f ₋₁  = 1 は空集合を面として数え、右側では、f _d  = 1 はP自体を数えます。立方体の場合、拡張 ƒ ベクトルは (1,8,12,6,1) で、八面体の場合は (1,6,12,8,1) です。これらの例の多面体のベクトルは単峰性(左から右の順に係数が最大まで増加してから減少する) ですが、これが当てはまらない高次元多面体もあります。^[3]

単体多面体（すべての面が単体である多面体）の場合、これらのベクトルを変換して、hベクトルと呼ばれる別のベクトルを生成すると便利なことがよくあります。 ƒ ベクトルの項（最後の 1 を省略）を多項式 ƒ( x ) = Σ f _i x ^{d  −  i  − 1}の係数として解釈すると（たとえば、八面体の場合、多項式 ƒ( x ) =  x ³  + 6 x ²  + 12 x  + 8 になります）、hベクトルには多項式h ( x ) = ƒ( x − 1)の係数がリストされます （この場合も、八面体の場合、h ( x ) =  x ³  + 3 x ²  + 3 x  + 1 になります）。^[4]ジーグラーは、「単体多面体に関するさまざまな問題では、hベクトルはƒベクトルよりも面数に関する情報をエンコードするはるかに便利で簡潔な方法である」と書いています。

多面体のƒベクトルの係数間の最も重要な関係はオイラーの公式Σ(−1) ⁱ f _i = 0であり、ここで和の項は拡張されたƒベクトルの係数の範囲にわたります。 3次元では、拡張されたƒベクトル（1、v、e、f、1）の左端と右端の2つの1を式の右側に移動すると、この恒等式はより馴染みのある形式v − e + f = 2に変換されます。3次元多面体の各面には少なくとも3つの辺があるという事実から、2倍数えると2e≥3fとなり、この不等式を使用してオイラーの公式からeとfを消去すると、さらに不等式e≤3v−6およびf≤2v−4が導かれます。双対性により、 e≤3f − 6およびv≤2f − 4です。シュタイニッツの定理から、これらの等式と不等式を満たす任意の3次元整数ベクトルは、凸多面体のƒベクトルであることが分かります。^[5]

高次元では、多面体の面の数の他の関係も重要になります。これには、単体多面体のhベクトルで表現されるデーン・ゾンマービル方程式が含まれます。これは、すべてのkに対してh _k = h _{d − k}という単純な形をとります。k = 0の場合のこれらの方程式のインスタンスはオイラーの公式と同等ですが、d > 3 の場合、これらの方程式の他のインスタンスは互いに線形独立であり、hベクトル (したがって ƒ ベクトルも) を追加の方法で制約します。^[4]

多面体の面数に関するもう一つの重要な不等式は、マクマレン (1970) によって最初に証明された上界定理によって与えられ、これは、 n個の頂点を持つd次元多面体が持つことのできる他の次元の面の数は、同じ数の頂点を持つ隣接多面体の最大で同じ数であるということを述べています。

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

ここでアスタリスクは、 dが偶数の場合に和の最終項が半分になることを意味します。 ^[6]漸近的には、これはすべての次元の面が最大で存在することを意味します。 ${\displaystyle \scriptstyle O(n^{\lfloor d/2\rfloor })}$

4次元であっても、凸多面体の可能なƒベクトルの集合は4次元整数格子の凸部分集合を形成せず、これらのベクトルの可能な値については多くのことが不明のままである。^[7]

研究者たちは、多面体の面の数を調査するとともに、多面体の頂点と辺から得られるグラフ（ 1 スケルトン）の記述など、多面体の他の組み合わせ特性も研究してきました。

バリンスキーの定理によれば、任意のd次元凸多面体からこのようにして得られるグラフはd頂点連結である。^[8] 3次元多面体の場合、この性質と平面性は多面体のグラフを正確に特徴付けるために使用できる。シュタイニッツの定理によれば、G が3 次元多面体の骨格であるためには、G が3 頂点連結平面グラフでなければならない。^[9]

Blind & Mani-Levitska (1987) の定理 (以前はMicha Perlesによって推測されていた) によれば、単純多面体の面構造はそのグラフから再構築できる。つまり、与えられた無向グラフが単純多面体のスケルトンである場合、これが成り立つ多面体は (組み合わせ同値性を除いて) 1 つだけである。これは、グラフが完全グラフである (単純でない) 隣接多面体とは際立った対照をなしている。同じグラフに対して多くの異なる隣接多面体が存在する可能性がある。一意のシンクの向きに基づくこの定理の別の証明はKalai (1988) によって与えられ、Friedman (2009) は、この定理を使用して、単純多面体の面格子をそのグラフから再構築するための多項式時間アルゴリズムを導出する方法を示した。しかし、与えられたグラフまたは格子が単純多面体の面格子として実現できるかどうかをテストすることは、（極性によって）単体多面体の実現と同等であり、これはアディプラシトとパドロール（2017）によって実数の存在理論に対して完全であることが示されました。

線形計画法の単体法の文脈では、多面体の直径、つまり任意の頂点から他の頂点への経路で到達するために必要な最小の辺数を理解することが重要です。線形計画の線形不等式システムは、プログラムのすべての実行可能な解を表す多面体の面を定義し、単体法はこの多面体内の経路をたどることで最適解を見つけます。したがって、直径は、この方法に必要なステップ数の下限を提供します。現在では反証されているヒルシュ予想は、固定された次元と面数を持つ多面体の直径がどれだけ大きくなるかについての強い（線形）境界を示唆していました。^[10]それらの直径の弱い（およびにおける準多項式）上限は既知であり、^[11]多面体の特別なクラスに対するヒルシュ予想の証明も知られています。^[12]${\displaystyle d}$ ${\displaystyle n}$${\displaystyle d}$${\displaystyle n}$

与えられた多面体の頂点の数がある自然数kで制限されるかどうかを決定することは計算上困難な問題であり、計算量クラスPPに対して完全である。^[13]

整数計画法の切断面法のコンテキストでは、組合せ最適化問題の解に対応する頂点を持つ多面体の面を正確に記述できることが重要です。多くの場合、これらの問題にはバイナリベクトルで記述できる解があり、対応する多面体の頂点座標はすべて 0 または 1 です。

例として、バーコフ多面体、つまり順列行列の凸結合から形成できるn  ×  n行列の集合を考えてみましょう。同様に、その頂点は完全な二部グラフのすべての完全マッチングを表すものと考えることができ、この多面体上の線形最適化問題は二部最小重み完全マッチング問題として解釈できます。バーコフ・フォン・ノイマンの定理によれば、この多面体は 2 種類の線形不等式または等式で表すことができます。まず、各行列セルには、このセルの値が非負であるという制約があります。次に、行列の各行または各列には、その行または列のセルの合計が 1 になるという制約があります。行と列の制約は、バーコフ多面体が存在する次元n ²  − 2 n + 1の線形部分空間を定義し 、非負性制約はその部分空間内のバーコフ多面体の面を定義します。

しかし、バーコフ多面体は、その面の完全な記述が可能である点で珍しい。他の多くの0-1多面体では、面の数が指数関数的または超指数関数的であり、面の部分的な記述しか利用できない。^[14]

• 抽象多面体
• 組合せ可換代数
• マトロイド多面体
• 多面体の順序
• 単体球
• 安定マッチング多面体

• カライ、ギル (2008)、凸多面体に関する 5 つの未解決問題。