Vapnik-Chervonenkis dimension and (pseudo-)hyperplane arrangements (Q1338464)

This paper investigates combinatorial abstractions of simple arrangements of hyperplanes in the following way. Let \({\mathcal R}\) be a family of subsets of a finite set \(X\). Then \((X,{\mathcal R})\) is called a range space, and the maximum cardinality of \(Y\in X\) such that \(\{R\cap Y\mid R\in{\mathcal R}\}= 2^ Y\) is called its VC-dimension. It turns out that the range space \((X,{\mathcal R})\) of VC-dimension \(d\) with maximum cardinality of \({\mathcal R}\) corresponds to the set of (full dimensional) cells of a simple arrangement of oriented pseudo-hyperplanes in affine \(d\)-space if and only if the number of ranges \(R\in {\mathcal R}\) for which also \(X-R\in {\mathcal R}\) has a certain value. Such range spaces are called pseudogeometric and are also characterized in different ways. The maximum range spaces of given VC-dimension with \(X-R\in {\mathcal R}\) for each \(R\in {\mathcal R}\) correspond to simple arrangements of pseudohemispheres (i.e. uniform oriented matroids). Thus a new approach to oriented matroids is obtained.