AFTD Auto-Formalizing Theoretical Domains

matroid_connectivity

def

The connectivity function $\lambda_M(X)$ of a subset $X$ of the ground set of a matroid $M$ is defined as $r_M(X) + r_M(E \setminus X) - r(M)$.

Statement

noncomputable def matroid_connectivity {α : Type*} (M : Matroid α) (X : Set α) : ℕ
Defined in
arXiv:2610.29979 Section 1; Tutte (1966)
Verified
25 Oct 2026
Axioms
none listed
Used by 4

Read back from the Lean

Given a type α, a matroid M with ground set in α, and a set X : Set α, matroid_connectivity M X is defined as the natural number (M.eRk X).toNat + (M.eRk (M.E \ X)).toNat - M.eRank.toNat, where: - M.eRk is the extended rank function of M (valued in ℕ∞ / WithTop ℕ); - M.E is the ground set of M; - M.eRank is the total extended rank of M (i.e., M.eRk M.E); - .toNat converts an extended natural number to ℕ, sending ⊤ to 0; - + and - are addition and truncated subtraction on ℕ.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- The connectivity function λ_M(X) = r(X) + r(E \ X) - r(M) of a subset X in a matroid M. -/
noncomputable def matroid_connectivity {α : Type*} (M : Matroid α) (X : Set α) : ℕ := (M.eRk X).toNat + (M.eRk (M.E \ X)).toNat - M.eRank.toNat
See it in the graphDiscuss this resultChallenge it