Editing Matroid (section)

==Definition== <!-- [[Hereditary property (matroid)]] redirects to this section title -->
There are many [[Cryptomorphism|equivalent]] ways to define a (finite) matroid.{{efn|
{{harvp|Oxley|1992}} is a standard source for basic definitions and results about matroids; {{harvp|Welsh|1976}} is an older standard source.
:
See the appendix by Brylawski in {{harvp|White|1986|pp=298–302}}, for a list of matroid axiom systems that are equivalent.
:
}}

=== Independent sets <span class="anchor" id="independent_sets_anchor"></span>===
In terms of independence, a finite matroid <math> M </math> is a pair <math> (E, \mathcal{I})</math>, where <math> E </math> is a [[finite set]] (called the ''ground set'') and <math> \mathcal{I} </math> is a [[family of sets|family]] of [[subset]]s of <math> E </math> (called the ''independent sets'') with the following properties:<ref name=w7-9>{{harvtxt|Welsh|1976|pp=7–9}}, Section&nbsp;1.2, "Axiom Systems for a Matroid".</ref>

* (I1)  The [[empty set]] is independent, i.e., <math> \emptyset \in \mathcal{I}</math>.

* (I2)  Every subset of an independent set is independent, i.e., for each <math> A' \subseteq A \subseteq E</math>, if <math> A \in \mathcal{I} </math> then <math> A' \in \mathcal{I}</math>. This is sometimes called the ''hereditary property'', or the ''downward-closed'' property.

* (I3) If <math>A</math> and <math>B</math> are two independent sets (i.e., each set is independent) and <math>A</math> has more elements than <math> B</math>, then there exists <math> x \in A \setminus B</math> such that <math> B \cup \{ x \} </math> is in <math> \mathcal{I}</math>. This is sometimes called the ''augmentation property'' or the ''independent set exchange property''.

The first two properties define a combinatorial structure known as an [[independence system]] (or [[abstract simplicial complex]]). Actually, assuming (I2), property (I1) is equivalent to the fact that at least one subset of <math>E</math> is independent, i.e., <math>\mathcal{I}\neq\emptyset</math>.

=== Bases and circuits <span class="anchor" id="bases_circuits_anchor"></span> ===
{{Main|Basis of a matroid}}
A subset of the ground set <math> E </math> that is not independent is called ''dependent''. A maximal independent set – that is, an independent set that becomes dependent upon adding any element of <math>E</math> – is called a ''basis'' for the matroid. A ''circuit'' in a matroid <math> M </math> is a minimal dependent subset of <math>E</math> – that is, a dependent set whose proper subsets are all independent. The term arises because the circuits of [[graphic matroid]]s are cycles in the corresponding graphs.<ref name=w7-9/>

The dependent sets, the bases, or the circuits of a matroid characterize the matroid completely: a set is independent if and only if it is not dependent, if and only if it is a subset of a basis, and if and only if it does not contain a circuit. The collections of dependent sets, of bases, and of circuits each have simple properties that may be taken as axioms for a matroid. For instance, one may define a matroid <math> M </math> to be a pair <math> (E,\mathcal{B}) </math>, where <math> E </math> is a finite set as before and <math> \mathcal{B} </math> is a collection of subsets of <math> E</math>, called ''bases'', with the following properties:<ref name=w7-9/>

* (B1) <math> \mathcal{B} </math> is nonempty.

* (B2) If <math> A </math> and <math> B </math> are distinct members of <math> \mathcal{B} </math> and <math> a \in A \smallsetminus B</math>, then there exists an element <math> b \in B \smallsetminus A </math> such that <math> (A \smallsetminus \{ a \}) \cup \{b\} \in \mathcal{B}</math>.

This property (B2) is called the ''basis exchange property''. It follows from this property that no member of <math> \mathcal{B} </math> can be a proper subset of any other.

