1
$\begingroup$

This is perhaps an easy question, but...

Let $M$ be a matroid on a ground set $E$, and let $A$ and $B$ be non-disjoint subsets of $E$ such that $M|A$ and $M|B$ are both connected. Is $M|(A\cup B)$ then necessarily connected? Clearly this is true for graphic matroids, but I can't find any results in the literature regarding the general case.

$\endgroup$

1 Answer 1

3
$\begingroup$

Yes. Let $E$ be the ground set of a matroid. Define an equivalence relation $\sim$ on $E$ by imposing that $i \sim j$ if $i$ and $j$ are in the same circuit of $E$. Then the equivalence classes of $\sim$ are the connected components of the matroid.

Any circuit of $M|_A$ is also a circuit of $M$, so if two elements of $A$ are in the same connected component of $M|_A$ then they are in the same connected component of $M$. (The converse is not true.)

Let $x$ be in $A \cap B$. For any $a \in A$, since $A$ is connected, we have that $a$ is in the same connected component of $M|_A$ as $x$ is. By the observation of the previous paragraph, this means that $a$ and $x$ are in the same connected component of $M$. Similarly, every $b \in B$ is in the same connected component of $M$ as $x$ is. So all of $M$ is one connected component.

$\endgroup$
3
  • $\begingroup$ Thanks for the swift response. Surprising that such a fundamental result doesn't seem to appear in any textbooks. $\endgroup$
    – MrB
    Oct 22, 2011 at 1:06
  • $\begingroup$ How does one show transitivity of $\sim$? $\endgroup$
    – MrB
    Oct 22, 2011 at 3:31
  • $\begingroup$ $\sim$ is the transitive closure of "is in the same circuit", so it is transitive by definition. Think about the graphical case. $\endgroup$ Oct 22, 2011 at 12:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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