World's most popular travel blog for travel bloggers.

Is a set system an independence system, if and only if it is an accessible system, and has the Interval Property without Lower Bounds

, , No Comments
Problem Detail: 

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)

Asked By : Tim

Answered By : Yuval Filmus

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/27926

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback