Matroid

Matroid --- матроид.

A matroid [math]\displaystyle{ {\mathcal M} = (E,{\mathcal I}) }[/math] is a pair of a finite set [math]\displaystyle{ E }[/math] and a family [math]\displaystyle{ {\mathcal I} }[/math] of elements of [math]\displaystyle{ E }[/math] such that

(I0) [math]\displaystyle{ {\mathcal I} }[/math] is non-empty;

(I1) if [math]\displaystyle{ I \in {\mathcal I} }[/math] and [math]\displaystyle{ J \subseteq I }[/math], then [math]\displaystyle{ J \in {\mathcal I} }[/math]; and

(I2) if [math]\displaystyle{ I,J \in {\mathcal I} }[/math] and [math]\displaystyle{ |I| \lt |J| }[/math], then there is an element [math]\displaystyle{ e \in J-I }[/math] such that [math]\displaystyle{ I \cup \{e\} \in {\mathcal I} }[/math].

An element of [math]\displaystyle{ {\mathcal I} }[/math] is called an independent set of a matroid [math]\displaystyle{ {\mathcal M} }[/math], and an element in [math]\displaystyle{ 2^{E} \setminus {\mathcal I} }[/math] is called a dependent set, where [math]\displaystyle{ 2^{E} }[/math] is the set of all the subsets of [math]\displaystyle{ E }[/math].

The system of postulates (I0) -(I2) is equivalent to that of (I0), (I1) and

(I2') for [math]\displaystyle{ X \subseteq E }[/math], if [math]\displaystyle{ I }[/math] and [math]\displaystyle{ J }[/math] are two maximal independent subsets of [math]\displaystyle{ X }[/math], then [math]\displaystyle{ |I| = |J| }[/math].

A maximal independent set in [math]\displaystyle{ {\mathcal I} }[/math] is called a base of [math]\displaystyle{ {\mathcal M} }[/math], and a minimal dependent set a circuit.

By (I2'), any maximal independent subset of a subset [math]\displaystyle{ X }[/math] of [math]\displaystyle{ E }[/math] has a common cardinality, which is called the rank of [math]\displaystyle{ X }[/math] and denoted by [math]\displaystyle{ \rho(X) }[/math], i.e. [math]\displaystyle{ \rho(X) = \max\{|I|: \; I \subseteq X, I \in {\mathcal I}\} \; (X \subseteq E). }[/math]

[math]\displaystyle{ \rho(E) }[/math] is called the rank of a matroid [math]\displaystyle{ {\mathcal M} }[/math]. The function [math]\displaystyle{ \rho: 2^{E} \rightarrow N_{+} }[/math] (where [math]\displaystyle{ N_{+} }[/math] is the set of non-negative integers) is called the rank function of [math]\displaystyle{ {\mathcal M} }[/math].