Матроид, уникальное свойство цепи

Question

Для уникальности схемы в матроиде относится к этой ноте: 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, поэтому | S | = | X |

X независим, потому что он создается путем принятия независимого набора C1-f и делает его максимально независимым - таким образом, все еще независимым. f не является элементом X, потому что это воссоздает C1 внутри него, что, как мы знаем, зависит. Но для воспроизведения есть только всего | S | +1 элементов, так что если | X | = | S | и X не содержит f, в нем больше всего e.