Rado's theorem for a monotone submodular integer rank function
ProvedEdmondsPartition.Main.rado_rankLet be a finite index set and a type. Let be an integer-valued function on the finite subsets of that is monotone (), submodular () and satisfies (for example the rank function of a matroid). Let be finite subsets of such that Rado's condition holds:
Then there are elements such that the set has rank .
Since , the rank condition forces , so the are pairwise distinct: they form an independent transversal when is a matroid rank function. This is Rado's theorem (1942). The proof is the standard shrinking argument: while some has two elements , deleting or deleting preserves Rado's condition, by submodularity applied to two violating index sets; at the end every is a singleton.
Formalization Note Only monotonicity, submodularity and are assumed; neither nor nonnegativity is needed. The conclusion is stated as so that it applies to any such rank function.
import Mathlib
namespace EdmondsPartition.Main
theorem rado_rank {ι β : Type*} [DecidableEq ι] [DecidableEq β] [Fintype ι]
(r : Finset β → ℤ)
(hmono : ∀ {X Y : Finset β}, X ⊆ Y → r X ≤ r Y)
(hsub : ∀ X Y : Finset β, r (X ∪ Y) + r (X ∩ Y) ≤ r X + r Y)
(hcard : ∀ X : Finset β, r X ≤ X.card)
(A : ι → Finset β) (hA : ∀ J : Finset ι, (J.card : ℤ) ≤ r (J.biUnion A)) :
∃ a : ι → β, (∀ i, a i ∈ A i) ∧ r (Finset.univ.image a) = Fintype.card ι := by sorry
end EdmondsPartition.Main