Equivalence of Definitions of Matroid Rank Axioms

From ProofWiki
Jump to navigation Jump to search


This article needs proofreading.
Please check it for mathematical errors.
If you believe there are none, please remove {{Proofread}} from the code.
To discuss this page in more detail, feel free to use the talk page.
When this work has been completed, you may remove this instance of {{Proofread}} from the code.


Theorem

Let $S$ be a finite set.

Let $\rho : \powerset S \to \Z$ be a mapping from the power set of $S$ to the integers.


The following statements are equivalent:

Condition 1

$\rho$ satisfies formulation 1 of the rank axioms:

\((\text R 1)\)   $:$   \(\ds \map \rho \O = 0 \)      
\((\text R 2)\)   $:$     \(\ds \forall X \in \powerset S \land y \in S:\) \(\ds \map \rho X \le \map \rho {X \cup \set y} \le \map \rho X + 1 \)      
\((\text R 3)\)   $:$     \(\ds \forall X \in \powerset S \land y, z \in S:\) \(\ds \map \rho {X \cup \set y} = \map \rho {X \cup \set z} = \map \rho X \implies \map \rho {X \cup \set y \cup \set z} = \map \rho X \)      


Condition 2

$\rho$ satisfies formulation 2 of the rank axioms:

\((\text R 4)\)   $:$     \(\ds \forall X \in \powerset S:\) \(\ds 0 \le \map \rho X \le \size X \)      
\((\text R 5)\)   $:$     \(\ds \forall X, Y \in \powerset S:\) \(\ds X \subseteq Y \implies \map \rho X \le \map \rho Y \)      
\((\text R 6)\)   $:$     \(\ds \forall X, Y \in \powerset S:\) \(\ds \map \rho {X \cup Y} + \map \rho {X \cap Y} \le \map \rho X + \map \rho Y \)      


Condition 3

$\rho$ is the rank function of a matroid $M = \struct{S, \mathscr I}$.


Proof

Condition 1 implies Condition 3

Let $\rho$ satisfy formulation 1 of the rank axioms:

\((\text R 1)\)   $:$   \(\ds \map \rho \O = 0 \)      
\((\text R 2)\)   $:$     \(\ds \forall X \in \powerset S \land y \in S:\) \(\ds \map \rho X \le \map \rho {X \cup \set y} \le \map \rho X + 1 \)      
\((\text R 3)\)   $:$     \(\ds \forall X \in \powerset S \land y, z \in S:\) \(\ds \map \rho {X \cup \set y} = \map \rho {X \cup \set z} = \map \rho X \implies \map \rho {X \cup \set y \cup \set z} = \map \rho X \)      



Lemma 1
$\forall A, B \subseteq S: A \subseteq B \implies \map \rho A \le \map \rho B$

$\Box$


Lemma 2
$\forall A \subseteq S: \map \rho A \le \card A$

$\Box$


Lemma 3

Let:

$A \subseteq S : \map \rho A = \card A$

Let:

$B \subseteq S : \forall b \in B \setminus A : \map \rho {A \cup \set b} \ne \card{A \cup \set b}$


Then:

$\map \rho {A \cup B} = \map \rho A$

$\Box$


Let:

$\mathscr I = \set{X \subseteq S : \map \rho X = \card X}$

It is to be shown that:

and


Matroid Axioms

Matroid Axiom $(\text I 1)$

We have:

\(\ds \map \rho \O\) \(=\) \(\ds 0\) Rank axiom $(\text R 1)$
\(\ds \) \(=\) \(\ds \card \O\) Cardinality of Empty Set

So:

$\O \in \mathscr I$

Hence:

$M$ satisfies matroid axiom $(\text I 1)$.

$\Box$


Matroid Axiom $(\text I 2)$

Let

$X \in \mathscr I$


Aiming for a contradiction, suppose

$\exists Y \subseteq X : Y \notin \mathscr I$

Let:

$Y_0 \subseteq X : \card {Y_0} = \max \set{\card Z : Z \subseteq X \land Z \notin \mathscr I}$


By definition of $\mathscr I$:

$Y_0 \notin \mathscr I \leadsto \map \rho {Y_0} \ne \card {Y_0}$

From Lemma 2:

$\map \rho {Y_0} < \card {Y_0}$


As $X \in \mathscr I$ then:

$Y_0 \ne X$

From Set Difference with Proper Subset:

$X \setminus Y_0 \ne \O$


Let $y \in X \setminus Y_0$.


We have:

