Matroid Constraints

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 (finite) matroid.

Independent sets

In terms of independence, a finite matroid $M$ is a pair $(E, \mathcal)$, where $E$ is a finite set (called the ''ground set'') and $\mathcal$ is a family of subsets of $E$ (called the ''independent sets'') with the following properties:, Section 1.2, "Axiom Systems for a Matroid".

* (I1) The empty set is independent, i.e., $\emptyset \in \mathcal$.

* (I2) Every subset of an independent set is independent, i.e., for each $A' \subseteq A \subseteq E$, if $A \in \mathcal$ then $A' \in \mathcal$. This is sometimes called the ''hereditary property'', or the ''downward-closed'' property.

* (I3) If $A$ and $B$ are two independent sets (i.e., each set is independent) and $A$ has more elements than $B$, then there exists $x \in A \setminus B$ such that $B \cup \$ is in $\mathcal$. 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 (or abstract simplicial complex). Actually, assuming (I2), property (I1) is equivalent to the fact that at least one subset of $E$ is independent, i.e., $\mathcal\neq\emptyset$.

Bases and circuits

A subset of the ground set $E$ that is not independent is called ''dependent''. A maximal independent set – that is, an independent set that becomes dependent upon adding any element of $E$ – is called a ''basis'' for the matroid. A ''circuit'' in a matroid $M$ is a minimal dependent subset of $E$ – 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 $M$ to be a pair $(E,\mathcal)$, where $E$ is a finite set as before and $\mathcal$ is a collection of subsets of $E$, called ''bases'', with the following properties:

* (B1) $\mathcal$ is nonempty.

* (B2) If $A$ and $B$ are distinct members of $\mathcal$ and $a \in A \smallsetminus B$, then there exists an element $b \in B \smallsetminus A$ such that $(A \smallsetminus \) \cup \ \in \mathcal$.

This property (B2) is called the ''basis exchange property''. It follows from this property that no member of $\mathcal$ 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 $M$ have the same number of elements. This number is called the ''rank'' If $M$ is a matroid on $E$, and $A$ is a subset of $E$, then a matroid on $A$ can be defined by considering a subset of $A$ to be independent if and only if it is independent in $M$. This allows us to talk about ''submatroids'' and about the rank of any subset of $E$. The rank of a subset $A$ is given by the '' rank function'' $r(A)$ of the matroid, which has the following properties:

*(R1) The value of the rank function is always a non-negative integer.

*(R2) For any subset $A\subset E$, we have $r(A) \le , A,$.

*(R3) For any two subsets $A, B\subset E$, we have: $r(A \cup B) + r(A \cap B) \le r(A) + r(B)$. That is, the rank is a submodular function.

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

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

The difference $, A, - r(A)$ is called the ''nullity'' of the subset $A$. It is the minimum number of elements that must be removed from $A$ to obtain an independent set. The nullity of $E$ in $M$ is called the nullity of $M$. The difference $r(E) - r(A)$ is sometimes called the ''corank'' of the subset $A$.

Closure operators

Let $M$ be a matroid on a finite set $E$, with rank function $r$ as above. The ''closure'' or ''span'' $\operatorname(A)$ of a subset $A$ of $E$ is the set
:$\operatorname(A) = \Bigl\$.
This defines a closure operator $\operatorname: \mathcal(E) \mapsto \mathcal(E)$ where $\mathcal$ denotes the power set, with the following properties:

* (C1) For all subsets $X$ of $E$, $X \subseteq \operatorname(X)$.

* (C2) For all subsets $X$ of $E$, $\operatorname(X)= \operatorname\left( \operatorname\left( X \right) \right)$.

* (C3) For all subsets $X$ and $Y$ of $E$ with $X\subseteq Y$, $\operatorname(X)\subseteq \operatorname(Y)$.

* (C4) For all elements $a$ and $b$ from $E$ and all subsets $Y$ of $E$, if $a \in \operatorname( Y \cup \) \smallsetminus \operatorname(Y)$ then $b \in \operatorname( Y \cup \) \smallsetminus \operatorname(Y)$.

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 $\operatorname: \mathcal(E)\to \mathcal(E)$ 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:

* (F1) The whole point set $E$ is closed.

* (F2) If $S$ and $T$ are flats, then $S\cap T$ is a flat.

