Dual matroid

In matroid theory, the dual of a matroid is another matroid that has the same elements as , and in which a set is independent if and only if has a basis set disjoint from it.[1][2][3]

Matroid duals go back to the original paper by Hassler Whitney defining matroids.[4] They generalize to matroids the notions of plane graph duality.

  1. ^ Schrijver, Alexander (2003), Combinatorial Optimization: Polyhedra and Efficiency. Vol. B: Matroids, Trees, Stable Sets, Algorithms and Combinatorics, vol. 24, Berlin: Springer-Verlag, p. 652, ISBN 3-540-44389-4, MR 1956925.
  2. ^ Welsh, D. J. A. (2010), Matroid Theory, Courier Dover Publications, p. 34, ISBN 9780486474397.
  3. ^ Oxley, James G. (2006), Matroid Theory, Oxford Graduate Texts in Mathematics, vol. 3, Oxford University Press, pp. 69–70, ISBN 9780199202508.
  4. ^ Whitney, Hassler (1935), "On the abstract properties of linear dependence", American Journal of Mathematics, 57 (3), The Johns Hopkins University Press: 509–533, doi:10.2307/2371182, hdl:10338.dmlcz/100694, JSTOR 2371182, MR 1507091. Reprinted in Kung (1986), pp. 55–79. See in particular section 11, "Dual matroids", pp. 521–524.