{"document_url": "https://en.wikipedia.org/wiki/Basis_of_a_matroid"}
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 R2 (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:

Properties

Exchange

All matroids satisfy the following properties, for any two distinct bases
and
:
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
need not be unique. Regular matroids have the unique exchange property, meaning that for some
, the corresponding b is unique.

Cardinality

It follows from the basis exchange property that no member of
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
to be a pair
, where
is the ground-set and
is a collection of subsets of
, called "bases", with the following properties:

(B1) There is at least one base --
is nonempty;

(B2) If
and
are distinct bases, and
, then there exists an element
such that
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
is a finite matroid, we can define the orthogonal or dual matroid
by calling a set a basis in
if and only if its complement is in
. It can be verified that
is indeed a matroid. The definition immediately implies that the dual of
is
.

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

(B2*) If
and
are distinct bases, and
, then there exists an element
such that
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
to be a pair
, where
is the ground-set and
is a collection of subsets of
, called "circuits", with the following properties:

(C1) The empty set is not a circuit;
(C2) A subset of a circuit is not a circuit;
(C3) If C1 and C2 are circuits, and x is an element in their intersection, then
contains a circuit.

Another property of circuits is that, if a set
is independent, and the set
is dependent (i.e., adding the element
makes it dependent), then
contains a unique circuit
, and it contains
. This circuit is called the fundamental circuit of
w.r.t.
. It is analogous to the linear algebra fact, that if adding a vector
to an independent vector set
makes it dependent, then there is a unique linear combination of elements of
that equals
.