Oriented matroid

. A network with the value of flow equal to the capacity of an s-t cut 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.

. A network with the value of flow equal to the capacity of an s-t cut]] 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. The set \underline{X} = X^+ \cup X^- is called the support of X . The empty signed set, \empty , is defined as the empty set \underline{\empty} combined with an (ordered) bipartition of it into two empty sets: \emptyset^+ and \emptyset^- . The signed set Y is the opposite of X , written Y = -X , if Y^+ = X^- and Y^- = X^+. Given an element x of the support, we will write x for a positive element and -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. (C2) (incomparable) \text{ For all } X,Y \in \mathcal{C},~~ \text{ if } \underline X\subseteq \underline Y\text{ then } (X=Y \text{ or } X = -Y). (C3) (weak elimination) \text{ For all } X,Y \in \mathcal{C}, X \neq -Y \text{ with an } e \in X^+ \cap Y^- \text{ there is a } Z \in \mathcal{C} \text{ such that } Z^+ \subseteq (X^+ \cup Y^+)\setminus\{e\} \text{ and } Z^- \subseteq (X^- \cup Y^-)\setminus\{e\}. The composition of signed sets X and Y is the signed set X\circ Y defined by \underline{X\circ Y}= {\underline X} \cup {\underline Y} , (X\circ Y)^+ = X^+ \cup \left(Y^+ \setminus X^-\right) , and (X\circ Y)^- = X^- \cup \left(Y^- \setminus X^+\right) . The vectors of an oriented matroid are the compositions of circuits. The vectors \mathcal V of an oriented matroid satisfy the following axioms: \emptyset \in \mathcal V \mathcal V = -\mathcal V for all X, Y\in \mathcal V , X\circ Y \in \mathcal V for all X, Y\in \mathcal V , e\in X^+ \cap Y^- and f\in (\underline X \setminus \underline Y)\cup (\underline Y \setminus \underline X) \cup (X^+\cap Y^+) \cup (X^- \cap Y^-) , there is a Z\in \mathcal V , such that Z^+ \subset X^+ \cup Y^+ \setminus e , Z^- \subset X^- \cup Y^- \setminus e , and f\in \underline Z . The covectors of an oriented matroid are the vectors of its dual oriented matroid. (B1) (alternating): For any permutation \sigma and x_1,\dots,x_r\in E , \chi\left(x_{\sigma(1)},\dots,x_{\sigma(r)}\right)=\operatorname{sgn}(\sigma)\chi\left(x_1,\dots,x_r\right) , where \operatorname{sgn}(\sigma) is the sign of the permutation. (B2) (exchange): For any x_1,\dots,x_r,y_1,\dots,y_r\in E such that \chi(y_i,x_2,\dots,x_r)\chi(y_1,\dots,y_{i-1},x_1,y_{i+1},\dots,y_r)\ge 0 for each i , then we also have \chi\left(x_1,\dots,x_r\right)\chi\left(y_1,\dots,y_r\right)\ge0 . The term chirotope is derived from the mathematical notion of chirality, which is a concept abstracted from chemistry, where it is used to distinguish molecules that have the same structure except for a reflection. C^+=\{x_i: (-1)^i\chi(x_1,\dots,x_{i-1},x_{i+1},\dots,x_{r+1})=1\} and negative elements the complement. Thus a chirotope gives rise to the oriented bases of an oriented matroid. In this sense, (B0) is the nonempty axiom for bases and (B2) is the basis exchange property. \sum_{i=1}^m \lambda_i v_i =0 with \textstyle \lambda_i\in\mathbb{R} . Then the signed circuit \textstyle X=\{X^+,X^-\} has positive elements \textstyle X^+=\{v_i:\lambda_i>0\} and negative elements \textstyle X^-=\{v_i:\lambda_i . The set of all such \textstyle X forms the set of signed circuits of an oriented matroid on \textstyle E . Oriented matroids that can be realized this way are called representable. Given the same set of vectors E , we can define the same oriented matroid with a chirotope \chi:E^r\rightarrow\{-1,0,1\} . For any x_1,\dots,x_r\in E let \chi(x_1,\dots,x_r)=\operatorname{sgn}(\det(x_1,\dots,x_r)) where the right hand side of the equation is the sign of the determinant. Then \chi is the chirotope of the same oriented matroid on the set E . A real hyperplane arrangement \mathcal A = \{H_1, \ldots, H_n\} is a finite set of hyperplanes in \R^d , each containing the origin. By picking one side of each hyperplane to be the positive side, we obtain an arrangement of half-spaces. A half-space arrangement breaks down the ambient space into a finite collection of cells, each defined by which side of each hyperplane it lands on. That is, assign each point x\in \R^d to the signed set X = (X^+, X^-) with i \in X^+ if x is on the positive side of H_i and i\in X^- if x is on the negative side of H_i . This collection of signed sets defines the set of covectors of the oriented matroid, which are the vectors of the dual oriented matroid. Each rank-3 oriented matroid is equivalent to an arrangement of pseudolines, and each oriented matroid which is also uniform is equivalent to a simple pseudoline arrangement (where every 2 lines cross exactly once, and no 3 lines cross at the same point). Tools for dealing with one form can therefore be used to analyze its equivalent form for either study.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1373726662 under CC BY-SA 4.0; modifications have been made.