Matroid，唯一电路属性

Question

对于matroid电路的唯一性，请参考此注意： http://math.mit.edu/~goemans/18433S13/matroid-notes.pdf。在定理4.1的证明中，最后2个句子“由于S也是独立的，我们必须有| X | = | S |并且由于e∈C1-f，我们必须有X = S + e - f∈I但这意味着C2⊆S + e - f = X，这是C2以来的一个矛盾。“有人可以解释为什么“| S | = | X |”为什么“e∈C1-f，我们必须有X = S + e-f∈I”。我不知道它是如何从几个小时..

Answer 1

作者声明没有证明下面的第一页公理的定义，最大独立集都具有相同数量的成员。通过I2，如果你有两个不同大小的最大独立集合，你可以从大集合中选取一个元素并用它来增加较小的元素，这是一个矛盾。 S和X都是S + e so | S |的最大独立集合= | X |

X是独立的，因为它是通过创建一个独立集合C1-f并使其最大独立 - 因此仍然是独立的。 f不是X的元素，因为它会重新创建它内部的C1，我们知道它是依赖的。但是如果| X | = | S |，只有总共有| S | +1元素可以玩X不包含f，它大部分包含e。