Basis of a matroid

Short description: Maximal independent set of the matroid

In mathematics, a basis of a matroid is a maximal independent set of the matroid—that is, an independent set that is not contained in any other independent set.

Examples

As an example, consider the matroid over the ground-set R² (the vectors in the two-dimensional Euclidean plane), with the following independent sets:

{ {}, {(0,1)}, {(2,0)}, {(0,1),(2,0)}, {(0,3)}, {(0,3),(2,0)} }.

It has two bases, which are the sets {(0,1),(2,0)} , {(0,3),(2,0)}. These are the only independent sets that are maximal under inclusion.

The basis has a specialized name in several specialized kinds of matroids:

• In a graphic matroid, where the independent sets are the forests, the bases are called the spanning forests of the graph.
• In a transversal matroid, where the independent sets are endpoints of matchings in a given bipartite graph, the bases are called transversals.
• In a linear matroid, where the independent sets are the linearly-independent sets of vectors in a given vector-space, the bases are just called bases of the vector space. Hence, the concept of basis of a matroid generalizes the concept of basis from linear algebra.
• In a uniform matroid, where the independent sets are all sets with cardinality at most k (for some integer k), the bases are all sets with cardinality exactly k.
• In a partition matroid, where elements are partitioned into categories and the independent sets are all sets containing at most k_c elements from each category c, the bases are all sets which contain exactly k_c elements from category c.
• In a free matroid, where all subsets of the ground-set E are independent, the unique basis is E.

Properties

Exchange

All matroids satisfy the following properties, for any two distinct bases [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math]:

• Basis-exchange property: if [math]\displaystyle{ a\in A\setminus B }[/math], then there exists an element [math]\displaystyle{ b\in B\setminus A }[/math] such that [math]\displaystyle{ (A \setminus \{ a \}) \cup \{b\} }[/math] is a basis.
• Symmetric basis-exchange property: if [math]\displaystyle{ a\in A\setminus B }[/math], then there exists an element [math]\displaystyle{ b\in B\setminus A }[/math] such that both [math]\displaystyle{ (A \setminus \{ a \}) \cup \{b\} }[/math] and [math]\displaystyle{ (B \setminus \{ b \}) \cup \{a\} }[/math] are bases. Brualdi showed that it is in fact equivalent to the basis-exchange property.
• Multiple symmetric basis-exchange property: if [math]\displaystyle{ X\subseteq A\setminus B }[/math], then there exists a subset [math]\displaystyle{ Y\subseteq B\setminus A }[/math] such that both [math]\displaystyle{ (A \setminus X) \cup Y }[/math] and [math]\displaystyle{ (B \setminus Y) \cup X }[/math] are bases. Brylawski, Greene, and Woodall, showed (independently) that it is in fact equivalent to the basis-exchange property.
• Bijective basis-exchange property: There is a bijection [math]\displaystyle{ f }[/math] from [math]\displaystyle{ A }[/math] to [math]\displaystyle{ B }[/math], such that for every [math]\displaystyle{ a\in A\setminus B }[/math], [math]\displaystyle{ (A \setminus \{ a \}) \cup \{f(a)\} }[/math] is a basis. Brualdi showed that it is equivalent to the basis-exchange property.
• Partition basis-exchange property: For each partition [math]\displaystyle{ (A_1, A_2, \ldots, A_m) }[/math] of [math]\displaystyle{ A }[/math] into m parts, there exists a partition [math]\displaystyle{ (B_1, B_2, \ldots, B_m) }[/math] of [math]\displaystyle{ B }[/math] into m parts, such that for every [math]\displaystyle{ i\in[m] }[/math], [math]\displaystyle{ (A \setminus A_i) \cup B_i }[/math] is a basis.

However, a basis-exchange property that is both symmetric and bijective is not satisfied by all matroids: it is satisfied only by base-orderable matroids.

In general, in the symmetric basis-exchange property, the element [math]\displaystyle{ b\in B\setminus A }[/math] need not be unique. Regular matroids have the unique exchange property, meaning that for some [math]\displaystyle{ a\in A\setminus B }[/math], the corresponding b is unique.

Cardinality

It follows from the basis exchange property that no member of [math]\displaystyle{ \mathcal{B} }[/math] can be a proper subset of another.

Moreover, all bases of a given matroid have the same cardinality. In a linear matroid, the cardinality of all bases is called the dimension of the vector space.

