
> 
> Given a matroid $M$ with ground set $E$ of size $2n$, suppose there exists $A\subseteq E$ of size $n$ such that both $A$ and $E\setminus A$ are independent. What is the minimum number of $B\subseteq E$ such that both $B$ and $E\setminus B$ are independent?
> 
> 
> 


With $n=2$, some casework shows that the answer is $4$: suppose $\{1,2\},\{3,4\}$ are independent. Using the augmentation property with $\{1\}$ and $\{3,4\}$, we get that wlog $\{1,3\}$ is independent. If $\{2,4\}$ is independent, we get four sets $B$, so using $\{2\}$ against $\{3,4\}$, it must be that $\{2,3\}$ is independent. But then using $\{4\}$ against $\{1,2\}$ gives us the claim. It is possible that the independent sets are $\emptyset,\{1\},\{2\},\{3\},\{4\},\{1,2\},\{3,4\},\{1,3\},\{2,4\}$, giving the answer of $4$.



Minimum number of independent pairs in a matroid
As observed by Geva Yashfe, the answer is $2^n$. This can be achieved when each of $A$ and $\overline{A}:=E\setminus A$ are bases, with $A = \{a\_1,\ldots,a\_n\}$, $\overline{A} = \{b\_1,\ldots,b\_n\}$, and $a\_i$ parallel to $b\_i$ for all $i \in [n]$.


For the lowerbound, by truncation, we may assume that $A$ and $\overline{A}$ are both bases. It is well-known that every matroid actually satisfies the following stronger basis exchange axiom: for all distinct bases $B\_1$ and $B\_2$ and every $X \subseteq B\_1 \setminus B\_2$, there exists $Y \subseteq B\_2 \setminus B\_1$ such that *both* $(B\_1 \setminus X) \cup Y$ and $(B\_2 \cup X) \setminus Y$ are bases. Applying this axiom to the bases $A$ and $\overline{A}$ and every $X \subseteq A$, we get $2^n$ distinct bases $B$ such that $\overline{B}$ is also a basis.


As requested by TZM, here is a proof that the stronger exchange axiom always holds. The key idea is to use the Matroid Partition Theorem on two appropriately defined matroids. Given two matroids $M\_1$ and $M\_2$ on the same ground set $E$, we say that a set $X \subseteq E$ is *$(M\_1, M\_2)$-partitionable* if $X$ is the disjoint union of $I\_1$ and $I\_2$ where $I\_i$ is independent in $M\_i$. We denote the size of a largest $(M\_1, M\_2)$-partitionable set as $\pi(M\_1, M\_2)$.


**Matroid Partition Theorem.** Let $M\_1$ and $M\_2$ be matroids on the same ground set $E$ with rank functions $r\_1$ and $r\_2$. Then
$$\pi(M\_1, M\_2)=\min\_{A \subseteq E} (|E-A|+r\_1(A)+r\_2(A)).$$


We can now prove the stronger exchange axiom.


**Lemma.** Let $B\_1$ and $B\_2$ be distinct bases of $M$ and $X \subseteq B\_1 \setminus B\_2$. Then there exists $Y \subseteq B\_2 \setminus B\_1$ such that $(B\_1 \setminus X) \cup Y$ and $(B\_2 \cup X) \setminus Y$ are both bases.


**Proof.** Let $M\_1$ be the restriction of $M / (B\_1 \setminus X)$ to $B\_2 \setminus B\_1$ and $M\_2$ be the restriction of $M / (X \cup (B\_1 \cap B\_2))$ to $B\_2 \setminus B\_1$. Let $r\_1$ and $r\_2$ be the rank functions of $M\_1$ and $M\_2$. A simple calculation (using submodularity) shows that $r\_1(A)+r\_2(A) \geq |A|$ for all $A \subseteq B\_2 \setminus B\_1$. Therefore, by the Matroid Partition Theorem, $\pi(M\_1, M\_2)=|B\_2 \setminus B\_1|$. That is, there exists a partition $Y \cup Z$ of $B\_2 \setminus B\_1$ such that $Y$ is independent in $M\_1$ and $Z$ is independent in $M\_2$. In other words, $(B\_1 \setminus X) \cup Y$ is independent in $M$ and $X \cup (B\_1 \cap B\_2) \cup Z$ is independent in $M$. Note that this implies $|Y|=|X|$; otherwise one of these two sets has size more than $|B\_1|$. Thus, $(B\_1 \setminus X) \cup Y$ and $(B\_2 \cup X) \setminus Y$ are both bases of $M$, as required.


