JOVANA
Explore Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

多胞形、面、Euler 關係式與 Dehn-Sommerville

多胞形是最簡單的凸體——有限個點的凸包、面全是平的——但它的面卻服從一套隱藏的記帳法則。我們從頂點與小面爬升到 Euler 關係式,再到鎖死單純多胞形面數的 Dehn-Sommerville 方程組。

多胞形的兩張面孔:凸包與交集

由上一份指南,你已經信得過:緊緻凸體可由它的極點透過 Krein-Milman 定理重建。當那組角點是有限的,得到的就是多胞形。它有兩個等價的定義,而整個主題都建立在它們彼此一致這件事上。V-描述:多胞形是 R^n 中有限多個點的凸包。H-描述:它是有限多個閉半空間的有界交集。Weyl-Minkowski 定理說這兩者定義出完全相同的對象——每個有界的 H-多面體都是它頂點的凸包,反之亦然。

為何兩個都要堅持?因為它們各自把相反的事情變簡單。從 V 這一側,投影或取凸包是平凡的,但讀出小面卻要費工;從 H 這一側,用一條不等式去切是平凡的,但列出頂點卻要費工。R^3 中的立方體是最乾淨的例子:作為凸包它是 conv{(+/-1, +/-1, +/-1)},八個點;作為交集它是 {x : -1 <= x_i <= 1},六條不等式。同一個實體,兩本帳。在兩者之間轉換——頂點列舉對小面列舉——正是理論的計算核心,而且它可能呈指數爆炸。

面是被支撐超平面切出的平片

多胞形的結構活在它的裡,而乾淨的定義要用上指南 1 的工具。一個支撐超平面 H 觸碰多胞形 P 卻不穿過它;交集 F = P ∩ H 就是 P 的一個。依約定,P 自己與空集也算面(這兩個是「非真」面)。每個面又是一個某維度 d 的多胞形。我們按維度命名:0 維面是頂點,1 維面是,(dim P - 1) 維面是小面(facet),(dim P - 2) 維面是脊(ridge)

把面按包含關係排序,就得到面格(face lattice):一個有限的分次偏序集,有最小元(空面)與最大元(P)。這個格是多胞形的組合靈魂:兩個多胞形「在組合上相同」,恰好當它們的面格同構之時,即使其中一個是另一個被拉伸、被剪切後的版本。立方體與一般的長方盒有相同的面格;立方體與正八面體則沒有——但請注意——它們互為對偶,意思是其中之一的面格正是另一個上下顛倒後的樣子。立方體的頂點(8 個)對應八面體的小面(8 個);立方體的小面(6 個)對應八面體的頂點(6 個)。

有兩個結構性事實不斷地發揮作用。其一,面的面仍是 P 的面,且兩個面的交也是面——所以面格確實是一個格。其二,一個 d 維多胞形對每個從 0 到 d 的維度都有面,而且(這正是下一節的引擎)你可以去數它們。我們把這些計數收進 f-向量 f = (f_0, f_1, ..., f_{d-1}),其中 f_k 是 k 維面的個數。對 R^3 中的立方體:f = (8, 12, 6)——八個頂點、十二條邊、六個小面。

Euler 關係式及其推廣

現在迎來第一個奇蹟。對任何凸的 3 維多胞形,面數並非自由的——它們滿足 V - E + F = 2。立方體:8 - 12 + 6 = 2。四面體:4 - 6 + 4 = 2。八面體:6 - 12 + 8 = 2。無論多胞形多麼歪斜,每次都是同一個「2」。這就是 Euler 關係式,而 Euler 多面體公式正是在說:這個交錯和是一個拓撲不變量——凸的 3 維多胞形的邊界是球面 S^2,而 2 正是它的 Euler 示性數。

看清它的乾淨方式,是認識到這條公式並不講凸的形狀,而講它邊界上的胞腔結構。凸多胞形的邊界與球面同胚,而把球面任意三角化(或分胞)都給出相同的交錯計數。所以 Euler 關係式其實是 S^(d-1) 的 Euler 示性數透出來的結果。在一般維度 d,它變成 Euler-Poincare 關係式:f_0 - f_1 + f_2 - ... + (-1)^(d-1) f_{d-1} = 1 - (-1)^d。對 d = 3,右邊是 1 - (-1) = 2,重現 V - E + F = 2;對 d = 4 則得 0,於是 f_0 - f_1 + f_2 - f_3 = 0。

