List of all matroids

Question

List all matroids $(E, S)$ with $E = \{1\}, E = \{1, 2\}, E = \{1, 2, 3\}$.

I know that $(E, S)$ is called an independence system, and that according to the definition $S \subseteq 2^E$ and $S$ is closed under inclusion. The point is that, I don't exactly understand the problem above. What will be the matroids in question?

EDIT:

Matroids for $E = \{1, 2\}$

$\{ \emptyset \}, \{ \emptyset, \{1\} \}, \{ \emptyset, \{2\} \}, \{ \emptyset, \{1\}, \{2\}\}, \{ \emptyset, \{1\}, \{2\}, \{1, 2\}\}$

Matroids for $E = \{1, 2, 3\}$

$\{ \emptyset \}, \{ \emptyset, \{1\} \}, \{ \emptyset, \{2\} \}, \{ \emptyset, \{3\} \}, \{ \emptyset, \{1\}, \{2\}\}, \{ \emptyset, \{1\}, \{3\}\}, \{ \emptyset, \{2\}, \{3\}\}, \{ \emptyset, \{1\}, \{2\}, \{1, 2\}\}, \{ \emptyset, \{1\}, \{3\}, \{1, 3\}\}, \{ \emptyset, \{2\}, \{3\}, \{2, 3\}\}, \{ \emptyset, \{1\}, \{2\}, \{3\}\}, \{ \emptyset, \{1\}, \{2\}, \{3\}, \{1, 2, 3\}\}$

Answer 1

The question asks for which sets of subsets $S$ satisfy the requirements of an independence system.

For example, for $E=\{1\}$, we have $2^E=\{\emptyset, \{1\}\}$, so $|2^E|=2$. Hence potentially there are $2^2=4$ candidates:

$S_1=\{\}=\emptyset$
$S_2=\{\emptyset\}$
$S_3=\{\{1\}\}$
$S_4=\{\emptyset,\{1\}\}$

However, we eliminate $S_3$ because it is not closed under inclusion. We also eliminate $S_1$ because it does not contain the empty set (a requirement of being an independence system). Hence it is exactly $S_2$ and $S_4$ that are independence systems for that particular $E$.

Answer 2

I could be totally wrong, this is confusing and new for me as well.

See https://people.cs.umass.edu/~barring/cs611/lecture/4.pdf page 8 and 9.

Taking that and the previous poster into account, I believe (hope?) this should be right

E = $\{1\}$

S = $\{\emptyset, \{1\}\}$

E = $\{1, 2\}$

S = $\{\emptyset, \{1\}, \{2\}, \{1,2\}\}$

E = $\{1, 2, 3\}$

S = $\{\emptyset, \{1\}, \{2\},\{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\}\}$

I think these all satisfy the 3 properties of matroids...

1) empty set is independent

2) every subset of an independent set is independent; $\{2,3\} \subset \{1,2,3\}\ $, $\{2,3\} \subset S$ and $\{1,2,3\} \subset S$

3) $A = \{1,2,3\}$

$\,\,\,\,\,$$B = \{3\}$

$\,\,\,\,\,$$B\,\cup \{1\} = \{1,3\} \in S$

$\,\,\,\,\,$$B\,\cup \{2\} = \{2,3\} \in S$

Answer 3

Using the Macaulay2 software package Matroids one can quickly and easily obtain all (isomorphism classes of) matroids on $n$ elements for $n\le 8$. To do this use the allMatroids method:

i1 : loadPackage "Matroids";

i2 : VerticalList apply (allMatroids 1, M -> bases M)
o2 = {{set {}} }
     {{set {0}}}

i3 : VerticalList apply (allMatroids 2, M -> bases M)
o3 = {{set {}}          }
     {{set {0}, set {1}}}
     {{set {1}}         }
     {{set {0, 1}}      }

i4 : VerticalList apply (allMatroids 3, M -> bases M)
o4 = {{set {}}                            }
     {{set {0}, set {1}, set {2}}         }
     {{set {1}, set {2}}                  }
     {{set {2}}                           }
     {{set {0, 1}}                        }
     {{set {0, 2}, set {0, 1}}            }
     {{set {1, 2}, set {0, 2}, set {0, 1}}}
     {{set {0, 1, 2}}                     }

Notice that we only specified the bases of each (representative of the isomorphism class of a) matroid. But this is enough since the independence complex of a matroid is a simplicial complex and every simplicial complex is determined by its maximal simplices.