ゲイルダイアグラム

多面体組合せ論という数学の分野では、ゲール変換は任意の凸多面体の頂点を異なる次元の空間、つまり多面体のゲール図のベクトルまたは点の集合に変換する。これは、頂点の少ない高次元多面体を、同じ数の点を持つ集合に変換して、はるかに低い次元の空間に記述するために使用できる。このプロセスは逆にして、ゲール図から望ましい特性を持つ多面体を構築することもできる。ゲール変換とゲール図は、 1956 年に近隣多面体に関する論文でこれらの方法を紹介したDavid Galeにちなんで名付けられました。^[1]

頂点を持つ次元多面体が与えられた場合、各頂点の直交座標に 1 を付加して、次元の列ベクトルを取得します。これらの列ベクトルの行列は次元を持ち、階数 で射影的な、空間から空間への線形写像を定義します。の核は、係数の合計がゼロになる元の頂点間の線形依存関係を記述します。この核は次元 です。 のゲール変換は次元 の行列であり、その列ベクトルはの核に対して選択された基底です。したがって、 には次元 の行ベクトルがあります。これらの行ベクトルは多面体のゲール図を形成します。核の基底の選択が異なると、線形変換によってのみ結果が変わります。^[2]${\displaystyle d}$${\displaystyle n}$${\displaystyle (d+1)}$ ${\displaystyle A}$${\displaystyle n}$${\displaystyle (d+1)\times n}$${\displaystyle n}$${\displaystyle (d+1)}$${\displaystyle d+1}$${\displaystyle A}$${\displaystyle n}$${\displaystyle nd-1}$${\displaystyle A}$${\displaystyle B}$${\displaystyle n\times (nd-1)}$${\displaystyle A}$${\displaystyle B}$${\displaystyle n}$ ${\displaystyle nd-1}$

ゲール図のベクトルは元の次元多面体の頂点と自然一対一であるが、 の場合はゲール図の次元が小さくなることに注意してください。 ${\displaystyle n}$${\displaystyle d}$${\displaystyle n\leq 2d}$

多面体の頂点の適切な部分集合が多面体の面の頂点集合を形成するのは、ゲイル変換のベクトルの補集合が相対内部に原点を含む凸包を持つ場合に限られます。同様に、頂点の部分集合が面を形成するのは、そのアフィンスパンが補ベクトルの凸包と交差しない場合に限られます。^[3]

ゲール変換は線形変換までしか定義されていないため、その非ゼロベクトルはすべて次元単位ベクトルに正規化できます。線形ゲール図は、すべてのベクトルがゼロまたは単位ベクトルであるゲール変換の正規化バージョンです。^[4]${\displaystyle (nd-1)}$

多面体のゲイル図、つまり -次元空間の単位ベクトルの集合が与えられた場合、すべてのベクトルを避ける原点を通る- 次元部分空間と、原点を通らない平行部分空間を選択できます。次に、原点からへの中心射影により、 - 次元点の集合が生成されます。この射影では、どのベクトルがその上にあるか、どのベクトルがその下にあるかに関する情報は失われますが、この情報は各点に符号 (正、負、ゼロ) または同等の色 (黒、白、灰色) を割り当てることで表すことができます。結果として得られる符号付きまたは色付きの点の集合は、与えられた多面体のアフィン ゲイル図です。この構成には、ゲイル変換に比べて、与えられた多面体の構造を表すのに 1 つ少ない次元を使用するという利点があります。^[5]${\displaystyle n}$${\displaystyle (nd-1)}$${\displaystyle (nd-2)}$${\displaystyle S}$${\displaystyle S'}$${\displaystyle S'}$${\displaystyle (nd-2)}$${\displaystyle S}$

ゲール変換と線形およびアフィンゲール図も、有向マトロイドの双対性によって記述できます。^[6] 線形図と同様に、頂点のサブセットが面を形成するのは、補集合の各正ベクトルに非負の値を割り当て、補集合の各負ベクトルに非正の値を割り当てるアフィン関数（非ゼロの可能性のある定数項を持つ線形関数）が存在しないときのみです。^[7]

ゲール図は、頂点の数が次元よりわずかに大きい多面体を説明するのに特に効果的です。

最小の頂点を持つ次元多面体は単体です。この場合、線型ゲール図は0次元であり、ゼロベクトルのみで構成されます。アフィン図には灰色の点があります。^[8]${\displaystyle d}$${\displaystyle n=d+1}$${\displaystyle n}$

頂点を持つ次元多面体では、線型ゲール図は 1 次元であり、各点を表すベクトルは 3 つの数値、、 のいずれかになります。アフィン図では、点は 0 次元であるため、位置の値なしで、符号または色のみで表すことができます。多面体を表すには、図に 0 以外の符号を持つ点が少なくとも 2 つ必要です。2 つの図は、各符号の点の数が同じである場合、またはすべての符号を反転することで互いに取得できる場合、多面体の同じ組み合わせ同値類を表します。^[8]${\displaystyle d}$${\displaystyle n=d+2}$${\displaystyle -1}$${\displaystyle 0}$${\displaystyle +1}$

