Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

From Wikipedia, a finite matroid $M$ is defined to be $(E,F)$, where $E$ is a finite set and $F$ is a family of subsets of $E$, so that it satisfies

The two definitions should be equivalent. Do we need the augmentation property, for the following to be true:

a set system $(E,F)$ is nonempty and has the hereditary property, if and only if it is an accessible system, and has the Interval Property without Lower Bounds?

Without assuming the augmentation property, it is simple to see that the "only if" part is true, but I wonder if the "if"part is also true? Thanks and regards!


Note:

A set system $(E,F)$ that is nonempty and has the hereditary property is also called an independence system.


The aforementioned properties are defined as follows:

  • The empty set is in $F$. (nonempty property)
  • if $X \in F$, then every subset of $X$ is also in $F$. (The hereditary property)
  • for all $X,Y ∈ F$ with $|X| > |Y|$, there is some $x ∈ X-Y$ such that $Y∪{x} ∈ F$. (The augmentation property)

  • Every nonempty $X \in F$ contains an element $x$ such that $X-\{x\} \in F$. (I.e. $(E,F)$ is an accessible system)

  • If $B, C ∈ F$ with $B ⊆ C$, then, for all $x ∈ E-C$, $C∪\{x\} ∈ F$ implies $B∪\{x\} ∈ F$. (the Interval Property without Lower Bounds)

share|improve this question
    
I hope this is not a homework question, but if it is, I suggest you try to solve the next homework problem on your own. –  Yuval Filmus Jun 24 at 1:32
    
It is not homework. My self study. –  Tim Jun 24 at 1:35

1 Answer 1

up vote 2 down vote accepted

Suppose that a set system $F$ is accessible and satisfies the interval property. We show that it is hereditary. Let $C = \{x_1,\ldots,x_n\}$ be any set. Without loss of generality, by accessibility we can assume that for all $t \in \{0,\ldots,n\}$, $\{x_1,\ldots,x_t\} \in F$. We show by induction that all subsets $B$ of $C$ are in $F$. If $|B| = 0$ then $B = \emptyset \in F$ (the case $t = 0$ above). Now suppose $B = \{x_{i_1}, \ldots, x_{i_k}\}$, where $i_1 < i_2 < \cdots < i_k$. By assumption, $A = \{x_{i_1},\ldots,x_{i_{k-1}}\} \in F$. Now $A \subseteq \{x_1,\ldots,x_{i_k-1}\}$ and both $\{x_1,\ldots,x_{i_k-1}\},\{x_1,\ldots,x_{i_k}\} \in F$, and so by the interval property, $B = A \cup \{x_{i_k}\} \in F$.

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.