Leigh.Samphier/Sandbox/Matroid satisfies Rank Axioms/Necessary Condition

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S$ be a finite set.

Let $\rho : \powerset S \to \Z$ be the rank function of a matroid on $S$.


Then $\rho$ satisfies the rank axioms:

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


Proof

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 Leigh.Samphier/Sandbox/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:

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

$\Box$


Case 2: $y \notin Y$

We have:

\(\displaystyle \map \rho X + 1\) \(>\) \(\displaystyle \map \rho X\)
\(\displaystyle \) \(\ge\) \(\displaystyle \card{Y \setminus \set y}\) Definition of Rank Function
\(\displaystyle \) \(=\) \(\displaystyle \card Y - \card{Y \cap \set y}\) Cardinality of Set Difference
\(\displaystyle \) \(=\) \(\displaystyle \card Y - \O\) Intersection With Singleton is Disjoint if Not Element
\(\displaystyle \) \(=\) \(\displaystyle \card Y - 0\) Cardinality of Empty Set
\(\displaystyle \) \(=\) \(\displaystyle \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, 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 Leigh.Samphier/Sandbox/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:

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

Hence:

\(\displaystyle \card{Y \cup Z'}\) \(=\) \(\displaystyle \card Z\)
\(\displaystyle \) \(=\) \(\displaystyle \map \rho A\)
\(\displaystyle \) \(>\) \(\displaystyle \map \rho X\)
\(\displaystyle \) \(\ge\) \(\displaystyle \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:

\(\displaystyle \map \rho {X \cup \set y}\) \(\ge\) \(\displaystyle \card{Y \cup \set y}\) Definition of Rank Function (Matroid)
\(\displaystyle \) \(=\) \(\displaystyle \card Y + \card{\set y}\) Corollary of Cardinality of Set Union
\(\displaystyle \) \(=\) \(\displaystyle \card Y + 1\) Cardinality of Singleton
\(\displaystyle \) \(>\) \(\displaystyle \card Y\)
\(\displaystyle \) \(=\) \(\displaystyle \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, z} = X \cup \set z$

Hence:

$\map \rho {X \cup \set{y, 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, z}} = \map \rho X$

$\blacksquare$


Sources