Minimum number of independent pairs in a matroid

Question

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$.

Answer 1

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.