1
$\begingroup$

Let $E_1$ and $E_2$ be two disjoint sets.

Moreover, assume that $(E_1, S_1)$ and $(E_2, S_2)$ are matroids.

Define $S:=\{X\cup Y | X\subseteq S_1 \text{ and} Y \subseteq S_2\}$.

S1,S2 and S are independent sets of Matroid.

Prove that $(E_1 \cup E_2, S)$ is a matroid.

$\endgroup$
5
  • $\begingroup$ Welcome to stackexchange. If you edit your question to show what you have tried and where you are stuck you are more likely to get answers rather then downvotes or votes to close. $\endgroup$ Nov 4, 2017 at 23:53
  • $\begingroup$ @EthanBokler yes you are right. I actually changed a typo $\endgroup$ Nov 4, 2017 at 23:55
  • 1
    $\begingroup$ I'm not sure what you're thanking me for, since you did not in fact edit your question to show what you tried. In the meanwhile, you did get an answer. If it's a good one for you be sure to accept it (the check mark). $\endgroup$ Nov 5, 2017 at 0:09
  • $\begingroup$ What are the $S_i$ supposed to be? This matters because there are many different ways to define a matroid (from their bases, independent sets, flats, circuits, cocircuits, hyperplanes, etc. etc.) and the validity of the result you want to prove depends on which definition(s) we are working with. It seems from the accepted answer that you assume the $S_i$ are the sets of independent sets. For clarity, you should add that assumption to your question. $\endgroup$
    – Aaron Dall
    Nov 5, 2017 at 12:46
  • $\begingroup$ @AaronDall yes, they are sets of independent sets. I already edited the question now. $\endgroup$ Nov 5, 2017 at 13:30

1 Answer 1

3
$\begingroup$

You have three properties to check, using the definition here.

  1. Clearly $\emptyset \in S$.
  2. Suppose $A' \subseteq A \in S$. Then $A = X \cup Y$ for $X \in S_1$, $Y \in S_2$, so $$A' = A' \cap A = (A' \cap X) \cup (A' \cap Y).$$ But $A' \cap X \subseteq X$, so $A' \cap X \in S_1$; similarly $A' \cap Y \in S_2$. Thus $A' \in S$.
  3. Let $A, B \in S$, $|A| > |B|$. Write $A = X \cup Y$, $B = X' \cup Y'$. Then we must have $|X| > |X'|$ or $|Y| > |Y'|$; suppose we have $|X| > |X'|$. Then there is $x \in X$ such that $X' \cup \{ x \} \in S_1$ by the augmentation property for the first matroid. In particular, $B \cup \{ x \} = (X' \cup \{ x \}) \cup Y' \in S$. So we have the augmentation property.
$\endgroup$
7
  • $\begingroup$ thanks for your answer. For the 1st and 3rd property all clear. But for the 2nd property, I have a feeling that A′ = A. Because A ∩ X = X, and A ∩ Y = Y, which means that A' = A. Or maybe I got it wrong? $\endgroup$ Nov 5, 2017 at 0:30
  • $\begingroup$ Why should $A \cap X = X$ or $A \cap Y = Y$? $\endgroup$
    – Mr. Chip
    Nov 5, 2017 at 0:33
  • $\begingroup$ Because of the absorption laws. A = X U Y, therefore (X U Y) ∩ X = X $\endgroup$ Nov 5, 2017 at 0:43
  • $\begingroup$ Oops, sorry. I miswrote. I should have said $A' = (A' \cap X) \cup (A' \cap Y)$. Now is it clear? $\endgroup$
    – Mr. Chip
    Nov 5, 2017 at 1:07
  • 1
    $\begingroup$ Yeah, now it looks much better. Thank you man! $\endgroup$ Nov 5, 2017 at 1:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .