×

The axiomatization of affine oriented matroids reassessed. (English) Zbl 1391.52034

The main aim of the paper is to provide a correct proof of Karlander’s axiomatization of affine oriented matroids. Before we formulate the main result, we need to recall some basics on oriented matorids (these objects can be considered as a combinatorial abstraction of real hyperplane arrangements).
Let \(E\) be a finite set. A signed subset \(X\) of \(E\) is a member of \(\{+,-,0\}^{E}\). Every signed subset \(X\) can be identified with an ordered pair \((X^{+},X^{-})\), according to the sign. Let \(X,Y\) be signed subsets of \(E\). Then \(\bar{X} = X^{+} \cap X^{-}\) is the support of \(X\). The composition \(X \circ Y\) of \(X,Y\) is defined by \((X\circ Y)_{e} = X_{e}\) if \(X_{e} \neq 0\) or \(Y_{e}\) otherwise. The separation set \(S(X,Y)\) of \(X,Y\) is defined by \[ S(X,Y) = (X^{+} \cap Y^{-}) \cup (X^{-} \cap Y^{+}). \] Let \(\mathcal{O}\) be an oriented matroid on \(E\) and fix \(g \in E\). Let \(g^{+}\) be the signed subset \((\{g\},0)\), then the set \(\mathcal{O}_{g^{+}}\) consists of those covectors in \(\mathcal{O}\) whose sign at \(g\) is \(+\).
Definition 1. Let \(E\) be a finite set. A set \(\mathcal{W}\) of signed subsets of \(E\) is an affine oriented matroid if and only if there is an oriented matroid \(\mathcal{O}\) on \(E\) such that \(\mathcal{W} = \mathcal{O}_{g^{+}}(E \setminus \{g\})\).
Definition 2. Let \(E\) be a finite set. For \(X,Y \in \{+,-,0\}^{E}\) with \(\bar{X} = \bar{Y}\) and \(X \neq Y\) we define
i)
the \(e\)-th elimination set of \(X\) and \(Y\) for some \(e \in S(X,Y)\) by \[ I_{e}(X,Y) = \{V \in \{+,-,0\}^{E} : \bar{V} \subseteq \bar{X} \setminus \{e\} \text{ and } V_{f} = X_{f} \text{ for all } f \notin S(X,Y)\}. \]
ii)
the elimination set of \(X\) and \(Y\) by \[ I(X,Y) = \bigcup_{e \in S(X,Y)} I_{e}(X,Y). \]
Definition 3. Let \(E\) be a finite set and \(X,Y\) be signed subsets of \(E\). Then \(X+Y\) is given by \((X+Y)_{e} = 0\) if \(e \in S(X,Y)\) or \((X \circ Y)_{e}\) otherwise.
Definition 4. Let \(E\) be a finite set and \(\mathcal{W} \subseteq \{+,-,0\}^{E}\). Then
i)
\(\text{Sym}(\mathcal{W}) = \{V \in \{+,-,0\}^{E} : \pm V \in \mathcal{W}\},\)
ii)
\(\text{Asym}(\mathcal{W}) = \{V \in \{+,-,0\}^{E} : V \in \mathcal{W}, -V \notin \mathcal{W} \},\)
iii)
\(\mathcal{P}(\mathcal{W}) = \{X + (-Y): X,Y \in \text{Asym}(\mathcal{W}), \bar{X} = \bar{Y} \text{ and } I(X,-Y) \cap \mathcal{W} = I(-X,Y) \cap \mathcal{W} = \emptyset\}.\)
Now we are ready to present the main result of the paper (the idea is due to Karlander).
Main Theorem. A set \(\mathcal{W} \subseteq \{+,-,0\}^{E}\) is an affine oriented matroid if and only if \(\mathcal{W}\) satisfies the following:
A1)
if \(X,Y \in \mathcal{W}\), then \(X \circ (\pm Y) \in \mathcal{W}\),
A2)
if \(X,Y \in \mathcal{W}\) with \(\bar{X} = \bar{Y}\), then \(I_{e}(X,Y) \cap \mathcal{W} \neq \emptyset\) for all \(e \in S(X,Y)\),
A3)
\(\mathcal{P}(\mathcal{W}) \circ \mathcal{W} \subseteq \mathcal{W}\).

MSC:

52C40 Oriented matroids in discrete geometry
52C35 Arrangements of points, flats, hyperplanes (aspects of discrete geometry)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bandelt, H.-J, et al., COMs: Complexes of oriented matroids. J. Combin. Theory Ser. A (2018). https://doi.org/10.1016/j.jcta.2018.01.002 · Zbl 1381.05008
[2] Björner, A., Las Vergnas, M., Sturmfels, B., White, N., Ziegler, G.M.: Oriented Matroids. Cambridge Univ. Press, Cambridge (1993) · Zbl 0773.52001
[3] Björner, A.: Subspace arrangements. First European Congress of Mathematics, vol. 1 (Paris 1992) pp. 321-370. Birkhäuser, Basel (1994) · Zbl 0844.52008
[4] Heinz, G.: The concept of cutting vectors for vector systems in the Euclidean plane. Contrib. Algebra Geom. 41(1), 181-193 (2000) · Zbl 0953.52011
[5] Karlander, J.: A characterization of affine sign vector systems. In: Zero-One Matrices Matroids and Characterization Problems, pp. 67-91. Ph.D. Thesis KTH Stockholm (1992)
[6] Ziegler, G.: What is a complex matroid? Discrete Comput. Geom. 10(1), 313-348 (1993) · Zbl 0782.52005 · doi:10.1007/BF02573983
[7] http://www.emis.de/journals/SLC/wpapers/s34stockholm_des.pdf
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.