 # Matroid

This is an abstraction of independence that includes vectors in linear algebra and circuits in graphs. First, we need some preliminary definitions. Let $LaTeX: N = \{1, \ldots, n\}$ be a finite set, and let $LaTeX: M = \{S_1, \ldots, S_m\}$ be a collection of subsets of $LaTeX: N$. $LaTeX: (N,M)$ is an independence system if $LaTeX: S_i$ in $LaTeX: M$ implies every subset of $LaTeX: S_i$ is in $LaTeX: M$. Elements of $LaTeX: M$ are called independent sets, and the remaining subsets of $LaTeX: N$ are called dependent sets. An independent set, say $LaTeX: S_i$, is maximal if $LaTeX: S_i \cup \{k\}$ is not in $LaTeX: M$ for any $LaTeX: k \in N\backslash S_i$. The max-cardinality independent set of any subset of $LaTeX: N$, say $LaTeX: T,$ is given by: $LaTeX: m(T) = \max \{ |S_i|: S_i \in M, \, S_i \subseteq T\}.$
A matroid is an independence system $LaTeX: (N, M)$ in which for any subset of $LaTeX: N$, say $LaTeX: T$, every independent set in $LaTeX: T$ that is maximal in $LaTeX: T$ has cardinality $LaTeX: m(T)$. The definition essentially means that maximal and maximum are the same. In other words, a system is a matroid if, and only if, a greedy algorithm yields a globally optimal solution to the associated max weight problem. An example is the spanning tree.