1
$\begingroup$

Given a matroid $(S, F)$, $\forall x,y,z \in S$, if $\{x\}, \{y\}, \{z\} \in F$, $\{x,y\} \notin F, \{y,z\} \notin F$, will $\{x, z\} \notin F$? I can't figure this out by definition of matroid.

Motivation from an example from Corollary 3.1.7 in Lovasz's Matching Theory:

Given a graph $G$, the class of sets of vertices, where each set can be missed by some maximum matching in $G$, forms a matroid. Let $D \subseteq V(G)$ be the set of those points of $G$, where each point can be missed by some maximum matching. For all $u,v \in D$, define $u \sim v$ if and only if $u=v$ or no maximum matching misses both $u$ and $v$. Then $\sim$ is an equivalence relation on $D$.

Thanks!

1 Answers 1

2

The easiest way to see this is to use the rank function of the matroid. In terms of the question we have that $r(x)=r(y)=r(z)=r(x,y)=r(y,z)=1$, and we want to prove that $r(x,z) \leq 1$. By submodularity, we have that

$ 2=r(x,y)+r(y,z) \geq r(x,y,z)+r(y)=r(x,y,z)+1. $

Thus, $r(x,y,z) \leq 1$. By monotonicity, we have $r(x,z) \leq 1$ as required.

Note that I am implicitly assuming $x \neq z$, otherwise the claim is false.