An oriented matroid is a mathematical structure that abstracts the properties of directed graphs, vector arrangements over ordered fields, and hyperplane arrangements over ordered fields. In comparison, an ordinary (i.e., non-oriented) matroid abstracts the dependence properties that are common both to graphs, which are not necessarily directed, and to arrangements of vectors over fields, which are not necessarily ordered.
All oriented matroids have an underlying matroid. Thus, results on ordinary matroids can be applied to oriented matroids. However, the converse is false; some matroids cannot become an oriented matroid by orienting an underlying structure (e.g., circuits or independent sets). The distinction between matroids and oriented matroids is discussed further below. Matroids are often useful in areas such as dimension theory and algorithms. Because of an oriented matroid's inclusion of additional details about the oriented nature of a structure, its usefulness extends further into several areas including geometry and optimization.
History The first appearance of oriented matroids was in a 1966 article by George J. Minty and was confined to regular matroids. Subsequently R.T. Rockafellar (1969) suggested the problem of generalizing Minty's concept to real vector spaces. His proposal helped lead to the development of the general theory.
Background
In order to abstract the concept of orientation on the edges of a graph to sets, one needs the ability to assign "direction" to the elements of a set. The way this achieved is with the following definition of signed sets.
A signed set, X {\displaystyle X} , combines a set of objects, X _ {\displaystyle {\underline {X}}} , with an ordered bipartition ( X + , X − ) {\displaystyle (X^{+},X^{-})} of that set into two disjoint subsets: X + {\displaystyle X^{+}} and X − {\displaystyle X^{-}} . The members of X + {\displaystyle X^{+}} are called the positive elements; members of X − {\displaystyle X^{-}} are the negative elements. The set X _ = X + ∪ X − {\displaystyle {\underline {X}}=X^{+}\cup X^{-}} is called the support of X {\displaystyle X} . The empty signed set, ∅ {\displaystyle \emptyset } , is defined as the empty set ∅ _ {\displaystyle {\underline {\emptyset }}} combined with an (ordered) bipartition of it into two empty sets: ∅ + {\displaystyle \emptyset ^{+}} and ∅ − {\displaystyle \emptyset ^{-}} . The signed set Y {\displaystyle Y} is the opposite of X {\displaystyle X} , written Y = − X {\displaystyle Y=-X} , if Y + = X − {\displaystyle Y^{+}=X^{-}} and Y − = X + . {\displaystyle Y^{-}=X^{+}.}
Given an element x {\displaystyle x} of the support, we will write x {\displaystyle x} for a positive element and − x {\displaystyle -x} for a negative element. In this way, a signed set is just adding negative signs to distinguished elements. This will make sense as a "direction" only when we consider orientations of larger structures. Then the sign of each element will encode its direction relative to this orientation.
Axiomatizations
Like ordinary matroids, several equivalent systems of axioms exist. (Such structures that possess multiple equivalent axiomatizations are called cryptomorphic.)
Circuit axioms Let E {\displaystyle E} be any set. We refer to E {\displaystyle E} as the ground set. Let C {\displaystyle {\mathcal {C}}} be a collection of signed sets, each of which is supported by a subset of E {\displaystyle E} . If the following axioms hold for C {\displaystyle {\mathcal {C}}} , then equivalently C {\displaystyle {\mathcal {C}}} is the set of signed circuits for an oriented matroid on E {\displaystyle E} .
(C0) ∅ ∉ C {\displaystyle \emptyset \notin {\mathcal {C}}}
… excerpt ends here. Continue reading the full article.
