TU Wien:Diskrete Mathematik für Informatik UE (Gittenberger)/Übungen WS13/Beispiel 19

19) Let M = (E, S) be a matroid and $ℬ$ the family of all its bases. Let A, B ∈ $ℬ$ such that A $\ne$ B. Prove that

• (a) neither of the inclusions A⊆B and B⊆A holds,
• (b) for each x ∈ A there exists y ∈ B such that (A\{x})∪{y}∈ $ℬ$.

Solution

a) Assume: 1.$A\subseteq B$ or 2.$B\subseteq A$

• $1.⟹|A|\le |B|$
• $2.⟹|B|\le |A|$
• but then $A≠B⟹|A|<|B|or|B|<|A|$ which has been disproved in assignment 16.

b) Assume it is not the case:

$\mathrm{\neg }\mathrm{\forall }x\in A:$	$\mathrm{\exists }y\in B:$	$[(A\setminus \{x\})\cup \{y\}\in ℬ]$
$\mathrm{\exists }x\in A:$	$\mathrm{\neg }\mathrm{\exists }y\in B:$	$[(A\setminus \{x\})\cup \{y\}\in ℬ]$
$\mathrm{\exists }x\in A:$	$\mathrm{\forall }y\in B:$	$\mathrm{\neg }[(A\setminus \{x\})\cup \{y\}\in ℬ]$
$\mathrm{\exists }x\in A:$	$\mathrm{\forall }y\in B:$	$[(A\setminus \{x\})\cup \{y\}\in ̸ℬ]$

We know $|(A\setminus \{x\})\cup \{y\}|=|A|$, therefore it must be a basis or it is not in $S$

• $\mathrm{\exists }x\in A:\mathrm{\forall }y\in B:[(A\setminus \{x\})\cup \{y\}\in ̸S]$

But then:

• $A\cap B=\{\}$

Now we only have to provide counter evidence:

$M=(E,S),E=\{1,2,3\},S=\{\{\},\{1\},\{2\},\{3\},\{1,2\},\{2,3\}\}$

$\{1,2\},\{2,3\}$ are bases and not disjunct, therefore our assumption must be wrong