Incombinatorics, amatroid/ˈmeɪtrɔɪd/ is a structure that abstracts and generalizes the notion oflinear independence invector spaces. There are many equivalent ways to define a matroidaxiomatically, the most significant being in terms of: independent sets; bases or circuits; rank functions; closure operators; and closed sets orflats. In the language ofpartially ordered sets, a finite simple matroid is equivalent to ageometric lattice.

Matroid theory borrows extensively from the terms used in bothlinear algebra andgraph theory, largely because it is the abstraction of various notions of central importance in these fields. Matroids have found applications ingeometry,topology,combinatorial optimization,network theory, andcoding theory.^[1][2]

There are manyequivalent ways to define a (finite) matroid.^[a]

In terms of independence, a finite matroid${\displaystyle M}$ is a pair${\displaystyle (E,\mathcal{I})}$, where${\displaystyle E}$ is afinite set (called theground set) and${\displaystyle \mathcal{I}}$ is afamily ofsubsets of${\displaystyle E}$ (called theindependent sets) with the following properties:^[3]

• (I1) Theempty set is independent, i.e.,${\displaystyle \mathrm{\varnothing }\in \mathcal{I}}$.

• (I2) Every subset of an independent set is independent, i.e., for each${\displaystyle A^{\prime }\subseteq A\subseteq E}$, if${\displaystyle A\in \mathcal{I}}$ then${\displaystyle A^{\prime }\in \mathcal{I}}$. This is sometimes called thehereditary property, or thedownward-closed property.

• (I3) If${\displaystyle A}$ and${\displaystyle B}$ are two independent sets (i.e., each set is independent) and${\displaystyle A}$ has more elements than${\displaystyle B}$, then there exists${\displaystyle x\in A\setminus B}$ such that${\displaystyle B\cup \{x\}}$ is in${\displaystyle \mathcal{I}}$. This is sometimes called theaugmentation property or theindependent set exchange property.

The first two properties define a combinatorial structure known as anindependence system (orabstract simplicial complex). Actually, assuming (I2), property (I1) is equivalent to the fact that at least one subset of${\displaystyle E}$ is independent, i.e.,${\displaystyle \mathcal{I}\ne \mathrm{\varnothing }}$.

A subset of the ground set${\displaystyle E}$ that is not independent is calleddependent. A maximal independent set – that is, an independent set that becomes dependent upon adding any element of${\displaystyle E}$ – is called abasis for the matroid. Acircuit in a matroid${\displaystyle M}$ is a minimal dependent subset of${\displaystyle E}$ – that is, a dependent set whose proper subsets are all independent. The term arises because the circuits ofgraphic matroids are cycles in the corresponding graphs.^[3]

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${\displaystyle M}$ to be a pair${\displaystyle (E,\mathcal{B})}$, where${\displaystyle E}$ is a finite set as before and${\displaystyle \mathcal{B}}$ is a collection of subsets of${\displaystyle E}$, calledbases, with the following properties:^[3]

• (B1)${\displaystyle \mathcal{B}}$ is nonempty.

• (B2) If${\displaystyle A}$ and${\displaystyle B}$ are distinct members of${\displaystyle \mathcal{B}}$ and${\displaystyle a\in A\setminus B}$, then there exists an element${\displaystyle b\in B\setminus A}$ such that${\displaystyle (A\setminus \{a\})\cup \{b\}\in \mathcal{B}}$.

This property (B2) is called thebasis exchange property. It follows from this property that no member of${\displaystyle \mathcal{B}}$ can be a proper subset of any other.

It is a basic result of matroid theory, directly analogous to a similar theorem ofbases in linear algebra, that any two bases of a matroid${\displaystyle M}$ have the same number of elements. This number is called therankof${\displaystyle M}$. If${\displaystyle M}$ is a matroid on${\displaystyle E}$, and${\displaystyle A}$ is a subset of${\displaystyle E}$, then a matroid on${\displaystyle A}$ can be defined by considering a subset of${\displaystyle A}$ to be independent if and only if it is independent in${\displaystyle M}$. This allows us to talk aboutsubmatroids and about the rank of any subset of${\displaystyle E}$. The rank of a subset${\displaystyle A}$ is given by therank function${\displaystyle r(A)}$ of the matroid, which has the following properties:^[3]

• (R1) The value of the rank function is always a non-negativeinteger.

• (R2) For any subset${\displaystyle A\subset E}$, we have${\displaystyle r(A)\le |A|}$.

• (R3) For any two subsets${\displaystyle A,B\subset E}$, we have:${\displaystyle r(A\cup B)+r(A\cap B)\le r(A)+r(B)}$. That is, the rank is asubmodular function.

• (R4) For any set${\displaystyle A}$ and element${\displaystyle x}$, we have:${\displaystyle r(A)\le r(A\cup \{x\})\le r(A)+1}$. From the first inequality it follows more generally that, if${\displaystyle A\subseteq B\subseteq E}$, then${\displaystyle r(A)\le r(B)\le r(E)}$. That is, rank is amonotonic function.

