拟阵⊊独立系统

hbghlyj

一个有限的拟阵 $ M $ 是一个二元组 $ (E,{\mathcal {I}}) $, 其中 $ E $ 是一个有限集，称之为 基础集(ground set)，$ {\mathcal {I}} $ 是一个$ E $的子集族，称之为 独立集(independent sets) 它需要满足下面的条件:

• (I1)空集是独立的：$ \emptyset \in {\mathcal {I}} $.
• (I2)每个独立集的子集是独立的：
  对于 $ A'\subset A\subset E $, 如果 $ A\in {\mathcal {I}} $ 则 $ A'\in {\mathcal {I}} $. 称之为 遗传特性(hereditary property).
• (I3)如果 $ A $ 和 $ B $ 是 $ {\mathcal {I}} $ 的两个独立集，$A $ 比 $B$ 有更多的元素，则存在 $ x\in A\setminus B$ 使得 $B \cup \{x\} ∈\mathcal {I}$. 称之为 扩充特性(augmentation property) 或 独立集交换特性(independent set exchange property).
  

头两个特性定义了一个组合结构，叫做独立系统(independence system) 或 抽象单形(abstract simplicial complex)。实际上，假设 (I2)，性质 (I1) 等价于 $E$ 的至少一个子集是独立的，即 $ {\mathcal {I}}\neq \emptyset $。

hbghlyj

OSChina技术问答 - 关于拟阵的问题

Provide an example of (S,C) which is an independent system but not a matroid.

这个问题就是寻找一例满足(I1)(I2)但不满足(I3).

hbghlyj

hbghlyj 发表于 2023-3-20 13:27
这个问题就是寻找一例满足(I1)(I2)但不满足(I3).

Let $S=\set{1, 2, 3}$ and $C=\set{\emptyset,\set{1}, \set{2}, \set{3}, \set{1, 2}}$. This system $(S,C)$ is independent. It is not a matroid because it violates the exchange property:
Consider $\set{1, 2}$ and $\set{3}$. Both of them are in $C$, but $\set{1, 3},\set{2,3}$ are not.