Английская Википедия:Basis of a matroid

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Шаблон:Short description 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: Шаблон:Block indentIt 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]

  • 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 kc elements from each category c, the bases are all sets which contain exactly kc 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>A</math> and <math>B</math>:[2][3]

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

Cardinality

It follows from the basis exchange property that no member of <math>\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:[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'.

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>M</math> to be a pair <math>(E,\mathcal{B})</math>, where <math>E</math> is the ground-set and <math>\mathcal{B}</math> is a collection of subsets of <math>E</math>, called "bases", with the following properties:[7][8]

(B1) There is at least one base -- <math>\mathcal{B}</math> is nonempty;
(B2) If <math>A</math> and <math>B</math> are distinct bases, and <math>a\in A\setminus B</math>, then there exists an element <math>b\in B\setminus A</math> such that <math>(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>(E,\mathcal{B})</math> is a finite matroid, we can define the orthogonal or dual matroid <math>(E,\mathcal{B}^*)</math> by calling a set a basis in <math>\mathcal{B}^* </math> if and only if its complement is in <math>\mathcal{B}</math>. It can be verified that <math>(E,\mathcal{B}^*)</math> is indeed a matroid. The definition immediately implies that the dual of <math>(E,\mathcal{B}^*)</math> is <math>(E,\mathcal{B})</math>.[9]Шаблон:Rp[10]

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

(B2*) If <math>A</math> and <math>B</math> are distinct bases, and <math>b\in B\setminus A</math>, then there exists an element <math>a\in A\setminus B</math> such that <math>(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>M</math> to be a pair <math>(E,\mathcal{C})</math>, where <math>E</math> is the ground-set and <math>\mathcal{C}</math> is a collection of subsets of <math>E</math>, called "circuits", with the following properties:[8]

(C1) The empty set is not a circuit;
(C2) A proper subset of a circuit is not a circuit;
(C3) If C1 and C2 are distinct circuits, and x is an element in their intersection, then <math>C_1 \cup C_2 \setminus \{x\}</math> contains a circuit.

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

See also

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

References

Шаблон:Reflist