* (F3) If $S$ is a flat, then each element of $E\smallsetminus S$ is in precisely one of the flats $T$ that cover $S$ (meaning that $T$ properly contains $S$, but there is no flat $U$ between $S$ and $T$).

The class $\mathcal(M)$ of all flats, partially ordered by set inclusion, forms a matroid lattice. Conversely, every matroid lattice $L$ forms a matroid over its set $E$ of atoms under the following closure operator: for a set $S$ of atoms with join $\bigvee S$,
:$\operatorname(S) = \$.
The flats of this matroid correspond one-for-one with the elements of the lattice; the flat corresponding to lattice element $y$ is the set
:$\$.
Thus, the lattice of flats of this matroid is naturally isomorphic to $L$.

Hyperplanes

In a matroid of rank $r$, a flat of rank $r - 1$ is called a ''hyperplane''. (Hyperplanes are also called ''co-atoms'' or ''copoints''.) These are the maximal proper flats; that is, the only superset of a hyperplane that is also a flat is the set $E$ 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., Section 2.2, "The Hyperplanes of a Matroid".

The family $\mathcal$ of hyperplanes of a matroid has the following properties, which may be taken as yet another axiomatization of matroids:

* (H1) There do not exist distinct sets $X$ and $Y$ in $\mathcal$ with $X \subseteq Y$. That is, the hyperplanes form a Sperner family.

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

Graphoids

Minty (1966) defined a ''graphoid'' as a triple $(L, C, D)$ in which $C$ and $D$ are classes of nonempty subsets of $L$ such that

*(G1) no element of $C$ (called a "circuit") contains another,

*(G2) no element of $D$ (called a "cocircuit") contains another,

*(G3) no set in $C$ and set in $D$ intersect in exactly one element, and

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

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

Examples

Free matroid

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

Uniform matroids

Let $E$ be a finite set and $k$ a natural number. One may define a matroid on $E$ by taking every subset of $E$ to be a basis. This is known as the '' uniform matroid'' of rank $k$. A uniform matroid with rank $k$ and with $n$ elements is denoted $U_$. All uniform matroids of rank at least 2 are simple (see ). The uniform matroid of rank 2 on $n$ points is called the $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 called partition matroids.

In the uniform matroid $U_$, every element is a loop (an element that does not belong to any independent set), and in the uniform matroid $U_$, 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 a ''discrete matroid''. An equivalent definition of a discrete matroid is a matroid in which every proper, non-empty subset of the ground set $E$ 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:
: If $E$ is any finite subset of a vector space $V$, then we can define a matroid $M$ on $E$ by taking the independent sets of $M$ to be the linearly independent subsets of $E$.
The validity of the independent set axioms for this matroid follows from the Steinitz exchange lemma.

: If $M$ is a matroid that can be defined in this way, we say the set $E$ '' represents'' $M$.

: Matroids of this kind are called ''vector matroids''.

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

A matrix $A$ with entries in a field gives rise to a matroid $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 the ''column matroid'' of $A$, and $A$ is said to ''represent'' $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.

A matroid that is equivalent to a vector matroid, although it may be presented differently, is called ''representable'' or ''linear''. If $M$ is equivalent to a vector matroid over a field $F$, then we say $M$ is ''representable over'' in particular, $M$ is ''real 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 $F$; Rota's conjecture describes a possible characterization for every finite field. The main results so far are characterizations of binary matroids (those representable over GF(2)) due to Tutte (1950s), of ternary matroids (representable over the 3 element field) due to Reid and Bixby, and separately to Seymour (1970s), and of quaternary matroids (representable over the 4 element field) 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.

Matroids from graph theory

A second original source for the theory of matroids is graph theory.

Every finite graph (or multigraph) $G$ gives rise to a matroid $M(G)$ as follows: take as $E$ the set of all edges in $G$ and consider a set of edges independent if and only if it is a forest; that is, if it does not contain a simple cycle. Then $M(G)$ is called a ''cycle matroid''. Matroids derived in this way are ''graphic matroids''. Not every matroid is graphic, but all matroids on three elements are graphic. Every graphic matroid is regular.

Other matroids on graphs were discovered subsequently:

*The bicircular 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 $G$ let $E$ and $F$ be two distinguished sets of vertices. In the set $E$, define a subset $U$ to be independent if there are $, U,$ vertex-disjoint paths from $F$ onto $U$. This defines a matroid on $E$ called a '' gammoid'': a ''strict gammoid'' is one for which the set $E$ is the whole vertex set of $G$.

