Simplicial cells in arrangements and mutations of oriented matroids (Q1108279)

The authors provide two proofs of a theorem of \textit{R. W. Shannon} [Geom. Dedicata 8, 179--187 (1979; Zbl 0423.51013)], one a modification of Shannon's proof, the other based on convexity arguments, that every arrangement of \(n\) hyperplanes in \(E^d\) has at least \(n\) simplicial cells, the bound being sharp for every \(n\) and \(d\). If \(M\) and \(M'\) denote two rank \(r\) uniform oriented matroids on \(E\), \(M\) and \(M'\) are mutants if they differ in exactly one simplex orientation. Then the base is called a mutation of \(M\) (and \(M'\)). This defines the mutation graph \(\mathcal G^{n,r}\) on the set of all rank \(r\) uniform oriented matroids on \(n\) elements: \(M\) and \(M'\) are joined by an edge in \(\mathcal G^{n,r}\) if and only if they are mutants. If \(\mathcal G^{n,r}_{\text{real}}\) is a subgraph of \(\mathcal G^{n,r}\) induced by the set of representable oriented matroids, then it is shown that \(\mathcal G^{n,r}_{\text{real}}\) is connected. Further the authors show that the concatenation operation of \textit{J. Lawrence} and \textit{L. Weinberg} [Linear Algebra Appl. 41, 183--200 (1981; Zbl 0517.05022)] can be used to generate a large class of arrangements of hyperplanes each with the minimal number of \(d\)-simplices. Shannon's ``cyclic arrangements'' are obtained as a special case. \textit{M. Las Vergnas} [J. Comb. Theory, Ser. B 29, 231--243 (1980; Zbl 0443.05026)] conjectured that every loopless oriented matroid has at least one acyclic reorientation with exactly \(r\) extreme points. In a theorem of Shannon's -- let \(M\) be a representable rank \(r\) oriented matroid on \(n\) elements without loops or parallel elements, then there exist at least \(n\) acyclic reorientations of \(M\), each with exactly \(r\) extreme points -- the above raises the question whether ``representable'' could be dropped from the statement. \textit{B. Grünbaum} [Arrangements and spreads. Providence, R. I.: AMS (1972; Zbl 0249.50011)] answered positively for \(r\le 3\); the authors show the answer is negative for \(r\ge 4\). This yields a new proof of the non-polytopality of \(M^9_{963}\), the smallest non-polytopal matroid sphere. The paper ends with a series of open questions.