These properties can be used as one of the alternative definitions of a finite matroid: If${\displaystyle (E,r)}$ satisfies these properties, then the independent sets of a matroid over${\displaystyle E}$ can be defined as those subsets${\displaystyle A}$ of${\displaystyle E}$ with${\displaystyle r(A)=|A|}$. In the language ofpartially ordered sets, such a matroid structure is equivalent to thegeometric lattice whose elements are the subsets${\displaystyle A\subset M}$, partially ordered by inclusion.

The difference${\displaystyle |A|-r(A)}$ is called thenullity of the subset${\displaystyle A}$. It is the minimum number of elements that must be removed from${\displaystyle A}$ to obtain an independent set. The nullity of${\displaystyle E}$ in${\displaystyle M}$ is called the nullity of${\displaystyle M}$. The difference${\displaystyle r(E)-r(A)}$ is sometimes called thecorank of the subset${\displaystyle A}$.

Let${\displaystyle M}$ be a matroid on a finite set${\displaystyle E}$, with rank function${\displaystyle r}$ as above. Theclosure orspan${\displaystyle \mathrm{cl}(A)}$ of a subset${\displaystyle A}$ of${\displaystyle E}$ is the set

${\displaystyle \mathrm{cl}(A)=\{x\in E\mid r(A)=r(A\cup \{x\})\}}$.

This defines aclosure operator${\displaystyle \mathrm{cl}:\mathcal{P}(E)\mapsto \mathcal{P}(E)}$ where${\displaystyle \mathcal{P}}$ denotes thepower set, with the following properties:

• (C1) For all subsets${\displaystyle X}$ of${\displaystyle E}$,${\displaystyle X\subseteq \mathrm{cl}(X)}$.

• (C2) For all subsets${\displaystyle X}$ of${\displaystyle E}$,${\displaystyle \mathrm{cl}(X)=\mathrm{cl}\left(\mathrm{cl}\left(X\right)\right)}$.

• (C3) For all subsets${\displaystyle X}$ and${\displaystyle Y}$ of${\displaystyle E}$ with${\displaystyle X\subseteq Y}$,${\displaystyle \mathrm{cl}(X)\subseteq \mathrm{cl}(Y)}$.

• (C4) For all elements${\displaystyle a}$ and${\displaystyle b}$ from${\displaystyle E}$ and all subsets${\displaystyle Y}$ of${\displaystyle E}$, if${\displaystyle a\in \mathrm{cl}(Y\cup \{b\})\setminus \mathrm{cl}(Y)}$ then${\displaystyle b\in \mathrm{cl}(Y\cup \{a\})\setminus \mathrm{cl}(Y)}$.

The first three of these properties are the defining properties of a closure operator. The fourth is sometimes called theMac Lane–Steinitz exchange property. These properties may be taken as another definition of matroid: every function${\displaystyle \mathrm{cl}:\mathcal{P}(E)\to \mathcal{P}(E)}$ that obeys these properties determines a matroid.^[3]

A set whose closure equals itself is said to beclosed, or aflat orsubspace of the matroid.^[4] A set is closed if it ismaximal 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:

• (F1) The whole point set${\displaystyle E}$ is closed.

• (F2) If${\displaystyle S}$ and${\displaystyle T}$ are flats, then${\displaystyle S\cap T}$ is a flat.

• (F3) If${\displaystyle S}$ is a flat, then each element of${\displaystyle E\setminus S}$ is in precisely one of the flats${\displaystyle T}$ thatcover${\displaystyle S}$ (meaning that${\displaystyle T}$ properly contains${\displaystyle S}$, but there is no flat${\displaystyle U}$ between${\displaystyle S}$ and${\displaystyle T}$).

The class${\displaystyle \mathcal{L}(M)}$ of all flats,partially ordered by set inclusion, forms amatroid lattice. Conversely, every matroid lattice${\displaystyle L}$ forms a matroid over its set${\displaystyle E}$ ofatoms under the following closure operator: for a set${\displaystyle S}$ of atoms with join${\displaystyle \bigvee S}$,

${\displaystyle \mathrm{cl}(S)=\{x\in E\mid x\le \bigvee S\}}$.

The flats of this matroid correspond one-for-one with the elements of the lattice; the flat corresponding to lattice element${\displaystyle y}$ is the set

${\displaystyle \{x\in E\mid x\le y\}}$.

Thus, the lattice of flats of this matroid is naturally isomorphic to${\displaystyle L}$.

In a matroid of rank${\displaystyle r}$, a flat of rank${\displaystyle r-1}$ is called ahyperplane. (Hyperplanes are also calledco-atoms orcopoints.) These are the maximal proper flats; that is, the only superset of a hyperplane that is also a flat is the set${\displaystyle E}$ of all the elements of the matroid. An equivalent definition is that a coatom is a subset ofE that does not spanM, but such that adding any other element to it does make a spanning set.^[5]

