Matroid with complemented basis sets
In matroid theory, the dual of a matroid formula_1 is another matroid formula_2 that has the same elements as formula_1, and in which a set is independent if and only if formula_1 has a basis set disjoint from it.
Matroid duals go back to the original paper by Hassler Whitney defining matroids. They generalize to matroids the notions of plane graph duality.
Basic properties.
Duality is an involution: for all formula_1, formula_6.
An alternative definition of the dual matroid is that its basis sets are the complements of the basis sets of formula_1. The basis exchange axiom, used to define matroids from their bases, is self-complementary, so the dual of a matroid is necessarily a matroid.
The flats of formula_1 are complementary to the cyclic sets (unions of circuits) of formula_2, and vice versa.
If formula_10 is the rank function of a matroid formula_1 on ground set formula_12, then the rank function of the dual matroid is formula_13.
Minors.
A matroid minor is formed from a larger matroid formula_1 by two operations: the restriction formula_15 deletes element formula_16 from formula_1 without changing the independence or rank of the remaining sets, and the contraction formula_18 deletes formula_16 from formula_1 after subtracting one from the rank of every set it belongs to. These two operations are dual: formula_21 and formula_22. Thus, a minor of a dual is the same thing as a dual of a minor.
Self-dual matroids.
An individual matroid is self-dual (generalizing e.g. the self-dual polyhedra for graphic matroids) if it is isomorphic to its own dual. The isomorphism may, but is not required to, leave the elements of the matroid fixed. Any algorithm that tests whether a given matroid is self-dual, given access to the matroid via an independence oracle, must perform an exponential number of oracle queries, and therefore cannot take polynomial time.
Matroid families.
Many important matroid families are self-dual, meaning that a matroid belongs to the family if and only if its dual does. Many other matroid families come in dual pairs. Examples of this phenomenon include:
It is an open problem whether the family of algebraic matroids is self-dual.
If "V" is a vector space and "V"* is its orthogonal complement, then the linear matroid of "V" and the linear matroid of "V"* are duals. As a corollary, the dual of any linear matroid is a linear matroid.
References.
 ;templatestyles src="Reflist/styles.css" / ;