Matroid、固有回路プロパティ

Question

matroidの回路の一意性については、 http://math.mit.edu/~goemans/18433S13/matroid-notes.pdfを参照してください。定理4.1の証明では、最後の2つの文は "Sも独立であるので、| X | = | S |を持つ必要があり、e∈C1 - fであるので、X = S + e - しかし、これはC2⊆S + e - f = Xを意味します。これはC2が依存しているので矛盾です。 "誰かがなぜ "| S | = | X |"そしてなぜ "e∈C1 - f、それはX = S + e - f∈Iでなければならないのか？"私はそれが何時間からであるかについての手がかりを持っていませんでした..

Answer 1

著者は、最大独立したセットのメンバーがすべて同じであることを最初のページの公理の定義の真下に記載しています。 I2では、大きさの異なる2つの独立した最大セットがある場合、大きい方の要素から1つを取り出し、小さい方の要素を増やすことができます。これは矛盾です。 SとXは両方ともS + eの最大独立独立集合です。so | S | = | X |

Xは独立したセットC1-fをとり、それを最大限に独立させることによって作成されるため、独立しています。 fはXの要素ではありません。なぜなら、その内部にC1が再作成されるからです。しかし、| X | = | S |ならば、| S | Xにfが含まれていない場合は、eが最も多く含まれます。