Matroid, Уникальное свойство Circuit

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, поэтому | S | = | X |

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