Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given a Matroid (E,I), I is a set of independent subsets of E, right?

And independent subsets means that no two of these subsets must have an element in common, right?

Now according to the hereditary property of Matroids, if A is a subset of B which is a subset of E and if B belongs to I, then A also belongs to I.

If A is a subset of B, then all the elements in A are in B, then how are these two independent? All the sets that are supposed to belong to I (i.e. A and B in this case) must be independent (i.e. must not have any common element) right?

share|improve this question

2 Answers 2

And independent subsets means that no two of these subsets must have an element in common, right?

No, it's not. A subset $A$ of $E$ is independent if it belongs to the family of subsets $\cal I$. It doesn't make sense to say that two sets $A_1 \subset E$ and $A_2 \subset E$ are independent.

share|improve this answer

Look again at the definition. A matroid $\langle E,\mathscr{I}\rangle$ defined in terms of independent sets is a finite set $E$ with a family $\mathscr{I}$ of subsets of $E$ such that

  1. $\mathscr{I}\ne\varnothing$;
  2. if $J\subseteq I\in\mathscr{I}$, then $J\in\mathscr{I}$; and
  3. if $I,J\in\mathscr{I}$, and $|I|>|J|$, then there is some $i\in I\setminus J$ such that $J\cup\{i\}\in\mathscr{I}$.

The members of $\mathscr{I}$ are called the independent subsets of $E$.

Condition (2) says that independence is hereditary: every subset of an independent set is also independent. This in conjunction with (1) implies that $\varnothing\in\mathscr{I}$.

Nothing here says that independent sets must be disjoint. In fact, condition (2) guarantees that if the matroid has an independent set with more than one element, then it does have two independent sets with an element in common. Suppose that $I\in\mathscr{I}$, and $a,b\in I$ with $a\ne b$; then $\{a\}$ and $\{a,b\}$ are both subsets of $I$, so by (2) both are independent sets, and $a\in\{a\}\cap\{a,b\}$.

You can get some intuition for this by thinking of the independent sets as being analogous to linearly independent sets in a finite-dimensional vector space. Suppose that $V$ is such a space, and let $\mathscr{I}$ be the set of all linearly independent subsets of $V$. Certainly $\mathscr{I}\ne\varnothing$, and if $I$ is a linearly independent set in $V$, then so is every subset of $I$. Finally, if $I$ and $J$ are linearly independent subsets of $V$, and $|I|>|J|$, then $\dim\operatorname{span}I=|I|>|J|=\dim\operatorname{span}J$, so there is at least one vector $v\in I$ that is not in the span of $J$, and $J\cup\{v\}$ is therefore linearly independent. Thus, the family of linearly independent subsets of $V$ satisfies (1)-(3) above. The only thing that keeps $\langle V,\mathscr{I}\rangle$ from being a matroid is the fact that $V$ may not be finite: $V$ is finite if and only if it’s over a finite field.

If you continue reading the cited Wikipedia article, you’ll see that there are further analogies with vector spaces. For example, maximal independent sets are analogous to bases for a vector space, and their cardinality, called the rank of the matroid, is analogous to the dimension of a vector space.

share|improve this answer

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.