=== Rank functions <span class="anchor" id="rank_func_anchor"></span> ===
It is a basic result of matroid theory, directly analogous to a similar theorem of [[basis (linear algebra)|bases in linear algebra]], that any two bases of a matroid <math> M </math> have the same number of elements.  This number is called the ''[[matroid rank|rank]]'' {{nobr|of <math> M</math>.}} If <math> M </math> is a matroid on <math>E</math>, and <math>A</math> is a subset of <math>E</math>, then a matroid on <math> A </math> can be defined by considering a subset of <math> A </math> to be independent if and only if it is independent in <math> M</math>. This allows us to talk about ''submatroids'' and about the rank of any subset of <math> E</math>. The rank of a subset <math>A</math> is given by the ''[[matroid rank|rank function]]'' <math> r(A) </math> of the matroid, which has the following properties:<ref name=w7-9/>

*(R1) The value of the rank function is always a non-negative [[integer]].

*(R2) For any subset <math>A\subset E</math>, we have <math>r(A) \le |A|</math>. 

*(R3) For any two subsets <math>A, B\subset E</math>, we have: <math> r(A \cup B) + r(A \cap B) \le r(A) + r(B)</math>. That is, the rank is a [[submodular function]].

*(R4) For any set <math>A</math> and element <math> x</math>, we have: <math> r(A) \le r( A \cup \{x\} ) \le r(A) + 1</math>. From the first inequality it follows more generally that, if <math> A \subseteq B \subseteq E</math>, then <math> r(A) \leq r(B )\leq r(E)</math>. That is, rank is a [[monotonic function]].

These properties can be used as one of the alternative definitions of a finite matroid: If <math> (E,r) </math> satisfies these properties, then the independent sets of a matroid over <math> E </math> can be defined as those subsets <math> A </math> of <math>E</math> with <math> r(A) = |A|</math>. In the language of [[partially ordered set]]s, such a matroid structure is equivalent to the [[geometric lattice]] whose elements are the subsets <math> A \subset M</math>, partially ordered by inclusion.

The difference <math>|A| - r(A)</math> is called the ''nullity'' of the subset <math> A</math>. It is the minimum number of elements that must be removed from <math> A </math> to obtain an independent set. The nullity of <math>E</math> in <math>M</math> is called the nullity of <math> M</math>. The difference <math>r(E) - r(A)</math> is sometimes called the ''corank'' of the subset <math>A</math>.

=== Closure operators <span class="anchor" id="closure_ops_anchor"></span> ===
Let <math>M</math> be a matroid on a finite set <math> E</math>, with rank function <math>r</math> as above.  The ''closure'' or ''span'' <math> \operatorname{cl}(A) </math> of a subset <math>A</math> of <math>E</math> is the set
:<math> \operatorname{cl}(A) = \Bigl\{\ x \in E \mid r(A) = r\bigl( A \cup \{x\} \bigr) \Bigr\}</math>.
This defines a [[closure operator]] <math> \operatorname{cl}: \mathcal{P}(E) \mapsto \mathcal{P}(E) </math> where <math>\mathcal{P}</math> denotes the [[power set]], with the following properties:

* (C1) For all subsets <math> X </math> of <math> E</math>, <math> X \subseteq \operatorname{cl}(X)</math>. 

* (C2) For all subsets <math>X</math> of <math> E</math>, <math>\operatorname{cl}(X)= \operatorname{cl}\left( \operatorname{cl}\left( X \right) \right)</math>. 

* (C3) For all subsets <math>X</math> and <math>Y</math> of <math>E</math> with <math> X\subseteq Y</math>, <math>\operatorname{cl}(X)\subseteq \operatorname{cl}(Y)</math>.

* (C4) For all elements <math>a</math> and <math>b</math> from <math>E</math> and all subsets <math>Y</math> of <math>E</math>, if <math> a \in \operatorname{cl}( Y \cup \{b\}) \smallsetminus \operatorname{cl}(Y)</math> then <math> b \in \operatorname{cl}( Y \cup \{a\}) \smallsetminus \operatorname{cl}(Y)</math>. 

The first three of these properties are the defining properties of a closure operator. The fourth is sometimes called the ''[[Saunders Mac Lane|Mac Lane]]–[[Ernst Steinitz|Steinitz]] exchange property''. These properties may be taken as another definition of matroid: every function <math>\operatorname{cl}: \mathcal{P}(E)\to \mathcal{P}(E)</math> that obeys these properties determines a matroid.<ref name=w7-9/>

