Signotopes with Few Plus Signs

Abstract

Arrangements of pseudohyperplanes are widely studied in computational geometry. A rich subclass of pseudohyerplane arrangements, which has gained more attention in recent years, is the so-called signotopes. Introduced by Manin and Schechtman (1989), the higher Bruhat order is a natural order of r-signotopes on n elements, with the signotope corresponding to the cyclic arrangement as the minimal element. In this paper, we show that the lower (and by symmetry upper) levels of this higher Bruhat order contain the same number of elements for a fixed difference n - r. This result implies that given the difference d = n - r and p, the number of one-element extensions of the cyclic arrangement of n hyperplanes in Rd with at most p points on one side of the extending pseudohyperplane does not depend on n, as long as n ≥ d + p.