Before discussing oriented matroids, we first recall the definition of a matroid. A matroid abstracts the notion of independence that appears in many settings, such as linear independence in a vector space and acyclicity in a graph.
Formally, a matroid is a pair , where is a ground set and is a family of subsets of , called the independent sets. The family must satisfy the following three axioms:
First, the empty set is independent: .
Second, every subset of an independent set is independent. That is, if and , then .
Third, if two independent sets have different cardinalities, the smaller one can be enlarged by an element of the larger one. More precisely, if and , then there exists an element such that .
These axioms allow us to define the rank of any subset as the maximum size of an independent subset of :
Any subset of that does not belong to is called dependent. A minimal dependent set is called a circuit. Thus, a matroid can be described equivalently by either its independent sets or its circuits.
1.1 Oriented matroids from directed graphs
Consider a directed graph with vertex set and arc set . Each simple cycle, being a minimal dependent set, can be regarded as a signed subset of . After choosing a direction in which to traverse the cycle, we place each arc in the positive or negative part according to whether its orientation agrees or disagrees with the direction of traversal. The resulting signed subset is called a signed circuit of .
An oriented matroid obtained from a digraph can be described by its signed circuits. The collection of all signed circuits of is
We denote the resulting oriented matroid by . Note that contains both signed circuits in every opposite pair . By forgetting the signs, we obtain the underlying matroid , where .
A second description uses minimal cuts. Given a partition of the vertex set, the arcs between and form a minimal cut if removing them increases the number of connected components of the underlying undirected graph by one. Let consist of the arcs directed from to , and let consist of those directed from to . The resulting signed sets are called the signed cocircuits of . We write
Properties of can be expressed in terms of the collections and . For example, the digraph is acyclic—that is, it contains no directed cycle—if and only if contains no positive circuit, where a circuit is positive if . The same property can be characterized in terms of cocircuits: is acyclic if and only if every arc belongs to a positive cocircuit. In other words, for every , there exists a cocircuit such that .
Sketch of Proof.
Suppose that is acyclic, and fix an arc . Let be the set of vertices from which is reachable. Since is acyclic, ; otherwise, a path from to , together with the arc , would form a directed cycle. Hence, belongs to the cut induced by the partition . Moreover, no arc enters : if were an arc with and , then would imply , contradicting . Thus, this cut is positive. By restricting it to a minimal cut containing , we obtain a positive cocircuit with .
We now introduce the dual oriented matroid, whose collection of circuits is . To motivate this definition, suppose that is a planar digraph. There is a canonical way to orient its dual graph such that the circuits of the dual graph correspond exactly to the cocircuits of the original graph, and conversely.
The next important property is orthogonality: if a directed cycle crosses a cut in one direction, then it must also cross the cut in the opposite direction.
If is a circuit and is a cocircuit of an oriented matroid, then
For two signed sets and , let
denote their separation set. The orthogonality condition can then be written as for every and every .
