Matroids
Dual
construct the dual of a matroid
Calling Sequence
Parameters
Description
Examples
References
Dual(M)
M
-
Matroid
The dual M* of a matroid M is itself a matroid on the same ground set. The bases of M* are the complements of bases of M.
The operations of deletion and contraction are dual to each other. That is, M∖e* is isomorphic to M*/e.
The Tutte polynomial of the dual of a matroid simply swaps the roles of the variables.
The dual of a representable matroid is the matroid on its orthogonal complement. More precisely, if M is the matroid representable by the columns of a matrix A, and B is a matrix whose rows form the orthogonal complement to the rows of A, then M* is the matroid representable by the columns of B.
Given a planar graph G, the dual of the matroid underlying G is the graph dual of G.
The dual of the dual of a matroid M is itself.
with⁡Matroids:
Consider the following matroid, M.
A≔Matrix⁡1,1,1,0,0,0,0,0,0,1,1,1,1,0,0,1,0,0,0,1,0,0,1,0,0,0,1,0,0,2
A≔111000000111100100010010001002
M≔Matroid⁡A
M≔thⅇ lⅈnⅇar matroⅈⅆ whosⅇ grounⅆ sⅇt ⅈs thⅇ sⅇt of column vⅇctors of thⅇ matrⅈx:111000000111100100010010001002
B≔Bases⁡M
B≔1,2,3,4,6,1,2,3,5,6,1,3,4,5,6,2,3,4,5,6
The bases of the dual of M are the complements of the bases of M.
M2≔Dual⁡M
M2≔a matroⅈⅆ on 6 ⅇlⅇmⅇnts wⅈth 4 basⅇs of sⅈzⅇ 1
B2≔Bases⁡M2
B2≔1,2,4,5
The Tutte polynomial of M2 is the Tutte polynomial of M with the variables swapped.
T≔TuttePolynomial⁡M,x,y
T≔x5+x4+x3+x2⁢y
T2≔TuttePolynomial⁡M2,y,x
T2≔x5+x4+x3+x2⁢y
James G. Oxley. Matroid Theory (Oxford Graduate Texts in Mathematics). New York: Oxford University Press. 2006.
See Also
Matroids[Contraction]
Matroids[Deletion]
Download Help Document