Leigh.Samphier/Sandbox/Bound for Cardinality of Matroid Circuit

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $M = \struct {S, \mathscr I}$ be a matroid.

Let $C \subseteq S$ be a circuit of $M$.

Let $\rho: \powerset S \to \Z$ denote the rank function of $M$.


Then:

$\card C \le \map \rho S + 1$

Proof

By definition of a circuit:

$C$ is dependent

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

$C \ne \O$


Let $x \in C$.

From Set Difference is Subset and Set Difference with Disjoint Set:

$C \setminus \set x \subsetneq C$

From Leigh.Samphier/Sandbox/Proper Subset of Matroid Circuit is Independent and matroid axiom $(\text I 1)$:

$C \setminus \set x \in \mathscr I$


We have:

\(\ds \map \rho S\) \(\ge\) \(\ds \card{C \setminus \set x}\) Definition of Rank Function
\(\ds \) \(=\) \(\ds \card C - \card{\set x}\) Cardinality of Set Difference with Subset
\(\ds \) \(=\) \(\ds \card C - 1\) Cardinality of Singleton
\(\ds \leadsto \ \ \) \(\ds \map \rho S + 1\) \(\ge\) \(\ds \card C\) Adding 1 to both sides of the equqrion

$\blacksquare$

Sources