\(\ds \card {Y_0} + 1\) \(=\) \(\ds \card {Y_0 \cup \set y}\) Corollary of Cardinality of Set Union
\(\ds \) \(=\) \(\ds \map \rho {Y_0 \cup \set y}\) As $\card {Y_0} = \max \set{\card Z : Z \subseteq X \land Z \notin \mathscr I}$
\(\ds \) \(\le\) \(\ds \map \rho {Y_0} + 1\) Rank axiom $(\text R 2)$
\(\ds \) \(<\) \(\ds \card {Y_0} + 1\) As $\map \rho {Y_0} < \card {Y_0}$

This is a contradiction.


So:

$\forall Y \subseteq X : Y \in \mathscr I$

Hence:

$M$ satisfies matroid axiom $(\text I 2)$.

$\Box$


Matroid Axiom $(\text I 3)$

Let

$U \in \mathscr I$
$V \subseteq S$
$\card U < \card V$


We prove the contrapositive statement:

$\paren{\forall x \in V \setminus U : U \cup \set x \notin \mathscr I} \implies V \notin \mathscr I$


Let for all $x \in V \setminus U$: $U \cup \set x \notin \mathscr I$

That is:

$\forall x \in V \setminus U : \map \rho {U \cup \set x} \ne \card {U \cup \set x}$


We have:

\(\ds \card V\) \(>\) \(\ds \card U\)
\(\ds \) \(=\) \(\ds \map \rho U\) As $U \in \mathscr I$
\(\ds \) \(=\) \(\ds \map \rho {U \cup V}\) Lemma 3
\(\ds \) \(\ge\) \(\ds \map \rho V\) Lemma 1

Hence:

$V \notin \mathscr I$

$\Box$


$\rho$ is Rank Function

Let $\rho_M$ be the rank function of the matroid $M = \struct{S, \mathscr I}$.


Let $X \subseteq S$.


By definition of the rank function:

$\map {\rho_M} X = \max \set{\card Y : Y \subseteq X, Y \in \mathscr I}$

Let $Y_0 \subseteq X$:

$\card {Y_0} = \max \set{\card Y : Y \subseteq X, Y \in \mathscr I}$

We have:

\(\ds \map {\rho_M} X\) \(=\) \(\ds \card {Y_0}\) By choice of $Y_0$
\(\ds \) \(=\) \(\ds \map \rho {Y_0}\) As $Y_0 \in \mathscr I$

So it remains to show:

$\map \rho {Y_0} = \map \rho X$


Case 1 : $Y_0 = X$

Let $Y_0 = X$.

Then:

$\map \rho {Y_0} = \map \rho X$

$\Box$


Case 2 : $Y_0 \ne X$

Let $Y_0 \ne X$.

Then:

$Y_0 \subsetneq X$

From Set Difference with Proper Subset:

$X \setminus Y_0 \ne \O$

By choice of $Y_0$:

$\forall y \in X \setminus Y_0 : Y_0 \cup \set y \notin \mathscr I$

That is:

$\forall y \in X \setminus Y_0 : \map \rho {Y_0 \cup \set y} \ne \card {Y_0 \cup \set y}$

From Lemma 3:

$\map \rho {Y_0} = \map \rho {Y_0 \cup X} = \map \rho X$

$\Box$


In either case:

$\map \rho {Y_0} = \map \rho X$

It follows that:

$\forall X \subseteq S : \map {\rho_M} X = \map \rho X$

Hence $\rho$ is the rank function of the matroid $M = \struct{S, \mathscr I}$.


$\Box$


Condition 3 implies Condition 2

Let $\rho$ be the rank function of a matroid $M = \struct{S, \mathscr I}$.


$\rho$ satisfies $(\text R 4)$

This follows immediately from Bounds for Rank of Subset.

$\Box$


$\rho$ satisfies $(\text R 5)$

This follows immediately from Rank Function is Increasing.

$\Box$


$\rho$ satisfies $(\text R 6)$

Let $X, Y \subseteq S$.


Let $A$ be a maximal independent subset of $X \cap Y$.

From Cardinality of Maximal Independent Subset Equals Rank of Set:

$\card A = \map \rho {X \cap Y}$


From Independent Subset is Contained in Maximal Independent Subset:

$\exists B \subseteq X \setminus Y : A \cup B$ is a maximal independent subset of $X$

Simiarly from Independent Subset is Contained in Maximal Independent Subset:

$\exists C \subseteq Y \setminus X : \paren{A \cup B} \cup C$ is a maximal independent subset of $X \cup Y$

and:

$\card{A \cup B \cup C} = \map \rho {X \cup Y}$


By matroid axiom $(\text I 2)$:

$A \cup C$ is an independent subset of $Y$.


We have:

