5
$\begingroup$

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

$\endgroup$
7
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Yours is superior - mine had the same idea with an unnecessary complication. $\endgroup$ – Geva Yashfe Oct 21 at 14:28
  • 1
    $\begingroup$ Thanks. I +1ed your answer. Since you deleted your answer, I edited the first part of your answer in. $\endgroup$ – Tony Huynh Oct 21 at 14:34
  • $\begingroup$ The Matroid Partition Theorem should be in most matroid theory texts (for example Oxley's book). It also follows immediately from the Matroid Intersection Theorem. I don't have it in front of me, but I think Schrijver's encyclopedic Combinatorial Optimization has references for who first proved all these things. $\endgroup$ – Tony Huynh Oct 22 at 6:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.