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.
As an example, consider the matroid over the ground-set R2 (the vectors in the two-dimensional Euclidean plane), with the following independent sets: 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:[1] All matroids satisfy the following properties, for any two distinct bases
:[2][3] 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
Regular matroids have the unique exchange property, meaning that for some
[6] 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.
It is conjectured that all matroids satisfy the following property:[2] 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'.
The bases of a matroid characterize the matroid completely: a set is independent if and only if it is a subset of a basis.
, called "bases", with the following properties:[7][8] (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.
is a finite matroid, we can define the orthogonal or dual matroid
by calling a set a basis in
The definition immediately implies that the dual of
Using duality, one can prove that the property (B2) can be replaced by the following:(B2*) If
is a basis.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.
, called "circuits", with the following properties:[8] Another property of circuits is that, if a set
is independent, and the set
is dependent (i.e., adding the element
contains a unique circuit
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