Matroid Duals

• Let be a matroid on . The Dual Matroid of , denoted is defined as the matroid such that
  • It is also on
  • A set in is independent if and only if there exists a basis in that is disjoint from it.

Definitions §

• is a cobasis of if they form a basis in .

  • (Wilson 32.2) If is a basis of , then is a basis on .
  • (Wilson 32.5) Every cobasis of a matroid intersects with every cycle.
    • Remark: This generalizes Wilson 9.3.

• is a cocycle of if they form a cycle in

  • (Wilson 32.4) Every cocycle of a matroid intersects every basis.
    • Remark: This generalizes Wilson 9.3a.z.

• The corank of is defined as the rank of ¹

  • (Wilson 32.1) The rank function of the dual , denoted may be defined as:
    Where .

Theorems §

• Matroid Duality is involutionary
• The graphic and cogrpahic matroids are duals. ²

• (Wilson e32.8) Let be a matroid. For cycle and cocycle , we have

  • Proof: Let be a cycle and a cocycle respectively. be a basis and a cobasis respectively.

    By Wilson 32.4 every cocycle intersects with every basis at least once. By Wilson 32.5, the same is true for cobases and cycles. Then, by Inclusion-Exclusion and Wilson 32.2.

• (Wilson e32.9) is Eulerian if and only if is bipartite.

  • Remark: This generalizes Wilson e15.9.

Links §

• Matroid Definitions and Constructs
• Matroid Types

Footnotes §

1. It is analogous to the concept of nullity in Linear Algebra. ↩

2. This follows from here. ↩