拉東定理(Radon's theorem)
/ RAH-dohn /
在 n 維空間中丟進略微太多的點,它們就免不了彼此擋路。拉東定理把這點說精確:R^n 中任意 n + 2 個點總能分成兩組,其凸包相重疊。無論你在平面上如何散佈四點,你都能把它們染成紅藍,使紅色區域與藍色區域共有一點。一旦點數比維數多兩個,就有不可避免的「交叉」。
精確地說,給定 R^n 中任意 n + 2 個點 x_1, ..., x_{n+2},存在把指標集分成兩不相交部分 I 與 J 的分割,使 conv{x_i : i in I} 與 conv{x_j : j in J} 有共同點。這樣的分割稱為拉東分割,共同點稱為拉東點。證明是純線性代數:R^n 中的 n + 2 個向量,藉附加一個 1 提升到 R^{n+1} 後線性相依,故有不全為零的係數 a_i,使 sum a_i x_i = 0 且 sum a_i = 0。把 a_i > 0 的指標放入 I、a_i < 0 的放入 J;將正部與負部規範化,從兩側各得同一個點作為凸組合——該點同時落在兩個凸包中。
拉東定理是赫利定理背後的引擎(赫利的標準證明用拉東分割作歸納),也是與赫利、卡拉特奧多里並列的組合凸性三巨頭之一。它還壯觀地推廣:特韋伯格定理說 R^n 中 (r-1)(n+1) + 1 個點能分成 r 組、其凸包全都共有一點,拉東是 r = 2 的情形。這些結果支撐中心點定理,並在組合學與棋盤複形的拓樸中有出人意表的應用。一個誠實的提醒:分割保證存在但不唯一,而拉東對共同點「在哪裡」、或在高維中如何在線性代數構造之外有效率地找到它,什麼也沒說;點也不必處於一般位置——無論如何定理都成立,但退化的配置會使多個分割同時有效。
平面上四點(n = 2,故 n + 2 = 4)總有拉東分割。若這四點是凸四邊形 ABCD 的角,把它們按兩條對角線分成 {A, C} 與 {B, D}:線段 AC 與 BD 相交,所以兩個凸包(兩條對角線)共有那個交點。若改為一點 D 落在三角形 ABC 內,分成 {A, B, C} 與 {D}:三角形含 D,所以凸包再次相遇——就在 D 本身。
平面四點分成兩個相遇的凸包:相交的對角線,或落在三角形內的一點。
拉東分割存在但不必唯一,而定理對於如何在線性相依構造之外有效率地定位共同點,保持沉默。它是個存在性結果;特韋伯格定理是深刻的多部推廣,證明起來困難得多。