Definitions for **"Matroid"**

This is an abstraction of independence that includes vectors in linear algebra and circuits in graphs. First, we need some preliminary definitions. Let N={1, ..., n} be a finite set, and let M={S1, ..., Sm} be a collection of subsets of N. (N,M) is an independence system if Si in M implies every subset of Si is in M. Elements of M are called independent sets, and the remaining subsets of N are called dependent sets. An independent set, say Si, is maximal if Si\/{k} is not in M for any k in N\Si. The max-cardinality independent set of any subset of N, say T, is given by: m(T) = max{|Si|: Si in M, Si a subset of T}. matroid is an independence system (N, M) in which for any subset of N, say T, every independent set in T that is maximal in T has cardinality 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.

a combinatorial object which captures the essence of dependence, generalizing these three notions simultaneously

a combinatorial structure which abstracts the idea of linear independence in a vector space