# Minimum number of independent pairs in a matroid

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

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.

• Yours is superior - mine had the same idea with an unnecessary complication. Oct 21, 2020 at 14:28