Is a non-disjoint union of connected matroids always connected? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T01:32:12Z http://mathoverflow.net/feeds/question/78802 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/78802/is-a-non-disjoint-union-of-connected-matroids-always-connected Is a non-disjoint union of connected matroids always connected? MrB 2011-10-21T22:19:00Z 2011-10-22T01:11:45Z <p>This is perhaps an easy question, but...</p> <p>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.</p> http://mathoverflow.net/questions/78802/is-a-non-disjoint-union-of-connected-matroids-always-connected/78809#78809 Answer by David Speyer for Is a non-disjoint union of connected matroids always connected? David Speyer 2011-10-22T00:04:29Z 2011-10-22T00:04:29Z <p>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.</p> <p>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.) </p> <p>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.</p>