d = 3 :  f_0 - f_1 + f_2            = 1 - (-1)^3 = 2
d = 4 :  f_0 - f_1 + f_2 - f_3      = 1 - (-1)^4 = 0
d = 5 :  f_0 - f_1 + f_2 - f_3 + f_4 = 1 - (-1)^5 = 2

cube  (d=3):  8 - 12 +  6           = 2   ok
24-cell(d=4): 24 - 96 + 96 - 24     = 0   ok
跨維度的 Euler-Poincare 關係式,並驗算兩個多胞形。

單純多胞形與 Dehn-Sommerville 方程組

Euler 只是一條方程。對一類特殊而非常常見的多胞形,方程多得多。一個多胞形稱為單純的(simplicial),若它的每個小面都是單純形——在 R^3 中意指每個面都是三角形,像八面體或正二十面體,而非立方體。單純多胞形是一般情形(把頂點稍微擾動一下,小面就變成單純形),也是最深刻的計數律的正確場景。其對偶概念,即每個頂點恰好落在 d 個小面上的,稱為單形的(simple);立方體是單形的,八面體是單純的,兩者互為對偶。

現在是第二個奇蹟。對一個單純 d 維多胞形,f-向量滿足的不只一條、而是約 d/2 條獨立的線性方程——Dehn-Sommerville 方程組。最俐落的敘述方式要用 h-向量:它是 f-向量的一個可逆改裝,由 sum over i of f_{i-1}(t-1)^(d-i) = sum over i of h_i t^(d-i) 所定義。在那組座標下,Dehn-Sommerville 關係式坍縮成一句令人屏息的話:h-向量是迴文的,對所有 i 都有 h_i = h_{d-i}。這是你光看原始面數絕對猜不到的對稱。

  1. 取八面體,一個單純 3 維多胞形,其 f = (f_0, f_1, f_2) = (6, 12, 8)。
  2. 由 sum f_{i-1}(t-1)^(d-i) = (t-1)^3 + 6(t-1)^2 + 12(t-1) + 8 算出 h-向量,展開得 t^3 + 3t^2 + 3t + 1。
  3. 讀出 h = (h_0, h_1, h_2, h_3) = (1, 3, 3, 1)——就在這裡,迴文的:h_0 = h_3 且 h_1 = h_2。
  4. 對照 Euler:h_0 = 1,而 f 的交錯和如前一致——Dehn-Sommerville 把 Euler 作為它的 h_0 = h_d 那一條含納其中。

多胞形最多能有幾個面?上界定理

Dehn-Sommerville 說的是哪些 f-向量對單純多胞形而言在算術上根本可能;下一個問題是它們能長到多大。固定 d 與頂點數 n。在 n 個頂點上的單純 d 維多胞形中,哪一個有最多小面?答案是迴圈多胞形(cyclic polytope) C(n, d):它是矩量曲線 t -> (t, t^2, ..., t^d) 上 n 個點的凸包。迴圈多胞形是「鄰接的(neighborly)」:任意不超過 d/2 個頂點的子集都構成一個面,這已是可能的極大值,而正是這種極大性把小面數推到頂。

上界定理由 Motzkin 猜測、McMullen 於 1970 年證明,它說迴圈多胞形就是冠軍:在所有具 n 個頂點的單純 d 維多胞形中,C(n, d) 同時把每個 k 的 f_k 都最大化。上界定理並非一則奇談——它是幾何演算法最壞情況分析中那道緊束的約束。當你去界定 R^d 中凸包或 Voronoi 計算的執行時間時,它所提供的面數上限(約 n^(d/2))正是會冒出來的那一項。

對於這裡何者已知、何者未知,要誠實以待。上界定理(天花板)有個搭檔——下界定理(地板,Barnette),它們連同 Dehn-Sommerville 一起被收進著名的 Billera-Lee 與 Stanley 的 g-定理,該定理完整刻畫了究竟哪些整數向量能作為單純多胞形的 f-向量出現。那是一個真正深刻的結果——Stanley 那一半用的是某個複曲簇上的硬 Lefschetz 定理,而非初等組合學。一般(非單純)高維多胞形的相應完整分類則遠未完成,提醒我們「去數面」通往的是活的研究,而非一本闔上的書。