Helly 定理

形式陈述 ​

设 $\mathcal{F}=\{C_1,\dots ,C_n\}$ 是 ${\mathbb{R}}^d$ 中的有限公理库有限集Finite set与某个初始自然数段存在双射的集合。凸集族。若每个至多 $d+1$ 个成员组成的子族都有非空交，则

$$\bigcap _{i=1}^n{C}_i\ne \varnothing .$$

当 $n\ge d+1$ 时，只检查每个恰含 $d+1$ 个成员的子族已经足够；当 $n\le d+1$ 时，假设本身就包含全族相交。有限版不要求集合开、闭、有界或紧，只要求凸。

证明的核心是 $n=d+2$。对每个 $i$，选择

$$x_i\in \bigcap _{j\ne i}{C}_j.$$

由Radon 定理公理库Radon 定理Radon theorem欧氏 d 维空间中的任意 d 加二个点都能划分为两个凸包相交的非空部分。，这些点的指标可分为非空两部分 $I,J$，并有

$$y\in \mathrm{conv}\{x_i:i\in I\}\cap \mathrm{conv}\{x_j:j\in J\}.$$

对任意 $k$，若 $k\in I$，则 $J$ 中每个 $x_j$ 都属于 $C_k$；由凸性公理库凸集Convex set任意两点间线段全部包含在集合中的向量空间子集。，$y\in C_k$。若 $k\in J$ 同理使用 $I$。所以 $y$ 属于全部 $d+2$ 个集合。

一般有限 $n$ 用归纳完成。已知 $d+2$ 情形后，把最后两个集合替换为 $C_{n-1}\cap C_n$；新族中任何至多 $d+1$ 个集合的交非空，这一点在涉及该交集时由刚证明的 $d+2$ 情形保证。对较小族应用归纳，即得原全族交非空。

直觉 ​

在固定维数中，凸集的全局可行性拥有大小受限的局部证书。若全族无公共点，必能在至多 $d+1$ 个约束中看到冲突；维数决定了需要同时检查多少个方向，而不是集合总数。

Radon 点是证明的粘合器。每个 $x_i$ 可能缺少对第 $i$ 个集合的保证，但 Radon 划分让交点 $y$ 总能从“不缺少 $C_i$ 的那一侧”表示出来，凸性再把它留在 $C_i$ 中。

例子与边界 ​

在实线中 $d=1$，有限区间族只要每两个区间相交，全部区间就相交；公共点可取所有左端点的最大值。在平面中，只要有限凸集族的每三个成员相交，整个族便有公共点。

凸性不能删除。取平面中四个不同点 $p_1,\dots ,p_4$，令

$$C_i=\{p_j:j\ne i\}.$$

任意三个 $C_i$ 的交包含剩下那个点，但四者总交为空；这些有限点集通常非凸。它们满足平面中“三三相交”却破坏结论。

有限性也不能直接删除。实线上的开区间族 $C_n=(n,\mathrm{\infty })$ 任意有限子族都有非空交，任意两个当然相交，但全族交为空。无限版本需要有限交性质配合紧性，例如要求至少一个集合紧；不能把有限 Helly 定理原样搬过去。

$d+1$ 一般是最优数目。在 ${\mathbb{R}}^d$ 中令

$$C_i=\{x:x_i\ge 1\}(1\le i\le d),C_{d+1}=\{x:\sum _{i=1}^d{x}_i\le d-1\}.$$

全部 $d+1$ 个集合不相交，因为前 $d$ 条约束推出坐标和至少为 $d$；删掉最后一个集合后显然可行，删掉任一 $C_i$ 后又可把该坐标取得足够小，使其余约束与和式同时成立。因此每 $d$ 个集合相交仍不能保证全交。

推论与应用 ​

Helly 定理把线性不等式可行性转成固定大小子系统的证书：若有限半空间系统在 ${\mathbb{R}}^d$ 无解，则存在至多 $d+1$ 条约束已经无解。它与多面体公理库多面体与多胞形Polyhedron · Polytope分别由有限线性不等式交与有限点凸包描述，并由 Minkowski–Weyl 定理连接的凸几何对象。的 H-表示直接相连，但不是 Farkas 引理；后者给线性组合形式的代数证书。

几何横截、设施选址和组合优化常借 Helly 数把全局相交问题降为局部检查。其作用是保证证书存在，不自动给出寻找证书的最优算法，也不替代对输入表示、退化与数值鲁棒性的分析。

参考资料

• Jiří Matoušek, Lectures on Discrete Geometry, Springer, 2002, Ch. 1, Helly’s theorem.
• Branko Grünbaum, Convex Polytopes, 2nd ed., Springer, 2003, Ch. 1, Helly-type theorems.