The family${\displaystyle \mathcal{H}}$ of hyperplanes of a matroid has the following properties, which may be taken as yet another axiomatization of matroids:^[5]

• (H1) There do not exist distinct sets${\displaystyle X}$ and${\displaystyle Y}$ in${\displaystyle \mathcal{H}}$ with${\displaystyle X\subseteq Y}$. That is, the hyperplanes form aSperner family.

• (H2) For every${\displaystyle x\in E}$ and distinct${\displaystyle Y,Z\in \mathcal{H}}$ with${\displaystyle x\notin Y\cup Z}$, there exists${\displaystyle X\in \mathcal{H}}$ with${\displaystyle (Y\cap Z)\cup \{x\}\subseteq X}$.

Minty (1966) defined agraphoid as a triple${\displaystyle (L,C,D)}$ in which${\displaystyle C}$ and${\displaystyle D}$ are classes of nonempty subsets of${\displaystyle L}$ such that

• (G1) no element of${\displaystyle C}$ (called a "circuit") contains another,

• (G2) no element of${\displaystyle D}$ (called a "cocircuit") contains another,

• (G3) no set in${\displaystyle C}$ and set in${\displaystyle D}$ intersect in exactly one element, and

• (G4) whenever${\displaystyle L}$ is represented as the disjoint union of subsets${\displaystyle R,G,B}$ with${\displaystyle G=\{g\}}$ (a singleton set), then either an${\displaystyle X\in C}$ exists such that${\displaystyle g\in X\subseteq R\cup G}$ or a${\displaystyle Y\in D}$ exists such that${\displaystyle g\in Y\subseteq B\cup G}$.

He proved that there is a matroid for which${\displaystyle C}$ is the class of circuits and${\displaystyle D}$ is the class of cocircuits. Conversely, if${\displaystyle C}$ and${\displaystyle D}$ are the circuit and cocircuit classes of a matroid${\displaystyle M}$ with ground set${\displaystyle E}$, then${\displaystyle (E,C,D)}$ is a graphoid. Thus, graphoids give aself-dual cryptomorphic axiomatization of matroids.

Let${\displaystyle E}$ be a finite set. The set of all subsets of${\displaystyle E}$ defines the independent sets of a matroid. It is called thefree matroid over${\displaystyle E}$.

Let${\displaystyle E}$ be a finite set and${\displaystyle k}$ anatural number. One may define a matroid on${\displaystyle E}$ by taking every${\displaystyle k}$ element subset of${\displaystyle E}$ to be a basis. This is known as theuniform matroid of rank${\displaystyle k}$. A uniform matroid with rank${\displaystyle k}$ and with${\displaystyle n}$ elements is denoted${\displaystyle U_{k,n}}$. All uniform matroids of rank at least 2 are simple (see§ Additional terms). The uniform matroid of rank 2 on${\displaystyle n}$ points is called the${\displaystyle n}$ 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 calledpartition matroids.

In the uniform matroid${\displaystyle U_{0,n}}$, every element is a loop (an element that does not belong to any independent set), and in the uniform matroid${\displaystyle U_{n,n}}$, every element is a coloop (an element that belongs to all bases). 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 adiscrete matroid. An equivalent definition of a discrete matroid is a matroid in which every proper, non-empty subset of the ground set${\displaystyle E}$ is a separator.

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:

If${\displaystyle E}$ is any finite subset of avector space${\displaystyle V}$, then we can define a matroid${\displaystyle M}$ on${\displaystyle E}$ by taking the independent sets of${\displaystyle M}$ to be thelinearly independent subsets of${\displaystyle E}$.

The validity of the independent set axioms for this matroid follows from theSteinitz exchange lemma.

If${\displaystyle M}$ is a matroid that can be defined in this way, we say the set${\displaystyle E}$represents${\displaystyle M}$.

Matroids of this kind are calledvector matroids.

An important example of a matroid defined in this way is the Fano matroid, a rank three matroid derived from theFano plane, afinite geometry with seven points (the seven elements of the matroid) and seven lines (the proper nontrivial flats of the matroid). It is a linear matroid whose elements may be described as the seven nonzero points in a three dimensional vector space over thefinite fieldGF(2). However, it is not possible to provide a similar representation for the Fano matroid using thereal numbers in place of GF(2).

Amatrix${\displaystyle A}$ with entries in afield gives rise to a matroid${\displaystyle M}$ on its set of columns. The dependent sets of columns in the matroid are those that are linearly dependent as vectors.

This matroid is called thecolumn matroid of${\displaystyle A}$, and${\displaystyle A}$ is said torepresent${\displaystyle M}$.

For instance, the Fano matroid can be represented in this way as a 3 × 7(0,1) matrix. Column matroids are just vector matroids under another name, but there are often reasons to favor the matrix representation.^[b]