Neil White's conjecture

It is conjectured that all matroids satisfy the following property: For every integer t ≥ 1, If B and B' are two t-tuples of bases with the same multi-set union, then there is a sequence of symmetric exchanges that transforms B to B'.

Characterization

The bases of a matroid characterize the matroid completely: a set is independent if and only if it is a subset of a basis. Moreover, one may define a matroid [math]\displaystyle{ M }[/math] to be a pair [math]\displaystyle{ (E,\mathcal{B}) }[/math], where [math]\displaystyle{ E }[/math] is the ground-set and [math]\displaystyle{ \mathcal{B} }[/math] is a collection of subsets of [math]\displaystyle{ E }[/math], called "bases", with the following properties:

(B1) There is at least one base -- [math]\displaystyle{ \mathcal{B} }[/math] is nonempty;

(B2) If [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math] are distinct bases, and [math]\displaystyle{ a\in A\setminus B }[/math], then there exists an element [math]\displaystyle{ b\in B\setminus A }[/math] such that [math]\displaystyle{ (A \setminus \{ a \}) \cup \{b\} }[/math] is a basis (this is the basis-exchange property).

(B2) implies that, given any two bases A and B, we can transform A into B by a sequence of exchanges of a single element. In particular, this implies that all bases must have the same cardinality.

Duality

If [math]\displaystyle{ (E,\mathcal{B}) }[/math] is a finite matroid, we can define the orthogonal or dual matroid [math]\displaystyle{ (E,\mathcal{B}^*) }[/math] by calling a set a basis in [math]\displaystyle{ \mathcal{B}^* }[/math] if and only if its complement is in [math]\displaystyle{ \mathcal{B} }[/math]. It can be verified that [math]\displaystyle{ (E,\mathcal{B}^*) }[/math] is indeed a matroid. The definition immediately implies that the dual of [math]\displaystyle{ (E,\mathcal{B}^*) }[/math] is [math]\displaystyle{ (E,\mathcal{B}) }[/math].

Using duality, one can prove that the property (B2) can be replaced by the following:

(B2*) If [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math] are distinct bases, and [math]\displaystyle{ b\in B\setminus A }[/math], then there exists an element [math]\displaystyle{ a\in A\setminus B }[/math] such that [math]\displaystyle{ (A \setminus \{ a \}) \cup \{b\} }[/math] is a basis.

Circuits

A dual notion to a basis is a circuit. A circuit in a matroid is a minimal dependent set—that is, a dependent set whose proper subsets are all independent. The terminology arises because the circuits of graphic matroids are cycles in the corresponding graphs.

One may define a matroid [math]\displaystyle{ M }[/math] to be a pair [math]\displaystyle{ (E,\mathcal{C}) }[/math], where [math]\displaystyle{ E }[/math] is the ground-set and [math]\displaystyle{ \mathcal{C} }[/math] is a collection of subsets of [math]\displaystyle{ E }[/math], called "circuits", with the following properties:

(C1) The empty set is not a circuit;

(C2) A proper subset of a circuit is not a circuit;

(C3) If C₁ and C₂ are distinct circuits, and x is an element in their intersection, then [math]\displaystyle{ C_1 \cup C_2 \setminus \{x\} }[/math] contains a circuit.

Another property of circuits is that, if a set [math]\displaystyle{ J }[/math] is independent, and the set [math]\displaystyle{ J \cup \{x\} }[/math] is dependent (i.e., adding the element [math]\displaystyle{ x }[/math] makes it dependent), then [math]\displaystyle{ J \cup \{x\} }[/math] contains a unique circuit [math]\displaystyle{ C(x,J) }[/math], and it contains [math]\displaystyle{ x }[/math]. This circuit is called the fundamental circuit of [math]\displaystyle{ x }[/math] w.r.t. [math]\displaystyle{ J }[/math]. It is analogous to the linear algebra fact, that if adding a vector [math]\displaystyle{ x }[/math] to an independent vector set [math]\displaystyle{ J }[/math] makes it dependent, then there is a unique linear combination of elements of [math]\displaystyle{ J }[/math] that equals [math]\displaystyle{ x }[/math].

See also

• Matroid polytope - a polytope in Rⁿ (where n is the number of elements in the matroid), whose vertices are indicator vectors of the bases of the matroid.