*In a bipartite graph $G = (U,V,E)$, one may form a matroid in which the elements are vertices on one side $U$ of the bipartition, and the independent subsets are sets of endpoints of matchings of the graph. This is called a ''transversal matroid'', and it is a special case of a gammoid. The transversal matroids are the dual matroids to the strict gammoids.

*Graphic matroids have been generalized to matroids from signed graphs, gain graphs, and biased graphs. A graph $G$ with a distinguished linear class $B$ of cycles, known as a "biased graph" $(G, B)$, has two matroids, known as the ''frame matroid'' and the ''lift matroid'' of the biased graph.

: If every cycle belongs to the distinguished class, these matroids coincide with the cycle matroid of $G$. If no cycle is distinguished, the frame matroid is the bicircular matroid of $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.

*The Laman graphs form the bases of the two dimensional rigidity matroid, a matroid defined in the theory of structural rigidity.

*Let $G$ be a connected graph and $E$ be its edge set. Let $I$ be the collection of subsets $F$ of $E$ such that $G - F$ is still connected. Then $M^*(G)$, whose element set is $E$ and with $I$ as its class of independent sets, is a matroid called the ''bond matroid'' of $G$.

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

Matroids from field extensions

A third original source of matroid theory is field theory.

An extension of a field gives rise to a matroid:
: Suppose $F$ and $K$ are fields with $K$ containing $F$. Let $E$ be any finite subset of $K$.
: Define a subset $S$ of $E$ to be algebraically independent if the extension field $F(S)$ has transcendence degree equal to $, S,$.

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

Basic constructions

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

Duality

If $M$ is a finite matroid, we can define the ''orthogonal'' or ''dual matroid'' $M^*$ by taking the same underlying set and calling a set a ''basis'' in $M^*$ if and only if its complement is a basis in $M$. It is not difficult to verify that $M^*$ is a matroid and that the dual of $M^*$ is $M$.

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

* A set is independent in $M^*$ if and only if its complement spans $M$.

* A set is a circuit of $M^*$ if and only if its complement is a coatom in $M$.

* The rank function of the dual is $r^*(S) = , S, - r(M) + r\left(E\smallsetminus S\right)$.

According to a matroid version of Kuratowski's theorem, the dual of a graphic matroid $M$ is a graphic matroid if and only if $M$ is the matroid of a planar graph. In this case, the dual of $M$ is the matroid of the dual graph of $G$. The dual of a vector matroid representable over a particular field $F$ is also representable over $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.

Minors

If ''M'' is a matroid with element set ''E'', and ''S'' is a subset of ''E'', the ''restriction'' of ''M'' to ''S'', written ''M'' , ''S'', is the matroid on the set ''S'' whose independent sets are the independent sets of ''M'' that are contained in ''S''. Its circuits are the circuits of ''M'' that are contained in ''S'' and its rank function is that of ''M'' restricted to subsets of ''S''.

In linear algebra, this corresponds to restricting to the subspace generated by the vectors in ''S''. Equivalently if ''T'' = ''M''−''S'' this may be termed the ''deletion'' of ''T'', written ''M''\''T'' or ''M''−''T''. The submatroids of ''M'' are precisely the results of a sequence of deletions: the order is irrelevant.

The dual operation of restriction is contraction. 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 $r'(A) = r(A \cup T) - r(T)$. 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''. We say ''M'' ''contains'' ''N'' ''as a minor''. Many important families of matroids may be characterized by the minor-minimal matroids that do not belong to the family; these are called ''forbidden'' or ''excluded minors''.

Sums and unions

Let ''M'' be a matroid with an underlying set of elements ''E'', and let ''N'' be another matroid on an underlying set ''F''.
The ''direct sum'' of matroids ''M'' and ''N'' is the matroid whose underlying set is the disjoint union of ''E'' and ''F'', and whose independent sets are the disjoint unions of an independent set of ''M'' with an independent set of ''N''.

The ''union'' of ''M'' and ''N'' is the matroid whose underlying set is the union (not the disjoint union) of ''E'' and ''F'', and whose independent sets are those subsets that are the union of an independent set in ''M'' and one in ''N''. Usually the term "union" is applied when ''E'' = ''F'', but that assumption is not essential. If ''E'' and ''F'' are disjoint, the union is the direct sum.

Additional terms girth