の場合、唯一の可能性は、各非ゼロ符号の2つの点であり、凸四辺形 を表します。 の場合、2つのゲール図が考えられます。各非ゼロ符号の2つの点と1つのゼロ点を持つ図は四角錐 を表し、1つの非ゼロ符号の2つの点と他の符号の3つの点を持つ図は三角錐 を表します。^[8]${\displaystyle d=2}$${\displaystyle d=3}$

一般に、 を持つ異なるゲール図の数は であり、次元多面体の頂点の組み合わせ同値類の数はである。^[8]${\displaystyle n=d+2}$${\displaystyle d}$${\displaystyle n}$${\displaystyle \lfloor d^{2}/4\rfloor }$

頂点を持つ次元多面体では、線型ゲール図は単位円（単位ベクトル）上の点とその中心から構成されます。アフィンゲール図は、線上のラベル付き点または点の集まりから構成されます。頂点の場合とは異なり、2つのゲール図が同じ多面体を表すかどうかを判断するのは完全に簡単ではありません。^[8]${\displaystyle d}$${\displaystyle n=d+3}$${\displaystyle n=d+2}$

6 つの頂点を持つ 3 次元多面体は、元の多面体の次元が視覚化できるほど低いが、ゲール図によって次元削減効果が依然として得られる自然な例です。

• 正八面体は、単位円（八面体の反対の頂点のペアを表す）上の3組の等しい点で構成される線型ゲール図を持ち、円を 未満の角度の弧に分割します。そのアフィンゲール図は、直線上の3組の等しい符号の点で構成され、中央のペアは外側の2組と反対の符号を持ちます。^[9]${\displaystyle \pi}$
• 三角柱には、円周上に正反対の3組の6つの点からなる線型ゲール図があり、各組は柱の2つの正方形の面で隣接する頂点を表します。対応するアフィンゲール図は、正八面体のように線上に3組の点がありますが、各組には各符号の点が1つずつあります。^[10]

ゲイル図は、頂点を持つ次元多面体の完全な組み合わせ列挙を提供するために使用され、 ^[11]珍しい特性を持つ多面体を構築するために使用されています。これには以下が含まれます。 ${\displaystyle d}$${\displaystyle n=d+3}$

• パールズ多面体は、有理直交座標では実現できない12の頂点を持つ8次元多面体である。ミカ・パールズはパールズ構成（平面上の9つの点と9つの直線で、有理座標では実現できない）から、3つの点を2倍にして、結果として得られる12の点に符号を割り当て、結果として得られる符号付き構成を多面体のゲール図として扱うことでこれを構築した。無理多面体は4次元まで低いことが知られているが、それより少ない頂点を持つものは知られていない。^[12]
• クラインシュミット多面体は、ピーター・クラインシュミットによって構築された、8 つの頂点、10 の四面体面、および 1 つの八面体面を持つ 4 次元多面体です。八面体面は正八面体と同じ組み合わせ構造を持ちますが、正八面体になることはできません。^[13]この多面体の 2 つのコピーを八面体面で接着すると、10 頂点の多面体が生成されますが、この多面体では、実現のいくつかのペアが連続的に互いに変形することはできません。^[14]
• 四角錐上の双錐は、頂点図形の1つ（中心の錐の頂点）の形状を規定できないという二重の性質を持つ、7つの頂点を持つ4次元多面体である。これはもともとデイビッド・W・バーネットによって発見され、ゲール図を用いてベルント・シュトゥルムフェルスによって再発見された。^[15]
• 小さな「隣接しない多面体」、つまり普遍頂点を持たない多面体と、すべての頂点が多面体の内部を通過する対角線に接する「照明された多面体」の構築。交差多面体はこれらの特性を持つが、16次元以上では頂点の少ない照明された多面体が存在し、6次元以上では頂点の最も少ない照明された多面体は単体である必要はない。構築にはゲイル図が関係する。^[16]

• ゲイル、デイビッド (1956)、「凸多面体上の隣接頂点」、線形不等式および関連システム、数学研究年報、第 38 号、プリンストン大学出版局、プリンストン、ニュージャージー、pp. 255–263、MR  0085552
• Sturmfels, Bernd (1988)、「頂点数が少ない多面体へのアフィン ゲール図の応用」、SIAM Journal on Discrete Mathematics、1 (1): 121–133、doi :10.1137/0401014、MR  0936614
• Thomas, Rekha R. (2006)、「第 5 章: ゲイル図」、幾何組合せ論の講義、学生数学図書館、第 33 巻、高等研究所 (IAS)、プリンストン、ニュージャージー、pp. 37–45、doi :10.1090/stml/033、ISBN 0-8218-4140-8、MR  2237292
• Wotzlaw, Ronald F.; Ziegler, Günter M. (2011)、「失われた反例と照明付き多面体に関する問題」、American Mathematical Monthly、118 (6): 534–543、CiteSeerX  10.1.1.249.4822、doi :10.4169/amer.math.monthly.118.06.534、MR  2812284、S2CID  15007113
• ジーグラー、ギュンター M. (1995)、「第 6 章: 双対性、ゲイル図、およびアプリケーション」、多面体に関する講義、Graduate Texts in Mathematics、第 152 巻、ニューヨーク: Springer-Verlag、pp. 149–190、doi :10.1007/978-1-4613-8431-1_6、ISBN 0-387-94365-X、MR  1311028