A matroid that is equivalent to a vector matroid, although it may be presented differently, is calledrepresentable orlinear. If${\displaystyle M}$ is equivalent to a vector matroid over afield${\displaystyle F}$, then we say${\displaystyle M}$ isrepresentable over${\displaystyle F}$; in particular,${\displaystyle M}$ isreal representable if it is representable over the real numbers. For instance, although a graphic matroid (see below) 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${\displaystyle F}$;Rota's conjecture describes a possible characterization for everyfinite field. The main results so far are characterizations ofbinary matroids (those representable over GF(2)) due toTutte (1950s), of ternary matroids (representable over the 3 element field) due to Reid and Bixby, and separately toSeymour (1970s), and of quaternary matroids (representable over the 4 element field) due toGeelen, Gerards & Kapoor (2000). A proof of Rota's conjecture was announced, but not published, in 2014 by Geelen, Gerards, and Whittle.^[6]

Aregular matroid is a matroid that is representable over all possible fields. TheVámos matroid is the simplest example of a matroid that is not representable over any field.

A second original source for the theory of matroids isgraph theory.

Every finite graph (ormultigraph)${\displaystyle G}$ gives rise to a matroid${\displaystyle M(G)}$ as follows: take as${\displaystyle E}$ the set of all edges in${\displaystyle G}$ and consider a set of edges independent if and only if it is aforest; that is, if it does not contain asimple cycle. Then${\displaystyle M(G)}$ is called acycle matroid. Matroids derived in this way aregraphic matroids. Not every matroid is graphic, but all matroids on three elements are graphic.^[7] Every graphic matroid is regular.

Other matroids on graphs were discovered subsequently:

• Thebicircular matroid of a graph is defined by calling a set of edges independent if every connected subset contains at most one cycle.

• In any directed or undirected graph${\displaystyle G}$ let${\displaystyle E}$ and${\displaystyle F}$ be two distinguished sets of vertices. In the set${\displaystyle E}$, define a subset${\displaystyle U}$ to be independent if there are${\displaystyle |U|}$ vertex-disjoint paths from${\displaystyle F}$ onto${\displaystyle U}$. This defines a matroid on${\displaystyle E}$ called agammoid:^[8] astrict gammoid is one for which the set${\displaystyle E}$ is the whole vertex set of${\displaystyle G}$.^[9]

• In abipartite graph${\displaystyle G=(U,V,E)}$, one may form a matroid in which the elements are vertices on one side${\displaystyle U}$ of the bipartition, and the independent subsets are sets of endpoints ofmatchings of the graph. This is called atransversal matroid,^[10][11] and it is a special case of a gammoid.^[8] The transversal matroids are thedual matroids to the strict gammoids.^[9]

• Graphic matroids have been generalized to matroids fromsigned graphs,gain graphs, andbiased graphs. A graph${\displaystyle G}$ with a distinguished linear class${\displaystyle B}$ of cycles, known as a "biased graph"${\displaystyle (G,B)}$, has two matroids, known as theframe matroid and thelift matroid of the biased graph.

If every cycle belongs to the distinguished class, these matroids coincide with the cycle matroid of${\displaystyle G}$. If no cycle is distinguished, the frame matroid is the bicircular matroid of${\displaystyle G}$. A signed graph, whose edges are labeled by signs, and a gain graph, which is a graph whose edges are labeled orientably from a group, each give rise to a biased graph and therefore have frame and lift matroids.

• TheLaman graphs form the bases of the two dimensionalrigidity matroid, a matroid defined in the theory ofstructural rigidity.

• Let${\displaystyle G}$ be a connected graph and${\displaystyle E}$ be its edge set. Let${\displaystyle I}$ be the collection of subsets${\displaystyle F}$ of${\displaystyle E}$ such that${\displaystyle G-F}$ is still connected. Then${\displaystyle M^{\ast }(G)}$, whose element set is${\displaystyle E}$ and with${\displaystyle I}$ as its class of independent sets, is a matroid called thebond matroid of${\displaystyle G}$.

The rank function${\displaystyle r(F)}$ is thecyclomatic number of the subgraph induced on the edge subset${\displaystyle F}$, which equals the number of edges outside a maximal forest of that subgraph, and also the number of independent cycles in it.

A third original source of matroid theory isfield theory.

Anextension of a field gives rise to a matroid:

Suppose${\displaystyle F}$ and${\displaystyle K}$ are fields with${\displaystyle K}$ containing${\displaystyle F}$. Let${\displaystyle E}$ be any finite subset of${\displaystyle K}$.

Define a subset${\displaystyle S}$ of${\displaystyle E}$ to bealgebraically independent if the extension field${\displaystyle F(S)}$ hastranscendence degree equal to${\displaystyle |S|}$.^[12]

A matroid that is equivalent to a matroid of this kind is called analgebraic matroid.^[13] The problem of characterizing algebraic matroids is extremely difficult; little is known about it. TheVámos matroid provides an example of a matroid that is not algebraic.