\(\ds \map \rho X + \map \rho Y\) \(\ge\) \(\ds \card{A \cup B} + \card{A \cup C}\) Definition of rank function $\rho$
\(\ds \) \(=\) \(\ds \card{A \cup B} + \paren{\card A + \card C }\) Cardinality of Set Union: Corollary
\(\ds \) \(=\) \(\ds \paren{\card{A \cup B} + \card A } + \card C\) Sum of Cardinals is Associative
\(\ds \) \(=\) \(\ds \card{A \cup B \cup C} + \card A\) Cardinality of Set Union: Corollary
\(\ds \) \(=\) \(\ds \map \rho {X \cup Y} + \map \rho {X \cap Y}\) Definition of rank function $\rho$

$\Box$


Condition 2 implies Condition 1

Let $\rho$ satisfy formulation 2 of the rank axioms:

\((\text R 4)\)   $:$     \(\ds \forall X \in \powerset S:\) \(\ds 0 \le \map \rho X \le \size X \)      
\((\text R 5)\)   $:$     \(\ds \forall X, Y \in \powerset S:\) \(\ds X \subseteq Y \implies \map \rho X \le \map \rho Y \)      
\((\text R 6)\)   $:$     \(\ds \forall X, Y \in \powerset S:\) \(\ds \map \rho {X \cup Y} + \map \rho {X \cap Y} \le \map \rho X + \map \rho Y \)      



$\rho$ satisfies $(\text R 1)$

We have:

\(\ds 0\) \(\le\) \(\ds \map \rho \O\) Rank axiom $(\text R 4)$
\(\ds \) \(\le\) \(\ds \card \O\) Rank axiom $(\text R 4)$
\(\ds \) \(=\) \(\ds 0\) Cardinality of Empty Set

Hence:

$\map \rho \O = 0$

$\Box$


$\rho$ satisfies $(\text R 2)$

Let $X \subseteq S$.

Let $y \in S$.


We have:

\(\ds \map \rho X\) \(\le\) \(\ds \map \rho {X \cup y}\) Rank axiom $(\text R 5)$
\(\ds \) \(\le\) \(\ds \map \rho X + \map \rho {\set y} - \map \rho {X \cup \set y}\) Rank axiom $(\text R 6)$
\(\ds \) \(\le\) \(\ds \map \rho X + \map \rho {\set y}\)
\(\ds \) \(\le\) \(\ds \map \rho X + \card {\set y}\) Rank axiom $(\text R 4)$
\(\ds \) \(\le\) \(\ds \map \rho X + 1\) Cardinality of Singleton

This proves rank axiom $(\text R 2)$

$\Box$


$\rho$ satisfies $(\text R 3)$

Let $X \subseteq S$.

Let $x, y \in S$.

Let $\map \rho {X \cup \set x} = \map \rho {X \cup \set y} = \map \rho X$.


We have:

\(\ds \map \rho X\) \(\le\) \(\ds \map \rho {X \cup \set x \cup \set y }\) Rank axiom $(\text R 5)$
\(\ds \) \(=\) \(\ds \map \rho {\paren{X \cup \set x} \cup \paren{X \cup \set y} }\)
\(\ds \) \(\le\) \(\ds \map \rho {X \cup \set x} + \map \rho {X \cup \set x} - \map \rho {\paren{X \cup \set x} \cap \paren{X \cup \set y} }\) Rank axiom $(\text R 6)$
\(\ds \) \(\le\) \(\ds \map \rho {X \cup \set x} + \map \rho {X \cup \set x} - \map \rho X\)
\(\ds \) \(=\) \(\ds \map \rho X + \map \rho X - \map \rho X\)
\(\ds \) \(=\) \(\ds \map \rho X\)

Hence:

$\map \rho {X \cup \set x \cup \set y} = \map \rho X$

This proves rank axiom $(\text R 3)$

$\blacksquare$


Condition 3 implies Condition 1

Let $\rho$ be the rank function of a matroid $M = \struct{S, \mathscr I}$ on $S$


$\rho$ satisfies $(\text R 1)$

$\rho$ satisfies $(\text R 1)$ follows immediately from Rank of Empty Set is Zero.

$\Box$


$\rho$ satisfies $(\text R 2)$

Let:

$X \subseteq S$
$y \in S$

From Rank Function is Increasing:

$\map \rho X \le \map \rho {X \cup \set y}$


Let $Y$ be a maximal independent subset of $X \cup \set y$.

From Cardinality of Maximal Independent Subset Equals Rank of Set

$\card Y = \map \rho {X \cup \set y}$

By matroid axiom $(\text I 2)$:

$Y \setminus \set y \in \mathscr I$

We now consider two cases.

Case 1: $y \in Y$

We have:

\(\ds \map \rho X\) \(\ge\) \(\ds \card{Y \setminus \set y}\) Definition of Rank Function
\(\ds \) \(=\) \(\ds \card Y - \card{Y \cap \set y}\) Cardinality of Set Difference
\(\ds \) \(=\) \(\ds \card Y - \card{\set y}\) Singleton of Element is Subset
\(\ds \) \(=\) \(\ds \card Y - 1\) Cardinality of Singleton
\(\ds \leadsto \ \ \) \(\ds \map \rho X + 1\) \(\ge\) \(\ds \card Y\) Add one to both sides

