Notes2.pdf

Theorem 1 states that if x is an extreme point of the polytope defined by the system of inequalities x(U) ≤ rM(U) for all U ⊆ S and x(e) ≥ 0 for all e ∈ S, then there exists an element e ∈ S such that x(e) ∈ {0, 1}. The proof of Theorem 1 involves several lemmas, including Lemma 3, which states that if A and B are sets in F, then A ∩ B and A ∪ B are also in F, and Lemma 4, which states that there exists a laminar family C ⊆ F such that span(C) = span(F). The proof also involves a chain C′ ⊆ C, where C′ is a chain of sets such that x is the unique solution to the system x(U) = rM(U) for all U ∈ C′.

The system of inequalities (∗) determines the matroid polytope, and the removal of redundant inequalities gives a system with only polynomially many constraints. A flat is a subset U ⊆ S such that U = span(U), and the system (∗) can be replaced by (∗∗), which only includes constraints for flats. A flat F is separable if there exist flats F1, F2 such that F1 and F2 partition F and rM(F1) + rM(F2) = rM(F), and if F is a separable flat, the constraint x(F) ≤ rM(F) can be removed from (∗∗).