There are some standard ways to make new matroids out of old ones.

If${\displaystyle M}$ is a finite matroid, we can define theorthogonal ordual matroid${\displaystyle M^{\ast }}$ by taking the same underlying set and calling a set abasis in${\displaystyle M^{\ast }}$ if and only if its complement is a basis in${\displaystyle M}$. It is not difficult to verify that${\displaystyle M^{\ast }}$ is a matroid and that the dual of${\displaystyle M^{\ast }}$ is${\displaystyle M}$.^[14]

The dual can be described equally well in terms of other ways to define a matroid. For instance:

• A set is independent in${\displaystyle M^{\ast }}$ if and only if its complement spans${\displaystyle M}$.

• A set is a circuit of${\displaystyle M^{\ast }}$ if and only if its complement is a coatom in${\displaystyle M}$.

• The rank function of the dual is${\displaystyle r^{\ast }(S)=|S|-r(M)+r\left(E\setminus S\right)}$.

According to a matroid version ofKuratowski's theorem, the dual of a graphic matroid${\displaystyle M}$ is a graphic matroid if and only if${\displaystyle M}$ is the matroid of aplanar graph. In this case, the dual of${\displaystyle M}$ is the matroid of thedual graph of${\displaystyle G}$.^[15] The dual of a vector matroid representable over a particular field${\displaystyle F}$ is also representable over${\displaystyle F}$. The dual of a transversal matroid is a strict gammoid and vice versa.

Example

The cycle matroid of a graph is the dual matroid of its bond matroid.

IfM is a matroid with element setE, andS is a subset ofE, therestriction ofM toS, writtenM |S, is the matroid on the setS whose independent sets are the independent sets ofM that are contained inS. Its circuits are the circuits ofM that are contained inS and its rank function is that ofM restricted to subsets ofS.

In linear algebra, this corresponds to restricting to the subspace generated by the vectors inS. Equivalently ifT =M−S this may be termed thedeletion ofT, writtenM\T orM−T. The submatroids ofM are precisely the results of a sequence of deletions: the order is irrelevant.^[16][17]

The dual operation of restriction is contraction.^[18] IfT is a subset ofE, thecontraction ofM byT, writtenM/T, is the matroid on the underlying setE − T whose rank function is${\displaystyle r^{\prime }(A)=r(A\cup T)-r(T)}$.^[19] In linear algebra, this corresponds to looking at the quotient space by the linear space generated by the vectors inT, together with the images of the vectors inE - T.

A matroidN that is obtained fromM by a sequence of restriction and contraction operations is called aminor ofM.^[17][20] We sayMcontainsNas a minor. Many important families of matroids may be characterized by theminor-minimal matroids that do not belong to the family; these are calledforbidden orexcluded minors.^[21]

LetM be a matroid with an underlying set of elementsE, and letN be another matroid on an underlying setF.Thedirect sum of matroidsM andN is the matroid whose underlying set is thedisjoint union ofE andF, and whose independent sets are the disjoint unions of an independent set ofM with an independent set ofN.

Theunion ofM andN is the matroid whose underlying set is the union (not the disjoint union) ofE andF, and whose independent sets are those subsets that are the union of an independent set inM and one inN. Usually the term "union" is applied whenE =F, but that assumption is not essential. IfE andF are disjoint, the union is the direct sum.

LetM be a matroid with an underlying set of elementsE.

• E may be called theground set ofM. Its elements may be called thepoints ofM.

• A subset ofEspansM if its closure isE. A set is said tospan a closed setK if its closure isK.

• Thegirth of a matroid is the size of its smallest circuit or dependent set.

• An element that forms a single-element circuit ofM is called aloop. Equivalently, an element is a loop if it belongs to no basis.^[7][22]

• An element that belongs to no circuit is called acoloop oristhmus. Equivalently, an element is a coloop if it belongs to every basis.

Loop and coloops are mutually dual.^[22]

• If a two-element set {f, g} is a circuit ofM, thenf andg areparallel inM.^[7]

• A matroid is calledsimple if it has no circuits consisting of 1 or 2 elements. That is, it has no loops and no parallel elements. The termcombinatorial geometry is also used.^[7] A simple matroid obtained from another matroidM by deleting all loops and deleting one element from each 2-element circuit until no 2 element circuits remain is called asimplification ofM.^[23] A matroid isco-simple if its dual matroid is simple.^[24]

• A union of circuits is sometimes called acycle ofM. A cycle is therefore the complement of a flat of the dual matroid. (This usage conflicts with the common meaning of "cycle" in graph theory.)

• Aseparator ofM is a subsetS ofE such that${\displaystyle r(S)+r(E-S)=r(M)}$. Aproper ornon-trivial separator is a separator that is neitherE nor the empty set.^[25] Anirreducible separator is a non-empty separator that contains no other non-empty separator. The irreducible separators partition the ground setE.

