Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

From Wikipedia

In terms of independence, a finite matroid $M$ is a pair $(E,\mathcal{I})$, where $E$ is a finite set (called the ground set) and $\mathcal{I}$ is a family of subsets of $E$ (called the independent sets) with the following properties:

  • The empty set is independent, i.e., $\emptyset\in\mathcal{I}$. Alternatively, at least one subset of $E$ is independent, i.e., $\mathcal{I}\neq\emptyset$.

  • Every subset of an independent set is independent, i.e., for each $A'\subset A\subset E$, if $A\in\mathcal{I}$ then $A'\in\mathcal{I}$. This is sometimes called the hereditary property.

  • If $A$ and $B$ are two independent sets of $\mathcal{I}$ and $A$ has more elements than $B$, then there exists an element in $A$ that when added to $B$ gives a larger independent set. This is sometimes called the augmentation property or the independent set exchange property.

A subset of the ground set E that is not independent is called dependent. A maximal independent set—that is, an independent set which becomes dependent on adding any element of E—is called a basis for the matroid.

  1. Can a matroid be defined equivalently by replacing the augmentation property with the following one :

    • $\forall A \in \mathcal{I}$, $A$ has a maximal superset in $\mathcal{I}$, and the cardinality of the maximal superset of $A$ is the same for all members of $\mathcal{I}$.
  2. I was wondering if there has already existed a concept which is opposite to a matroid? For example, for a pair $(E, \mathcal{J})$,

    • $E \in \mathcal{J}$,

    • for each $A'\subset A\subset E$, if $A' \in\mathcal{J}$ then $A \in\mathcal{J}$.

    • If $A$ and $B$ are both in $\mathcal{J}$ and $A$ has less elements than $B$, then there exists an element in $B$ when removed from $B$ gives a smaller member in $\mathcal{J}$. ($A$ may or may not be helpful in finding such an element in $B$.)

    or can the third point be replaced by

    • $\forall A \in \mathcal{J}$, $A$ has a minimal subset in $\mathcal{J}$, and the cardinality of the minimal subset of $A$ is the same for all members of $\mathcal{J}$.

    Based on the definition, can we further define a concept just opposite to a basis of a matroid, something like "a minimal set in $\mathcal{J}$ is called a basis for $(E, \mathcal{J})$".

    An example of such $(E, \mathcal{J})$ will be the collection of all bases of a topology.

Thanks and regards!

share|cite|improve this question
Not quite what you are asking for, but antimatroids is somewhat close: – mrf Jan 1 '13 at 1:13
@mrf: I just saw antimatroid today. Agree, it is not the one I described. – Tim Jan 1 '13 at 1:14
up vote 2 down vote accepted

For the first question, the augmentation property cannot be replaced by this new statement. This statement essentially says that all maximal independent sets (bases) are of same size. But this is not sufficient to prove the augmentation property. Consider this example, with $E = \{ 1,2,3,4\}$ and $I = \{ \phi, \{1\}, \{2\}, \{1,2\}, \{3\}, \{4\}, \{3,4\}\}$. This satisfies your new statement, but not the augmentation property. When trying to describe in terms of bases, a property similar to augmentation is used. In terms of independent sets, another typically used definition is to replace augmentation by the following property.

  • Given any $A \subseteq E$, all maximal independent sets contained in $A$ have the same size.
share|cite|improve this answer
+1 Thanks! Nice to know the property. Does "all maximal independent sets contained in $A$" mean maximal within $A$ not maximal within $E$? Essentially does the property make use of the fact that the restriction of a matroid $(E, I)$ on any subset $A \subseteq E$ is also a matroid? – Tim Jan 1 '13 at 4:24
References on the alternative definition using the property are also appreciated! – Tim Jan 1 '13 at 4:31
Yes, it is maximal within $A$ (in the collection of independent sets contained in $A$, the maximal sets have the same size). As we are looking at this property as definition of matroid, the restriction result follows from this. Chapter 4 in this book details multiple definitions for matroids and their equivalence. – polkjh Jan 1 '13 at 5:27

Your Answer


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.