Basis of a matroid explained

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:^[1]

• 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 :^{[2] [3]}

• Basis-exchange property: if

a\in A\setminus B , then there exists an element b\in B\setminus A such that (A \setminus \{ a \}) \cup \{b\} 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 \{ a \}) \cup \{b\} and (B \setminus \{ b \}) \cup \{a\} are bases. Brualdi^[4] 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 \{ a \}) \cup \{f(a)\} 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[m] , (A \setminus A _{i)} \cup B _{i} is a basis.^[5]

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.^[6]

Cardinality

It follows from the basis exchange property that no member of

l{B} 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, l{B}) , where E is the ground-set and l{B} is a collection of subsets of E , called "bases", with the following properties:^{[7] [8]}

(B1) There is at least one base --

l{B} 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 \{ a \}) \cup \{b\} 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, l{B}) is a finite matroid, we can define the orthogonal or dual matroid (E, l{B} ^{*)} by calling a set a basis in l{B} ^{*} if and only if its complement is in l{B} . It can be verified that (E, l{B} ^{*)} is indeed a matroid. The definition immediately implies that the dual of (E, l{B} ^{*)} is (E, l{B}) .^[9]

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 \{ a \}) \cup \{b\} 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, l{C}) , where E is the ground-set and l{C} is a collection of subsets of E , 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

C _{1} \cup C _{2} \setminus \{x\} contains a circuit.

Another property of circuits is that, if a set

J is independent, and the set J \cup \{x\} is dependent (i.e., adding the element x makes it dependent), then J \cup \{x\} 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.

Notes and References

1. Web site: Ardila. Federico. 2007. Matroids, lecture 3. live. youtube. https://web.archive.org/web/20200214051519/https://www.youtube.com/watch?v=L7U1k_urI0U . 2020-02-14 .
2. 2016-01-01. An infinite family of excluded minors for strong base-orderability. Linear Algebra and Its Applications. en. 488. 396–429. 1507.05521. 10.1016/j.laa.2015.09.055. 0024-3795 . Bonin. Joseph E.. Savitsky. Thomas J.. 119161534.
   • Web site: Joseph E. Bonin . Thomas J. Savitsky . April 2016 . Excluded Minors for (Strongly) Base-Orderable Matroids .
3. Web site: Matroids Lecture 2: Bases. YouTube.
4. Brualdi. Richard A.. 1969-08-01. Comments on bases in dependence structures. Bulletin of the Australian Mathematical Society. en. 1. 2. 161–167. 10.1017/S000497270004140X. 1755-1633. free.
5. Greene. Curtis. Magnanti. Thomas L.. 1975-11-01. Some Abstract Pivot Algorithms. SIAM Journal on Applied Mathematics. en-US. 29. 3. 530–539. 10.1137/0129045. 0036-1399. 1721.1/5113. free.
6. McGuinness. Sean. 2014-07-01. A base exchange property for regular matroids. Journal of Combinatorial Theory, Series B. en. 107. 42–77. 10.1016/j.jctb.2014.02.004. 0095-8956. free.
7. . Section 1.2, "Axiom Systems for a Matroid", pp. 7–9.
8. Web site: Federico. Ardila. 2012. Matroids: Lecture 6. Youtube.
9. Web site: Ardila. Federico. 2012. Matroids lecture 7. Youtube.