• A matroid that cannot be written as the direct sum of two nonempty matroids, or equivalently that has no proper separators, is calledconnected orirreducible. A matroid is connected if and only if its dual is connected.^[26]

• A maximal irreducible submatroid ofM is called acomponent ofM. A component is the restriction ofM to an irreducible separator, and contrariwise, the restriction ofM to an irreducible separator is a component. A separator is a union of components.^[25]

• A matroidM is called aframe matroid if it, or a matroid that contains it, has a basis such that all the points ofM are contained in the lines that join pairs of basis elements.^[27]

• A matroid is called apaving matroid if all of its circuits have size at least equal to its rank.^[28]

• Thebasis polytope${\displaystyle P_M}$ is theconvex hull of theindicator vectors of the bases of${\displaystyle M}$

• The independence polytope of${\displaystyle M}$ is theconvex hull of theindicator vectors of the independent sets of${\displaystyle M}$.

Several important combinatorial optimization problems can be solved efficiently on every matroid. In particular:

• Finding amaximum-weight independent set in aweighted matroid can be solved by agreedy algorithm. This fact may even be used to characterize matroids: if a familyF of sets, closed under taking subsets, has the property that, no matter how the sets are weighted, the greedy algorithm finds a maximum-weight set in the family, thenF must be the family of independent sets of a matroid.^[29]

• Thematroid partitioning problem is to partition the elements of a matroid into as few independent sets as possible, and thematroid packing problem is to find as many disjoint spanning sets as possible. Both can be solved in polynomial time, and can be generalized to the problem of computing the rank or finding an independent set in a matroid sum.

• Amatroid intersection of two or more matroids on the same ground set is the family of sets that are simultaneously independent in each of the matroids. The problem of finding the largest set, or the maximum weighted set, in the intersection of two matroids can be found inpolynomial time, and provides a solution to many other important combinatorial optimization problems. For instance,maximum matching inbipartite graphs can be expressed as a problem of intersecting twopartition matroids. However, finding the largest set in an intersection of three or more matroids isNP-complete.

Two standalone systems for calculations with matroids are Kingan'sOid and Hlineny'sMacek. Both of them are open-sourced packages. "Oid" is an interactive, extensible software system for experimenting with matroids. "Macek" is a specialized software system with tools and routines for reasonably efficient combinatorial computations with representable matroids.

Both open source mathematics software systemsSAGE andMacaulay2 contain matroid packages.Maple has a package for dealing with matroids since the version 2024.^[30]

There are two especially significant polynomials associated to a finite matroidM on the ground setE. Each is amatroid invariant, which means that isomorphic matroids have the same polynomial.

Thecharacteristic polynomial ofM – sometimes called thechromatic polynomial,^[31] although it does not count colorings – is defined to be

${\displaystyle p_M(\lambda ):=\sum _{S\subseteq E}(-1{)}^{|S|}{\lambda }^{r(E)-r(S)},}$

or equivalently (as long as the empty set is closed inM) as

${\displaystyle p_M(\lambda ):=\sum _A\mu (\mathrm{\varnothing },A){\lambda }^{r(E)-r(A)}}$,

where μ denotes theMöbius function of thegeometric lattice of the matroid and the sum is taken over all the flats A of the matroid.^[32]

• WhenM is the cycle matroidM(G) of a graphG, the characteristic polynomial is a slight transformation of thechromatic polynomial, which is given by χ_G (λ) = λ^cp_M(G) (λ), wherec is the number of connected components ofG.

• WhenM is the bond matroidM*(G) of a graphG, the characteristic polynomial equals theflow polynomial ofG.

• WhenM is the matroidM(A) of anarrangementA of linear hyperplanes inℝⁿ (orFⁿ whereF is any field), the characteristic polynomial of the arrangement is given byp_A (λ) = λ^n−r(M)p_M (λ).

Thebeta invariant of a matroid, introduced byCrapo (1967), may be expressed in terms of the characteristic polynomial${\displaystyle p}$ as an evaluation of the derivative^[33]

${\displaystyle \beta (M)=(-1{)}^{r(M)-1}{p}_M^{\prime }(1)}$

or directly as^[34]

${\displaystyle \beta (M)=(-1{)}^{r(M)}\sum _{X\subseteq E}(-1{)}^{|X|}r(X)}$.

The beta invariant is non-negative, and is zero if and only if${\displaystyle M}$ is disconnected, or empty, or a loop. Otherwise it depends only on the lattice of flats of${\displaystyle M}$. If${\displaystyle M}$ has no loops and coloops then${\displaystyle \beta (M)=\beta (M^{\ast })}$.^[34]

TheWhitney numbers of the first kind of${\displaystyle M}$ are the coefficients of the powers of${\displaystyle \lambda }$ in the characteristic polynomial. Specifically, the${\displaystyle i}$th Whitney number${\displaystyle w_i(M)}$ is the coefficient of${\displaystyle {\lambda }^{r(M)-i}}$ and is the sum of Möbius function values:

