拟阵的秩函数

拟阵的秩函数（matroid rank function）把底集的每个子集映射为其中最多能选出的独立元素数。它把一个独立集族改写成整数值集合函数，既能判断独立，也能描述冗余和扩充的边界。

考虑两个互不重叠的组 $R=\{a,b,c\}$、$B=\{d,e\}$，每组最多选一个。集合 $\{a,b,d\}$ 有三个元素，却最多独立选出两个；$\{a,b,c\}$ 最多只能选一个。秩数的不是元素总量，而是在给定独立性规则下仍有区分作用的数量。

从独立集到整数值函数

设 $M=(E,ℐ)$ 是有限拟阵。其秩函数为 $$r:2^E⟶{\mathbb{Z}}_{\ge 0},r(A)=max\{|I|:I\subseteq A,I\in ℐ\}.$$ 空集可行且候选有限，所以最大值存在。$A$ 独立当且仅当 $r(A)=|A|$：正向取 $I=A$；反向最大独立子集与 $A$ 等大，只能等于 $A$。

开头的分划拟阵有 $$r(A)=min(1,|A\cap R|)+min(1,|A\cap B|).$$ 因为两组的限制互不干扰，每个出现过的组恰能贡献一个代表。一般组容量为 $k_i$、组为不交的 $E_i$ 时，公式相应变成 $\sum _{i}min(k_i,|A\cap E_i|)$。

秩满足 $r(\varnothing )=0$、$0\le r(A)\le |A|$，以及单调性 $A\subseteq B\Rightarrow r(A)\le r(B)$。加入一个元素最多增加一：若最大独立集用了新元素，删去它就得到 $A$ 内的独立集；没用它则秩不变。因此 $$r(A)\le r(A\cup \{e\})\le r(A)+1.$$

次模不等式的基扩充证明

秩还有比单调性更强的性质：对任意 $A,B\subseteq E$， $$r(A)+r(B)\ge r(A\cup B)+r(A\cap B).$$ 这称为次模性。下面直接从增广公理证明，不能只从某张向量图推广。

先在 $A\cap B$ 内取基 $K$，再把它扩充为 $A$ 内的基 $I$，最后把 $I$ 扩充为 $A\cup B$ 内的基 $J$。这些扩充可以逐次完成，因为有限拟阵内每个极大独立集都是最大独立集。$I\cap B=K$：若多出元素，$K$ 还能在 $A\cap B$ 内扩大。类似地，$J\setminus I$ 全在 $B\setminus A$ 内，否则 $I$ 就不是 $A$ 内的基。因此 $$K\cup (J\setminus I)\subseteq B$$ 是 $J$ 的独立子集，给出 $$r(B)\ge |K|+|J|-|I|=r(A\cap B)+r(A\cup B)-r(A).$$ 移项便得到待证不等式。关键是两次扩充保留了旧基，新增元素因此有明确归属。

取 $A=\{a,d\}$、$B=\{b,d\}$，有 $r(A)=r(B)=2$，$r(A\cap B)=1$、$r(A\cup B)=2$，所以 $4\ge 3$。严格不等式来自 $a,b$ 属于同一组：两边分开计算时重复利用了这一个独立名额。

闭包中的冗余

定义 $$\mathrm{cl}(A)=\{e\in E:r(A\cup \{e\})=r(A)\}.$$ 它称为闭包或张成，包含 $A$。在本例中 $\mathrm{cl}(\{a\})=R$；已经选到红组代表，再加入其他红组元素不会增加秩。

闭包随集合增大而增大。若 $A\subseteq B$ 且 $e\notin B$，把次模不等式用于 $A+e$ 和 $B$，得到 $$r(A+e)-r(A)\ge r(B+e)-r(B).$$ 如果左边是零，右边因单调性也只能为零。因此在小集合里已冗余的元素，在大集合里仍冗余。逐个加入闭包元素，秩一直不变，从而 $r(\mathrm{cl}(A))=r(A)$，再次闭包也不会扩大。这是抽象张成与线性张成共有的结构。

变式。 取 $A=\{d\}$，求秩和闭包；再加 $a$。答案是 $r(A)=1$、$\mathrm{cl}(A)=\{d,e\}$；加入 $a$ 后秩为二，闭包变成全部 $E$。仅凭元素数不能推出这个变化，必须知道各元素属于哪一组。

秩条件不能任意删弱

归一化、整数值、单调、次模且 $r(A)\le |A|$ 的函数反过来也恰好描述拟阵秩；这里每一个条件都限制了“独立数量”的含义。例如 $f(A)=2|A|$ 虽单调且次模，却让单元素集合的值为二，不可能是本底集上的拟阵秩。非整数的 $f(A)=|A|/2$ 也不能数独立元素。这些更一般的容量函数可以定义多拟阵，却不能直接沿用 $r(A)=|A|$ 的独立集判断而声称原函数仍是所得拟阵的秩。