Matroid Deletion #
For M : Matroid α
and X : Set α
, the deletion of X
from M
is the matroid M \ X
with ground set M.E \ X
, in which a subset of M.E \ X
is independent if and only if it is
independent in M
.
The deletion M \ X
is equal to the restriction M ↾ (M.E \ X)
, but is of special importance
in the theory because it is the dual notion of contraction, and thus plays a more central
and natural role than restriction in many contexts.
Because of the implementation of the restriction M ↾ R
allowing R
to not be a subset of M.E
,
the relation M ↾ R ≤r M
holds only with the assumption R ⊆ M.E
,
whereas M \ D
, being defined as M ↾ (M.E \ D)
, satisfies M \ D ≤r M
unconditionally.
This is often quite convenient.
Main Declarations #
Matroid.delete M D
, writtenM \ D
, is the restriction ofM
to the setM.E \ D
, or equivalently the matroid onM.E \ D
whose independent sets are theM
-independent sets.
Naming conventions #
We use the abbreviation deleteElem
in lemma names to refer to the deletion M \ {e}
of a single element e : α
from M : Matroid α
.
Deletion #
M \ D
refers to the deletion of a set D
from the matroid M
.
Equations
- Matroid.«term_\_» = Lean.ParserDescr.trailingNode `Matroid.«term_\_» 75 75 (Lean.ParserDescr.binary `andthen (Lean.ParserDescr.symbol " \ ") (Lean.ParserDescr.cat `term 76))
Instances For
Alias of the reverse direction of Matroid.delete_eq_self_iff
.