dual matroid

Duality is an involution: for all $M$, $(M^\backslash ast)^\backslash ast=M$.

An alternative definition of the dual matroid is that its basis sets are the complements of the basis sets of $M$. 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 $M$ are complementary to the cyclic sets (unions of circuits) of $M^\backslash ast$, and vice versa.

If $r$ is the rank function of a matroid $M$ on ground set $E$, then the rank function of the dual matroid is $r^\backslash ast(S)=r(E\; \backslash setminus\; S)+|S|-r(E)$.

A matroid minor is formed from a larger matroid $M$ by two operations: the restriction $M\backslash setminus\; x$ deletes element $x$ from $M$ without changing the independence or rank of the remaining sets, and the contraction $M/x$ deletes $x$ from $M$ after subtracting one from the rank of every set it belongs to. These two operations are dual: $M\backslash setminus\; x=(M^\backslash ast/x)^\backslash ast$ and $M/x=(M^\backslash ast\backslash setminus\; x)^\backslash ast$. Thus, a minor of a dual is the same thing as a dual of a minor.{{harvtxt|Schrijver|2003}}, p. 653.

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.{{citation

| last1 = Jensen | first1 = Per M.

| last2 = Korte | first2 = Bernhard

| doi = 10.1137/0211014

| issue = 1

| journal = SIAM Journal on Computing

| mr = 646772

| pages = 184–190

| title = Complexity of matroid property algorithms

| volume = 11

| year = 1982}}.

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:

• The binary matroids (matroids representable over GF(2)), the matroids representable over any other field, and the regular matroids, are all self-dual families.{{harvtxt|Whitney|1935}}, Section 13, "Orthogonal hyperplanes and dual matroids".
• The gammoids form a self-dual family. The strict gammoids are dual to the transversal matroids.{{harvtxt|Schrijver|2003}}, pp. 659–661; {{harvtxt|Welsh|2010}}, pp. 222–223.
• The uniform matroids and partition matroids are self-dual. The dual to a uniform matroid $U\{\}^r\_n$ is the uniform matroid $U\{\}^\{n-r\}\_n$. Within the family of uniform matroids, any matroid where $r=n/2$ is dual exactly to itself.{{harvtxt|Oxley|2006}}, pp. 77 & 111.
• The dual of a graphic matroid is itself graphic if and only if the underlying graph is planar; the matroid of the dual of a planar graph is the same as the dual of the matroid of the graph. Thus, the family of graphic matroids of planar graphs is self-dual.{{citation

| last = Tutte | first = W. T.

| journal = Journal of Research of the National Bureau of Standards

| mr = 0179781

| pages = 1–47

| title = Lectures on matroids

| url = http://cdm16009.contentdm.oclc.org/cdm/ref/collection/p13011coll6/id/66650

| volume = 69B

| year = 1965

| doi=10.6028/jres.069b.001| doi-access = free

}}.

• Among the graphic matroids, and more generally among the binary matroids, the bipartite matroids (matroids in which every circuit is even) are dual to the Eulerian matroids (matroids that can be partitioned into disjoint circuits).{{citation

| last = Welsh | first = D. J. A. | authorlink = Dominic Welsh

| journal = Journal of Combinatorial Theory

| mr = 0237368

| pages = 375–377

| title = Euler and bipartite matroids

| volume = 6

| issue = 4 | year = 1969

| doi=10.1016/s0021-9800(69)80033-5| doi-access = free

}}.{{citation

| last1 = Harary | first1 = Frank | author1-link = Frank Harary

| last2 = Welsh | first2 = Dominic | author2-link = Dominic Welsh

| contribution = Matroids versus graphs

| doi = 10.1007/BFb0060114

| location = Berlin

| mr = 0263666

| pages = 155–170

| publisher = Springer

| series = Lecture Notes in Mathematics

| title = The Many Facets of Graph Theory (Proc. Conf., Western Mich. Univ., Kalamazoo, Mich., 1968)

| volume = 110

| year = 1969| isbn = 978-3-540-04629-5 }}.

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.{{Cite web|last=Federico|first=Ardila|date=2012|title=Matroids Lecture 9|website=YouTube |url=https://www.youtube.com/watch?v=vcsLtgdiWGs&list=PL-XzhVrXIVeSu_b29hbX5xJ0bRThokU8a&index=9&t=124s}}

{{reflist}}

• {{citation |editor-last=Kung |editor-first=Joseph P. S.v|title=A Source Book in Matroid Theory |publisher=Birkhäuser |isbn=978-0-8176-3173-4 |location=Boston |year=1986 |mr=0890330 |doi=10.1007/978-1-4684-9199-9 |url=https://archive.org/details/sourcebookinmatr0000kung}}.

Category:Matroid theory

Matroid