TU Wien:Diskrete Mathematik für Informatik UE (Gittenberger)/Übungen WS13/Beispiel 15

List all matroids (E, S) with E={1}, E={1,2} or E={1,2,3}

Theory

A matroid M=(E,S), where E is a finite set and S is a subset of the power set of E s.t:

• non emptiness: The empty set is in S. (S is therefore not an empty set itself i.e. not empty)
• S is downward closed: if $s\in S$ and $t\subseteq s$ then $t\in S$
• S has the exchange property: if $s,t\in S$ and $|t|=|s|+1$, then there exists an element $x\in t\setminus s$ s.t. $s\cup \{x\}\in S$

Solution

• a. E={1}: S={{}} or S={{}, {1}}
• b. E={1,2}: as in a., but also: S={{}, {2}} or S={{}, {1}, {2}} or S={{}, {1}, {2}, {1,2}}
• c. E={1,2,3}: as in b, but also: S={{}, {3}} or S={{}, {1}, {3}, {1,3}} and so on ... (shouldn't be too hard to figure this out)

Kommentar: Jemand hat im WS15 die Frage auf Mathematics SE gestellt.