Matroid

In combinatorics, a matroid /ˈmeɪtrɔɪd/ is a structure that abstracts and generalizes the notion of linear independence in vector spaces.

In the language of partially ordered sets, a finite simple matroid is equivalent to a geometric lattice.

The term arises because the circuits of graphic matroids are cycles in the corresponding graphs.

The collections of dependent sets, of bases, and of circuits each have simple properties that may be taken as axioms for a matroid.

In the language of partially ordered sets, such a matroid structure is equivalent to the geometric lattice whose elements are the subsets

The closed sets of a matroid are characterized by a covering partition property: The class

of all flats, partially ordered by set inclusion, forms a matroid lattice.

Matroid theory developed mainly out of a deep examination of the properties of independence and dimension in vector spaces.

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(2).

However, it is not possible to provide a similar representation for the Fano matroid using the real numbers in place of GF(2).

For instance, although a graphic matroid (see below) is presented in terms of a graph, it is also representable by vectors over any field.

[18] If T is a subset of E, the contraction of M by T, written M/T, is the matroid on the underlying set E − T whose rank function is

[19] In linear algebra, this corresponds to looking at the quotient space by the linear space generated by the vectors in T, together with the images of the vectors in E - T. A matroid N that is obtained from M by a sequence of restriction and contraction operations is called a minor of M.[17][20] We say M contains N as a minor.

In particular: Two standalone systems for calculations with matroids are Kingan's Oid and Hlineny's Macek.

"Macek" is a specialized software system with tools and routines for reasonably efficient combinatorial computations with representable matroids.

Both open source mathematics software systems SAGE and Macaulay2 contain matroid packages.

The characteristic polynomial of M – sometimes called the chromatic polynomial,[31] although it does not count colorings – is defined to be or equivalently (as long as the empty set is closed in M) as where μ denotes the Möbius function of the geometric lattice of the matroid and the sum is taken over all the flats A of the matroid.

[32] The beta invariant of a matroid, introduced by Crapo (1967), may be expressed in terms of the characteristic polynomial

They were named after Hassler Whitney, the (co)founder of matroid theory, by Gian-Carlo Rota.

The name has been extended to the similar numbers for finite ranked partially ordered sets.

, specifically, Another definition is in terms of internal and external activities and a sum over bases, reflecting the fact that

[36] This, which sums over fewer subsets but has more complicated terms, was Tutte's original definition.

For a long time, one of the difficulties has been that there were many reasonable and useful definitions, none of which appeared to capture all the important aspects of finite matroid theory.

For instance, it seemed to be hard to have bases, circuits, and duality together in one notion of infinite matroids.

Finite-rank matroids include any subsets of finite-dimensional vector spaces and of field extensions of finite transcendence degree.

Finitary infinite matroids are studied in model theory, a branch of mathematical logic with strong ties to algebra.

Many notions of infinite matroids were defined in response to this challenge, but the question remained open.

It was also independently discovered by Takeo Nakasawa, whose work was forgotten for many years Nishimura & Kuroda (2009).

[c] His key observation was that these axioms provide an abstraction of "independence" that is common to both graphs and matrices.

His contributions were plentiful, including and the tools he used to prove many of his results: which are so complicated that later theorists have gone to great trouble to eliminate the need for them in proofs.