Matroid

In combinatorics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being in terms of: independent sets; bases or circuits; rank functions; closure operators; and closed sets or flats. In the language of partially ordered sets, a finite simple matroid is equivalent to a geometric lattice.
Matroid theory borrows extensively from the terms used in both 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.

Definition

There are many equivalent ways to define a matroid.
File:Graphic matroid of C4.svg|thumb|upright=1.3|class=skin-invert-image|The graphic matroid of the cycle graph, which is the uniform matroid. More generally, the graphic matroid of is.

Independent sets

In terms of independence, a finite matroid is a pair, where is a finite set and is a family of subsets of with the following properties:

The empty set is independent, i.e.,.
Every subset of an independent set is independent, i.e., for each, if then. This is sometimes called the hereditary property, or the downward-closed property.
If and are two independent sets and has more elements than, then there exists such that is in. This is sometimes called the augmentation property or the independent set exchange property.

The first two properties define a combinatorial structure known as an independence system. Actually, assuming, property is equivalent to the fact that at least one subset of is independent, i.e.,.

Bases and circuits

A subset of the ground set that is not independent is called dependent. A maximal independent set – that is, an independent set that becomes dependent upon adding any element of – is called a basis for the matroid. A circuit in a matroid is a minimal dependent subset of – that is, a dependent set whose proper subsets are all independent. The term arises because the circuits of graphic matroids are cycles in the corresponding graphs.
The dependent sets, the bases, or the circuits of a matroid characterize the matroid completely: a set is independent if and only if it is not dependent, if and only if it is a subset of a basis, and if and only if it does not contain a circuit. The collections of dependent sets, of bases, and of circuits each have simple properties that may be taken as axioms for a matroid. For instance, one may define a matroid to be a pair, where is a finite set as before and is a collection of subsets of, called bases, with the following properties:

is nonempty.
If and are distinct members of and, then there exists an element such that.

This property is called the basis exchange property. It follows from this property that no member of can be a proper subset of any other.

Rank functions

It is a basic result of matroid theory, directly analogous to a similar theorem of bases in linear algebra, that any two bases of a matroid have the same number of elements. This number is called the rank If is a matroid on, and is a subset of, then a matroid on can be defined by considering a subset of to be independent if and only if it is independent in. This allows us to talk about submatroids and about the rank of any subset of. The rank of a subset is given by the rank function of the matroid, which has the following properties:

The value of the rank function is always a non-negative integer.
For any subset, we have.
For any two subsets, we have:. That is, the rank is a submodular function.
For any set and element, we have:. From the first inequality it follows more generally that, if, then. That is, rank is a monotonic function.

These properties can be used as one of the alternative definitions of a finite matroid: If satisfies these properties, then the independent sets of a matroid over can be defined as those subsets of with. In the language of partially ordered sets, such a matroid structure is equivalent to the geometric lattice whose elements are the subsets, partially ordered by inclusion.
The difference is called the nullity of the subset. It is the minimum number of elements that must be removed from to obtain an independent set. The nullity of in is called the nullity of. The difference is sometimes called the corank of the subset.

Closure operators

Let be a matroid on a finite set, with rank function as above. The closure or span of a subset of is the set
This defines a closure operator where denotes the power set, with the following properties:

For all subsets of,.
For all subsets of,.
For all subsets and of with,.
For all elements and from and all subsets of, if then.

The first three of these properties are the defining properties of a closure operator. The fourth is sometimes called the Mac Lane–Steinitz exchange property. These properties may be taken as another definition of matroid: every function that obeys these properties determines a matroid.

Flats

A set whose closure equals itself is said to be closed, or a flat or subspace of the matroid. A set is closed if it is maximal for its rank, meaning that the addition of any other element to the set would increase the rank. The closed sets of a matroid are characterized by a covering partition property:

The whole point set is closed.
If and are flats, then is a flat.
If is a flat, then each element of is in precisely one of the flats that cover .

