*** Welcome to piglix ***

Matroids


In combinatorics, a branch of mathematics, a matroid /ˈmtrɔɪd/ is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid, the most significant being in terms of independent sets, bases, circuits, closed sets or flats, closure operators, and rank functions.

Matroid theory borrows extensively from the terminology of linear algebra and graph theory, largely because it is the abstraction of various notions of central importance in these fields. Matroids have found applications in geometry, topology, combinatorial optimization, network theory and coding theory.

There are many equivalent (cryptomorphic) ways to define a (finite) matroid.

In terms of independence, a finite matroid is a pair , where is a finite set (called the ground set) and is a family of subsets of (called the independent sets) with the following properties:


...
Wikipedia

...