Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

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$, and taking the transitive closure of this. 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.

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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