Circuit of a 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: It has two bases, which are the sets , . 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 $A$ and $B$:
*

* Basis-exchange property: if $a\in A\setminus B$, then there exists an element $b\in B\setminus A$ such that $(A \setminus \) \cup \$ is a basis.
* Symmetric basis-exchange property: if $a\in A\setminus B$, then there exists an element $b\in B\setminus A$ such that both $(A \setminus \) \cup \$ and $(B \setminus \) \cup \$ are bases. Brualdi showed that it is in fact equivalent to the basis-exchange property.
* Multiple symmetric basis-exchange property: if $X\subseteq A\setminus B$, then there exists a subset $Y\subseteq B\setminus A$ such that both $(A \setminus X) \cup Y$ and $(B \setminus Y) \cup X$ 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 ''$f$'' from ''$A$'' to $B$, such that for every $a\in A\setminus B$, $(A \setminus \) \cup \$ is a basis. Brualdi showed that it is equivalent to the basis-exchange property.
*Partition basis-exchange property: For each partition $(A_1, A_2, \ldots, A_m)$ of ''$A$'' into ''m'' parts, there exists a partition $(B_1, B_2, \ldots, B_m)$ of $B$ into ''m'' parts, such that for every i\in /math>, $(A \setminus A_i) \cup B_i$ 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 $b\in B\setminus A$ need not be unique. Regular matroids have the unique exchange property, meaning that for ''some'' $a\in A\setminus B$, the corresponding ''b'' is unique.

Cardinality

It follows from the basis exchange property that no member of $\mathcal$ 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 $M$ to be a pair $(E,\mathcal)$, where $E$ is the ground-set and $\mathcal$ is a collection of subsets of $E$, called "bases", with the following properties:. Section 1.2, "Axiom Systems for a Matroid", pp. 7–9.

:(B1) There is at least one base -- $\mathcal$ is nonempty;

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

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

(B2*) If $A$ and $B$ are distinct bases, and $b\in B\setminus A$, then there exists an element $a\in A\setminus B$ such that $(A \setminus \) \cup \$ 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 $M$ to be a pair $(E,\mathcal)$, where $E$ is the ground-set and $\mathcal$ is a collection of subsets of $E$, 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 C₁ and C₂ are circuits, and ''x'' is an element in their intersection, then $C_1 \cup C_2 \setminus \$ contains a circuit.

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

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.

References

{{reflist

Matroid theory