=== Flats<span class="anchor" id="closed_sets_flats_anchor"></span> ===
A set whose closure equals itself is said to be ''closed'', or a ''flat'' or ''subspace'' of the matroid.<ref>{{harvtxt|Welsh|1976|pp=21–22}}, Section&nbsp;1.8, "Closed sets = Flats = Subspaces".</ref> A set is closed if it is [[maximal element|maximal]] for its rank, meaning that the addition of any other element to the set would increase the rank. The closed sets of a matroid are characterized by a covering partition property:

* (F1) The whole point set <math>E</math> is closed.

* (F2) If <math>S</math> and <math>T</math> are flats, then <math>S\cap T</math> is a flat.

* (F3) If <math>S</math> is a flat, then each element of <math>E\smallsetminus S</math> is in precisely one of the flats <math>T</math> that [[Covering relation|cover]] <math>S</math> (meaning that <math>T</math> properly contains <math>S</math>, but there is no flat <math>U</math> between <math>S</math> and <math>T</math>).

The class <math>\mathcal{L}(M)</math> of all flats, [[partially ordered set|partially ordered]] by set inclusion, forms a [[matroid lattice]]. Conversely, every matroid lattice <math>L</math> forms a matroid over its set <math>E</math> of [[Atom (order theory)|atoms]] under the following closure operator:  for a set <math>S</math> of atoms with join <math> \bigvee S</math>, 
:<math>\operatorname{cl}(S) = \{ x\in E\mid x\le\bigvee S \}</math>. 
The flats of this matroid correspond one-for-one with the elements of the lattice; the flat corresponding to lattice element <math>y</math> is the set
:<math>\{ x\in E\mid x\le y\}</math>. 
Thus, the lattice of flats of this matroid is naturally isomorphic to <math>L</math>.

===Hyperplanes===
In a matroid of rank <math> r</math>, a flat of rank <math>r - 1</math> is called a ''hyperplane''. (Hyperplanes are also called ''co-atoms'' or ''copoints''.) These are the maximal proper flats; that is, the only superset of a hyperplane that is also a flat is the set <math>E</math> of all the elements of the matroid. An equivalent definition is that a coatom is a subset of ''E'' that does not span ''M'', but such that adding any other element to it does make a spanning set.<ref name=w38-39>{{harvtxt|Welsh|1976|pp=38–39}}, Section&nbsp;2.2, "The Hyperplanes of a Matroid".</ref>

The family <math>\mathcal{H}</math> of hyperplanes of a matroid has the following properties, which may be taken as yet another axiomatization of matroids:<ref name=w38-39/>

* (H1) There do not exist distinct sets <math>X</math> and <math>Y</math> in <math>\mathcal{H}</math> with <math> X \subseteq Y</math>. That is, the hyperplanes form a [[Sperner family]].

* (H2) For every <math> x \in E </math> and distinct <math> Y, Z \in \mathcal{H} </math> with <math> x\notin Y \cup Z</math>, there exists <math> X \in \mathcal{H} </math> with <math> (Y \cap Z) \cup \{x\} \subseteq X</math>.

===Graphoids===

[[George J. Minty|Minty]] (1966) defined a ''graphoid'' as a triple <math>(L, C, D)</math> in which <math>C</math> and <math>D</math> are classes of nonempty subsets of <math>L</math> such that 

*(G1) no element of <math>C</math> (called a "circuit") contains another, 

*(G2) no element of <math>D</math> (called a "cocircuit") contains another, 

*(G3) no set in <math>C</math> and set in <math>D</math> intersect in exactly one element, and 

*(G4) whenever <math>L</math> is represented as the disjoint union of subsets <math> R, G, B </math> with <math>G = \{ g \}</math> (a singleton set), then either an <math>X \in C</math> exists such that <math>g \in X \subseteq R \cup G</math> or a <math>Y \in D</math> exists such that <math>g \in Y \subseteq B \cup G</math>.

He proved that there is a matroid for which <math>C</math> is the class of circuits and <math>D</math> is the class of cocircuits. Conversely, if <math>C</math> and <math>D</math> are the circuit and cocircuit classes of a matroid <math>M</math> with ground set <math> E</math>, then <math>(E, C, D)</math> is a graphoid. Thus, graphoids give a ''self-dual cryptomorphic axiomatization'' of matroids.