Matroid的基

(超纲内容)
拟阵的基是一个最大独立集，即一个独立集且不被包含在任何其他独立集中的集合。

示例

在二维欧几里得平面 ${\mathbb{R}}^2$ 上的拟阵中，考虑以下独立集：

$$\{\varnothing ,\{(0,1)\},\{(2,0)\},\{(0,1),(2,0)\},\{(0,3)\},\{(0,3),(2,0)\}\}$$

该拟阵有两个基：

$$\{(0,1),(2,0)\},\{(0,3),(2,0)\}$$

这是唯一的最大独立集。

在不同类型的拟阵中，基有不同的名称：

• 图拟阵 (graphic matroid)：基是图的生成森林。
• 横拟阵 (transversal matroid)：基是匹配端点的横截面。
• 线性拟阵 (linear matroid)：基是向量空间中的基。
• 均匀拟阵 (uniform matroid)：基是所有满足 $|B|=k$ 的集合。
• 分区拟阵 (partition matroid)：基是每个类别中元素数量恰好为 $k_c$ 的集合。
• 自由拟阵 (free matroid)：基是全集 $E$。

性质

交换性质

对于任意两个不同的基 $A$ 和 $B$，拟阵满足以下性质：

• 基交换性质：若 $a\in A\setminus B$，则存在 $b\in B\setminus A$，使得 $$(A\setminus \{a\})\cup \{b\}$$ 是一个基。
• 对称基交换性质：存在 $b\in B\setminus A$，使得 $$(A\setminus \{a\})\cup \{b\}\text{ 和 }(B\setminus \{b\})\cup \{a\}$$ 均为基。
• 多对称交换性质：对于任意 $X\subseteq A\setminus B$，存在 $Y\subseteq B\setminus A$ 使得 $$(A\setminus X)\cup Y\text{ 和 }(B\setminus Y)\cup X$$ 均为基。
• 双射交换性质：存在双射 $f:A\to B$ 使得 $$(A\setminus \{a\})\cup \{f(a)\}$$ 为基。

基的数量与大小

所有拟阵的基的基数相等，即

$$|A|=|B|\forall A,B\in \mathcal{B}$$

在线性拟阵中，这个基数称为向量空间的维数。

对偶

拟阵 $(E,\mathcal{B})$ 的对偶拟阵 $(E,{\mathcal{B}}^{\ast })$ 定义为：

$$B^{\ast }\in {\mathcal{B}}^{\ast }⟺E\setminus B^{\ast }\in \mathcal{B}$$

对偶拟阵满足 $(E,{\mathcal{B}}^{\ast \ast })=(E,\mathcal{B})$。

电路

基的对偶概念是电路。电路是最小的依赖集，即任意真子集都是独立的。

拟阵可以定义为 $(E,\mathcal{C})$，其中 $\mathcal{C}$ 为电路集，满足：

1. $\varnothing \notin \mathcal{C}$
2. 电路的任意真子集都不是电路
3. 若 $C_1\ne C_2$ 且 $x\in C_1\cap C_2$，则 $$(C_1\cup C_2)\setminus \{x\}$$ 包含一个电路。

参考

• Matroids Lecture 3 - Federico Ardila
• Theory of Matroids - Neil White
• [Matroid Theory - D.J.A. Welsh]