组合数学中的组合凸性 组合凸性是组合数学与离散几何交叉领域的重要概念，它研究离散点集上凸性结构的组合性质。与连续空间中的凸性（通过凸包、凸集等定义）不同，组合凸性关注点集在离散设置下的分离性、交性以及秩等性质。 基本定义：凸几何 一个 凸几何 （convex geometry）是一个有限集合 \( S \) 及其上的一个闭包算子 \( \tau: 2^S \to 2^S \)，满足： 扩展性：\( X \subseteq \tau(X) \)。 单调性：若 \( X \subseteq Y \)，则 \( \tau(X) \subseteq \tau(Y) \)。 幂等性：\( \tau(\tau(X)) = \tau(X) \)。 反交换性：若 \( y \notin \tau(X) \) 但 \( y \in \tau(X \cup \{x\}) \)，则 \( x \in \tau(X \cup \{y\}) \)。 集合 \( C \subseteq S \) 称为 凸集 ，如果 \( \tau(C) = C \)。反交换性保证了凸集的极值点（如凸包的顶点）具有良好定义。 例子：点集的凸包 在欧几里得平面中，取有限点集 \( S \)，定义 \( \tau(X) \) 为 \( X \) 的凸包（所有凸组合的点集）与 \( S \) 的交集。这构成一个凸几何，其中凸集是 \( S \) 中位于某个凸多边形顶点上的子集。 例如，若 \( S \) 是平面上处于一般位置的点（无三点共线），则凸集恰是 \( S \) 的所有子集，其点位于某个凸多边形的边界上。 组合凸性的关键性质：极值点与基 在凸几何中，子集 \( B \subseteq X \) 称为 \( X \) 的 基 ，如果 \( \tau(B) = \tau(X) \) 且 \( B \) 是极小的（即删除任意元素后闭包缩小）。 基的大小称为集合 \( X \) 的 秩 。凸几何的秩函数满足拟阵的秩公理，但增加了局部次模性，使得凸集的结构更紧密。 极值点：点 \( x \in X \) 是 \( X \) 的极值点，如果 \( x \notin \tau(X \setminus \{x\}) \)。极值点集是凸集的最小生成集。 分离公理与Helly型定理 组合凸性推广了连续凸集的分离性质。称凸几何具有 分离性 ，如果对任意两个不交凸集 \( C_ 1, C_ 2 \)，存在凸集 \( C \) 使得 \( C_ 1 \subseteq C \)，\( C_ 2 \subseteq S \setminus C \)，且 \( C \) 和 \( S \setminus C \) 均为凸集。 离散Helly定理 ：若凸几何中任意 \( d+1 \) 个凸集两两相交，则所有凸集有公共交。这推广了欧几里得空间中的Helly定理，但需对凸几何的秩或维度附加条件。 应用与推广 组合凸性用于编码理论（凸码）、组合优化（贪婪算法的可行性）和计算几何（点集凸性的离散模型）。 推广包括 反拟阵 （antimatroid，凸几何的对偶结构）和 凸多面体的面格 ，其中面格组合了凸多面体的凸性。