${\displaystyle w_i(M)=\sum \{\mu (\mathrm{\varnothing },A):r(A)=i\},}$

summed over flats of the right rank. These numbers alternate in sign, so that${\displaystyle (-1{)}^i{w}_i(M)>0}$ for${\displaystyle 0\le i\le r(M)}$.

TheWhitney numbers of the second kind of${\displaystyle M}$ are the numbers of flats of each rank. That is,${\displaystyle W_i(M)}$ is the number of rank ${\displaystyle i}$ flats.

The Whitney numbers of both kinds generalize theStirling numbers of the first and second kind, which are the Whitney numbers of the cycle matroid of thecomplete graph, and equivalently of thepartition lattice. They were named afterHassler Whitney, the (co)founder of matroid theory, byGian-Carlo Rota. The name has been extended to the similar numbers for finite rankedpartially ordered sets.

TheTutte polynomial of a matroid,${\displaystyle T_M(x,y)}$, generalizes the characteristic polynomial to two variables. This gives it more combinatorial interpretations, and also gives it the duality property

${\displaystyle T_{M^{\ast }}(x,y)=T_M(y,x)}$,

which implies a number of dualities between properties of${\displaystyle M}$ and properties of${\displaystyle M^{\ast }}$. One definition of the Tutte polynomial is

${\displaystyle T_M(x,y)=\sum _{S\subseteq E}(x-1{)}^{r(M)-r(S)}(y-1{)}^{|S|-r(S)}}$.

This expresses the Tutte polynomial as an evaluation of theco-rank-nullity orrank generating polynomial,^[35]

${\displaystyle R_M(u,v)=\sum _{S\subseteq E}{u}^{r(M)-r(S)}{v}^{|S|-r(S)}}$.

From this definition it is easy to see that the characteristic polynomial is, up to a simple factor, an evaluation of${\displaystyle T_M}$, specifically,

${\displaystyle p_M(\lambda )=(-1{)}^{r(M)}{T}_M(1-\lambda ,0)}$.

Another definition is in terms of internal and external activities and a sum over bases, reflecting the fact that${\displaystyle T(1,1)}$ is the number of bases.^[36] This, which sums over fewer subsets but has more complicated terms, was Tutte's original definition.

There is a further definition in terms of recursion by deletion and contraction.^[37] The deletion-contraction identity is

${\displaystyle F(M)=F(M-e)+F(M/e)}$

when${\displaystyle e}$ is neither a loop nor a coloop.An invariant of matroids (i.e., a function that takes the same value on isomorphic matroids) satisfying this recursion and the multiplicative condition

${\displaystyle F(M\oplus M^{\prime })=F(M)F(M^{\prime })}$

is said to be aTutte-Grothendieck invariant.^[35] The Tutte polynomial is the most general such invariant; that is, the Tutte polynomial is a Tutte-Grothendieck invariant and every such invariant is an evaluation of the Tutte polynomial.^[31]

TheTutte polynomial${\displaystyle T_G}$ of a graph is the Tutte polynomial${\displaystyle T_{M(G)}}$ of its cycle matroid.

The theory of infinite matroids is much more complicated than that of finite matroids and forms a subject of its own. 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.

The simplest definition of an infinite matroid is to requirefinite rank; that is, the rank ofE is finite. This theory is similar to that of finite matroids except for the failure of duality due to the fact that the dual of an infinite matroid of finite rank does not have finite rank. Finite-rank matroids include any subsets of finite-dimensional vector spaces and offield extensions of finitetranscendence degree.

The next simplest infinite generalization is finitary matroids, also known aspregeometries. A matroid with possibly infinite ground set isfinitary if it has the property that

${\displaystyle x\in \mathrm{cl}(Y)\iff \text{ there is a finite set }{Y}^{\prime }\subseteq Y\text{ such that }x\in \mathrm{cl}(Y^{\prime }).}$

Equivalently, every dependent set contains a finite dependent set.

Examples are linear dependence of arbitrary subsets of infinite-dimensionalvector spaces (but not infinite dependencies as inHilbert andBanach spaces), and algebraic dependence in arbitrary subsets of field extensions of possibly infinite transcendence degree. Again, the class of finitary matroid is not self-dual, because the dual of a finitary matroid is not finitary.

Finitary infinite matroids are studied inmodel theory, a branch ofmathematical logic with strong ties toalgebra.

In the late 1960s matroid theorists asked for a more general notion that shares the different aspects of finite matroids and generalizes their duality. Many notions of infinite matroids were defined in response to this challenge, but the question remained open. One of the approaches examined by D.A. Higgs became known asB-matroids and was studied by Higgs, Oxley, and others in the 1960s and 1970s. According to a recent result byBruhn et al. (2013), it solves the problem: Arriving at the same notion independently, they provided five equivalent systems of axiom—in terms of independence, bases, circuits, closure and rank. The duality of B-matroids generalizes dualities that can be observed in infinite graphs.

