Combinatorial Theory

In 1926, Levi showed that, for every pseudoline arrangement \(\mathcal{A}\) and two points in the plane, \(\mathcal{A}\) can be extended by a pseudoline which contains the two prescribed points. Later extendability was studied for arrangements of pseudohyperplanes in higher dimensions. While the extendability of an arrangement of proper hyperplanes in \(\mathbb{R}^d\) with a hyperplane containing \(d\) prescribed points is trivial, Richter-Gebert found an arrangement of pseudoplanes in \(\mathbb{R}^3\) which cannot be extended with a pseudoplane containing two particular prescribed points. In this article, we investigate the extendability of signotopes, which are a combinatorial structure encoding a rich subclass of pseudohyperplane arrangements. Our main result is that signotopes of odd rank are extendable in the sense that for two prescribed crossing points we can add an element containing them. Moreover, we conjecture that in all even ranks \(r \geq 4\) there exist signotopes that are not extendable for two prescribed points. Our conjecture is supported by examples in ranks \(4\), \(6\), \(8\), \(10\), and \(12\) that were found with a SAT-based approach.

Mathematics Subject Classifications: 68R05, 51H99

Keywords: Arrangement of pseudolines, extendability, Levi's extension lemma, arrangement of pseudohyperplanes, signotope, oriented matroid, partial order, Boolean satisfiability (SAT)