Matroids-Discrete Optimization

Question

I happen to stumble across this question where they ask to give an example of an independent system that has two maximal independent sets $X$ and $Y$ such that $|X|\neq |Y|$. How exactly would you formulate such an example?

Answer 1

An independence system is a collection $C$ of subsets of a finite set $E$ such that if $c \in C$ and $b \subset c$ then $b \in C$. Independence systems are also known as finite (abstract) simplicial complexes. A simplicial complex whose inclusion-maximal subsets all have the same cardinality is called pure. The question asks for a simplicial complex that is not pure. Here is a minimal example.

Let $E = \{1,2,3\}$ and let $C$ be the set of all subsets of $A = \{1\}$ together with the set of all subsets of $B = \{2,3\}$. So $C = \{\emptyset, \{1\},\{2\},\{3\},\{23\}\}$. Then $C$ is an independence system with (inclusion-)maximal subsets $A$ and $B$.

For contrast, a matroid is a simplicial complex whose maximal subsets satisfy the matroid basis exchange property. Here's a pure simplicial complex on $E = \{1,2,3,4\}$ that is not a matroid: $C = \{\emptyset, \{1\},\{2\},\{3\},\{4\},\{1,2\},\{3,4\}\}$.

Answer 2

An example can be constructed by matchings in a graph, where the independent sets are the edges of a matching. Here is a particular case:

On the left is the graph and next to it, marked in red, the edges of two maximal independent sets with different cardinality. If we call the edges from left to right 1,2,3. Then the set of all matchings is $\lbrace \emptyset, 1, 2, 3, 13\rbrace$, where $\lbrace 2\rbrace$ and $\lbrace 1,3\rbrace$ denote the maximal independent sets.