Submodularity of the matroid rank function
ProvedFamousTheorems.matroid_rank_submodular_7aSubmodularity of the matroid rank function. For every matroid on a ground set and all sets ,
where is the rank function of .
Submodularity, together with monotonicity and , characterises matroid rank functions, as Whitney showed in 1935. It is the source of the connection between matroids and combinatorial optimization. It underlies Edmonds' matroid intersection theorem, the greedy algorithm and the theory of submodular functions.
Formalization note. Mathlib's Matroid.eRk_inter_add_eRk_union_le. M.eRk X is the rank of in , so the statement also covers infinite matroids. Sets outside the ground set are allowed, and their rank is that of their intersection with the ground set.
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
theorem matroid_rank_submodular_7a {α : Type*} (M : Matroid α) (X Y : Set α) : M.eRk (X ∩ Y) + M.eRk (X ∪ Y) ≤ M.eRk X + M.eRk Y := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `Matroid.eRk_inter_add_eRk_union_le`. Proof here reduces to that Mathlib result.