Dominik Farhan

Matroids: Duality

Let $M = (X, S)$ be a matroid than we define the dual $M^* = (X, S^*)$ where $S^* = \{ x \mid x \subseteq X, \exists B \text{ base } M: B \cap x = \emptyset\}$ .

Equivalent to it is the following: the set of basis of $M^*$ is the set $\{F \mid X \setminus F \text{ is a base of } M\}$ (then $S$ is defined as the set of bases + all their subsets).

Theorem (Dual of dual is the original matroid).

M^{**} = M

Solution (Dual of dual is the original matroid)

Proof. Let

B^{**} \in S^{**}

then there is basis

B^*

M^*

such that

B^*\cap B^{**} = \emptyset

which means that there is a basis of

M

for which

B^{**} \cap X \setminus B = \emptyset

, which by the definition of a dual matroid is the same as saying that

B^{**} \in S

Theorem (Rank of a dual). Let

M^*

be the dual matroid then

r^*(A) = |A| - r(X) + r(X \setminus A).

Solution (Rank of a dual)

Proof.

Let $J\subseteq A$ be the maximal independent set with regard to $S^*$ . Let $Z\subseteq X\setminus A$ be the maximal independent set with regard to $S$ . Let $B$ be a basis of $M$ containing $Z$ .

With this, its trivial: $r^*(A) = |J| = |A| - (|B| - |Z|) = |A| - r(X) + r(X\setminus A).$

Definition (circuit). minimal dependent subset of

S

with respect to inclusion.

Definition (closed set).

A\subseteq X

is closed if

\forall y \in X\setminus A: r(A\cup {y}) > r(A)

Definition (co-circuit). circuit of a dual.

Definition (co-base). base of a dual.

Theorem (Circuits of a graph). Let

G

be a graph. For

Y \subset E

Y

is cocircuit iff

Y

is a minimal edge-cut.

Proof ( $\implies$ ). Let

Y

be a cocircuit but let there be base

B

such that

Y \cap B = \emptyset

. However, we know that for any

A

A \cap B = \emptyset

means that

A

is independent in

S^*

, hence contradiction.

Proof ( $\Longleftarrow$ ). Let

Y

be a minimal edge cut but not cocircuit. Two possibilities.

Y

is independent in the dual. Then there is base

B

M

which is not intersected by

Y

-> contradiction. Or

Y

is not minimal dependent. Then we can remove some

y

from

Y

and the result is still dependent. This result is also a minimal edge-cut (intersects every base) and we have contradiction with minimality of the edge cut.

Corollary. If

G

is planar,

G^*

geometric dual then

M(G^*) = M^*(G)