The independence axioms are as follows:

1. The empty set is independent.
2. Every subset of an independent set is independent.
3. For everynonmaximal (under set inclusion) independent set${\displaystyle I}$ and maximal independent set${\displaystyle J}$, there is${\displaystyle x\in J\setminus I}$ such that${\displaystyle I\cup \{x\}}$ is independent.
4. For every subset${\displaystyle X}$ of the base space, every independent subset${\displaystyle I}$ of${\displaystyle X}$ can be extended to a maximal independent subset of${\displaystyle X}$.

With these axioms, every matroid has a dual.

Matroid theory was introduced byWhitney (1935). It was also independently discovered byTakeo Nakasawa, whose work was forgotten for many yearsNishimura & Kuroda (2009).

In his seminal paper, Whitney provided two axioms for independence, and defined any structure adhering to these axioms to be "matroids".^[c]His key observation was that these axioms provide an abstraction of "independence" that is common to both graphs and matrices.Because of this, many of the terms used in matroid theory resemble the terms for their analogous concepts inlinear algebra orgraph theory.

Almost immediately after Whitney first wrote about matroids, an important article was written byMacLane (1936) on the relation of matroids toprojective geometry. A year later,van der Waerden (1937) noted similarities between algebraic and linear dependence in his classic textbook on Modern Algebra.

In the 1940sRichard Rado developed further theory under the name "independence systems" with an eye towardstransversal theory, where his name for the subject is still sometimes used.

In the 1950sW.T. Tutte became the foremost figure in matroid theory, a position he retained for many years. His contributions were plentiful, including

• the characterization ofbinary,regular, andgraphic matroids byexcluded minors

• the regular-matroid representability theorem

• the theory of chain groups and their matroids

and the tools he used to prove many of his results:

• the "Path theorem"

• "Tutte homotopy theorem" (see, e.g.,Tutte (1965))

which are so complicated that later theorists have gone to great trouble to eliminate the need for them in proofs.^[d]

Crapo (1969) andBrylawski (1972) generalized to matroids Tutte's "dichromate", a graphic polynomial now known as theTutte polynomial (named by Crapo). Their work has recently (especially in the 2000s) been followed by a flood of papers—though not as many as on the Tutte polynomial of a graph.

In 1976Dominic Welsh published the first comprehensive book on matroid theory.

Paul Seymour's decomposition theorem for regular matroids (Seymour (1980)) was the most significant and influential work of the late 1970s and the 1980s.Another fundamental contribution, byKahn & Kung (1982), showed why projective geometries andDowling geometries play such an important role in matroid theory.

By the 1980s there were many other important contributors, but one should not omit to mentionGeoff Whittle's extension to ternary matroids of Tutte's characterization of binary matroids that are representable over the rationals (Whittle 1995), perhaps the biggest single contribution of the 1990s.

In the current period (since around 2000) the Matroid Minors Project ofGeelen, Gerards, Whittle, and others,^[e]has produced substantial advances in the structure theory of matroids. Many others have also contributed to that part of matroid theory, which (in the first and second decades of the 21st century) is flourishing.

Mathematicians who pioneered the study of matroids include

Some of the other major contributors are

• Antimatroid – Mathematical system of orderings or sets with antiexchange axiom
• Coxeter matroid – Group-theoretic generalization of matroids
• Greedoid – Set system used in greedy optimization
• Oriented matroid – Abstraction of ordered linear algebra
• Polymatroid – Multiset analogue of matroids
• Pregeometry (model theory) – Formulation of matroids using closure operators

• "Matroid".Encyclopedia of Mathematics.EMS Press. 2001 [1994].

• Kingan, Sandra."Matroid theory".userhome.brooklyn.cuny.edu (academic personal site).Brooklyn College. Brooklyn, NY:City University of New York. — A large bibliography of matroid papers, matroid software, and links.

• Locke, S.C."Greedy algorithms".math.fau.edu (academic personal site). Boca Raton, FL:Florida Atlantic University.

• Pagano, Steven R."Matroids and signed graphs".math.binghamton.edu (academic personal site). Binghamton, NY:Binghamton University.

• Hubenthal, Mark."A brief look at matroids"(PDF).math.washington.edu (academic personal site). Seattle, WA:University of Washington. Archived fromthe original(PDF) on 12 August 2010. — Gives proofs for statements in this article.

• Oxley, James."What is a matroid?"(PDF).math.lsu.edu (academic personal site). Baton Rouge, LA:Louisiana State University.

• White, Neil, ed. (1992b).Matroid Applications. Cambridge University Press.ISBN 978-0-5213-8165-9.ISSN 0953-4806 – via Google Books.

• Matroid theory
• Closure operators
• Families of sets

• Articles with short description
• Short description is different from Wikidata
• CS1: long volume value
• Template SpringerEOM with broken ref