$\Box$


Case 2: $y \notin Y$

We have:

\(\ds \map \rho X + 1\) \(>\) \(\ds \map \rho X\)
\(\ds \) \(\ge\) \(\ds \card{Y \setminus \set y}\) Definition of Rank Function
\(\ds \) \(=\) \(\ds \card Y - \card{Y \cap \set y}\) Cardinality of Set Difference
\(\ds \) \(=\) \(\ds \card Y - \O\) Intersection With Singleton is Disjoint if Not Element
\(\ds \) \(=\) \(\ds \card Y - 0\) Cardinality of Empty Set
\(\ds \) \(=\) \(\ds \card Y\)

$\Box$


In either case:

$\map \rho X + 1 \ge \card Y = \map \rho {X \cup \set y}$

$\Box$


$\rho$ satisfies $(\text R 3)$

Let:

$X \subseteq S$
$y, z \in S$
Case 1: $y, z \notin X$

Let $A = X \cup \set y \cup \set z$.

From Rank Function is Increasing:

$\map \rho A \ge \map \rho X$

We now prove the contrapositive statement:

$\map \rho A > \map \rho X \implies$ either $\map \rho {X \cup \set y} > \map \rho X$ or $\map \rho {X \cup \set z} > \map \rho X$


Let $\map \rho A > \map \rho X$.

Let $Y$ be a maximal independent subset of $X$.

Let $Z$ be a maximal independent subset of $A$.

From Cardinality of Maximal Independent Subset Equals Rank of Set:

$\card Y = \map \rho X < \map \rho A = \card Z$

From Independent Set can be Augmented by Larger Independent Set there exists non-empty set $Z' \subseteq Z \setminus Y$:

$Y \cup Z' \in \mathscr I$
$\card{Y \cup Z'} = \card Z$


Aiming for a contradiction, suppose:

$y, z \notin Z'$

We have:

\(\ds Z'\) \(=\) \(\ds Z' \cap Z\)
\(\ds \) \(\subseteq\) \(\ds Z' \cap A\)
\(\ds \) \(=\) \(\ds Z' \cap \paren{X \cup \set y \cup \set z}\)
\(\ds \) \(=\) \(\ds \paren{Z' \cap X} \cup \paren{Z' \cap \paren{\set y \cup \set z} }\)
\(\ds \) \(=\) \(\ds \paren{Z' \cap X} \cup \O\)
\(\ds \) \(=\) \(\ds \paren{Z' \cap X}\)
\(\ds \) \(\subseteq\) \(\ds X\)
\(\ds \leadsto \ \ \) \(\ds Y \cup Z'\) \(\subseteq\) \(\ds X\)

Hence:

\(\ds \card{Y \cup Z'}\) \(=\) \(\ds \card Z\)
\(\ds \) \(=\) \(\ds \map \rho A\)
\(\ds \) \(>\) \(\ds \map \rho X\)
\(\ds \) \(\ge\) \(\ds \card{Y \cup Z'}\)

This is a contradiction.

Hence:

either $y \in Z'$ or $z \in Z'$


Without loss of generality, assume $y \in Z'$.

From matroid axiom $(\text I 2)$:

$Y \cup \set y \in \mathscr I$

We have:

\(\ds \map \rho {X \cup \set y}\) \(\ge\) \(\ds \card{Y \cup \set y}\) Definition of Rank Function (Matroid)
\(\ds \) \(=\) \(\ds \card Y + \card{\set y}\) Corollary of Cardinality of Set Union
\(\ds \) \(=\) \(\ds \card Y + 1\) Cardinality of Singleton
\(\ds \) \(>\) \(\ds \card Y\)
\(\ds \) \(=\) \(\ds \map \rho X\) Definition of Rank Function (Matroid)

This proves the contrapositive statement.

$\Box$


Case 2: Either $y \in X$ or $z \in X$

Without loss of generality, assume $y \in X$.


Let:

$\map \rho {X \cup \set y} = \map \rho {X \cup \set z} = \map \rho X$.

We have:

$X \cup \set y \cup \set z = X \cup \set z$

Hence:

$\map \rho {X \cup \set y \cup \set z} = \map \rho {X \cup \set z} = \map \rho X$

$\Box$


In either case:

$\map \rho {X \cup \set y} = \map \rho {X \cup \set z} = \map \rho X \implies \map \rho {X \cup \set y \cup \set z} = \map \rho X$

$\blacksquare$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Equivalence_of_Definitions_of_Matroid_Rank_Axioms&oldid=607908"