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

19) Let M = (E, S) be a matroid and ${\mathcal {B}}$ the family of all its bases. Let A, B ∈ ${\mathcal {B}}$ such that A $\neq$ 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}∈ ${\mathcal {B}}$.

Solution

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

• $1.\implies |A|\leq |B|$
• $2.\implies |B|\leq |A|$
• but then $A\not =B\implies |A|<|B|or|B|<|A|$ which has been disproved in assignment 16.

b) Assume it is not the case:

$\neg \forall x\in A:~$	$\exists y\in B:\$	$[(A\setminus \{x\})\cup \{y\}\in {\mathcal {B}}]$
$\exists x\in A:~$	$\neg \exists y\in B:\$	$[(A\setminus \{x\})\cup \{y\}\in {\mathcal {B}}]$
$\exists x\in A:~$	$\forall y\in B:\$	$\neg [(A\setminus \{x\})\cup \{y\}\in {\mathcal {B}}]$
$\exists x\in A:~$	$\forall y\in B:\$	$[(A\setminus \{x\})\cup \{y\}\not \in {\mathcal {B}}]$

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

• $\exists x\in A:\forall y\in B:[(A\setminus \{x\})\cup \{y\}\not \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