1
$\begingroup$

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)

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Commented Jun 24, 2014 at 1:32
  • $\begingroup$ It is not homework. My self study. $\endgroup$
    – Tim
    Commented Jun 24, 2014 at 1:35

1 Answer 1

2
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.