Given bases $A$, $B$ of a matroid there is a one-to-one mapping $\omega$ from $A$ to $B$ such that $(A - {a}) \cup {\omega(a)}$ is independent

Question

Given any two bases A and B of a matroid, there is a one-to-one mapping $\omega$ between $A$ and $B$, such that for element $a$ in $A$, $ (A − {a}) \cup {\omega(a)}$ is independent.

I am having trouble coming up with a way of show that this one-to-one mapping exists. My thinking so far is to treat set $A$ and $B$ as two sets of nodes in a bipartite graph and attaching and edge between $a \in A$ and $b \in B - \{A - \{a\}\}$.

And then we can run a matching to get our one-to-one function. However, I am having issues arguing that this "perfect" matching between the two sets exists.

Answer 1

Consider a matroid $\mathcal{M} = (E, \mathcal{I})$, where $E$ is the ground set and $\mathcal I$ contains the independent sets. Let $\mathcal C$ be the family of circuits of $\mathcal M$, and $\mathcal B$ be the family of bases. The following are properties of circuits.

Property 1: If $C_1,C_2\in \mathcal C$ and $C_1\subseteq C_2$, then $C_1 = C_2$.

Property 2: For two distinct circuits $C_1,C_2 \in \mathcal C$ and $x\in C_1\cap C_2$, $\exists C\in \mathcal C$ such that $C\subseteq (C_1\cup C_2) \setminus \{x\}$. Furthermore, for any $y\in C_1\setminus C_2$, there is a circuit $C_y\subseteq (C_1\cup C_2)\setminus\{x\}$ containing $y$.

Using these, you can prove the following:

Lemma 1: For any $B\in \mathcal B$ and $x\in E\setminus B$, $B\cup \{x\}$ contains a unique circuit $C$ that contains $x$. Furthermore, for $b\in B$, $(B\setminus \{b\})\cup \{x\}$ is a basis iff $b\in C$.

Proof: It's obvious that $B\cup \{x\}$ contains a circuit $C$, since $B$ is a basis. We know that $x\in C$, otherwise we would have $C\subseteq B$, which is impossible since $B$ is an independent set. Now, suppose there are two distinct circuits $C,C'$ contained in $B\cup \{x\}$. Clearly, $x\in C$ and $x\in C'$, so by Property 2, there must be a third circuit in $B\cup \{x\}$ that does not contain $x$. This is clearly impossible, so the circuit $C$ is unique.

Now, consider $b\in B\cap C$. $(B\setminus \{b\})\cup \{x\}$ must be independent, otherwise it would imply the existence of another circuit $C'\neq C$ within $B\cup\{x\}$. Suppose that $(B\setminus \{b\})\cup \{x\}$ is not a basis. Then there is $e\in E\setminus (B\cup \{x\})$ such that $(B\setminus \{b\})\cup \{x,e\}$ is independent. The set $B\cup \{e\}$ contains a unique circuit $C'$ that contains $e$. We must have $b\in C'$, otherwise $C'\subseteq (B\setminus \{b\})\cup \{x,e\}$, which is a contradiction. However, $b\in C$ and $b\in C'$ implies the existence of a third circuit contained in $(C\cup C')\setminus \{b\}$ by Property 2. This contradicts the independence of $(B\setminus \{b\})\cup \{x,e\}$, so $(B\setminus \{b\})\cup \{x\}$ must be a basis.

Finally, consider $b\in B$ such that $b\notin C$. Then $(B\setminus\{b\})\cup\{x\}$ contains $C$ and cannot be a basis.

Lemma 2: Consider a collection of distinct circuits $C_1,C_2,...,C_n$ satisfying $C_k\not\subseteq \bigcup_{i\neq k}C_i$ for all $k\in\{1,2,...,n\}$. If $S\subseteq E$ with $|S| < n$, $\exists C\in \mathcal C$ such that $C\subseteq \left(\bigcup_i C_i\right)\setminus S$.

Sketch: This is obviously true if $S$ is empty. If $S$ is non-empty, consider $s\in S$. If $s\not\in \bigcup_i C_i$, we can simply move on to the next element of $S$ immediately. On the other hand, if $s\in \bigcup_i C_i$, then there is some $C_j$ such that $s\in C_j$. Choose elements $c_\ell\in C_\ell\setminus \left(\bigcup_{i\neq\ell} C_i\right)$ for all $\ell\neq j$. For all $\ell\neq j$, we can find a circuit $C_\ell'$ such that $C_\ell'\subseteq (C_j \cup C_\ell)\setminus\{s\}$ and $C_\ell'$ contains $c_\ell$ using Property 2 as needed. Notice that in either case, we now have a collection of at least $n-1$ circuits, all of which are contained within $\left(\bigcup_i C_i\right)\setminus \{s\}$. We may continue to repeat this process with the $r-$th element of $S$ and our newly constructed collection of circuits until we end up with a collection of circuits satisfying the desired property. This final collection is guaranteed to have at least one circuit since $|S|<n$.

Theorem: If $A,B\in\mathcal B$, then there is a bijection $\omega:A\rightarrow B$ such that $(A\setminus\{a\})\cup\{\omega(a)\}$ is a basis for all $a\in A$.

Proof: Consider $b\in B\setminus A$ and let $C_b$ be the unique circuit in $A\cup\{b\}$. Define $C_b' = C_b \cap (A\setminus B)$. $C_b'$ must be non-empty, otherwise $C_b\subseteq B$, which contradicts the independence of $B$. By Lemma 1, for all $a\in C_b'$, $(A\setminus \{a\})\cup \{b\}\in\mathcal B$.

Now, consider the family of sets $\mathcal F = (C_b':b\in B\setminus A)$. Suppose that there is a finite subfamily $\mathcal F_n = (C_{b_1}', C_{b_2}',...,C_{b_n}')$ such that $\left|\bigcup_{A\in \mathcal F_n}A\right|<n$. Then by Lemma 2, there is a circuit $C\subseteq \left(\bigcup_{i=1}^n C_{b_i}\right)\setminus \left(\bigcup_{A\in \mathcal F_n}A\right)$. But notice that $C\subseteq B$, which contradicts the independence of $B$. Therefore, no such subfamily can exist. We may therefore apply Hall's Theorem to conclude that $\mathcal F$ has a transversal $\tau$. Defining $\sigma(b) = \tau\left(C_b'\right)$ for $b\in B\setminus A$ and $\sigma(b) = b$ for $b\in B\cap A$, we obtain a bijection $\sigma: B\rightarrow A$ such that $(A\setminus \{\sigma(b)\})\cup \{b\}\in \mathcal B$. Then letting $\omega = \sigma^{-1}$, we have the claim.