The class of all flats, partially ordered by set inclusion, forms a matroid lattice. Conversely, every matroid lattice forms a matroid over its set of atoms under the following closure operator: for a set of atoms with join,
The flats of this matroid correspond one-for-one with the elements of the lattice; the flat corresponding to lattice element is the set
Thus, the lattice of flats of this matroid is naturally isomorphic to.

Hyperplanes

In a matroid of rank, a flat of rank is called a hyperplane. These are the maximal proper flats; that is, the only superset of a hyperplane that is also a flat is the set of all the elements of the matroid. An equivalent definition is that a coatom is a subset of E that does not span M, but such that adding any other element to it does make a spanning set.
The family of hyperplanes of a matroid has the following properties, which may be taken as yet another axiomatization of matroids:

The ground set itself is not a hyperplane.
There do not exist distinct sets and in with. That is, the hyperplanes form a Sperner family.
For every and distinct with, there exists with.
Graphoids

defined a graphoid as a triple in which and are classes of nonempty subsets of such that

no element of contains another,
no element of contains another,
no set in and set in intersect in exactly one element, and
whenever is represented as the disjoint union of subsets with , then either an exists such that or a exists such that.

He proved that there is a matroid for which is the class of circuits and is the class of cocircuits. Conversely, if and are the circuit and cocircuit classes of a matroid with ground set, then is a graphoid. Thus, graphoids give a self-dual cryptomorphic axiomatization of matroids.

Examples

Free matroid

Let be a finite set. The set of all subsets of defines the independent sets of a matroid. It is called the free matroid over.

Uniform matroids

Let be a finite set and a natural number. One may define a matroid on by taking every subset of to be a basis. This is known as the uniform matroid of rank. A uniform matroid with rank and with elements is denoted. All uniform matroids of rank at least 2 are simple. The uniform matroid of rank 2 on points is called the point line. A matroid is uniform if and only if it has no circuits of size less than one plus the rank of the matroid. The direct sums of uniform matroids are called partition matroids.
In the uniform matroid, every element is a loop, and in the uniform matroid, every element is a coloop. The direct sum of matroids of these two types is a partition matroid in which every element is a loop or a coloop; it is called a discrete matroid. An equivalent definition of a discrete matroid is a matroid in which every proper, non-empty subset of the ground set is a separator.

Matroids from linear algebra

Matroid theory developed mainly out of a deep examination of the properties of independence and dimension in vector spaces. There are two ways to present the matroids defined in this way:
The validity of the independent set axioms for this matroid follows from the Steinitz exchange lemma.
An important example of a matroid defined in this way is the Fano matroid, a rank three matroid derived from the Fano plane, a finite geometry with seven points and seven lines. It is a linear matroid whose elements may be described as the seven nonzero points in a three dimensional vector space over the finite field GF. However, it is not possible to provide a similar representation for the Fano matroid using the real numbers in place of GF.
A matrix with entries in a field gives rise to a matroid on its set of columns. The dependent sets of columns in the matroid are those that are linearly dependent as vectors.
For instance, the Fano matroid can be represented in this way as a 3 × 7 matrix. Column matroids are just vector matroids under another name, but there are often reasons to favor the matrix representation.
A matroid that is equivalent to a vector matroid, although it may be presented differently, is called representable or linear. If is equivalent to a vector matroid over a field, then we say is representable over in particular, is real representable if it is representable over the real numbers. For instance, although a graphic matroid is presented in terms of a graph, it is also representable by vectors over any field.
A basic problem in matroid theory is to characterize the matroids that may be represented over a given field ; Rota's conjecture describes a possible characterization for every finite field. The main results so far are characterizations of binary matroids due to Tutte, of ternary matroids due to Reid and Bixby, and separately to Seymour, and of quaternary matroids due to. A proof of Rota's conjecture was announced, but not published, in 2014 by Geelen, Gerards, and Whittle.
A regular matroid is a matroid that is representable over all possible fields. The Vámos matroid is the simplest example of a matroid that is not representable over any field.