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
- IsKConnectedSetA set $Z$ in a matroid $M$ is $k$-connected for an integer $k \ge 2$ if for every subset $A \subseteq E(M)$, the connectivity function…
- matroid_not_k_connected_iff_exact_separationLet $M$ be a finite matroid, let $k \ge 3$ be an integer, and let $Z \subseteq E(M)$ be a $(k-1)$-connected set in $M$. Then $Z$ is not…
- is_k_connected_set_emptyIn every matroid $M$, the empty set is $k$-connected for all $k$.
- matroid_not_k_connected_of_exact_separationLet $M$ be a matroid, let $k \ge 2$ be an integer, and let $Z$ be a set in $M$. If there exists a subset $X \subseteq E(M)$ such that…
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