Arnau Padrol
email: arnau.padrol@ub.edu

Eva Philippe
email: eva.philippe@imj-prg.fr

B Arnau

Sweeps, Polytopes, Oriented Matroids, and Allowable Graphs of Permutations

Keywords: Allowable sequences of permutations, oriented matroids, polytopes, sweep algorithms, monotone path polytopes, generalized Baues problem, permutahedra Mathematics Subject Classification 52B05, 52B11, 52B12, 52B22, 52B40, 52C35, 52C40, 05B35

A sweep of a point configuration is any ordered partition induced by a linear functional. Posets of sweeps of planar point configurations were formalized and abstracted by Goodman and Pollack under the theory of allowable sequences of permutations. We introduce two generalizations that model posets of sweeps of higher dimensional configurations. Sweeps of a point configuration are in bijection with faces of an associated sweep polytope. Mimicking the fact that sweep polytopes are projections of permutahedra, we define sweep oriented matroids as strong maps of the braid oriented matroid. Allowable sequences are then the sweep oriented matroids of rank 2, and many of their properties extend to higher rank. We show strong ties between sweep oriented matroids and both modular hyperplanes and Dilworth truncations from (unoriented) matroid theory. Pseudo-sweeps are a generalization of sweeps in which the sweeping hyperplane is allowed to slightly change direction, and that can be extended to arbitrary oriented matroids in terms of cellular strings. We prove that for sweepable oriented matroids, sweep oriented matroids provide a sphere that is a deformation retract of the poset of pseudo-sweeps. This generalizes a property of sweep polytopes (which can be interpreted as monotone path polytopes of zonotopes), and solves a special case of the strong Generalized Baues Problem for cellular strings. A second generalization are allowable graphs of permutations: symmetric sets of permutations

Introduction

It is very natural to order a point configuration by the values of a linear functional, and it is not surprising that applications abound in discrete and combinatorial geometry. For example, this is the core of sweep algorithms, a central paradigm in computational geometry (see [START_REF] De Berg | Computational Geometry, Algorithms and Applications[END_REF]Section 2.1]). The simplex methods for linear programming visit vertices of a convex polytope in such a linear order (see for example [START_REF] Matoušek | Understanding and using linear programming (universitext)[END_REF]). Moreover, these orderings are precisely those inducing the Bruggesser-Mani line shellings in the polar polytope [START_REF] Bruggesser | Shellable decompositions of cells and spheres[END_REF] (see [START_REF] Ziegler | Lectures on Polytopes[END_REF]Lec. 8]).

The set of all linear orderings of a planar point configuration was already studied by Perrin in 1882 [START_REF] Perrin | Sur le problème des aspects[END_REF]. This was a precursor to the theory of allowable sequences, introduced and developed by Goodman and Pollack [START_REF] Goodman | On the combinatorial classification of nondegenerate configurations in the plane[END_REF][START_REF] Goodman | Proof of Grünbaum's conjecture on the stretchability of certain arrangements of pseudolines[END_REF][START_REF] Goodman | A theorem of ordered duality[END_REF][START_REF] Goodman | Semispaces of configurations, cell complexes of arrangements[END_REF][START_REF] Goodman | Allowable sequences and order types in discrete and computational geometry[END_REF]. The idea is the following. Given a configuration A of n points in the plane, for each generic vector u ∈ R 2 , we sweep the plane with a line orthogonal to u. The order in which the points are hit by the line gives rise to a permutation σ ∈ S n (see Fig. 1). As u rotates 180 • clockwise, we obtain a sequence of permutations in which:

(i) the move from a permutation to the next one consists of reversing one or more disjoint substrings; (ii) each pair i, j with 1 ≤ i < j ≤ n is reversed in exactly one move along the sequence.

An allowable sequence is a sequence of permutations from the identity to its reverse (σ, σ ∈ S n are reverse if σ (t) = σ (nt + 1) for all t) fulfilling these two conditions. Contrary to Perrin's claim, Goodman and Pollack showed that there are unrealizable Fig. 1 A segment of an allowable sequence. The sweeps between two consecutive permutations in the sequence correspond to ordered partitions allowable sequences [START_REF] Goodman | On the combinatorial classification of nondegenerate configurations in the plane[END_REF]Fig. 3 and Thm. 3.1], that is, that do not arise from a point configuration with this construction (c.f. Fig. 10). Allowable sequences are hence purely combinatorial objects abstracting geometric properties of planar point configurations. They are closely related to pseudoline arrangements and oriented matroids (see [START_REF] Björner | Oriented Matroids, Encyclopedia of Mathematics and its Applications[END_REF]Sects. 1.10 & 6.4]), although their combinatorial structure is in some senses easier to grasp and manipulate. In particular, in the simple case (where consecutive permutations differ by a transposition), allowable sequences are in correspondence with reduced decompositions of the reverse of the identity and maximal chains in the weak Bruhat order of S n , see [START_REF] Björner | Oriented Matroids, Encyclopedia of Mathematics and its Applications[END_REF]Sec. 6.4], as well as with (minimal primitive) sorting networks [START_REF] Knuth | The Art of Computer Programming[END_REF]Sec. 5.3.4]. This has allowed for their complete enumeration [START_REF] Edelman | Balanced tableaux[END_REF][START_REF] Stanley | On the number of reduced decompositions of elements of Coxeter groups[END_REF], as well as the study of uniform random instances [START_REF] Angel | The local limit of random sorting networks[END_REF][START_REF] Angel | Random sorting networks[END_REF][START_REF] Dauvergne | The Archimedean limit of random sorting networks[END_REF].

They turned out to be a very effective tool to study problems of geometric combinatorics in the plane, used for example to prove Ungar's theorem (a configuration of 2n points not all on a same line determines at least 2n slopes) [START_REF] Ungar | 2N noncollinear points determine at least 2N directions[END_REF], to decide the stretchability of arrangements of at most eight pseudolines [START_REF] Goodman | Proof of Grünbaum's conjecture on the stretchability of certain arrangements of pseudolines[END_REF], or to estimate the number of k-sets and (≤ k)-sets [START_REF] Alon | The number of small semispaces of a finite set of points in the plane[END_REF][START_REF] Lovász | Convex quadrilaterals and k-sets[END_REF][START_REF] Welzl | More on k-sets of finite sets in the plane[END_REF]. See [START_REF] Goodman | Allowable sequences and order types in discrete and computational geometry[END_REF]Ch. V] and [START_REF] Felsner | Geometric graphs and arrangements, Some chapters from combinatorial geometry[END_REF]Ch. 6] for some of their applications.

The construction detailed above extends naturally to any higher dimensional point configuration A ∈ R d× [n] . Every vector u ∈ R d defines a sweep, which is the ordered partition of [n] in which the points of A are met when sweeping with a hyperplane in direction u. Goodman and Pollack already observed that sweeps induce a complex on the unit sphere S d-1 , "which has not yet been fully investigated" [START_REF] Goodman | Allowable sequences and order types in discrete and computational geometry[END_REF]after Def. 2.3]. This was further explored by Edelman [START_REF] Edelman | Ordering points by linear functionals[END_REF] and Stanley [START_REF] Stanley | Valid orderings of real hyperplane arrangements[END_REF] who, in particular, presented a tight upper bound for the number of sweeping orders of a d-dimensional configuration of n points.

Ordered by refinement, the poset of sweeps ( A) is isomorphic to the face poset of a polyhedral fan generated by a hyperplane arrangement SH( A), called the valid order arrangement by Stanley in a polar formulation [START_REF] Stanley | Valid orderings of real hyperplane arrangements[END_REF]. As we discuss in Sect. 2.3, this is the normal fan of a zonotope: the sweep polytope S P( A) (mentionned under the name of shellotope by Gritzmann and Sturmfels in [START_REF] Gritzmann | Minkowski addition of polytopes: computational complexity and applications to Gröbner bases[END_REF]).

Posets of sweeps of point configurations are the high-dimensional analogue of realizable allowable sequences. However, there is no purely combinatorial description of these objects. Indeed, Hoffmann and Merckx recently adapted the classical Universality Theorem for oriented matroids by Mnëv [START_REF] Mnëv | The universality theorems on the classification problem of configuration varieties and convex polytopes varieties[END_REF] to give a Universality Theorem for allowable sequences [START_REF] Hoffmann | A universality theorem for allowable sequences with applications[END_REF]. This shows that already in the plane the problem of deciding whether an allowable sequence arises from a point configuration is very hard (equivalent to the "existential theory of the reals", and in particular NP-hard).

Our main goal is to give a purely combinatorial high-dimensional generalization of allowable sequences that abstracts and encompasses the posets of sweeps of point configurations. We present two strongly related approaches with two levels of generality ( sweep oriented matroids and sweep acycloids). As we will see, the objects that we introduce fill a gap connecting several topics studied by different communities, providing a new and unified point of view. We also hope that, beside their intrinsic interest, having a purely combinatorial framework without the rigid constraints of realizability will open the door to new approaches to problems on discrete and combinatorial geometry, as happened in the two-dimensional case.

Our starting point are sweep polytopes. We report alternative constructions that highlight different points of view. On the one hand, sweep polytopes are affine projections of permutahedra. The n-permutahedron P n ⊂ R d is a classical polytope whose normal fan is the braid arrangement B n . Up to translation, every affine projection of a permutahedron is a sweep polytope, which gives a natural combinatorial interpretation of permutahedral shadows. Moreover, sweep polytopes can be realized as fiber polytopes, and in particular as monotone path polytopes of zonotopes [START_REF] Edelman | Ordering points by linear functionals[END_REF]Sec. 5]. These are polytopes whose vertices encode the parametric simplex paths induced by a linear functional [START_REF] Billera | Cellular strings on polytopes[END_REF][START_REF] Billera | Fiber polytopes[END_REF]. Conversely, every monotone path polytope of a zonotope is a sweep polytope (under mild technical conditions, see Proposition 2.10). This interpretation of sweep polytopes appears in the study of pivot rules in linear programming [START_REF] Black | The polyhedral geometry of pivot rules and monotone paths[END_REF].

Moreover, this construction naturally reveals a decomposition of sweep polytopes as Minkowski sums of k-set polytopes [START_REF] Andrzejak | In between k-sets, j-facets, and i-faces: (i, j)-partitions[END_REF][START_REF] Edelsbrunner | Cutting dense point sets in half[END_REF] (see Remark 2.9). After the appearance of the first version of this article, most of these constructions have been generalized to lineup polytopes, which encode prefixes of sweeps and are relevant for the 1-body N -representability problem in quantum physics, see [START_REF] Castillo | An effective solution to convex 1-body N -representability[END_REF] and references therein.

Inspired by the characterization of sweep polytopes as permutahedral shadows, in Sect. [START_REF] Alon | The number of small semispaces of a finite set of points in the plane[END_REF] we define sweep oriented matroids as strong maps of the oriented matroid of the braid arrangement. The strong link between allowable sequences, oriented matroids of rank 3, and arrangements of pseudolines is well documented in [START_REF] Björner | Oriented Matroids, Encyclopedia of Mathematics and its Applications[END_REF]Sects. 1.10 & 6.4] and explained in terms of big and little oriented matroids. These concepts extend to high dimensions too: each sweep oriented matroid of rank r determines a little and a big oriented matroid of rank r +1 (Theorem 4.1 and Leema 4.4). For sweep oriented matroids of rank 2, which are equivalent to allowable sequences, we recover the original definitions. In particular, in the realizable case, the little oriented matroid is the standard oriented matroid associated to the point configuration.

We show that, up to isomorphism, big oriented matroids are characterized by having a tight modular hyperplane (Theorem 4.9). Modular flats of matroids were introduced by Stanley [START_REF] Stanley | Modular elements of geometric lattices[END_REF] and play a structural role for matroid constructions [START_REF] Brylawski | Modular constructions for combinatorial geometries[END_REF]. We call a modular hyperplane tight if it is no longer modular after the deletion of one of its elements. The operation that determines the big oriented matroid from its sweep oriented matroid extends to all oriented matroids equipped with certain decorations (Corollary 4.10), and can be seen as an oriented matroid version of [START_REF] Bonin | Extending a matroid by a cocircuit[END_REF]Thm. 2.1].

We extend the bounds from [START_REF] Edelman | Ordering points by linear functionals[END_REF][START_REF] Stanley | Valid orderings of real hyperplane arrangements[END_REF] to the non-realizable case (Theorem 5.6). For this, we show in Sect. 5 that, at the level of the underlying unoriented matroids, the lattice of flats of a sweep oriented matroid is (a weak map of) the first Dilworth truncation of the lattice of flats of the little oriented matroid (Theorem 5.2). When one removes all the atoms from a geometric lattice, the resulting poset is no longer a geometric lattice. The first Dilworth truncation is a lattice obtained by adding the necessary joins in the most generic way to obtain a geometric lattice [START_REF] Brylawski | Constructions, Theory of Matroids[END_REF][START_REF] Dilworth | Dependence relations in a semi-modular lattice[END_REF]. We can therefore view sufficiently generic sweep oriented matroids as an oriented version of the first Dilworth truncation of the associated little oriented matroid. Unfortunately, in contrast to rank 3, not every (little) oriented matroid can be extended to a big oriented matroid (Theorem 4.13). The question of characterizing oriented matroids admitting such an extension is open.

In Sect. 6, we discuss pseudo-sweeps, which correspond to sweeps in which the sweeping hyperplane is allowed to change direction (in a controlled monotonous way). Whereas sweeps of a point configuration correspond to the parametric (coherent) monotone paths on an associated zonotope, pseudo-sweeps take into account all monotone paths. They admit a polar formulation in terms of galleries and cellular strings of pseudo-hyperplane arrangements, which extends to oriented matroids [START_REF] Björner | Essential chains and homotopy type of posets[END_REF]. This way, for every (little) oriented matroid, even those that cannot be extended to a big oriented matroid, one can define a poset of pseudo-sweeps. In general, an oriented matroid M can be the little oriented matroid of several sweep oriented matroids; each with a different associated poset of sweeps. They are all subposets of the poset of pseudo-sweeps of M. A classification of the cases when all pseudo-sweeps are actual sweeps is given in [START_REF] Edman | Zonotopes whose cellular strings are all coherent[END_REF].

There is a lot of literature concerning the graphs of pseudo-sweep permutations of oriented matroids. Cordovil and Moreira had shown that they are connected [START_REF] Cordovil | A homotopy theorem on oriented matroids[END_REF], extending to oriented matroids results that went back to Tits [START_REF] Tits | Le problème des mots dans les groupes de Coxeter[END_REF] (for reflection arrangements), Deligne [START_REF] Deligne | Les immeubles des groupes de tresses généralisés[END_REF] (for simplicial arrangements), and Salvetti [START_REF] Salvetti | Topology of the complement of real hyperplanes in C N[END_REF] (for realizable oriented matroids). More results concerning graphs of pseudo-sweeps can be found in [START_REF] Athanasiadis | Monotone paths on zonotopes and oriented matroids[END_REF][START_REF] Reiner | Diameter of graphs of reduced words and galleries[END_REF].

The topology of the posets of pseudo-sweeps has been extensively studied as a special case of the generalized Baues problem [START_REF] Billera | Fiber polytopes[END_REF][START_REF] Reiner | The generalized Baues problem, New perspectives in algebraic combinatorics[END_REF]. Without the trivial sweep, their order complexes have the homotopy type of, but in general are not homeomorphic to, a sphere. In the realizable case, Billera, Kapranov, and Sturmfels proved that the poset of sweeps is a strong deformation retract of the poset of pseudo-sweeps [START_REF] Billera | Cellular strings on polytopes[END_REF]. Their proof uses strongly the geometry of the fiber polytope construction. Björner [START_REF] Björner | Essential chains and homotopy type of posets[END_REF] and Athanasiadis, Edelman, and Reiner [START_REF] Athanasiadis | Monotone paths on polytopes[END_REF] found combinatorial proofs that extend to general oriented matroids, but only give the homotopy type. Nevertheless, Björner claims that it is "undoubtedly true" that even for unrealizable oriented matroids there must be a sphere to which the poset of pseudo-sweeps retracts [START_REF] Björner | Essential chains and homotopy type of posets[END_REF]below Thm. 2]. However, there were no explicit candidates for these spheres. For oriented matroids that are little oriented matroids, we show in Theorem 6.6 that any of the associated sweep oriented matroids can play this role. That is, that the poset of non-trivial sweeps (which is a sphere) is a strong deformation retract of the poset of non-trivial pseudosweeps of the little oriented matroid. This highlights the fact that sweep oriented matroids should be seen as combinatorial analogues of monotone path polytopes of zonotopes; that is, sweep polytopes. Unfortunately, the existence of oriented matroids that are not little oriented matroids leaves some cases where Björner's observation remains open.

In Sect. 7 we present a further generalization of sweep oriented matroids in terms of allowable graphs of permutations, which are closer to the original formulation of allowable sequences. Allowable graphs of permutations are graphs whose vertex sets are sets of permutations closed under taking reverses in which every pair of permutations is connected through a sequence of permutations fulfilling conditions (i) and (ii) above (plus some technical conditions when the moves are not simple). In the simple case, these are antipodal isometric subgraphs of the permutahedron. Translating back 123 to sign-vectors, we obtain sweep acycloids (Theorem 7.12), which have the structure of acycloids [START_REF] Handa | A characterization of oriented matroids in terms of topes[END_REF], also known as antipodal partial cubes [START_REF] Fukuda | Antipodal graphs and oriented matroids[END_REF]. Again, sweep acycloids (and thus allowable graphs of permutations) of rank 2 are equivalent to allowable sequences. Not every acycloid is an oriented matroid [START_REF] Handa | Topes of oriented matroids and related structures[END_REF]Sec. 7], but there are characterizations of those that are [START_REF] Da Silva | Axioms for maximal vectors of an oriented matroid: a combinatorial characterization of the regions determined by an arrangement of pseudohyperplanes[END_REF][START_REF] Handa | Topes of oriented matroids and related structures[END_REF][START_REF] Knauer | On tope graphs of complexes of oriented matroids[END_REF]. Since sweep acycloids that are oriented matroids are sweep oriented matroids (Corollary 7.18), these give alternative characterizations of sweep oriented matroids in terms of allowable graphs of permutations (Corollary 7.20). So far we could not find any example of a sweep acycloid that is not a sweep oriented matroid, and we leave this question as an open problem.

A Note Concerning the Terminology

The terms sweep and sweeping had already been used in the oriented matroids literature in the context of topological sweepings of affine oriented matroids and pseudohyperplane arrangements. These concepts should not be confused with the notions that we introduce in this paper.

The two colliding terminologies arise from the two classical dual geometric representations of realizable oriented matroids; namely, point configurations and hyperplane arrangements. Both give rise to a natural definition of sweep that generalizes to nonrealizable matroids.

On the one hand, our definition of sweep is meant to model sweeps of point configurations by parallel hyperplanes. Such a sweep induces an ordering of the points, which are the elements of the underlying oriented matroid. When this picture is polarized, the point configuration gives rise to a hyperplane arrangement, but the collection of sweeping hyperplanes becomes a point that travels in a linear direction (the associated sweep permutation records the order in which the point crosses the hyperplanes). This is the formulation studied by Edelman [START_REF] Edelman | Ordering points by linear functionals[END_REF] and Stanley [START_REF] Stanley | Valid orderings of real hyperplane arrangements[END_REF].

On the other hand, one can consider sweeps of hyperplane arrangements by parallel hyperplanes. Such a sweep induces an ordering of the vertices of the arrangement, which are the cocircuits of the underlying oriented matroid. This is the point of view of the literature on topological sweepings of pseudo-hyperplane arrangements and oriented matroids (see, for example, [17, 34, 37, 42, 55, p.172]), which concerns mostly the rank 3 case (pseudoline arrangements).

In rank 3, the two notions are strongly related. Indeed, the allowable sequence of a planar point configuration (which is a collection of sweeps in our terminology), can be interpreted as a topological sweep of the dual arrangement of lines. This correspondence exists in rank 3 but completely fails in higher rank, as it only works because in an oriented matroid of rank 3 the lines (flats of rank 2) coincide with the hyperplanes (flats of corank 1).

It is worth to note that in this second setup there exist other approaches to generalize allowable sequences to higher dimensions. For example, the signotopes described in [START_REF] Felsner | Sweeps, arrangements and signotopes[END_REF] (see also [START_REF] Felsner | Geometric graphs and arrangements, Some chapters from combinatorial geometry[END_REF]). These are strongly related to higher Bruhat orders [START_REF] Manin | Arrangements of hyperplanes, higher braid groups and higher Bruhat orders[END_REF] and singleelement extensions of cyclic hyperplane arrangements [START_REF] Felsner | Zonotopes associated with higher Bruhat orders[END_REF][START_REF] Ziegler | Higher Bruhat orders and cyclic hyperplane arrangements[END_REF]. However, as these generalizations are meant to model (topological) sweeps of hyperplane arrangements with a (pseudo) hyperplane, they do not cover the spherical complexes that Goodman

123

and Pollack alluded to in [START_REF] Goodman | Allowable sequences and order types in discrete and computational geometry[END_REF] as the natural way to generalize allowable sequences to higher dimensions.

Structure of this Document

This paper gravitates around the concept of sweep oriented matroid, which lies in the intersection of the theories of allowable sequences, valid order arrangements, and the generalized Baues problem for cellular strings. Our hope is to provide a unified reference that reflects all these connections. To this end, we give a broad overview of the topic, as we expect readers with diverse backgrounds and motivations to be interested in different aspects. In particular, most of the sections can be read independently.

Section 2 serves as an introduction and focuses in the realizable case. We present polytopal constructions that serve as motivation for the upcoming definitions. Sweep oriented matroids are defined in Sect. 3. In Sect. 4 we show how the structural results on allowable sequences from [START_REF] Björner | Oriented Matroids, Encyclopedia of Mathematics and its Applications[END_REF] generalize to sweep oriented matroids of arbitrary rank. Section 5 demonstrates that the results in [START_REF] Edelman | Ordering points by linear functionals[END_REF][START_REF] Stanley | Valid orderings of real hyperplane arrangements[END_REF] do not require realizability. Section 6 depicts sweep oriented matroids as highlighted spheres inside the poset of cellular strings of oriented matroids whose existence was conjectured by [START_REF] Björner | Essential chains and homotopy type of posets[END_REF]. A presentation in terms of permutations, akin to Goodman and Pollack's original formulation of allowable sequences [START_REF] Goodman | Allowable sequences and order types in discrete and computational geometry[END_REF], is given in Sect. 7 under the name of allowable graphs of permutations.

We end by discussing some open problems and further directions of research in Sect. 8.

Sweeps and Sweep Polytopes

Sweeps of Point Configurations

For any integer n, we use [n] to denote the set {1, . . . , n}, S n to denote the set of all permutations of [n], and [n] 2 = (i, j) 1 ≤ i < j ≤ n to denote the set of nonrepeating sorted pairs of elements of [n]. An ordered partition of [n] is an ordered collection of non-empty disjoint subsets (I 1 , . . . , I l ) whose union is [n]. Ordered partitions where all parts are singletons are identified with permutations. They are the maximal elements in the refinement order: we say that J = (J 1 , . . . , J l ) refines I = (I 1 , . . . , I k ), noted J I , if each I i is the union of some consecutive J j 's. In some proofs, it will be more comfortable to think of an ordered partition I as the surjection p

I from [n] to [l] such that I k = p -1 I ({k}) for all 1 ≤ k ≤ l.
Note that for a permutation σ , the ordered partition I = ({σ (1)}, . . . , {σ (n)}) corresponds to the bijection p I = σ -1 .

We always consider R d as an Euclidean space, equipped with the usual orthogonal scalar product • , • . A point configuration is an ordered sequence A = (a 1 , . . . , a n ) ∈ R d× [n] of points in R d indexed by [n]. We do not require the points to be distinct, although it will be often convenient to make this simplification. For u ∈ R d , consider the linear form u , • : R d → R sending x to u , x . The sweep of A associated to u is the ordered partition I u = (I 1 , . . . , I l ) of [n] that verifies u , a i = u , a j for all i, j in a same part I k , and u , a i < u , a j if i ∈ I r , j ∈ I s with r < s. In particular, u , a i ≤ u , a j if and only if p I u (i) ≤ p I u ( j). Note that the partition associated to the linear form 0 is the trivial sweep ([n]).

The poset of sweeps of A, denoted ( A), is the set of all sweeps ordered by refinement. Its maximal elements are permutations whenever A does not contain repeated points. We will often assume that this is the case, as we can always identify repeated points. Under this assumption, we denote by ( A) ⊆ S n the set of its maximal elements, the sweep permutations of A. If there are repeated points, we will still call the maximal elements sweep permutations for brevity.

Sweeps induce an equivalence relation on R d , where u ∼ v if they give the same sweep. Its equivalence classes are the cells of the polyhedral fan induced by the sweep hyperplane arrangement SH( A); the arrangement of the linear hyperplanes u ∈ R d u , a i = u , a j for all (i, j) ∈ [n] 2 . Note that the face poset of SH( A) is isomorphic to the poset ( A), with a bijection that sends each cell C of SH( A) to the sweep I in ( A) that verifies that the relative interior of C is u ∈ R d I u = I . In particular, the cones of dimension d of SH( A) are indexed by the sweep permutations in ( A).

We will see in Sect. 2.3 that SH( A) is the normal fan of a polytope: the sweep polytope of A, denoted by S P( A). Thus, the poset of sweeps ( A) enlarged with a top element is isomorphic to the poset opposite to the face lattice of S P( A), and is in particular a lattice. This provides a natural labeling of the faces of S P( A) by sweeps. In particular, the vertices of S P( A) are labeled by the sweep permutations in ( A).

The identification of sweeps with faces of S P( A) reflects the inherent topological structure of the poset of sweeps. This can be made precise in terms of its order complex. The order complex (P) of a poset P is the simplicial complex whose simplices are the chains of P, see [START_REF] Björner | Topological Methods[END_REF] or [START_REF] Björner | Oriented Matroids, Encyclopedia of Mathematics and its Applications[END_REF]Sec. 4.7] for some background. In our case, the order complex of ( A) ([n]), the poset of sweeps without the trivial sweep, is just the barycentric subdivision of the boundary of S P( A). We will implicitly identify ( A) with ( A) ([n]) whenever we make topological statements about posets of sweeps.

Examples

Before providing constructions for this polytope, we will present two particular examples.

The Simplex and the Permutahedron

If A n is the set of vertices of a standard (n -1)-simplex n-1 , i.e. the points a i are the canonical basis vectors e i in R n , then SH( A n ) is the braid arrangement B n consisting of the hyperplanes u u ju i = 0 for all 1 ≤ i < j ≤ n, the set of sweep permutations is the whole symmetric group ( A n ) = S n , and the poset of sweeps ( A n ) is the poset of all ordered partitions of [n]. Likewise for any set A of affinely independent points, up to affine transformation of the braid arrangement. The braid arrangement B n is the normal fan of a polytope, the n-permutahedron P n . It is usually defined as the convex hull of the points (σ (1), . . . , σ (n)) ∈ R n for all σ ∈ S n (see [START_REF] Ziegler | Lectures on Polytopes[END_REF]Ex 0.10] or [START_REF] Björner | Oriented Matroids, Encyclopedia of Mathematics and its Applications[END_REF]Ex. 2.2.5]). Thus, it lives in the (n -1)-dimensional affine subspace of the sum of coordinates constant equal to n(n+1)

2 . It can be described as the zonotope:

P n = n+1 2 1 n + 1≤i< j≤n - e i -e j 2 , e i -e j 2 , ( 1
)
where

1 n =
n i=1 e i is the all-ones vector and [ p, q] ⊂ R d denotes the segment between the points p and q, see [START_REF] Ziegler | Lectures on Polytopes[END_REF]Ex. 7.15].

The sweep polytope S P( A) associated to the standard simplex is the translation of P n centered at the origin. We will denote this translated permutahedron by P n

P n = 1≤i< j≤n - e i -e j 2 , e i -e j 2 (2)
to distinguish it from the standard realization. See Figs. 2 and3 for the cases n = 3, 4.

123 . By symmetry, the first half determines the whole permutation. This way, they can be represented by signed permutations of [n], where -k is denoted by k. We use this notation in Figs. 4 and5.

They are the elements of the Coxeter group of type B, also called hyperoctahedral group. See [START_REF] Björner | Combinatorics of Coxeter Groups[END_REF]Section 8.1] for more details on the combinatorics of this group. The sweep hyperplane arrangement SH(B n ) is the Coxeter arrangement of type B, which consists of the hyperplanes u ∈ R n u i ± u j = 0 for all 1 ≤ i < j ≤ n and u ∈ R n u i = 0 for all 1 ≤ i ≤ n. The sweeps are the centrally symmetric ordered partitions of [±n]. This complex is known as the Coxeter complex of type B, see [START_REF] Björner | Oriented Matroids, Encyclopedia of Mathematics and its Applications[END_REF]Sec. 2.3(c)]. See Fig. 4 for an example.

The associated sweep polytope is the Coxeter permutahedron of type B, also known as the Coxeterhedron of type B [START_REF] Reiner | Coxeter-associahedra[END_REF]. See Figs. 4 and5 for pictures in dimensions 2 and 3.

Sweeping with Polynomial Functions

Sweep polytopes can also be used to model sweeps of a point configuration A = (a 1 , . . . , a n ) ∈ R d× [n] by polynomial functions p ∈ R[x 1 , . . . , x d ] of bounded degree. The polynomial sweep of A associated to p is the ordered partition of [n] induced by the ordered level sets of p on A.

Let M be the set of monomials of degree at most D on variables x 1 , . . . , x d . There are

|M| = D+d D elements in M. For a point v = (v 1 , . . . , v d ) ∈ R d and a monomial M ∈ M, denote by M(v) ∈ R the evaluation of M on the values x 1 = v 1 , . . . , x d = v d .
The Veronese mapping is defined by the map

χ : R d → R M v → (M(v)) M∈M .
Then, the polynomial sweep of A induced by the polynomial p = M∈M c M M exactly corresponds to the sweep of χ( A) induced by the linear functional c , • for c = (c M ) M∈M ∈ R M . In particular, the poset of sweeps of χ( A) coincides with the poset of polynomial sweeps of A induced by polynomials of degre at most D. Note that if d = 1, the image χ( A) is a standard cyclic polytope of dimension D with n vertices.

Variants of the Veronese mapping can be used for particular families of polynomial sweeps. For example, the embedding

(v 1 , . . . , v d ) → (v 1 , . . . , v d , v 2 1 + • • • + v 2 d )
onto the paraboloid models sweeps by families of concentric spheres.

Constructions for Sweep Polytopes

In what follows, we describe three approaches to construct the sweep polytope S P( A).

Recall that S P( A) is a polytope whose normal fan coincides with the sweep hyperplane arrangement SH( A), and whose face poset is opposite to the poset of sweeps ( A).

As a Zonotope

The most direct realization is as the Minkowski sum of the segments with directions the differences between the points of the configuration, which is (a translation of) the presentation of sweep polytopes given in [START_REF] Gritzmann | Minkowski addition of polytopes: computational complexity and applications to Gröbner bases[END_REF] (under the name of shellotopes).

Definition 2.1

The sweep polytope S P( A) associated to the configuration A = (a 1 , . . . , a n ) ∈ R d× [n] is the zonotope:

S P( A) = 1≤i< j≤n - a i -a j 2 , a i -a j 2 ⊂ R d .
The normal fan of a zonotope is the arrangement of the hyperplanes orthogonal to its generators, see for example [START_REF] Ziegler | The face lattice of hyperplane arrangements[END_REF]Sec. 2] and [START_REF] Ziegler | Lectures on Polytopes[END_REF]Thm. 7.16]. Applied to sweep polytopes, we directly get:

Proposition 2.2 The normal fan of S P( A) is the hyperplane arrangement SH( A).

As a Projection of the Permutahedron

Our second incarnation is as a projection of the (centered) permutahedron P n . For a configuration A of n points a 1 , . . . , a n in R d , let M A be the linear map

M A : R n → R d (3) e i → a i .
Then it follows from Definition 2.1 and the description of P n in (2) that:

Proposition 2.3 S P( A) = M A ( P n ).
Conversely, all affine images of permutahedra are sweep polytopes, up to translation. This provides a combinatorial interpretation, in terms of sweeps, of the face lattice of any affine projection of a permutahedron (a permutahedral shadow). Note that, given a linear map from P n to R d , there is a d-dimensional family of ways to extend it to a linear map from R n to R d . This amounts to the fact that point configurations related by a translation give rise to the same sweep polytope. Remark 2.5 Proposition 2.3 follows from the fact that Minkowski sums and linear projections commute. This can be exploited also with other decompositions of the permutahedron. For example, the permutahedron P n can be written as the Minkowski sum of the hypersimplices n,k = x ∈ [0, 1] n x i = k with k ranging from 1 to n -1 (see for example [START_REF] Postnikov | Permutohedra, associahedra, and beyond[END_REF]). Therefore, any sweep polytope can be expressed as a Minkowski sum of projections of hypersimplices. Projections of hypersimplices are studied under the name of k-set polytopes [START_REF] Andrzejak | In between k-sets, j-facets, and i-faces: (i, j)-partitions[END_REF][START_REF] Edelsbrunner | Cutting dense point sets in half[END_REF], which (up to homothety) can be described as the convex hull of the barycenters of all k-subsets of A, see [START_REF] Martínez-Sandoval | The convex dimension of hypergraphs and the hypersimplicial Van Kampen-Flores theorem[END_REF]. The sweep polytope of A is thus the Minkowski sum of its k-set polytopes, up to translation and homothety. In particular, because conv( A) = M A ( n,1 ), this shows that conv( A) is a Minkowski summand of S P( A). See Fig. 6 for an example. Another point of view on this Minkowski decomposition will be discussed in Remark 2.9.

As a Monotone Path Polytope

Fiber polytopes are certain polytopes associated to polytope projections. This construction was introduced by Billera and Sturmfels in [START_REF] Billera | Fiber polytopes[END_REF], generalizing the theory of Fig. 6 The sweep polytope S P(B 3 ) = P 3 as a Minkowski sum of the k-set polytopes of B 3 for k = 1, . . . , 5 secondary polytopes in a unified way that encompasses concepts such as monotone path polytopes, zonotopal tiling polytopes and secondary polytopes. We refer to [START_REF] Ziegler | Lectures on Polytopes[END_REF]Lec. 9] and [30, Sec. 9.1] for gentle introductions to the topic.

Consider polytopes P and Q related by a linear surjection π : P → Q. The fibers of π over Q form a polytope bundle y ∈ Q → π -1 ({ y}) whose Minkowski integral, after some normalization, is the fiber polytope ( P, π):

( P, π) = 1 vol( Q) Q π -1 ({ y})d y.
Fiber polytopes can also be described as a finite Minkowski sum. Namely,

( P, π) = 1 vol( Q) C∈ ( P,π ) vol(C) π -1 ({b C }),
where ( P, π) is the set of chambers: the subsets of Q of the form

C y = F face of P y∈π(F) π(F)
for y ∈ Q; and b C is the barycenter of the chamber C.

Note that ( P, π) lies in the fiber over the barycenter of Q:

( P, π) ⊂ π -1 1 vol( Q) Q y d y .
An important feature of fiber polytopes is that their face lattice is isomorphic to the poset of π -coherent subdivisions of Q (ordered by refinement), which are subdivisions of Q composed of images of faces of P that are coherently induced by the map π . We refer to the aforementioned sources for the details in the definitions. We are particularly interested in a special case of fiber polytopes: monotone path polytopes. They will give a new interpretation of sweep polytopes and provide motivation for the definition of pseudo-sweeps, that will be further explored in Sect. [START_REF] Andrzejak | In between k-sets, j-facets, and i-faces: (i, j)-partitions[END_REF].

If Q is one dimensional and P ⊂ R n , then π : P → Q is a linear form defined by a vector u ∈ R n via π(x) = u , x . For simplicity, assume that π is generic in the sense that it is not constant along any edge of P, and let p m and p M be the minimal and maximal vertices of P with respect to π . A πmonotone path is a path from p m to p M composed of edges of P along which π is always increasing. One way to obtain π -monotone paths is to consider some generic vector w orthogonal to u and consider Fig. 7 The zonotope Z( B2 ). Three fibers of the height function h are highlighted, representing a copy of the convex hull of B 2 , and of its 2-set and 3-set polytopes. The lower (red) path represents the coherent monotone path associated to the permutation ( 2, 1, 1, 2) (which can be read off the directions of the steps in the path). The upper (blue) path is a monotone path that is not coherent. It is associated to the permutation ( 1, 2, 1, 2), which is not a sweep permutation, but a pseudo-sweep permutation, see Sect. 6 the sequence of vertices of P that are extreme in the direction w + λu as λ ranges from -∞ to ∞ (see Fig. 7). These paths induce the finest π -coherent subdivisions of Q, and are known as parametric simplex paths in linear programming, where they play an important role as they are the paths followed by the shadow-vertex simplex method [START_REF] Borgwardt | The simplex method, Algorithms and Combinatorics: Study and Research Texts[END_REF][START_REF] Gass | The computational algorithm for the parametric objective function[END_REF].

More generally, a cellular string on P with respect to π is a sequence of faces F 1 , . . . , F k of P of dimension at least 1 such that p m ∈ F 1 , p M ∈ F k , and every two adjacent faces F i , F i+1 meet at a vertex p i such that π(x) ≤ π( p i ) ≤ π( y) for each x ∈ F i and y ∈ F i+1 . Such a cellular string is π -coherent if there is some (notnecessarily generic) vector w orthogonal to u such that these are the maximal faces of P maximized in a direction of the form w+λu. The fiber polytope ( P, π) is called the monotone path polytope of P and π . Its vertices are in one-to-one correspondence with the parametric π -monotone paths of P, and its faces are in correspondence with the π -coherent cellular strings.

Example 2.6 [START_REF] Billera | Fiber polytopes[END_REF]Ex. 5.4], see also [START_REF] Ziegler | Lectures on Polytopes[END_REF]Ex. 9.8]) Let n = [-1, 1] n be the ndimensional ±1-hypercube, and let s : R n → R be the linear form that sums the coordinates, i.e. the form s = 1 n , • induced by the all-ones vector. Then the fiber polytope ( n , s) = 2 n P n is (homothetic to) the (centered) permutahedron P n , and

n 2 n , s = P n .
The following central property of fiber polytopes will be key for our purposes. We need some extra notation. Let A = (a 1 , . . . , a n ) ∈ R d× [n] be a point configuration, and consider its homogenization Ā = ( ā1 , . . . , ān ) ∈ R (d+1)× [n] consisting of the vectors āi = (a i , 1). We define the zonotope Z( Ā) associated to A as the following Minkowski sum of centrally symmetric segments:

Z( Ā) = n i=1 [-āi , āi ].
Let h : R d+1 → R denote the map that returns the last coordinate of a point, that we call its height.

This gives us another point of view on sweep polytopes.

Proposition 2.8 For any point configuration

A we have n 2 Z( Ā), h = S P( A) × {0},

and hence S P( A) is affinely isomorphic to the monotone path polytope

Z( Ā), h . Proof The projection M Ā : R n → R d+1 that maps e i to āi = (a i , 1) is such that Z( Ā) = M Ā( n ) and s = h • M Ā,
where s is the linear form that sums the coordinates defined in Example 2.6. Hence, by Lemma 2.7 and Example 2.6 we have Remark 2.9 If we intersect Z( Ā) with the hyperplane of height equal to -n + 2, we obtain conv(-

Z( Ā), h = M Ā( ( n , s)) = M Ā( 2 n P n ). Now, P n lies in s -1 1 vol( n ) n yd y = s -1 (0 n ), and thus M Ā( 2 n P n ) lies in the kernel of h, which means that Z( Ā), h = 2 n M A ( P n ) × {0}.
n i=1 āi + 2 ā j , j ∈ [n]) = conv(- n i=1 a i + 2 A) × {-n + 2},
which is an embedding of a dilation of the convex hull of A in R d+1 . Similarly, for any k ∈ [n] the slice at height -n +2k is an embedding of a dilation of the projection of the hypersimplex n,k under the map M A . This is the k-set polytope of A, see Remark 2.5.

The fiber polytope realization reflects the decomposition of the sweep polytope as a sum of k-set polytopes.

Conversely, monotone path polytopes of zonotopes for nondegenerate functionals are sweep polytopes, up to normal equivalence. Two polytopes are called normally equivalent if they have the same normal fan, and normal equivalence obviously implies combinatorial equivalence. Proposition 2.10 Let Z ⊂ R d be a zonotope, π : R d → R a linear map, and Z π the face of Z minimizing π . Then the monotone path polytope (Z, π) is normally equivalent to the Minkowski sum of Z π with the sweep polytope S P( A), where A consists of the points 1 π(z i ) z i for the generators

z i of Z such that π(z i ) = 0. 123 Proof Let c, z 1 . . . , z m ∈ R d be such that Z = c + m i=1 [-z i , z i ] ⊂ R d .
Then Z is normally equivalent to any zonotope

Z = c + m i=1 [-λ i z i , λ i z i ],
where c is a vector in R d and the λ i are non-zero scalars.

Up to relabeling the z i , one can suppose that i π(z i ) = 0 = {n + 1, . . . , m} for a certain n ∈ {0, . . . , m}. Let Z 1 and Z 2 be the zonotopes:

Z 1 = n i=1 - 1 π(z i ) z i , 1 π(z i ) z i , Z 2 = m i=n+1 [-z i , z i ] .
Note that the face Z π is a translation of Z 2 .

Since Z is normally equivalent to the Minkowski sum Z 1 + Z 2 , we have that its monotone path polytope (Z, π) is normally equivalent to the monotone path polytope (Z 1 + Z 2 , π) by [START_REF] Mcmullen | Fibre tilings[END_REF]Cor. 4.4].

Moreover,

(Z 1 + Z 2 , π) = (Z 1 , π) + Z 2 because π(Z 2 ) = {0}, thus (Z 1 + Z 2 )∩π -1 ({y}) = Z 1 ∩π -1 ({y})+ Z 2 for any y ∈ R. If we denote the configuration of points a 1 = 1 π(z 1 ) z 1 , . . . , a n = 1 π(z n ) z n in R d by A, we have exactly s = π • M A and Z 1 = M A ( n ),
, π) = M A ( ( n , s)) = M A ( 2 n P n ) =

n S P( A). Hence (Z, π) is normally equivalent to the Minkowski sum S P( A) + Z π .

There is an alternative (but strongly related) way to construct sweep polytopes as fiber polytopes. It is not directly used in the sequel, but we present it in Appendix A for completeness.

Sweep Oriented Matroids

The goal of this section is to provide a purely combinatorial definition of posets of sweeps generalizing allowable sequences to higher dimensions. Since already in the plane not all allowable sequences arise from point configurations, it is clear that our definition has to go beyond the realizable case. We will do it in terms of oriented matroids, which do have enough expressive power to completely describe allowable sequences. However, to motivate our definition, we will start by discussing some oriented matroids associated to point configurations, inspired by [START_REF] Björner | Oriented Matroids, Encyclopedia of Mathematics and its Applications[END_REF]Sects. 1.10 & 6.4]. While we will introduce the basic definitions in oriented matroid theory, we refer the reader not familiar with the topic to the introduction in [START_REF] Ziegler | Lectures on Polytopes[END_REF]Lec. 6], and to the classical book [START_REF] Björner | Oriented Matroids, Encyclopedia of Mathematics and its Applications[END_REF] for a comprehensive source.

Basic Notions and Notation

There are several cryptomorphic approaches to oriented matroids. We will use the presentation in terms of the covector axioms, which describe oriented matroids in terms of collections of sign-vectors M ⊆ {+, -, 0} E , called covectors, labeled by a finite ground set E.

For X ∈ M and e ∈ E, X e denotes the value of X at the coordinate e. The opposite -X of X ∈ M is the sign-vector obtained by switching + and -in X ; that is, (-X ) e = -(X e ). For X , Y ∈ M, the composition of X and Y is the sign-vector

X • Y ∈ {+, -, 0} E such that (X • Y ) e = X e if X e = 0; and (X • Y ) e = Y e otherwise. The separation set of X and Y , denoted S(X , Y ), is the set of elements e ∈ E such that (X e , Y e ) ∈ {(+, -), (-, +)}. Definition 3.1 (cf. [17, Def. 4.1.1]) A collection of sign-vectors M ⊆ {+, -, 0} E
is the set of covectors of an oriented matroid if it satisfies the following axioms:

(V0) 0 ∈ M, (V1) X ∈ M implies -X ∈ M, (V2) X , Y ∈ M implies X • Y ∈ M, (V3) if X , Y ∈ M and e ∈ S(X , Y ) then there exists Z ∈ M such that Z e = 0 and Z f = (X • Y ) f for all f / ∈ S(X , Y ).
The set of covectors of an oriented matroid, with the product partial order induced by 0 ≺ +,componentwise, forms a poset. It has the structure of a lattice, called the big face lattice of the oriented matroid, if a top element 1 is adjoined. The rank of the oriented matroid is the length of the maximal chains in the poset of covectors. The minimal non-zero covectors are called cocircuits, and they determine the oriented matroid as every non-zero covector is a composition of cocircuits. The maximal covectors for this partial order are called the topes of the oriented matroid. They also determine the oriented matroid, as X is a covector of M if and only if X • T is a tope for every tope T . In fact, the tope-graph of M, whose vertices are the topes and whose edges are given by the covectors covered by exactly two topes, already determines the oriented matroid up to FL-isomorphism, see [START_REF] Björner | Hyperplane arrangements with a lattice of regions[END_REF]Theorem 6.14] and [START_REF] Björner | Oriented Matroids, Encyclopedia of Mathematics and its Applications[END_REF]Theorem 4.2.14].

There are several standard notions of oriented matroid isomorphism. By FLisomorphism, we mean the coarsest, induced by isomorphism of the big face lattices. FL-isomorphism, called just isomorphism in [START_REF] Finschi | Generation of oriented matroids-a graph theoretical approach[END_REF], is the equivalence relation induced by reorientation, relabeling, and introduction/deletion of loops and parallel elements.

To understand the concepts used in the definition of FL-isomorphism, we need some extra notation. For X ∈ {+, -, 0} E and F ⊆ E, we denote by -F X the signed vector Z such that: Z f = -X f for f ∈ F and Z e = X e for e ∈ E\F, which we call the reorientation of X on F. If M is an oriented matroid on the ground set E, its reorientation on F is the oriented matroid -F M with covectors -F X for X ∈ M. The support of a sign-vector X is X = e ∈ E X e = 0 . A loop is an element e ∈ E that does not belong to the support of any covector. Two elements e, f ∈ E are said to be parallel if X f = X e for all X ∈ M or X f = -X e for all X ∈ M. This defines an equivalence relation on E, whose equivalence classes are called parallelism classes.

123

The parallelism class of e ∈ E is denoted e. An oriented matroid is called simple if it does not contain loops or distinct parallel elements.

For X ∈ {+, -, 0} E and F ⊆ E, the restriction of X to F, denoted X F is the covector Z ∈ {+, -, 0} F such that Z f = X f for all f ∈ F. If M is an oriented matroid on the ground set E, the set X F X ∈ M forms an oriented matroid, denotedM F and called the restriction of M to F. The set X E\F X ∈ M, X f = 0 ∀ f ∈ F also forms an oriented matroid, denoted M/ F and called the contraction of M along F.

An oriented matroid is called acyclic if the all-positive sign-vector + n is a tope. The standard way to associate an oriented matroid to a real vector configuration [n] is to consider the set of covectors on the ground set [n] induced by the signs of the evaluations of linear functionals on the elements of V :

V = (v 1 , . . . , v n ) ∈ R d×
M(V ) = (sign( u , v 1 , . . . , sign( u , v n ) u ∈ R n ⊆ {+, -, 0} n , ( 4
)
where sign(x) =

⎧ ⎪ ⎨ ⎪ ⎩ + if x > 0 -if x < 0 0 if x = 0.
That is, to each linear oriented hyperplane, we record which vectors of the configuration lie on the hyperplane, and which lie at the positive and negative sides, respectively. The covectors M(V ) label the regions of the hyperplane arrangement H V consisting of the hyperplanes orthogonal to the vectors of V . Under this labeling, the big face lattice is consistent with the inclusion order of the regions, the topes labeling the maximal cells of the arrangement. Thus, the big face lattice on M(V ) is isomorphic to (the opposite of) the face lattice of the zonotope i∈[n] [0, v i ]. The rank of M(V ) coincides with the dimension of the linear hull of V . We will call this oriented matroid the oriented matroid associated to V . Oriented matroids that arise this way are called realizable. Note that even non-realizable oriented matroids can be geometrically realized by arrangements of pseudo-spheres, see [17, Sec. 1.4.1 & 5.2].

Three Realizable Oriented Matroids Associated to a Point Configuration

The construction above extends directly to affine point configurations, by considering evaluations of affine functionals instead. (Or, equivalently, linear functionals on the homogenization Ā.) Although this is the standard way to associate an oriented matroid to a point configuration A, we will call it the little oriented matroid of A, which is consistent with the notation in [START_REF] Björner | Oriented Matroids, Encyclopedia of Mathematics and its Applications[END_REF]Sect. 1.10] for planar configurations. This is to avoid confusion with the other alternative notions of oriented matroid associated to a point configuration that we will introduce. The big oriented matroid, which contains more information than the little oriented matroid, is also inspired by [START_REF] Björner | Oriented Matroids, Encyclopedia of Mathematics and its Applications[END_REF]Sect. 1.10]. We will prefer a more compact presentation, the sweep oriented matroid, which was not explicitly introduced there. [n] be a full-dimensional point configuration (i.e. its affine span is the whole space R d ):

Definition 3.2 Let

A = (a 1 , . . . , a n ) ∈ R d×
Fig. 8 A big oriented matroid (with collinearities indicated). The points in the upper line, which represents the line at infinity, give rise to a sweep oriented matroid, whereas the points below give rise to the associated little oriented matroid (i) The little oriented matroid of A, denoted M lit ( Ā), is the oriented matroid of rank d +1 with ground set [n] associated to the (d +1)-dimensional homogenized vector configuration Ā = ( ā1 , . . . , ān ) ∈ R (d+1)× [n] , where āi = (a i , 1) ∈ R d+1 . This is always an acyclic oriented matroid. (ii) The sweep oriented matroid of A, denoted M sw ( Ā), is the oriented matroid of rank d with ground set

[n] 2 = (i, j) 1 ≤ i < j ≤ n associated to the d-dimensional vector configuration a (i, j) = a j -a i (i, j) ∈ [n] 2 ∈ R d×( [n]
2 ) .

(iii) The big oriented matroid1 of A, denoted M big ( Ā), is the oriented matroid of rank d + 1 on the ground set [n] ∪ [n] 2 associated to the (d + 1)-dimensional vector configuration

Ā ∪ (a (i, j) , 0) (i, j) ∈ [n] 2 ∈ R (d+1)× [n]∪( [n] 2 ) .
Little, sweep and big oriented matroids obtained this way from a point configuration will be called realizable. In Sects. 3.3 and 4.1, we give definitions for abstract sweep, little and big oriented matroids not necessarily arising from point configurations. We explain below how these structures are related to each other and to the poset of sweeps and the set of sweep permutations.

For a sweep I = (I 1 , . . . , I l ) ∈ ( A), corresponding to the surjection p I : [n] → [l], we define the sign-vector X I ∈ {+, -, 0} ( [n] 2 ) such that

X I (i, j) = ⎧ ⎪ ⎨ ⎪ ⎩ + if p I (i) < p I ( j), -if p I (i) > p I ( j), 0 if p I (i) = p I ( j);
(5) Fig. 9 The vector configuration a [START_REF] Angel | The local limit of random sorting networks[END_REF][START_REF] Athanasiadis | Monotone paths on polytopes[END_REF] , a [START_REF] Angel | The local limit of random sorting networks[END_REF][START_REF] Alon | The number of small semispaces of a finite set of points in the plane[END_REF] , a [START_REF] Athanasiadis | Monotone paths on polytopes[END_REF][START_REF] Alon | The number of small semispaces of a finite set of points in the plane[END_REF] associated to the point configuration A 3 from Fig. 2.

The covectors associated to the regions of the sweep hyperplane are indicated by sign-vectors of length 3 containing the sign of the scalar product of a vector in the region with a [START_REF] Angel | The local limit of random sorting networks[END_REF][START_REF] Athanasiadis | Monotone paths on polytopes[END_REF] , a [START_REF] Angel | The local limit of random sorting networks[END_REF][START_REF] Alon | The number of small semispaces of a finite set of points in the plane[END_REF] , and a [START_REF] Athanasiadis | Monotone paths on polytopes[END_REF][START_REF] Alon | The number of small semispaces of a finite set of points in the plane[END_REF] , respectively. This should be compared with the labeling of the regions of the sweep hyperplane arrangement in terms of partitions in Fig. 2 for (i, j)

∈ [n] 2 . For example, if I is the sweep ({1, 3}, {2}), we have p I (1) = p I (3) = 1, p I (2) = 2,
and the corresponding covector on the ground set {(1, 2), (1, 3), (2, 3)} is X I = (+, 0, -). Compare Figs. 2 and9 to see other examples. As the figures illustrate, this map induces an isomorphism at the level of posets.

Lemma 3.3 The map I → X I induces a poset isomorphism between the poset of sweeps ( A) and the poset of covectors of the sweep oriented matroid M sw ( Ā).

In particular, ( A)∪ 1, where 1 is an additional top element, is isomorphic to the big face lattice of M sw ( Ā), which is the opposite of the face lattice of the zonotope S P( A) (cf. [START_REF] Ziegler | Lectures on Polytopes[END_REF]Cor. 7.17]).

Proof Let I be an ordered partition in ( A), with corresponding surjection p I , and associated to the linear form u ∈ R d . This linear form u is also associated to a covector X of M sw ( Ā) that is exactly the image of I by the above bijection:

X (i, j) = 0 ⇔ u , a j -a i = 0 ⇔ p I (i) = p I ( j), X (i, j) = + ⇔ u , a j -a i > 0 ⇔ p I (i) < p I ( j), X (i, j) = -⇔ u , a j -a i < 0 ⇔ p I (i) > p I ( j).
Hence both the sweeps of ( A) and the covectors of M sw ( Ā) are in bijection with the cells of the hyperplane arrangement SH( A) and the bijections induce poset isomorphisms.

It follows from the previous lemma that the set of sweep permutations ( A) is in bijection with the topes of the sweep oriented matroid M sw ( Ā). Since the topes of an oriented matroid completely determine it (cf. [START_REF] Björner | Oriented Matroids, Encyclopedia of Mathematics and its Applications[END_REF]Proposition 3.8.2]), this implies:

Corollary 3.4 The set of sweep permutations ( A) determines the whole poset of sweeps ( A).

123

The structures we have introduced are related by the following hierarchy (whose proof depends on the upcoming Proposition 4.3): Theorem 3.5 Let A ∈ R d× [n] be a point configuration. Then the set of sweep permutations ( A), the poset of sweeps ( A), the sweep oriented matroid M sw ( Ā) and the big oriented matroid M big ( Ā) (cryptomorphically) determine each other. They determine the little oriented matroid M lit ( Ā), which does not always determine them.

In particular, the sweep oriented matroid is a combinatorial invariant of a point configuration that is finer than the order type (given by the little oriented matroid).

Proof The fact that ( A) and ( A) determine each other follows from Corollary 3.4. The equivalence between ( A) and M sw ( Ā) follows from Lemma 3.3. The equivalence between M sw ( Ā) and M big ( Ā) will be proved later, as a consequence of Definition 4.2 and Proposition 4.3.

Finally, M big ( Ā) determines M lit ( Ā) by restriction to the ground set [n] but this operation is not injective. Examples of planar configurations with different sets of sweep permutations but the same little oriented matroid can be found in [17, Section 1.10].

Sweep Oriented Matroids

The main insight for expanding the notion of sweep oriented matroids from Definition 3.2 beyond the realizable case is to note that a configuration of vectors of the form a ja i for (i, j) ∈ [n] 2 is just the projection of the braid configuration {e je i (i, j)

∈ [n] 2 } ∈ R n×( [n]
2 ) (the set of positive roots of the Coxeter root system A n-1 ) under the linear map M A defined in [START_REF] Alon | The number of small semispaces of a finite set of points in the plane[END_REF].

Consider the oriented matroid B n associated to the braid configuration, that is, the graphic oriented matroid of the complete graph K n with the acyclic orientation induced by the usual order on [n]. We will use the same notation B n as with the hyperplane arrangement, as it will be always clear from the context whether we are considering the hyperplane arrangement or the associated oriented matroid. Note that, since the configuration of the a ja i is a linear projection of the braid configuration, every covector of M sw ( Ā) is a covector of the braid oriented matroid, as we can pull back linear forms with M A * . The oriented matroid analogues of linear projections are strong maps. For two oriented matroids M 1 and M 2 on the same ground set, we say that there is a strong map from [START_REF] Björner | Oriented Matroids, Encyclopedia of Mathematics and its Applications[END_REF]Sec. 7.7]). This will be the starting point for our definition. Definition 3. [START_REF] Andrzejak | In between k-sets, j-facets, and i-faces: (i, j)-partitions[END_REF] An oriented matroid M on the ground set [n] 2 is a sweep oriented matroid if there is a strong map B n → M from B n to M, i.e. if all covectors of M are covectors of B n . Remark 3.7 Note that, if M is a sweep oriented matroid, then we can interpret its covectors as covectors of the braid arrangement, and hence each covector can be uniquely identified with an ordered partition via the bijection inverse to [START_REF] Athanasiadis | Monotone paths on zonotopes and oriented matroids[END_REF]. For a 123 covector X ∈ M of a sweep oriented matroid, we will denote by I X the associated ordered partition.

M 1 to M 2 , denoted M 1 → M 2 , if every covector of M 2 is a covector of M 1 (see
Our next result characterizes sweep oriented matroids via a 3-term orthogonality condition on covectors (c.f. [START_REF] Björner | Oriented Matroids, Encyclopedia of Mathematics and its Applications[END_REF]Sec. 3.4]) that provides an explicit test for deciding whether an oriented matroid is a sweep oriented matroid. It will be relevant later in the context of sweep acycloids in Sect. [START_REF] Babson | A combinatorial flag space[END_REF].

Recall that the support of a sign-vector X ∈ {+, -, 0} E is X = e ∈ E X e = 0 . Two sign-vectors X , Y ∈ {+, -, 0} E are said to be orthogonal if either X ∩ Y = ∅, or the restrictions of X and Y to X ∩ Y are neither equal nor opposite (i.e., there are i, j with X i = Y i = 0 and X j = -Y j = 0). Lemma 3.8 An oriented matroid M on [n] 2 is a sweep oriented matroid if and only if for every covector X and every choice of

1 ≤ i < j < k ≤ n, the triple (X (i, j) , X ( j,k) , X (i,k) ) is orthogonal to the sign vector (+, +, -).
Equivalently, M is a sweep oriented matroid if and only if for any covector X , and for 1 ≤ i < j < k ≤ n, the triple (X (i, j) , X ( j,k) , X (i,k) ) does not belong to the following list of forbidden patterns:

(+, +, -), (-, -, +), (0, +, -), (0, -, +), (+, 0, -), (-, 0, +), (+, +, 0), (-, -, 0), (0, 0, -), (0, 0, +), (0, +, 0), (0, -, 0), (+, 0, 0), (-, 0, 0) .

Proof There is a strong map B n → M if and only if all the covectors of M are covectors of B n , which is equivalent to the condition that all the covectors of M are orthogonal to all circuits of B n (see [START_REF] Björner | Oriented Matroids, Encyclopedia of Mathematics and its Applications[END_REF]Prop. 7.7.1]). The circuits of B n are induced by cycles of K n . They are of the form C i 1 ,...,i r for any collection i 1 , . . . , i r of at least 3 distinct elements of

[n], with C i 1 ,...,i r (i k ,i k+1 ) = + if i k < i k+1 and C i 1 ,...,i r (i k+1 ,i k ) = -if i k > i k+1
for all 1 ≤ k ≤ r (with the convention i r +1 = i 1 ), and C i 1 ,...,i r (h,l) = 0 for any other pair.

An easy induction shows that the orthogonality to the circuit C i 1 ,...,i r is implied by the orthogonality to all circuits C i 1 ,i k ,i k+1 for 2 ≤ k ≤ r -1, which is equivalent to our statement. This condition is actually a reformulation of the transitivity of the partial order induced by an ordered partition I (namely i j if and only if p I (i) ≤ p I ( j)). For example, forbidding the patterns (+, +, -) and (+, +, 0) is equivalent to stating that i ≺ j ≺ k implies i ≺ k, and so on. This is why we refer to it as the transitivity condition on sweep oriented matroids.

The poset of sweeps of a sweep oriented matroid M is the partially ordered set (M) of the ordered partitions I X for the covectors X ∈ M, ordered by refinement. Enlarged with a top element 1, this poset is isomorphic to the big face lattice of M. The topology of such complexes is well known [START_REF] Björner | Oriented Matroids, Encyclopedia of Mathematics and its Applications[END_REF]Thm. 4.3.3]. We describe it in the following proposition. Note that there is some ambiguity in the literature concerning the definition of the poset of faces of cell complexes, in particular whether it should be augmented by a bottom element or not (compare [12, Fig. 2] and [14, Fig. 2]). We 123 follow [START_REF] Björner | Topological Methods[END_REF] and [START_REF] Björner | Oriented Matroids, Encyclopedia of Mathematics and its Applications[END_REF] and do not include an additional bottom element in the definition of the face poset of a cell complex. Proposition 3.9 [START_REF] Björner | Oriented Matroids, Encyclopedia of Mathematics and its Applications[END_REF]Thm. 4.3.3] The poset of sweeps (M) ([n]) of a sweep oriented matroid M of rank r without the trivial sweep is isomorphic to the face poset of a shellable regular cell decomposition of the (r -1)-sphere. In particular, the order complex (M) ([n]) triangulates the (r -1)-sphere.

Big and Little Oriented Matroids

In this section we show how the big and little oriented matroids of a point configuration (Definition 3.2) are completely determined by its sweep oriented matroid. Actually, the construction of these matroids can be extended to any abstract sweep oriented matroid, providing definitions beyond the realizable case. This generalizes the results for rank 3 proved in [17, Sec. 1.10].

Big and Little Oriented Matroids Associated to Sweep Oriented Matroids

First, we will show how to extend any sweep oriented matroid to what will be called a big oriented matroid. For a covector X of a sweep oriented matroid, let p X : [n] → [l X ] be the surjection associated to the corresponding ordered partition. For each 1

≤ k ≤ 2l X + 1, let X k ∈ {+, -, 0} [n]∪( [n]
2 ) be the sign-vector:

X k i = ⎧ ⎪ ⎨ ⎪ ⎩ -if p X (i) ≤ k-1 2 , + if p X (i) > k 2 , 0 if k is even and p X (i) = k 2 . for 1 ≤ i ≤ n; X k (i, j) = X (i, j) for all 1 ≤ i < j ≤ n.
We defer the details of checking that the transitivity condition from Lemma 3.8 implies the oriented matroid axioms for these covectors to Appendix B. They are easy, but tedious.

Theorem 4.1 If M is the set of covectors of a sweep oriented matroid, then

M big = X k X ∈ M, 1 ≤ k ≤ 2l X + 1
is the set of covectors of an oriented matroid. Definition 4.2 Let M be a sweep oriented matroid. The oriented matroid M big is the big oriented matroid of M; and the oriented matroid M lit obtained by deleting all pairs (i, j) from M big is the little oriented matroid of M.

These definitions are indeed coherent with the realizable case, as the following proposition shows. This proves that the sweep oriented matroid of a point configuration determines its big and little oriented matroids, concluding the proof of Theorem 3.5.

Proposition 4.3 The big and little oriented matroids of a point configuration are the big and little oriented matroids associated to its sweep oriented matroid.

Proof Let A = (a 1 , . . . , a n ) ∈ R d×[n] be a d-dimensional point configuration. Every vector u ∈ R d induces an ordering of A, which is encoded in a covector X of M sw ( Ā). For c ∈ R, the partition i u , a i < c , i u , a i = c , i u , a i > c
only depends on which, or between which pair, of the l X values attained by u , • on A does c lie. These 2l X + 1 distinct partitions are precisely those encoded by the covectors X k defining the big oriented matroid of M sw ( Ā).

Note that, by the definition of the big oriented matroid of M, the zero covector 0 of M induces the all-positive tope + n in M lit , which is hence an acyclic oriented matroid.

The following lemma concerning the ranks of the big and little oriented matroids will be needed later.

Proof

To justify that M big has rank r + 1, it is sufficient to notice that if 0 ( [n] 2

) = Y 0 ≺ Y 1 ≺ • • • ≺ Y r is a maximal chain of covectors of M, then 0 [n]∪( [n] 2 ) = Z -1 ≺ Z 0 ≺ Z 1 ≺ • • • ≺ Z r
is a maximal chain of covectors of M big , where for any k ∈ {0, . . . , r }, we define Z k by Z k

( [n]
2 ) = Y k and Z k

[n] = + n . Indeed, we cannot add a covector Z in the big oriented matroid between Z -1 and Z 0 because if Z i = 0 and Z j = + we necessarily have Z (i, j) = 0 since i and j are not in the same part of the ordered partition l Z . We cannot add a covector strictly between Z k and Z k+1 either because its restriction to [n] 2 would give a covector of M strictly between Y k and Y k+1 . We prove that M lit also has rank r + 1 by induction on r . If M is of rank r = 0, then 0 ( [n] 2 ) is its only covector. It induces the little oriented matroid of rank 1 consisting of the covectorsn , 0 n , and + n . Now, suppose that M is a sweep oriented matroid on ground set [n] 2 that has rank r ≥ 1. Up to relabelling, we can suppose that (n -1, n) is not a loop. Then the contraction of M along {(n -1, n)} has rank r -1. Under the bijection (5), the covectors of this contraction M/ {(n-1,n)} correspond to the partitions associated to covectors of M such that n -1 and n are in the same part. This implies that for all i ≤ n -2, the pairs (i, n -1) and (i, n) are parallel. By deleting all the pairs (i, n) we obtain an oriented matroid M on [n-1] of M lit such that Y n-1 = + and Y n = 0. Setting X r = X r -1 •Y , and X r +1 = X r •+ n , we obtain a chain

0 n = X 0 ≺ • • • ≺ X r -1 ≺ X r ≺ X r +1
of lenght r + 1 of covectors of M lit . Moreover, the restriction operation on oriented matroids cannot increase the rank, thus the rank of M lit cannot be bigger than the rank of M big . Hence M lit also has rank r + 1.

Example 4.5 (The braid oriented matroids in types A and B) The study of big oriented matroids of Coxeter hyperplane arrangements in types A and B unveils a recursive decomposition that, in view of the upcoming Sect. 4.2, explains the existence of a maximal chain of modular flats. This important property was first studied by Stanley under the name of supersolvability [START_REF] Stanley | Supersolvable lattices[END_REF].

Type A. The big oriented matroid of the braid oriented matroid B n is the braid oriented matroid B n+1 . More precisely, if we relabel the elements i ∈ [n] by (1, i + 1) and the elements (i, j) ∈ [n] 2 by (i + 1, j + 1), then we recover the braid oriented matroid B n+1 . Indeed, the topes of B n big are of the form X 2k+1 where X is a tope of B n and 0 ≤ k ≤ n. If X corresponds to the permutation (σ (1), . . . , σ (n)) ∈ S n , then X 2k+1 corresponds to the permutation in S n+1 :

(σ (1) + 1, . . . , σ (k) + 1, 1, σ (k + 1) + 1, . . . , σ (n) + 1).
Type B. Consider the type B braid oriented matroid B B n from Sect. 2.2.2, indexed by the elements in [±n] 2 . That is, B B n is the sweep oriented matroid of the vertex set of the cross-polytope. Then its big oriented matroid

(B B n ) big is FL-isomorphic to B B n+1
without one element (of those of the form (-i, i) ).

To see it, it is easier to consider first an enlarged version, with base elements

[-n, n] = {-n, . . . , -1, 0, 1, . . . , n}
corresponding to the point configuration

B n = (-e n , . . . , -e 1 , 0, e 1 , . . . , e n )
that contains the vertices of the cross-polytope together with the origin. The FLisomorphism class of the sweep oriented matroid does not change, but we get some new parallel elements. Namely, the elements labeled (-i, i), (-i, 0), and (0, i) become parallel (with the same orientation) in the enlarged sweep oriented matroid

B B n = M sw ( B n ). Now, relabel the elements [-n, n] ∪ [-n,n] 2 to [-n-1,n+1]
(-σ (n), . . . , -σ (1), 0, σ (1), . . . , σ (n)).
123

Under the relabeling we can read the topes X 2k+1 of the big oriented matroid ( B B n ) big as centrally symmetric permutations of [-n -1, n + 1] representing topes of B B n+1 . Namely, for 0 ≤ k ≤ n + 1, the tope X 2k+1 corresponds to the centrally symmetric permutation:

(-σ (n), . . . , -σ (n -k + 1), -n -1, -σ (n -k), . . . , σ (n -k), n + 1, σ (n + 1 -k), . . . σ (n)).
whereas for n + 2 ≤ k ≤ 2n + 2 it corresponds to:

(-σ (n), . . . , -σ (n -k + 1), n + 1, -σ (n -k), . . . , σ (n -k), -n -1, σ (n + 1 -k), . . . σ (n)). This shows that ( B B n ) big is FL-isomorphic to B B n+1
, and hence to B B n+1 . If we want to consider the original configuration without the origin, we simply need to remove all the elements of the big oriented matroid that involve a label using 0. Every parallelism class conserves at least one representative except for the singleton 0, which was sent to the triple (-n -1, n + 1), (-n -1, 0), (0, n + 1) with our relabeling. This shows that

(B B n ) big is FL-isomorphic to B B n+1 (-n -1, n + 1).
Remark 4.6 (On labeling and isomorphism) The labeling plays an important role in the definition of a sweep oriented matroid and in Theorem 3.5. Indeed, non-isomorphic big oriented matroids might arise from isomorphic sweep oriented matroids. (Here, we mean FL-isomorphism, but the statement is also true for the other standard notions of oriented matroid isomorphism.) For example, all sufficiently generic planar npoint configurations give rise to FL-isomorphic sweep oriented matroids but their big oriented matroids are not FL-isomorphic.

Remark 4.7 (On realizability) Note that, for a big oriented matroid M, realizability as an oriented matroid (i.e. in the sense of ( 4)) is equivalent to realizability as a big oriented matroid (i.e. in the sense of Definition 3.2). Indeed, any point configuration A such that M big ( Ā) = M can be extended (with the corresponding points at infinity) to an oriented matroid realization of M. And reciprocally, the restriction of any oriented matroid realization of M to the elements indexed by [n] can be sent, after a suitable projective transformation and dehomogenization, to a point configuration A such that M big ( Ā) = M.

In contrast, there are sweep oriented matroids that are realizable as an oriented matroid but that are not of the form M sw ( Ā) for any point configuration A. Indeed, the non-realizable pentagon of [START_REF] Goodman | On the combinatorial classification of nondegenerate configurations in the plane[END_REF] (see Fig. 10) gives rise to a non-realizable allowable sequence; that is, to a non-realizable big oriented oriented matroid of rank 3. The associated sweep oriented matroid is an oriented matroid of rank 2, and thus realizable (as an oriented matroid) [START_REF] Björner | Oriented Matroids, Encyclopedia of Mathematics and its Applications[END_REF]Cor. 8.2.3]. However, it is not the sweep oriented matroid of a point configuration, because the corresponding big oriented matroid is not realizable.

123 Fig. 10 The allowable sequence (1, 2, 3, 4, 5) → (1, 2, 4, 3, 5) → (2, 1, 4, 3, 5) → (2, 1, 4, 5, 3) → (2, 4, 1, 5, 3) → (2, 4, 5, 1, 3) → (4, 2, 5, 1, 3) → (4, 5, 2, 1, 3) → (4, 5, 2, 3, 1) → (4, 5, 3, 2, 1) → (5, 4, 3, 2, 1) cannot be realized by a point configuration, because it would necessarily be a pentagon whose sides and "parallel diagonals" meet as in the above picture, which is geometrically impossible [START_REF] Goodman | On the combinatorial classification of nondegenerate configurations in the plane[END_REF] We end this remark by noting that the Universality Theorem for allowable sequences of Hoffmann and Merckx [START_REF] Hoffmann | A universality theorem for allowable sequences with applications[END_REF] implies that it is (∃R)-hard to decide whether a big oriented matroid is realizable.

Big Oriented Matroids and Tight Modular Hyperplanes

In this section we provide an alternative characterization of the FL-isomorphism classes of big oriented matroids, and hence of sweep oriented matroids. It is purely structural, without relying on the labeling of the elements. We show that they are closely related to the concept of modular hyperplanes.

According to our definition, every big oriented matroid M big on [n]∪ [n] 2 contains the cocircuit Z = (+ n , 0 ( n 2 ) ). Moreover, X (i, j) = 0 for any covector X such that X i = X j = 0; which is equivalent to the fact that for any i, j not in the same parallelism class, the restriction of M big to the set {i, j, (i, j)} ⊂ E has rank 2. These two properties show that the set of indices [n] 2 form a modular hyperplane. The flats of an oriented matroid M of rank r on E are the flats of its underlying (unoriented) matroid M; that is, the zero-sets of its covectors. The poset of flats ordered by inclusion forms a geometric lattice [17, 4.1.13]. The hyperplanes are the flats of rank r -1, and they arise as zero-sets of cocircuits. A flat F is called modular if rk(F) + rk(G) = rk(F ∧ G) + rk(F ∨ G) for any other flat G, where rk(•) is the rank function of the geometric lattice (for a flat F, rk(F) coincides with the rank of the oriented matroid M F ). Modular flats have many interesting properties, and play an important role in the theory of matroids, see [START_REF] Brylawski | Modular constructions for combinatorial geometries[END_REF][START_REF] Stanley | Modular elements of geometric lattices[END_REF].

Hence, a modular hyperplane is a hyperplane [START_REF] Brylawski | Modular constructions for combinatorial geometries[END_REF]Cor. 3.4] it is shown that a hyperplane is modular if and only if it intersects every line (flat G with rk(G) = 2). Equivalently, if for every 123 pair of elements x, y ∈ E F that are not parallel nor a loop, there is some element z ∈ F such that for every covector X with X x = X y = 0 we have X z = 0. We will say that a modular hyperplane F is tight if there is no z ∈ F such that F z is a modular hyperplane of M E z .

F ⊂ E such that rk(F ∧ G) = rk(F ∩ G) = rk(G) -1 for any flat G not contained in F. Said differently, F ∩ G is a hyperplane in M G . In
The following result gives a characterization of big oriented matroids similar to the one given in [START_REF] Björner | Oriented Matroids, Encyclopedia of Mathematics and its Applications[END_REF]Sect. 6.4] for the rank 3 case. Proposition 4.8 Let M be an oriented matroid on ground set E = [n] ∪ [n] 2 such that:

(1) there exists a cocircuit Z of M such that {e ∈ E | Z e = 0} = [n] 2 (i.e. Z = [n]), (2) for any (i, j) ∈ [n] 2 , for any covector X of M, if two coordinates among X i , X j , X (i, j) are zero, then the third one is zero too.

Then, up to reorientation, M is the big oriented matroid of the sweep oriented matroid M ( [n] 2 ) . In a realizable setting, and without parallel elements and loops, the conditions on M amount to asking that the real vector representing (i, j) is in the intersection of the 2-plane spanned by the real vectors representing i and j and the hyperplane given by the cocircuit Z (which contains all the vectors corresponding to elements in [n] 2 ). One can check that the example depicted in Fig. 8 satisfies this condition.

Proof We need to prove that, after the reorientation of some elements of the ground set, the restriction M ( [n] 2 ) is a sweep oriented matroid, i.e. it satisfies Lemma 3.8, and the covectors of M are exactly those obtained from the covectors of M ( [n] 2 ) as in Theorem 4.1.

We can assume that, after a suitable reorientation of M we have that Z = (+ n , 0 ( [n] 2 ) ). Note that M [n] cannot have loops, as witnessed by Z ; and that if i and j are parallel, then (i, j) must be a loop. We will from now on assume that M does not have parallel elements, as it simplifies the exposition.

Let us show that for any two covectors X , Y ∈ M such that X i = Y i = -, X j = Y j = + we have X (i, j) = Y (i, j) = 0. Assume the contrary. Then the axiom Definition 3.1 on oriented matroids would imply the existence of a covector T ∈ M such that T i = -, T j = + and T (i, j) = 0. A second application of the axiom Definition 3.1 between T and Z would give the existence of a covector T ∈ M such that T i = T (i, j) = 0 and T j = +, which contradicts the second assumption on M. Hence, we can reorient (i, j) so that for any covector X of M with X i =and X j = +, we have X (i, j) = +.

To check thatM

( [n]
2 ) is a sweep oriented matroid, it suffices to look at all restrictions of the form M {i, j,k,(i, j),( j,k),(i,k)} for 1 ≤ i < j < k ≤ n. This gives an oriented matroid of rank at most 3. One can easily check that with our conditions there are only three possible configurations, none of which violates the condition from Lemma 3.8. Moreover, it is clear that any covector X of M can be obtained from the covector X ( [n] 2 ) of M ( [n] 2 ) by the method described at the beginning of Sect. 4.1. Indeed, our reorientation on [n] 2 implies that the ordered partition of [n] given by (I

-= {i | X i = -}, I 0 = {i | X i = 0}, I + = {i | X i = +}) is refined by the ordered partition J induced by X ( [n]
2 ) , in such a way that either I 0 = ∅ or I 0 is an entire part of J . Thus X is of the form (X ( [n] 2 ) ) k for some k. It remains to check that, for every covector Y ∈ M ( [n] 2 ) , all covectors Y k obtained by the method described in Sect. 4.1 are indeed covectors of M. We do it by induction on k. Observe first that Y 1 = Z • Ỹ , where Ỹ is any covector in M whose restriction to [n] 2 gives Y . Thus, we have Y 1 ∈ M. Now, for an odd k 0 ∈ [2l Y ], we apply the Elimination Axiom (V3) to the covectors Y k 0 and (-Z ) • Y k 0 , and the smallest element

i 0 ∈ p -1 Y ({ k 0 +1 2 }
) to obtain a covector T . We claim that T = Y k 0 +1 . Indeed, for all i where p Y (i) < k 0 +1

2 we have

T i = Y k 0 i = (-Z ) i = -. For all i ∈ p -1 Y ({ k 0 +1 2 }), we have T i 0 = 0 and T (i 0 ,i) = Y k 0 (i 0 ,i) = (-Z ) (i 0 ,i) = 0, so the second hypothesis on M implies that T i = 0. Let i where p Y (i) > k 0 +1
2 . We assume that i > i 0 , the other case is analogous. We have that T (i 0 ,i) = Y k 0 (i 0 ,i) = 0 and T i 0 = 0, so T i = 0 by the second hypothesis. This forces that

T i = + as otherwise T • Z would satisfy (T • Z ) i 0 = -(T • Z ) i = (T • Z ) (i 0 ,i) ,
which contradicts our assumption on the reorientation.

To conclude, if k 0 is even, then

Y k 0 +1 = Y k 0 • (-Z ).
We get the following characterization as a direct corollary.

Theorem 4.9 A simple oriented matroid M is FL-isomorphic to a big oriented matroid if and only if it has a tight modular hyperplane.

Proof It is straightforward to check that in a big oriented matroid the elements indexed by [n] 2 form a modular hyperplane that is tight up to the simplification of parallel elements.

For the converse, let E be the ground set of M, and F ⊆ E a tight modular hyperplane. We will relabel the elements of E F by [n], where n = |E F|. Now, for each (i, j) ∈ [n] 2 there is an element z ∈ F in the line spanned by i and j by the modularity of F. We add to M an element parallel to z labeled by (i, j) ∈ [n] 2 . We obtain this way an isomorphic oriented matroid M . Note that, since the modular hyperplane F ⊆ E is tight, for each z ∈ F there are some i, j ∈ E F such that i, j, z are collinear. Hence, z is parallel to (i, j) and M z is isomorphic to M. We conclude that M

[n]∪( [n]
2 ) is isomorphic to M. It satisfies the conditions of Proposition 4.8 and is hence isomorphic to a big oriented matroid.

A consequence of this observation is that we can extend the process to determine the big oriented matroid from the sweep oriented matroid to any oriented matroid with a modular hyperplane (not necessarily tight). For sweep oriented matroids, this relies on the labeling of the elements (see Remark 4.6). Arbitrary modular hyperplanes also need a similar extra information. Let M be an oriented matroid on a ground set E with a modular hyperplane F. To simplify the exposition, we will assume that M is simple (no loops or parallel elements), that E F = [n], that F ∩ [n] 2 = ∅, and that all the elements of E F lie in a common halfspace defined by F. (We could omit this simplification by adding information to the decoration, but it unnecessarily complicates the notation.)

We will decorate the elements in F by constructing maps δ :

F → 2 ( [n]
2 ) and : [n] 2 → {+, -} that associate a subset of elements of [n] 2 to each f ∈ F and a sign to each pair in [n] 2 . This is done with the following algorithm. We start decorating each element in F with an empty set. For every (i, j) ∈ [n] 2 , let f ∈ F be the element of F in the flat spanned by i and j. We add to the decoration δ( f ) of f the ordered pair (i, j); and we set (i, j) = + if there is a covector X ∈ M such that X i = 0 and X j = X f = 0, or (i, j) =otherwise. We will call this information the decoration of F induced by M.

We will show that we can recover M from M = M F , its restriction to F, and the decoration. To state our result, we introduce valid decorations, which are those that can be obtained with the procedure above. For any simple oriented matroid M on the ground set F, we call a valid decoration a couple of maps δ :

F → 2 ( [n]
2 ) and : [n] 2 → {+, -} for a certain n, such that: • the decorations form a partition of [n] 2 , with empty parts accepted:

[n] 2 = f ∈F δ( f ) with δ( f ) ∩ δ( f ) = ∅ whenever f = f ; and • the covectors X ∈ M, seen as elements of {+, -, 0} ( [n]
2 ) by considering X (i, j) = (i, j)X f if (i, j) ∈ δ( f ), satisfy the transitivity condition from Lemma 3.8.

The following result should be seen as the oriented version of [19, Thm. 2.1], which similarly characterizes when an (unoriented) matroid can be extended so that its ground set is a modular hyperplane of the larger matroid. We have deferred its proof to Appendix B, since it relies on the proof of Theorem 4.1.

Corollary 4.10 If M is a simple oriented matroid on F with a valid decoration (δ, ), then M can be extended to a unique oriented matroid M for which F is a modular hyperplane and (δ, ) is the decoration of F induced by M.

In particular, an oriented matroid M with a modular hyperplane F is completely determined by M F together with the decoration of F induced by M.

Not Every Oriented Matroid is a Little Oriented Matroid

Little oriented matroids are always acyclic, meaning that + n is a tope. A first guess could be that all acyclic oriented matroids can be extended to a big oriented matroid. After all, this is trivially the case for realizable oriented matroids. Moreover, it is also true for rank 3 oriented matroids. Although stated in a different language, this follows directly from [START_REF] Björner | Oriented Matroids, Encyclopedia of Mathematics and its Applications[END_REF]Thm. 6.3.3] and [42, Lemma 1]2 , which was first proved in the uniform case in [START_REF] Snoeyink | Sweeping arrangements of curves[END_REF]. (Actually, their result is stronger, as the sweep oriented matroid they construct is Dilworth in the sense of the upcoming Sect. 5.1.) Theorem 4.11 [START_REF] Björner | Oriented Matroids, Encyclopedia of Mathematics and its Applications[END_REF]Thm. 6.3.3] Every loopless acyclic oriented matroid M of rank 3 is the little oriented matroid of a sweep oriented matroid.

However, contrary to the rank 3 case, starting at rank 4 there exist acyclic oriented matroids that cannot be extended to big oriented matroids. The proof of Theorem 4.11 in [START_REF] Björner | Oriented Matroids, Encyclopedia of Mathematics and its Applications[END_REF] uses Levi's extension lemma, that states that every arrangement of pseudolines can be extended with an extra pseudoline through two given points. We use a famous counterexample to the analogous statement in rank 4 by Richter-Gebert [START_REF] Richter-Gebert | Oriented matroids with few mutations[END_REF] to present an acyclic oriented matroid that cannot be extended to a big oriented matroid.

Theorem 4.12 [72, Cor. 3.4]

There is an oriented matroid RG of rank 4 with ground set [START_REF] Björner | Posets, regular CW complexes and Bruhat order[END_REF] with two topes U and T such that no extending pseudoplane intersects U and T simultaneously.

This means that if RG is an oriented matroid on [START_REF] Björner | Posets, regular CW complexes and Bruhat order[END_REF]∪{ f } such thatRG [START_REF] Björner | Posets, regular CW complexes and Bruhat order[END_REF] = RG, then it cannot contain covectors U , T ∈ RG such that U [START_REF] Björner | Posets, regular CW complexes and Bruhat order[END_REF] U and T [START_REF] Björner | Posets, regular CW complexes and Bruhat order[END_REF] T but U f = T f = 0. Theorem 4. [START_REF] Björner | Essential chains and homotopy type of posets[END_REF] The reorientation of RG sending U to + 12 is acyclic, but it is not the little oriented matroid of any sweep oriented matroid.

Proof After a suitable reorientation, assume that U = + 12 . Suppose that there is a big oriented matroid M on [12] ∪ [12] 2 such that M [START_REF] Björner | Posets, regular CW complexes and Bruhat order[END_REF] = RG. It contains a cocircuit U ∈ M with U i = U i = + for all i ∈ [START_REF] Björner | Posets, regular CW complexes and Bruhat order[END_REF] and U (i, j) = 0 for all (i, j) ∈ [12] 2 . Let X be a covector in RG such that [X , T ] forms an interval of length 2 in the face lattice of RG. This means that there are 1 ≤ i 0 < j 0 ≤ 12 such that X i 0 = X j 0 = 0 and X i T i for all i ∈ [START_REF] Björner | Posets, regular CW complexes and Bruhat order[END_REF]\{i 0 , j 0 }. Let X be a covector in M such that X [START_REF] Björner | Posets, regular CW complexes and Bruhat order[END_REF] = X . Hence, we have X (i 0 , j 0 ) = 0 and X [START_REF] Björner | Posets, regular CW complexes and Bruhat order[END_REF] T . Hence RG = M [START_REF] Björner | Posets, regular CW complexes and Bruhat order[END_REF]∪{(i 0 , j 0 )} is an extension of RG whose covectors U [START_REF] Björner | Posets, regular CW complexes and Bruhat order[END_REF]∪{(i 0 , j 0 )} and X [START_REF] Björner | Posets, regular CW complexes and Bruhat order[END_REF]∪{(i 0 , j 0 )} contradict the special property of RG.

Lattices of Flats of Sweep Oriented Matroids

Dilworth Sweep Oriented Matroids

It is also interesting to understand the underlying (unoriented) matroid M sw associated to a sweep oriented matroid M sw . In particular, because it plays an essential role in the enumeration of sweeps [START_REF] Björner | Oriented Matroids, Encyclopedia of Mathematics and its Applications[END_REF]Sec. 4.6]. In the realizable case, this was done by Edelman [START_REF] Edelman | Ordering points by linear functionals[END_REF] and Stanley [START_REF] Stanley | Valid orderings of real hyperplane arrangements[END_REF], who showed that, under certain genericity constraint, M sw can be obtained from M lit via the operation of Dilworth truncation.

We will work directly with the axiomatic of (unoriented) matroids in terms of geometric lattices of flats, which was already mentioned in Sect. 4.2. We refer to [START_REF]Theory of Matroids[END_REF] for a comprehensive reference on (unoriented) matroids.

Recall that if M is an oriented matroid on ground set E, a flat of M is a subset F ⊆ E that is the zero-set of a covector of M (there is X ∈ M such that F = {e ∈ 123 E | X e = 0}). The set F M of all flats of M, ordered by inclusion, has the special structure of a geometric lattice; that is, a finite atomistic semimodular lattice. If M has no loop, its minimal element is ∅. (Note that this order is reversed from the order on the covectors in the face lattice of M.) Conversely, any geometric lattice can be seen as the lattice of flats of a matroid. Let S ⊆ E. There is only one minimal flat F that contains S. The rank of S is the length of any maximal chain from ∅ to F in F M . It is denoted rk M (S), or rk M (S). The rank function satisfies the submodular inequality:

rk M (A) + rk M (B) ≥ rk M (A ∩ B) + rk M (A ∪ B).
The flats and the rank function give two cryptomorphic ways to define the underlying (unoriented) matroid M of the oriented matroid M. If M(V ) is the matroid associated to a real vector configuration V = (v 1 , . . . , v n ), the flats correspond to the sets of vectors in a same linear subspace and the rank of S ⊆ E is the dimension of the linear subspace generated by {v i | i ∈ S}.

The flats of the braid arrangement B n are in correspondence with the (unordered) partitions of [n], and the lattice of flats of B n is just the lattice of partitions of [n]. Similarly, each flat of a sweep oriented matroid can be associated to a partition, and the sweeps corresponding to orderings of this partition correspond to the covectors with this zero-pattern.

We will need the oriented and unoriented notions of weak maps, which are the matroidal version of perturbing a configuration to a more special position. If M and M are two oriented matroids on the same ground set E, we say that there is a weak map from M to M if for every covector X ∈ M , there is a covector Y ∈ M such that X Y . Note that every strong map is also a weak map, but not the other way round (the definition of strong maps is given in Sect. 3.3). If M and M are two unoriented matroids on the same ground set E, we say that there is a weak map from M to M if for any subset F ⊆ E we have rk M (F) ≤ rk M (F). Note that a weak map between oriented matroids induces a weak map on the underlying unoriented matroids (cf. [START_REF] Björner | Oriented Matroids, Encyclopedia of Mathematics and its Applications[END_REF]Cor. 7.7.7]).

The idea behind the Dilworth truncation is the following: if F is a geometric lattice and we remove the elements of rank 1, we obtain a poset F that is not necessarily a geometric lattice. The most generic way to augment it with all the joins needed to fulfill the semimodularity condition gives rise to a matroid called the first Dilworth truncation of F. The construction works in more generality when the elements of rank ≤ k are removed, giving rise to the kth Dilworth truncation, but we will not need it in such generality ( [START_REF] Dilworth | Dependence relations in a semi-modular lattice[END_REF], see also [START_REF] Brylawski | Constructions, Theory of Matroids[END_REF]). Definition 5.1 [START_REF] Brylawski | Constructions, Theory of Matroids[END_REF]Prop. 7.7.5] Let M be a matroid on ground set E. The first Dilworth truncation of M, denoted D 1 (M), is defined on the ground set E 2 and its rank function is given by:

rk D 1 (M) (∅) = 0, rk D 1 (M) (F) = min S∈S(F) r S (F) for ∅ = F ⊆ E 2 ,
where S (F) is the set of (unordered) partitions S = {F 1 , . . . ,

F l } of F (F = F 1 ∪ • • • ∪ F l , F k = ∅ for all k ∈ [l],
and

F k ∩ F h = ∅ for all k = h) and r S (F) = l k=1 rk M ( {i, j | (i, j) ∈ F k }) -l.
The flats of rank 1 of D 1 (M) are exactly the flats of rank 2 (i.e. the lines) of M. As noted by Brylawski [START_REF] Brylawski | Constructions, Theory of Matroids[END_REF] and Mason [61,Sec. 2.1], in the realizable case the Dilworth truncation can be geometrically realized by intersecting all the lines of M with a generic affine hyperplane. If A is generic enough (in the sense that incomparable flats spanned by its subsets are never parallel), then the hyperplane at infinity fulfills this genericity condition and M sw ( Ā) is the first Dilworth truncation of M lit ( Ā). Otherwise, we only get a weak map of D 1 (M lit ( Ā)), as M sw ( Ā) will be in less general position. This result extends to (not necessary realizable) sweep oriented matroids. Theorem 5.2 Let M be a sweep oriented matroid on [n] 2 . Then there is a weak map from D 1 (M lit ) to M.

The proof needs an auxiliary lemma.

Lemma 5.3 Let M lit be the little oriented matroid of the sweep oriented matroid M.

If I is a flat of M lit of rank at least two, and J is the minimal flat in M that contains (i, j) i, j ∈ I , then rk M (J ) = rk M lit (I ) -1. (G). Then there exists an unordered partition {I 1 , . . . , I l } of a subset of [n] into flats of M lit of rank at least two such that

Proof Let I = {(i, j) ∈ [n]

Proof of Theorem5.2 We want to show that rk

M (G) ≤ rk D 1 (M lit ) (G) for every G ⊆ [n] 2 . Let F be a minimal flat of D 1 (M lit ) that contains G, so that rk D 1 (M lit ) (F) = rk D 1 (M lit )
F = l k=1 (i, j) i, j ∈ I k and rk D 1 (M lit ) (F) = l k=1 (rk M lit (I k ) -1)
. Indeed, let S = {F 1 , . . . , F l } be a partition of F that minimizes r S (F), and let

I k = i, j (i, j) ∈ F k . The submodular inequality shows that rk M lit (I 1 ∪ I 2 ) - 1 ≤ rk M lit (I 1 ) + rk M lit (I 1 ) -2 whenever I 1 ∩ I 2 = ∅.
We can therefore assume that the I k 's are disjoint. Moreover, these parts I k have to be flats of M lit . Otherwise, if there was some e / ∈ I k such that rk M lit (I k ) = rk M lit (I k ∪ {e}), then we could add to F all the pairs (i, e) and (e, i) with i ∈ I k without augmenting its rank, but F was taken to be a flat.

Let J k be the minimal flat in M that contains (i, j) i, j ∈ I k ; and let J be the join of all the J k in the lattice of flats of M. The submodularity of geometric lattices implies that rk M (J ) ≤ l k=1 rk M (J k ). Moreover, such a J contains all the J k , hence it contains F, which contains G; and therefore rk M (G) ≤ rk M (J ). We conclude by Lemma 5.3, that implies that for any k, rk

M (J k ) = rk M lit (I k ) -1.

123

In view of this result, we will say that a sweep oriented matroid M is Dilworth if the weak map predicted by Theorem 5.2 is actually an equality and we have M = D 1 (M lit ). This is the case if for any flat F of M associated to a partition I = (I 1 , . . . , I l ) we have

rk M (F) = l k=1 rk M lit (I k ) -l. ( 6
)
In other words, coplanarities in M are induced by coplanarities in M lit . For sweep oriented matroids that come from a point configuration, it prevents the case where some subspaces spanned by disjoint subsets of points are parallel.

Note that Dilworth sweep oriented matroids provide an oriented version of the matroid operation of Dilworth truncation. However, contrary to the unoriented case, such a truncation is often not unique and may even not exist, as shown by Theorem 4.13.

Even if Theorem 5.2 only works at the level of unoriented matroids, we expect that a stronger statement holds at the level of oriented matroids. The following conjecture is true for sweep oriented matroids of rank 2 (by [START_REF] Björner | Oriented Matroids, Encyclopedia of Mathematics and its Applications[END_REF]Thm. 6.3.3]), and for sweep oriented matroids arising from point configurations (it suffices to make a generic projective perturbation that removes unwanted parallelisms).

Conjecture 5.4

For any sweep oriented matroid M there is a Dilworth sweep oriented matroid M such that there is a weak map from M to M, and M and M have the same little oriented matroid.

Bounds on the Number of Sweep Permutations

One motivation for studying the lattice of flats of an oriented matroid is that it completely determines its f -vector, as shown by the celebrated Las Vergnas-Zaslavsky Theorem [START_REF] Björner | Oriented Matroids, Encyclopedia of Mathematics and its Applications[END_REF]Thm 4.6.4].

Theorem 5.5 The number of topes of an oriented matroid M only depends on its lattice of flats F. More precisely, this number is:

(-1) r χ F (-1),
where r is the rank of M, and χ F is the characteristic polynomial of F.

We can therefore adapt [START_REF] Edelman | Ordering points by linear functionals[END_REF]Thm. 3.4], 3 and [80, Thm. 7] to oriented matroids. As noted by Stanley in [START_REF] Stanley | Valid orderings of real hyperplane arrangements[END_REF], for fixed r the bound is a polynomial in n of degree 2(r -1).

Theorem 5.6 Let M be a sweep oriented matroid on [n] 2 of rank r . Then its number of sweep permutations is bounded from above by:

| (M)| ≤ r -1 2 i=0 2c(n, n -r + 1 + 2i),
where the c(n, ni) are the unsigned Stirling numbers of the first kind. The equality is obtained for example for realizable sweep oriented matroids that come from generic configurations of n points in R r -1 .

Proof We demonstrate how the proof of [START_REF] Edelman | Ordering points by linear functionals[END_REF]Thm. 3.4] and [START_REF] Stanley | Valid orderings of real hyperplane arrangements[END_REF]Thm. 7] extends to our set-up. We repeat the main ideas for the reader's convenience and refer to these references for more details. We denote by G r n the geometric lattice obtained by removing all elements of rank greater than r from the Boolean lattice on [n] and adding a top element. This is the lattice of flats of any generic point configuration of n points in R r -1 . The computation and evaluation of the characteristic polynomial of D 1 (G r n ) gives the right hand side of the inequality (see [START_REF] Edelman | Ordering points by linear functionals[END_REF]Co. 3.2]), which is the number of topes of any oriented matroid whose lattice of flats is D 1 (G r n ) via Theorem 5.5. This is the case for the sweep oriented matroids arising from generic configurations.

By [START_REF] Kung | Weak maps[END_REF]Cor. 9.3.7], it suffices to show that there is a weak map from D 1 (G r n ) to M, because this implies that the coefficients of the characteristic polynomial of M are bounded by those of the characteristic polynomial of D 1 (G r n ). Note that for any subset F ⊆ [n], we have rk G r n (F) = min(|F|, r ). Like in any matroid, M lit satisfies rk M lit (F) ≤ |F|, and hence there is a weak map from G r n to M lit . It follows from Definition 5.1 of the Dilworth truncation by its rank function that this induces a weak map from D 1 (G r n ) to D 1 (M lit ). It follows from Theorem 5.2 that there is a weak map from D 1 (G r n ) to M.

Pseudo-sweeps

Even if the little oriented matroid does not change, the poset of sweeps of a point configuration is not invariant under admissible projective transformations (in the sense of [89, App. 2.6]). In this section we describe a larger poset, the poset of pseudosweeps, that contains the sweeps with respect to all possible choices of "hyperplane at infinity". It is a poset of cellular strings, and as such it can be defined at the level of oriented matroids. Thus it exists even for those oriented matroids that are not little oriented matroids of any sweep oriented matroid.

Pseudo-sweeps

With the presentation of S P( A) as a monotone path polytope introduced in Sect. 2.3.3, we know that sweep permutations of a point configuration A can be interpreted as coherent monotone paths of the zonotope Z( Ā) with respect to a linear form (which we called the height). Non-coherent monotone paths also give rise to permutations of the elements of A, which we will call pseudo-sweep permutations. They can be read in terms of k-sets. A k-set of A is a k-element subset S ⊆ A for which there is an affine hyperplane strictly separating S from A S. See [START_REF] Matoušek | Lectures on Discrete Geometry[END_REF]Ch. 11] for background. For simplicity, assume that A = (a 1 , . . . , a n ) ∈ R d× [n] does not contain repeated points. A pseudo-sweep permutation of A is a permutation σ ∈ S n such that a σ (i) 1 ≤ i ≤ k is a k-set for all 1 ≤ k ≤ n. Note that we are still sweeping with a hyperplane, although we are allowed to slightly change its direction every time the hyperplane hits a point, as long as the new hyperplane does not cross one of the already visited points.

This point of view can be extended to obtain ordered partitions (and lift the constraint of not having repeated points). Consider a sequence of affine functionals γ r (x) = u r , xc r for 1 ≤ r ≤ m such that for each point a i ∈ A there is an r with γ r (a i ) = 0, γ s (a i ) > 0 for all s < r , and γ s (a i ) < 0 for all r < s; and such that for each 1 ≤ r ≤ m there is some i such that γ r (a i ) = 0. The sets I r = i γ r (a i ) = 0 with 1 ≤ r ≤ m form an ordered partition of [n], which we call a pseudo-sweep of A.

There is another way to interpret pseudo-sweeps of A and monotone paths/cellular strings of Z( Ā) in terms of hyperplane arrangements, which extends to oriented matroids.

A gallery of a hyperplane arrangement (without parallels) is a sequence of chambers (topes) such that adjacent chambers are separated by exactly one hyperplane. More generally, a gallery of an oriented matroid is a collection of topes T 0 , . . . , T m+1 such that S(T i , T i+1 ) is a parallelism class for all i. A gallery is minimal if no parallelism class is crossed twice. We will work with acyclic oriented matroids and we will be interested in their minimal galleries from + n to its oppositen .

This definition can be relaxed to accept paths that go accross some covectors (other than subtopes). A cellular string of M with respect to + n is a sequence of nontope covectors (X 1 , . . . , X m ) that are such that X 1 • + n = + n , X m •n =n , and X i •n = X i+1 • + n for all i. This notation is consistent with the notion of cellular string for a polytope with respect to a linear functional given in Sect. 2.3.3. Indeed, for a hyperplane arrangement which is the normal fan of a zonotope Z, its cellular strings are equivalent to the cellular strings of Z with respect to a linear functional that is minimized at the vertex corresponding to + n . (Minimal galleries are in correspondence with monotone paths.)

Note that an allowable sequence is just a cellular string on the braid arrangement based at the tope indexed by the permutation id = (1, 2, . . . , n), and that its galleries correspond to simple allowable sequences.

The following lemma sums up the relations between these objects in the realizable case. It is illustrated in Fig. 11, where the example of B 2 from Figs. 4 and 7 is revisited.

Lemma 6.1 Let

A = (a 1 , . . . , a n ) ∈ R d×[n]
be a point configuration; let H Ā be the hyperplane arrangement in R d+1 composed of the linear hyperplanes

H i = x ∈ R d+1
x , āi = 0 (oriented towards āi ) for a i ∈ A, where ā = (a, 1); and let Z( Ā) = n i=1 [-āi , āi ] be the associated zonotope. There is a bijection between: (i) pseudo-sweeps of A, (ii) cellular strings of H Ā with respect to the all-positive tope + n , and Fig. 11 The hyperplane arrangement H B2

. To depict the arrangement, it is intersected with the unit sphere and stereographically projected from the south pole (0, 0, -1). We obtain an arrangement of circles, oriented so that the positive side is the interior. Two sweeps, corresponding to the permutation 2, 1, 1, 2 and the ordered partition 21, 12 are depicted; and also the pseudo-sweep that is not a sweep corresponding to the permutation 1, 2, 1, 2. (This resumes the example of Fig. 7, where the monotone paths corresponding to these two permutations were depicted.) To represent these pseudo-sweeps, an oriented ray from the all-positive tope (containing the origin) to its opposite (at infinity) is depicted. The order in which the circles are crossed gives the corresponding permutation. If the ray meets more than one circle at the same time, then one recovers an ordered partition. Note that this gives an alternative method to construct the sweep hyperplane arrangement SH(B 2 ). Indeed, it is not hard to see that when one does this procedure (intersection of H Ā with the unit sphere plus stereographic projection), the hyperplanes spanned by the origin and the intersections of all possible pairs of spheres are precisely those of SH( A). This is why, under this representation, sweeps correspond to straight rays emanating from the origin

(iii) h-monotone cellular strings of Z( Ā) (h-coherent subdivisions of h(Z( Ā))); and if moreover A does not have repeated points, then there is a bijection between: (i) pseudo-sweep permutations of A, (ii) minimal galleries of H Ā from the tope + n to its oppositen , and (iii) h-monotone paths of Z( Ā).

Proof The proof amounts simply to translate between definitions (the definition of cellular strings induced by a projection was given in Sect. 2.3.3). We omit the details and only give some indications.

To a sequence of affine functionals γ r (x) = u r , xc r for 1 ≤ r ≤ m such that for each point a i ∈ A there is an r with γ r (a i ) = 0, γ s (a i ) > 0 for all s < r , and γ s (a i ) < 0 for all r < s; we can associate (i) the ordered partition I 1 , . . . , I m of [n] given by I r = i γ r (a i ) = 0 , (ii) the sequence of non-tope covectors X 1 , . . . , X m obtained by considering the sign of evaluating γ r on each of the points of A, and (iii) the sequence F 1 , . . . , F m of faces of Z( Ā), where F r is the face of Z( Ā) minimized by the linear functional r : R d+1 → R given by (x, x d+1 ) → u r , xc r x d+1 .

One can easily check that the conditions imposed on γ 1 , . . . , γ m imply that these sequences are a pseudo-sweep of A, a cellular string of H Ā with respect to the all-positive tope + n , and a h-monotone cellular string of Z( Ā), respectively. And Fig. 12 The pseudo-sweeps of the point configuration B 2 . Without the trivial sweep, they index a non-pure cellular complex that retracts to the boundary of the sweep polytope S P(B 2 ) from Fig. 4, a 1-sphere conversely, for any pseudo-sweep or cellular string of H Ā or Z( Ā), one can find such a sequence of affine functionals. This is direct for pseudo-sweeps and cellular strings of H Ā. For cellular strings F 1 , . . . , F m of Z( Ā), we associate to each face F r an affine map γ r obtained by restricting the linear functional minimized by F r in Z( Ā) to the hyperplane x d+1 = 1. The map that associates the partition I 1 , . . . , I m to the sequence X 1 , . . . , X m with (X r ) i = 0 if i ∈ I r , (X r ) i =if i ∈ I s with s < r and (X r ) i = + if i ∈ I s with s > r , is hence a bijection between pseudo-sweeps and cellular strings of H Ā. And similarly the map that sends a cellular string X 1 , . . . , X m of H Ā to the cellular string F 1 , . . . , F m of Z( Ā) given by

F r = (X r ) i =+ {-āi } + (X r ) i =- { āi } + (X r ) i =0 [-āi , āi ]
is also a bijection.

The second part of the statement arises from the observation that these bijections are order-preserving.

In particular, we can define pseudo-sweeps of a realizable oriented matroid in terms of its cellular strings. We extend this definition to abstract oriented matroids. Definition 6.2 A pseudo-sweep of an acyclic oriented matroid M is an ordered partition (I 1 , . . . , I m ) arising from a cellular string (X 1 , . . . , X m ) of

M via I i = S(X i • + n , X i • -n ), that is, I i is the set of zeros of X i .
123 Remark 6. [START_REF] Alon | The number of small semispaces of a finite set of points in the plane[END_REF] If A is a (full-dimensional) admissible projective transformation of A, then any sweep of A gives rise to a pseudo-sweep of A. Indeed, under an admissible projective transformation a pencil of parallel hyperplanes is mapped into a pencil of hyperplanes containing a codimension 2 flat that does not intersect conv( A). The ksets defined by these hyperplanes clearly give rise to a pseudo-sweep. However, not all pseudo-sweeps arise this way. For example, if {a 1 , . . . , a 6 } are the vertices of a regular hexagon in cyclic order, then [START_REF] Angel | The local limit of random sorting networks[END_REF][START_REF] Athanasiadis | Monotone paths on polytopes[END_REF][START_REF] Alon | The number of small semispaces of a finite set of points in the plane[END_REF][START_REF] Andrzejak | In between k-sets, j-facets, and i-faces: (i, j)-partitions[END_REF][START_REF] Athanasiadis | Monotone paths on zonotopes and oriented matroids[END_REF][START_REF] Angel | Random sorting networks[END_REF] is a pseudo-sweep permutation that is not a sweep of any of its projective transformations. (Because in every realization the vector a 6a 3 is a positive linear combination of the vectors a 1a 2 and a 5a 4 .) Remark 6.4 (Pseudo-sweeps and shellings) One of Stanley's motivations for studying sweep permutations in [START_REF] Stanley | Valid orderings of real hyperplane arrangements[END_REF] is that they are in correspondence with Bruggesser-Mani line-shelling orders of polytopes [START_REF] Bruggesser | Shellable decompositions of cells and spheres[END_REF]. For a convex polytope P and a line through its interior, this is the order in which the facets of P become visible to a point following from the interior of P to infinity, plus the order in which the remaining facets lose visibility when the point returns from the opposite side to the interior of P along . Now, let P • be the polar of P with respect to an interior point p of P, and let be a line through p. (Here, we are considering the usual projective polarity, as in [62, Sec. 5.1], but after a translation byp.) Since contains p, which is mapped to the hyperplane at infinity by polarity, the set of points in corresponds to a family of parallel affine hyperplanes orthogonal to a common direction. The shelling order given by coincides with the sweep permutation of the vertices of P • with respect to this direction. Thus, sweep permutations of a point configuration in convex position are in bijection with line shelling orders of the polar polyhedron for lines that go through the center of polarity (here, the origin, which is the image of the hyperplane at infinity).

Actually, not only sweeps, but all pseudo-sweeps, give rise to shelling orders. And this is true in the more general level of oriented matroids. Indeed, every pseudo-sweep of M induces a shelling order of the (Edmonds-Mandel) face lattice of the tope + n [36, Sec. 3.VI], see also [START_REF] Björner | Oriented Matroids, Encyclopedia of Mathematics and its Applications[END_REF]Sec. 4.3]. (To the best of our knowledge, it is still an open problem whether the opposite of this lattice, called the Las Vergnas face lattice, is shellable.) Pseudo-sweep shellings have been recently rediscovered by Heaton and Samper in the special case of matroid polytopes under the name of broken line shellings [START_REF] Heaton | Dual matroid polytopes and internal activity of independence complexes[END_REF].

The Poset of Pseudo-sweeps and the Generalized Baues Problem

Just like sweeps, pseudo-sweeps can be naturally ordered by refinement. We denote by (M, T ) the poset of pseudo-sweeps of M. Topological properties of this poset have been studied in the context of a special case of the generalized Baues problem (GBP) of Billera and Sturmfels [START_REF] Billera | Fiber polytopes[END_REF] concerning the homotopy of the poset of subdivisions induced by a projection of polytopes; see [START_REF] Reiner | The generalized Baues problem, New perspectives in algebraic combinatorics[END_REF] for a nice survey. We recall that by the topology of a poset P we mean the topology of its order complex (P): the simplicial complex whose simplices are the chains of P (see [START_REF] Björner | Topological Methods[END_REF] or [START_REF] Björner | Oriented Matroids, Encyclopedia of Mathematics and its Applications[END_REF]Sec. 4.7]).

Billera, Kapranov and Sturmfels [START_REF] Billera | Cellular strings on polytopes[END_REF]Thm. 2.3] showed that the strong version of the GBP, as considered in [71, Q. 2.3], holds for monotone paths of polytopes. This implies that, in the realizable case, the poset of sweeps of a point configuration is a deformation retract of the poset of pseudo-sweeps. For the case of zonotopes, Björner [13, Thm. 2] gave an alternative combinatorial proof for the weak version of the GBP (in the sense of [71, Q. 2.2]) that extends to oriented matroids. Namely, he proved that the poset of pseudo-sweeps of an oriented matroid is homotopy equivalent to a sphere (once the trivial sweep ([n]) is removed). A further generalization to shellable CW-spheres, for an appropriate definition of cellular strings induced by shellings, was proven in [START_REF] Athanasiadis | Monotone paths on polytopes[END_REF]. Theorem 6.5 [START_REF] Björner | Essential chains and homotopy type of posets[END_REF]Thm. 2]) The poset of pseudo-sweeps of an oriented matroid M of rank r with respect to a tope T without the trivial sweep has the homotopy type of an (r -2)-sphere.

Note that, by Corollary 3.9, for oriented matroids that admit a sweep oriented matroid (in the sense that they are the little oriented matroid of some sweep oriented matroid) the poset of sweeps is an explicit (r -2)-sphere embedded in the poset of pseudo-sweeps. We will show that it is in fact a deformation retract; thus proving the strong GBP for cellular strings of little oriented matroids. In the realizable case, this holds by [START_REF] Billera | Cellular strings on polytopes[END_REF]Thm. 2.3]. In the more general case, Björner also remarks that he expects the poset of pseudo-sweeps to retract to a subcomplex homeomorphic to a (r -2)-sphere [13, below Thm. 2], but does not provide a candidate subcomplex. Theorem 6.6 Let M lit be the little oriented matroid of a sweep oriented matroid M sw . Then the poset of sweeps of M sw is a strong deformation retract of the poset of pseudosweeps of M lit ; and the poset of non-trivial sweeps is a strong deformation retract of the poset of non-trivial pseudo-sweeps.

The proof of Theorem 6.6 needs some auxiliary results concerning (combinatorial) homotopy theorems. We refer to [START_REF] Björner | Topological Methods[END_REF] for a very good introduction to the topic. First, we present a result that allows us to weaken the statement to prove, as a consequence of the fact that the homotopy extension property holds for order complexes of subposets (c.f. [53, Ch. 0]). Then we recall three results on the homotopy type of posets: the Carrier Lemma, Quillen's Fiber Theorem and Babson's Lemma (the last two being corollaries of the first one). Next, inspired by [START_REF] Athanasiadis | Monotone paths on polytopes[END_REF], we use the function that returns the first part of an ordered partition to show the contractibility of some subsets of pseudo-sweeps and sweeps, thanks to Babson's Lemma. Finally, we combine all these results to prove that the inclusion induces a homotopy equivalence.

The first result that we need shows that it suffices to prove a weaker statement, namely that the inclusion is a homotopy equivalence. A CW pair of a cell complex (such as a simplicial complex) is a pair (X , A) consisting of a cell complex X and a subcomplex A. In particular, if S is a subposet of P, then ( (P) , (S)) is a CW pair. Lemma 6.7 ([53, Prop. 0.16 and Cor. 0.20]) If (X , A) is a CW pair and the inclusion A → X is a homotopy equivalence, then A is a strong deformation retract of X .

We will use the following version of the Carrier Lemma, from [START_REF] Björner | Topological Methods[END_REF]. For a simplicial complex and a space T , let C : → 2 T be an order-preserving map (C(σ

) ⊆ C(τ ) for all σ ⊆ τ ). A mapping f : → T is carried by C if f ( σ ) ⊆ C(σ ) for 123
all σ ∈ , where • denotes the associated geometric realization of the simplicial complex.

Lemma 6.8 (Carrier Lemma [START_REF] Björner | Topological Methods[END_REF]Lem. 10.1]) Let C : → 2 T be an order-preserving map such that C(σ ) is contractible for all σ ∈ . If f , g : → T are both carried by C, then f and g are homotopy equivalent, f ∼ g.

We will also need Quillen's Fiber Theorem [START_REF] Quillen | Homotopy properties of the poset of nontrivial p-subgroups of a group[END_REF]. For a poset Q and x ∈ Q, let Q ≥x = y ∈ Q y ≥ x . For the claim about the carrier, see the proof in [START_REF] Björner | Topological Methods[END_REF]Thm. 10.5]. Theorem 6.9 (Quillen's Fiber Theorem [START_REF] Quillen | Homotopy properties of the poset of nontrivial p-subgroups of a group[END_REF]) Let f : P → Q be an order-preserving map of posets. If f -1 (Q ≥x ) is contractible for all x ∈ Q, then f induces a homotopy equivalence between (P) and (Q) whose homotopy inverse is carried by C(σ

) = f -1 (Q ≥min σ ).
For this variant of Quillen's Fiber Theorem, known as Babson's Lemma [7, Lem. 1 in Sec. 0.4.3], see also [START_REF] Sturmfels | Extension spaces of oriented matroids[END_REF]Lem. 3.2]. Lemma 6.10 (Babson's Lemma [START_REF] Babson | A combinatorial flag space[END_REF]) If an order-preserving map of posets f : P → Q fulfills (i) f -1 (x) is contractible for all x ∈ Q, and (ii) f -1 (x) ∩ P ≥y is contractible for all x ∈ Q and y ∈ P with f (y) ≤ x, then f induces a homotopy equivalence between (P) and (Q).

Moreover, we will need the following lemmas certifying the contractibility of certain subsets of pseudo-sweeps and sweeps. If F ⊆ [n] is the zero-set of a nonnegative covector Z of M lit , we denote by (M sw ) ⊆F the sets of sweeps (I 1 , . . . , I m ) with I 1 ⊆ F. Similarly, we denote by (M lit , + n ) ⊆F the sets of pseudo-sweeps (I 1 , . . . , I m ) with I 1 ⊆ F. Lemma 6.11 Let F ⊆ [n] be the zero-set of a non-negative covector Z of M lit , then

(M lit , + n ) ⊆F is contractible.
Proof The proof of [2, Lem. 5.5] can be adapted to prove that (M lit , + n ) ⊆F is contractible. First, we note that with the same proof we can make a slightly stronger statement. Namely, they define a map f : ω(P, O, a) → D(P, O, a), between certain posets ω(P, O, a) and D(P, O, a) that we describe below, and show that it induces a homotopy equivalence. However, the exact same proof also shows that f : ω(P, O, a) ∩ f -1 (I ) → I induces a homotopy equivalence for any order ideal (lower set) I of D(P, O, a).

To match their notations, we call P the poset opposite to the big face lattice of M lit (the atoms of P are the topes of M lit and its 1-skeleton is the tope graph) and O the orientation of the tope graph that goes fromn to + n . For a tope a, the poset ω(P, O, a) is the poset of partial cellular strings ending at a (i.e. sequences of non-tope covectors (X 1 , . . . , X m ) such that X 1 •n =n , X m • + n = a, and X i • + n = X i+1 •n for all i). Therefore taking a = a max = + n we have that ω(P, O, a max ) = ω(P, O) is exactly the poset of cellular strings of M lit with respect ton , which is in bijection with (M lit , + n ). However, their partial order is the opposite of our refinement order and the cellular strings have to be read in reverse order. The poset D(P, O, a) is the poset of the non-tope covectors X such that X • + n = a. Therefore, D(P, O, a max ) corresponds to the half-interval [0, + n ) in the face lattice of M lit .

If we take I the lower set of D(P, O, a max ) corresponding to the interval [Z , + n ), their function f : ω(P, O, a max ) ∩ f -1 (I ) → I corresponds to the function that sends the pseudo-sweep (I 1 , . . . , I m ) ∈ (M lit , + n ) ⊆F to the non-negative covector Y ∈ [Z , + n ) with zero-set I 1 . Hence it induces a homotopy equivalence from (M lit , + n ) ⊆F to [Z , + n ), which has a contractible order poset because it has a unique minimal element.

We wish to prove the same when restricted to sweeps. For this, we use an auxiliary result from [START_REF] Bandelt | COMs: complexes of oriented matroids[END_REF]. Let M ⊆ {+, -, 0} E be the set of covectors of an oriented matroid on E. Then, each element e ∈ E defines two halfspaces X ∈ M X e = + and X ∈ M X e = -, and a hyperplane X ∈ M X e = 0 . Lemma 6.12 Let M be the set of covectors of an oriented matroid. Then, any nonempty intersection of one or more halfspaces and hyperplanes, seen as a subposet of the face lattice, is contractible.

Proof This is a consequence of [START_REF] Bandelt | COMs: complexes of oriented matroids[END_REF]Prop. 15]. Indeed, an intersection of halfspaces and hyperplanes is a COM, because it satisfies Face symmetry and Strong elimination, see (i) f -1 (Y ) is the set of sweeps whose first part is G. It is not empty because Y must be of the form Ỹ 1 for a covector Ỹ ∈ M sw (in the sense of Definition 4.2), and such Ỹ corresponds to a sweep with first part G. Moreover, f -1 (Y ) is the intersection of halfspaces X ∈ M sw X (i, j) = + for all i ∈ G, j / ∈ G and i < j, and X ∈ M sw X (i, j) =for all i ∈ G, j / ∈ G and i > j. By Lemma 6.12 it is contractible. (ii) Let J = (J 1 , . . . , J r ) be a sweep in (M sw ) ⊆F such that f (J ) ≤ Y , i.e. G ⊆ J 1 .

The intersection f -1 (Y ) ∩ ( (M sw ) ⊆F ) ≥J is the set of sweeps that refine J and whose first part is G. As for f -1 (Y ), this set is an intersection of halfspaces. It is not empty because it contains the sweep corresponding to J • Ỹ . Hence it is contractible.

It follows from Babson's Lemma that (M sw ) ⊆F is homotopy equivalent to [Z , + n ), which has a contractible order poset because it has a unique minimal element. Definition 7.4 A set of permutations ⊆ S n is symmetric if σ ∈ for all σ ∈ , where σ is the reverse of σ , defined by σ (t) = σ (nt + 1) for all t ∈ [n]. Definition 7.5 Consider a set of permutations ⊆ S n and a set L of moves such that:

(P1)
is symmetric, (P2) for any σ, σ ∈ , there is an allowable sequence from σ to σ whose moves belong to L, (P3) for m, s ∈ L, either inv m = inv s or inv m ∩ inv s = ∅.

The graph with vertex set and whose edges are the pairs of permutations differing by a move in L is an allowable graph of permutations.

An allowable graph of permutations is simple if L consists only of simple moves.

Lemma 7. [START_REF] Andrzejak | In between k-sets, j-facets, and i-faces: (i, j)-partitions[END_REF] The graph is completely determined by and does not depend on L. More precisely, σ, σ ∈ form an edge if and only if there is no σ ∈ \ {σ } such that inv(σ ) inv(σ ) inv(σ ) inv(σ ).

Proof Suppose that σ, σ ∈ form an edge. It means that there is a move m in L with inversion set inv(σ ) inv(σ ). Suppose that σ ∈ L satisfies inv(σ ) inv(σ ) ⊆ inv(σ ) inv(σ ). For any move m in L along an allowable sequence from σ to σ we have inv m ⊆ inv(σ ) inv(σ ), thus inv m ∩ inv m = ∅. We deduce from (P3) that inv m = inv m , thus inv(σ ) inv(σ ) = inv(σ ) inv(σ ).

Reciprocally, suppose that σ, σ ∈ do not form an edge and let σ ∈ \ {σ } be the neighbor of σ on an allowable sequence from σ to σ . By (M2), we have inv(σ ) inv(σ ) ⊆ inv(σ ) inv(σ ), as if there was a pair in inv(σ ) inv(σ )\ inv(σ ) inv(σ ), then it would be reversed twice in the allowable sequence: first between σ and σ and later between σ and σ . Moreover, σ = σ because σ and σ form an edge, and thus inv(σ ) inv(σ ) = inv(σ ) inv(σ ).

We will therefore usually identify with the corresponding allowable graph, and directly call an allowable graph of permutations. Remark 7. [START_REF] Babson | A combinatorial flag space[END_REF] The set of moves can be recovered from the graph by gathering all moves between adjacent permutations in the graph.

Remark 7.8 If

forms an allowable graph of permutations and ω ∈ S n , then ω • = ω • σ σ ∈ is still an allowable graph of permutations. Sometimes it is convenient to suppose that the identity permutation id belongs to , as Goodman and Pollack did, which can always be obtained by multiplying by an ω that is the inverse of a permutation in . Remark 7.9 Note that in the case of a simple allowable graph of permutations Condition (P3) is redundant. However, the example of Fig. 13 shows that it is necessary in the general case and this is why we needed to fix a set of moves in Definition 7.5.

In this example, a valid set of moves L would necessarily contain all the moves represented with the arrows (and their reverse), which are all the singletons {[i, j]} for (i, j) ∈ [n] 2 . However, in order to satisfy Condition (P2), L also has to contain the move { [START_REF] Angel | The local limit of random sorting networks[END_REF][START_REF] Athanasiadis | Monotone paths on polytopes[END_REF], [START_REF] Alon | The number of small semispaces of a finite set of points in the plane[END_REF][START_REF] Angel | Random sorting networks[END_REF]} represented by the dashed segment joining permutations Fig. [START_REF] Björner | Essential chains and homotopy type of posets[END_REF] Example of a set of permutations that do not satisfy the definition of allowable graph of permutations. Neither graphs with or without the dashed segment are partial cubes [START_REF] Alon | The number of small semispaces of a finite set of points in the plane[END_REF][START_REF] Angel | Random sorting networks[END_REF][START_REF] Athanasiadis | Monotone paths on zonotopes and oriented matroids[END_REF][START_REF] Athanasiadis | Monotone paths on polytopes[END_REF][START_REF] Angel | The local limit of random sorting networks[END_REF] and (4, 3, 5, 1, 2), since there is no other allowable sequence between these two permutations. Indeed, we can see that the edges adjacent to [START_REF] Alon | The number of small semispaces of a finite set of points in the plane[END_REF][START_REF] Angel | Random sorting networks[END_REF][START_REF] Athanasiadis | Monotone paths on zonotopes and oriented matroids[END_REF][START_REF] Athanasiadis | Monotone paths on polytopes[END_REF][START_REF] Angel | The local limit of random sorting networks[END_REF] are labeled [START_REF] Athanasiadis | Monotone paths on polytopes[END_REF][START_REF] Athanasiadis | Monotone paths on zonotopes and oriented matroids[END_REF] and [START_REF] Angel | Random sorting networks[END_REF][START_REF] Athanasiadis | Monotone paths on zonotopes and oriented matroids[END_REF] but those pairs should not be reversed on an allowable sequence to (4, 3, 5, 1, 2). Thus, both conditions (P3) and (P2) cannot be satisfied simultaneously.

We need to have both conditions in order to have the structure of acycloids, as stated in Theorem 7.12.

Sweep Acycloids

Acycloids are combinatorial objects widely studied in connection with the characterization of tope sets of oriented matroids, c.f. [START_REF] Fukuda | Antipodal graphs and oriented matroids[END_REF][START_REF] Handa | A characterization of oriented matroids in terms of topes[END_REF]. They are equivalent to antipodal partial cubes (see [START_REF] Knauer | On tope graphs of complexes of oriented matroids[END_REF]), a concept well-studied in metric graph theory. A graph is a partial cube if it is (isomorphic to) an isometric subgraph of a hypercube graph, and it is antipodal (also called symmetric even [START_REF] Berman | Cross-cloning and antipodal graphs[END_REF]) if for every vertex v there exists exactly one vertex ṽ, called the antipode of v, such that the distance from v to ṽ is larger than the distance from v to any neighbor of ṽ. 123 Definition 7.13 A sweep acycloid is an acycloid on the ground set [n] 2 such that (i) its topes fulfill the transitivity condition from Lemma 3.8; namely for every covector X and every choice of 1 ≤ i < j < k ≤ n, the triple (X (i, j) , X ( j,k) , X (i,k) ) is orthogonal to the sign vector (+, +, -), and (ii) its parallelism classes verify the transitivity condition Definition 7.2; namely, if (i, j) or ( j, i) coincides with ( j, k) or (k, j), then it also coincides with (i, k)

or (k, i).

As we show in Proposition 7.15 below, sweep acycloids are essentially equivalent to allowable graphs of permutations. The only nuance is that sweep acycloids might have some elements outside its support, which under the map (5) would give rise to some partitions that are not permutations. In this case, there would be pairs of elements that belong to the same part in all the partitions. However, up to merging nonsingleton parts and relabeling, one can suppose that these maximal ordered partitions are permutations. We recover then an allowable graph of permutations.

These operations of merging and relabeling do not affect the tope-graphs.

Lemma 7.14 Let T ⊆ {+, -, 0} ( [n]
2 ) be a sweep acycloid with support S ⊆

[n] 2 . For 1 ≤ i < j ≤ n, if (i, j) / ∈ S, then the restriction of T to [n] { j} 2 is a sweep acycloid with isomorphic tope-graph.
Proof That this restriction is a sweep acycloid is straigthforward from the definition. Moreover, from the characterization in Lemma 3.8 one sees that for X ∈ T and k = i, j, the values of X on the pairs (i, k) (resp. (k, i)) and ( j, k) (resp. (k, j)) determine each other uniquely (the sign depending on the relative order of i, j, k), because X (i, j) = 0. Therefore, there is a bijection between topes (resp. parallelism classes) of T and topes (resp. parallelism classes) of the restriction.

If T is the tope set of a sweep acycloid, we denote by T = I X X ∈ T the set of associated ordered partitions. Theorem 7.15 If ⊆ S n forms an allowable graph of permutations, then T is the set of topes of a sweep acycloid. Conversely, if T is the tope set of a sweep acycloid of full support [n] 2 , then T forms an allowable graph of permutations.

Proof The first claim follows directly from Theorem 7.12. Indeed, the topes of the form X σ for a permutation σ ∈ S n fulfill the transitivity condition from Lemma 3.8 by construction. Moreover, the parallelism classes of T are the moves of by Lemma 7.11, and they fulfill condition Definition 7.2 by definition.

For the second claim, note first that T is clearly symmetric by (T2). Following Lemma 7.11, we set L to be the moves whose inversion sets are parallelism classes of the topes. By construction, two distinct moves in this family are either disjoint, or they are reverse to each other and have the same set of inversions.

Finally, let σ X , σ Y ∈ T be the permutations associated to the topes X , Y ∈ T . We will prove that they are joined by an allowable sequence by induction on the cardinality of the symmetric difference of their inversion sets. By the reorientation property (T3),

123 there is an element f ∈ S(X , Y ) such that Z = -f X ∈ T . The parallelism class f corresponds to a move m ∈ L such that inv m ⊆ inv σ X inv σ Y . Hence, Z is associated to a permutation σ Z such that inv σ Z inv σ Y = (inv σ X inv σ Y )\ inv m . By induction there is an allowable sequence σ Z → • • • → σ Y with labels in L. Note that m is not a label of this path because its inversion set is disjoint from inv σ Z inv σ Y . Then, σ X m -→ σ Z → • • • → σ Y is an allowable sequence from σ X to σ Y .

Sweeps and Potential Sweeps of Sweep Acycloids

With Handa's notation from [START_REF] Handa | Topes of oriented matroids and related structures[END_REF], a face of an acycloid T ⊆ {+, -, 0} E is a signvector X ∈ {+, -, 0} E such that X • T ∈ T for all T ∈ T ; and a coboundary of T is a sign-vector X ∈ {+, -, 0} E that conforms to a tope (which means that there is a tope that refines it) and such that, for every T ∈ T with X • T = T we have X • (-T ) ∈ T . In the language of partial cubes, faces correspond to gated subgraphs, and coboundaries are antipodal subgraphs. In an acycloid, every gated subgraph is antipodal, which shows that every face is a coboundary (see [START_REF] Knauer | On tope graphs of complexes of oriented matroids[END_REF] for definitions and details). In general, the converse is not true. However, if T is the set of topes of an oriented matroid, then faces and coboundaries coincide, and correspond to the covectors of the oriented matroid.

Augmented with a top element, the set of faces of an acycloid forms a lattice, the big face lattice of the acycloid [START_REF] Handa | Topes of oriented matroids and related structures[END_REF]. Face lattices of acycloids lack many nice properties of those of oriented matroids. In particular, they are not always graded.

We can translate these concepts to sweeps. To this end, define the composition I • J of two ordered partitions I = (I 1 , . . . , I l ) and J = (J 1 , . . . , J l ) of [n] as I • J = (I 1,1 , . . . , I 1,r 1 , . . . , I l,1 , I l,r l ), where for any k ∈ {1, . . . , l}, (I k,1 , . . . , I k,r k ) is the sequence (I k ∩ J 1 , I k ∩ J 2 , . . . , I k ∩ J l ) where the empty parts are removed. That is, the ordered partition of the elements of I k induced by J . Definition 7. [START_REF] Billera | Cellular strings on polytopes[END_REF] Let ⊆ S n be an allowable graph of permutations.

• A sweep of is an ordered partition I such that I • σ ∈ for all σ ∈ . • A potential sweep of is an ordered partition I of [n] refined by some permutation in and such that any sweep permutation σ ∈ that refines I satisfies I • σ ∈ .

Lemma 7.17 Let ⊆ S n form an allowable graph of permutations and let T be its associated sweep acycloid. Then the sweeps of are in bijection with the faces of T and the potential sweeps of are in bijection with the coboundaries of T .

Proof We prove first the equivalence between potential sweeps and coboundaries. It is clear that X I is a coboundary of T for any potential sweep I of . Indeed, if σ refines I , it implies that X I conforms to X σ , i.e.

X I • X σ = X σ . Moreover, I • σ ∈ implies that X I • (-X σ ) = X I • X σ = X I •σ is in T .
For the converse statement, let Y be a coboundary of T . We need to show that it is of the form X I for an ordered partition I of [n]. Then it is clear from the definitions that I is a potential sweep of . Suppose that there are 1 ≤ i < j < k ≤ n such that (Y (i, j) , Y ( j,k) , Y (i,k) ) is one of the forbidden patterns in Lemma 3.8. Let σ ∈ be a sweep permutation such that Z := Y • X σ = X σ . We denote σ the permutation in such that Z := Y • (-X σ ) = X σ . The fact that Z and Z satisfy the transitivity condition implies that the forbidden pattern of Y must be one of the last six ones (with two zeroes). We consider the case (Y (i, j) , Y ( j,k) , Y (i,k) ) = (0, 0, -), the other ones are similar. Then we must have {(Z (i, j) , Z ( j,k) , Z (i,k) ), ( Z(i, j) , Z( j,k) , Z(i,k) )} = {(+, -, -), (-, +, -)}, i.e. the elements i, j, k are ordered k, i, j and j, k, i in σ and σ . As a consequence of condition Definition 7.2, in any allowable sequence in from σ to σ , there must be a permutation where the elements i, j, k are ordered k, j, i. Such τ satisfies Y • X τ = X τ . Indeed, any pair (k, l) with Y (k,l) = 0 satisfies Z (k,l) = Z(k,l) , thus it cannot be reversed in an allowable sequence from σ to σ . But then the covector Y • (-X τ ) should belong to T while it has the forbidden pattern (+, +, -). We conclude that any coboundary satisfies the transitivity condition from Lemma 3.8.

To finish, it is clear that any sweep I of gives a covector

X I ∈ {+, -, 0} ( [n]
2 ) such that for any σ ∈ , X I • X σ = X I •σ ∈ T , thus X I is a face of T . For the converse, note that any face Y of T is a coboundary, and hence it must be of the form X I associated to a potential sweep I . The condition of being a face shows that this potential sweep is indeed a sweep.

Note in particular that the poset of sweeps of an allowable graph of permutations, augmented with a top element, is always a lattice, as it is isomorphic to the big face lattice of an acycloid.

Sweep Oriented Matroids from Sweep Acycloids and Allowable Graphs of Permutations

The set of topes of an oriented matroid is always an acycloid, but the converse statement is not true. However, the conditions in the definition of sweep acycloid guarantee that, whenever they correspond to an oriented matroid, it is a sweep oriented matroid. Note that, for this, the transitivity condition Definition 7.2 on the parallelism classes of sweep acycloids is necessary. Indeed, (+, +, +), (-, -, -), (-, +, +), (+, -, -) satisfy the conditions of Lemma 3.8 (they are orthogonal to (+, +, -)) and they are the topes of an oriented matroid, but not a sweep oriented matroid. This gives an acycloid whose topes fulfill the transitivity condition from Lemma 3.8 and that arises from an oriented matroid, but that is not a sweep oriented matroid. However, thanks to Lemma 7.17, we know that the conditions on topes and subtopes in the definition of sweep acycloids extend to the whole set of covectors.

Corollary 7.18

The set of topes of a sweep oriented matroid is a sweep acycloid. Conversely, if a sweep acycloid is the set of topes of an oriented matroid, then it is a sweep oriented matroid.

The following hierarchy summarizes our current knowledge: Theorem 7. [START_REF] Bonin | Extending a matroid by a cocircuit[END_REF] 123

Posets of sweeps of point configurations

Posets of sweeps of sweep oriented matroids

⊆

Posets of sweeps of sweep acycloids

Goodman and Pollack's unrealizable pentagon proves that the first inclusion is strict. For the second inclusion, it is known that there are acycloids that are not oriented matroids, but we do not know of any example that has the additional structure given by the transitivity condition from Lemma 3.8.

Corollary 7.18 allows us to use characterizations of acycloids arising from oriented matroids to characterize which allowable graphs of permutations arise from sweep oriented matroids. We know three families of such characterizations, summarized in [START_REF] Knauer | On tope graphs of complexes of oriented matroids[END_REF]Cor. 7.2]. In the language of permutations, da Silva's characterization [START_REF] Da Silva | Axioms for maximal vectors of an oriented matroid: a combinatorial characterization of the regions determined by an arrangement of pseudohyperplanes[END_REF]Thm. 4.1] concerns sweeps and potential sweeps. Handa's characterization is stated in terms of contractions. If is an allowable graph of permutations, and m ∈ L is one of its moves, the elementary contraction /m is obtained by taking all permutations γ ∈ that are separated from another permutation of by m, and replacing the substring m by its minimal element. One obtains this way a new set of permutations on the ground set [n] m ∪ {min(m)}. For a collection of moves M = {m 1 , . . . , m l }, the contraction /M, is defined inductively by /M = ((( /m 1 )/m 2 ) • • • )/m l . The characterization by Knauer and Marc [57,Cor. 7.2] is in terms of excluded partial cube minors. This operation goes outside the scope of allowable graphs of permutations. We will hence not present its details and refer the reader to the source [START_REF] Knauer | On tope graphs of complexes of oriented matroids[END_REF].

Corollary 7.20 Let form an allowable graph of permutations. The following conditions are equivalent: (i)

arises from a sweep oriented matroid, (ii) every potential sweep of is a sweep, (iii) all its contractions are allowable graphs of permutations, (iv) the graph is in F(Q -) in the sense of [START_REF] Knauer | On tope graphs of complexes of oriented matroids[END_REF].

These characterizations might be useful to answer the question whether all sweep acycloids are sweep oriented matroids. We have not been able to construct any counterexample, but we do not have any evidence on why the properties defining sweep acycloids should force these conditions to be satisfied.

Further Directions

Elementary Homotopies Between Sweep Oriented Matroids

In [START_REF] Felsner | Geometric graphs and arrangements, Some chapters from combinatorial geometry[END_REF][START_REF] Felsner | Sweeps, arrangements and signotopes[END_REF] it is proven that if an allowable sequence has two consecutive moves with disjoint support, then these can be merged into a single move and the result is still an allowable sequence; and that conversely, if a move consists of more than one disjoint substrings, these can be split into two disjoint moves. These operations induce an equivalence relation among sweep oriented matroids of rank 2 whose equivalence classes are in correspondence with the associated little oriented matroids.

Extending this result to higher rank is closely related to some of the open questions indicated in the paper. First of all, the higher analogue of the operation of merging would consist in collapsing some flats of a sweep oriented matroid to get a flat whose rank is lower than the one expected by [START_REF] Andrzejak | In between k-sets, j-facets, and i-faces: (i, j)-partitions[END_REF]. The reverse operation would break a flat with unexpected low rank into pieces fulfilling [START_REF] Andrzejak | In between k-sets, j-facets, and i-faces: (i, j)-partitions[END_REF]. Understanding this procedure would provide a method to prove Conjecture 5.4.

Even if the operations were well described, it is not clear that one could find a connectivity result analogous to that by Felsner and Weil in rank 2 [START_REF] Felsner | Sweeps, arrangements and signotopes[END_REF]. Note that, even if Theorem 6.6 goes in this direction, as it shows that all sweep oriented matroids are homotopy equivalent in the complex of pseudo-sweeps, it is not clear that there is a way to do this where all the intermediate steps are also sweep oriented matroids.

Are All Sweep Acycloids Oriented Matroids?

Another natural problem that is left open is Question 7.21, which asks whether every sweep acycloid is an oriented matroid. The answer would be very interesting in either direction. If it is affirmative, then the two categories of sweep acycloids and sweep oriented matroids would collapse into a single concept. This would make allowable graphs of permutations a useful alternative characterization of sweep oriented matroids. If, on the contrary, the answer is negative, then it would be interesting to understand the gap between the two categories.

We do not have any good reason to conjecture that every sweep acycloid is an oriented matroid, beyond the fact that we could not find any. This does not tell much, because the naive approaches to computationally generate all allowable graphs of permutations of a certain size fail badly very soon because of the rapid growth of these objects.

Allowable Graphs in Coxeter Groups

We already saw the hyperoctahedral group B n naturally appear before. First, in Sect. 2.2.2, because the permutahedron of type B is the sweep polytope of the crosspolytope. Then also in Example 4.5 to explain the supersolvability of the associated matroid. In fact, the definition of allowable graph extends naturally to any Coxeter group, specially in the simple case; namely, a simple allowable graph of Coxeter permutations is a symmetric set of elements of the Coxeter group, in which for every pair of elements w, w ∈ there is a path from w to w following a reduced decomposition of w -1 w . For the non-simple case one has to partition the generators into a collection of disjoint subsets to define the allowable moves.

123 Fig. 14 The first row shows a generic and a degenerate 2nd higher 5-permutahedra. The second row depicts two combinatorially different generic 3rd higher 6-permutahedra

Higher Sweep Oriented Matroids and Permutahedra

As we saw in Sect. 5.1, sweep oriented matroids are closely related to the first Dilworth truncation. What about higher truncations? In the realizable case, instead of studying the intersection of the lines spanned by the points of A with a hyperplane (at infinity), we would study the intersection of a flat F of codimension k (playing the role of hyperplane at infinity) with every flat spanned by k + 1 points of A. In [80, Thm. 8], Stanley states (in the polar formulation) that for a sufficiently generic choice of the flat, this gives rise to an arrangement whose lattice of flats is the kth Dilworth truncation of the original arrangement. Let's call this operation the kth Dilworth truncation of A with respect to F. Doing the kth Dilworth truncation of an standard (n -1)simplex gives rise to "higher" analogues of braid arrangements, which are the normal fans of the kth higher n-permutahedra. However, in comparison with the k = 1 case, there is no S n -invariant subspace that gives a canonical choice for F. Indeed, different choices for F can give rise to different combinatorial types of hyperplane arrangements and zonotopes, even if the flats are sufficiently generic in the sense of Stanley. See Fig. 14 for some examples. Nevertheless, every zonotope associated to a kth Dilworth truncation of a point configuration still arises as the projection of some kth higher permutahedron.

Which Matroids are Little Oriented Matroids?

In Sect. 4.3 we proved that not every oriented matroid is a little oriented matroid. This begs the question of which are the oriented matroids that are sweepable, in the sense that they can be extended to a big oriented matroid. Or, at least, to find sufficient conditions. For example, we know that realizable oriented matroids are sweepable, and also all oriented matroids of rank 3, by Theorem 4.11.

As shown in [START_REF] Hochstättler | Topological sweeping in oriented matroids[END_REF], Euclidean oriented matroids (see [START_REF] Björner | Oriented Matroids, Encyclopedia of Mathematics and its Applications[END_REF]Section 10.5]) always admit topological sweepings (see Sect. 1.1). Is there a relation between being Euclidean and being sweepable? Our example of non-sweepable oriented matroid in Sect. 4.3 is based on a well-known example of non-Euclidean oriented matroid.

Proof We have to check that M satisfies the axioms of Definition 3.1, namely: (V0) 0 ∈ M big , (V1) X ∈ M big implies -X ∈ M big , (V2) X , Y ∈ M big implies X • Y ∈ M big , (V3) if X , Y ∈ M big and e ∈ S(X , Y ) then there exists Z ∈ M big such that Z e = 0 and Z f = (X • Y ) f for all f / ∈ S(X , Y ).

(V 0) 0 n ∈ M, associated to the one part ordered partition ({1, 2, . . . , n}). Then (0 n ) 2 is the zero vector and it is in M big .

(V 1) Let X k be an element of M big . Then, -X k = (-X ) 2l X +2-k , so it is still in M big . (V 2) Let X k , Y h be two elements of M big . Then X k • Y h = (X • Y ) t , where t = 2(r 1 + . . . + r k-1 2 -1 ) + 1 if k is odd (with the same notations as in the definition of the composition between two ordered partitions), t = 2(r 1 + . . . + r k 2 -1 ) + j if k is even and j is the index corresponding to h when the elements of I k are ordered according to Y (that is to say, for all i ∈ I k , p X •Y (i)

≤ t-1 2 ⇔ p Y (i) ≤ h-1 2 and p X •Y (i) > t 2 ⇔ p Y (i) > h 2 )
. (V 3) Let X k , Y h be two elements of M big , and e ∈ S(X k , Y h ). It remains to find Z ∈ M and r ∈ {1, . . . , 2l Z + 1} such that (Z r ) e = 0 and

(Z r ) f = (X k • Y h ) f for any f / ∈ S(X k , Y h
). e can be of two types: e = (i, j) or e = i. In both cases, it will be convenient to define Then E -∪ E + ∪ E 0 = {1, . . . , n}\S(X k , Y h ) and part of the condition is that (Z r ) p = ε for all p ∈ E ε , ε ∈ {-, +, 0}.

(1) If e = (i, j), up to exchanging X k and Y h , one can suppose that X (i, j) =and Y (i, j) = +. Let Z ∈ M be given by (V 3) on M. For any r we will have that (Z r ) e = 0 and (Z r ) f = (X k • Y h ) f for any f / ∈ S(X k , Y h ) of the form f = ( p, q), because in that case, f is an index for X and Y that is not in S(X , Y ). Can we find r such that (Z r ) p = (X k • Y h ) p for any 1 ≤ p ≤ n such that p / ∈ S(X k , Y h ) ? It is sufficient to check that p Z ( p) < p Z (q) for all ( p, q) ∈ E -× E + ∪ E -× E 0 ∪ E 0 × E + and p Z ( p) = p Z (q) for all ( p, q) ∈ E 0 × E 0 . ( p, q) ∈ E 0 × E 0 and p < q implies that X ( p,q) = Y ( p,q) = 0, hence Z ( p,q) = 0 and p Z ( p) = p Z (q). If E 0 = ∅, we take r = 2 p Z (q) for any q ∈ E 0 . Then, we treat the case ( p, q) ∈ E -× E 0 , since the case ( p, q) ∈ E 0 × E + is similar. If p < q, then {(X k ) ( p,q) , (Y h ) ( p,q) } ∈ {{+, +}, {+, 0}} and Z ( p,q) = +. If p > q, then {(X k ) (q, p) , (Y h ) (q, p) } ∈ {{-, -}, {-, 0}} and Z (q, p) = -. In any case, p Z ( p) < p Z (q), thus (Z r ) p = -. If E 0 = ∅, there may be several possibilities for r . The same reasoning as precedently shows that for any ( p, q) ∈ E -× E + , p Z ( p) < p Z (q). Hence there is at least one appropriate r which separates the parts that contain elements in E -from parts that contain elements in E + .

(2) If e = i for some 1 ≤ i ≤ n, up to exchanging X k and Y h , one can suppose that (X k ) i =and (Y h ) i = +. First, we consider the case where E 0 = ∅. We take Z = X • Y and r = 2 p X •Y (i) If E 0 = ∅, let j be the smallest element of E 0 . Than p X (i) < p X ( j) and p Y (i) > p Y ( j), thus (i, j) ∈ S(X , Y ). Let Z ∈ M be given by axiom (V 3) applied to M with X , Y and (i, j). Than, for any k ∈ E 0 other than j, Z ( j,k) = 0 because X ( j,k) = 0 and Y ( j,k) = 0 (resp. Z (k, j) = 0 because X (k, j) = 0 and Y (k, j) = 0), and thus Z (i,k) = 0 (resp. Z (k,i) = 0), because Z (i, j) = 0 and M satisfies the transitivity condition from Lemma 3.8. We choose r = 2 p Z (i) (corresponding to the part of Z that contains i and all k ∈ E 0 ). Then: For the proof of Corollary 4.10, recall that for any simple oriented matroid M on the ground set F, we call a valid decoration a couple of maps δ : F → 2 ( [n] 2 ) and : [n] 2 → {+, -} for a certain n, such that: • the decorations form a partition of [n] 2 , with empty parts accepted: [n] 2 = f ∈F δ( f ) with δ( f ) ∩ δ( f ) = ∅ whenever f = f ; and • the covectors X ∈ M, seen as elements of {+, -, 0} ( [n] 2 ) by considering X (i, j) = (i, j)X f if (i, j) ∈ δ( f ), satisfy the transitivity condition from Lemma 3.8. Corollary (4.10) If M is a simple oriented matroid on F with a valid decoration (δ, ), then M can be extended to a unique oriented matroid M for which F is a modular hyperplane and (δ, ) is the decoration of F induced by M.

(
In particular, an oriented matroid M with a modular hyperplane F is completely determined by M F together with the decoration of F induced by M.

Proof

The proof is very simple, as it relies entirely on Theorem 4.1, but it involves some auxiliary oriented matroids and some cumbersome notation to identify them.

With the help of the decoration, we will first add to M the elements of [n] 2 to get a new oriented matroid M on F ∪ [n] 2 . We do this by adding for each f ∈ F the

Fig. 2 A 3 Fig. 3 A

 233 Fig. 2 A 3 , its sweep hyperplane arrangement SH( A 3 ) = B 3 (modulo linearity), and its sweep polytope S P( A 3 ) = P 3 , the 3-permutahedron, where each vertex is labeled by the corresponding sweep permutation of A 3

Fig. 4 B 2 )Fig. 5 B 2 . 2 . 2

 425222 Fig. 4 B 2 , its sweep hyperplane arrangement SH(B 2 ), and its sweep polytope S P(B 2 )

Corollary 2 . 4

 24 Let M : R n → R d be a linear map, then M( P n ) is the sweep polytope of the point configuration M(e 1 ), . . . , M(e n ).

Lemma 2 . 7 (

 27 [START_REF] Billera | Fiber polytopes[END_REF] Lem. 2.3]) Let R n θ -→ R m π-→ R d be linear maps, and P ⊂ R n a polytope. Then (θ( P), π) = θ( ( P, π • θ )).

  Finally, by Proposition 2.3, we have M A ( P n ) = S P( A), and therefore Z( Ā), h = 2 n S P( A) × {0}.

Lemma 4 . 4

 44 If the sweep oriented matroid M is of rank r , then M big and M lit are of rank r + 1.

  i ∈ [±n] to the pair of parallel elements (-n -1, -i), (i, n + 1); 0 to the triple of parallel elements (-n -1, n + 1), (-n -1, 0), (0, n + 1); and leaving the pairs in[-n,n] 2unchanged. Each tope X of the sweep oriented matroid B B n is represented by a centrally symmetric permutation σ of [-n, n]:

2 i

 2 , j ∈ I }. ThenM I is a sweep oriented matroid with little oriented matroidM lit I , and their respective ranks are rk M lit (I )-1 and rk M lit (I ) by Lemma 4.4. Therefore, rk M (J ) = rk M lit (I ) -1, because the rank function of a restriction is just the restriction of the rank function, see [22, Prop 7.3.1].

[ 9 ,

 9 Def. 1]. Lemma 6.13 Let F ⊆ [n] be the zero-set of a non-negative covector Z of M lit , then (M sw ) ⊆F is contractible. Proof Inspired by the proof of [2, Lem. 5.5], we apply Babson's Lemma 6.10 with the function f from the subposet of sweeps (M sw ) ⊆F to the half-open interval of the face lattice [Z , + n ) that sends a sweep (I 1 , . . . , I m ) to the non-negative covector with zero-set I 1 .Let Y be a covector in [Z , + n ), with zero-set G ⊆ F.

Question 7 . 21

 721 Is every sweep acycloid an oriented matroid?

E

  -= p | 1 ≤ p ≤ n and {(X k ) p , (Y h ) p } ∈ {{-, -}, {0, -}} = p ∈ {1, . . . , n} \ S(X k , Y h ) | (X k • Y h ) p = -, E + = p | 1 ≤ p ≤ n and {(X k ) p , (Y h ) p } ∈ {{+, +}, {0, +} , E 0 = p | 1 ≤ p ≤ n and {(X k ) p , (Y h ) p } = {0, 0} .

  with the same notations as in Proposition 2.3 and Example 2.6. Hence, Lemma 2.7 and Example 2.6 give (Z 1

  corresponding to the part of i in Z ). It only remains to check that if p ∈ E -(resp. E + ), than (Z r ) p = -(resp. +). p ∈ E -⇒ p Y ( p) < p Y (i) ⇒ p Z ( p) < p Z (i) ⇒ (Z r ) p = -, p ∈ E + ⇒ p X ( p) > p X (i) ⇒ p Z ( p) > p Z (i) ⇒ (Z r ) p = +.

Our definition differs slightly from that in[START_REF] Björner | Oriented Matroids, Encyclopedia of Mathematics and its Applications[END_REF] Sect. 1.10] We admit parallel vectors when the configuration is not generic, whereas in[START_REF] Björner | Oriented Matroids, Encyclopedia of Mathematics and its Applications[END_REF] Sect. 1.10] all parallel vectors of the form a ja i are merged into a single element of the oriented matroid.

isomorphic to M/ {(n-1,n)} . The transitivity condition from Lemma

3.8 is preserved, and hence M is a sweep oriented matroid of rank r -1 and M lit has rank r , by induction. A maximal chain of the contraction M lit /(n -1) induces a chain0 n = X 0 ≺ • • • ≺ X r -1 of M lit in which (X i ) n-1 = (X i ) n =0 for all 0 ≤ i ≤ r -1 and that is maximal with this property. Since n -1 and n are not parallel (because (n -1, n) is not a loop), there is a covector Y

This is usually presented in the context of "topological sweepings" of arrangements of pseudolines, for example in[START_REF] Felsner | Geometric graphs and arrangements, Some chapters from combinatorial geometry[END_REF][START_REF] Felsner | Sweeps, arrangements and signotopes[END_REF]. Note that the notation in these references collides slightly with ours, see Sect. 1.1.

There is a small typo in the statement of[START_REF] Edelman | Ordering points by linear functionals[END_REF] Thm. 3.4] but the correct statement can be recovered from[START_REF] Edelman | Ordering points by linear functionals[END_REF] Cor. 3.2] with d = nk -1.

Recall that the parallelism class f of f is the set of elements e ∈ E such that X f = X e for all covectors X or X f = -X e for all covectors X . The reorientation -F X is the signed vector Z such that Z f = -X f for all f ∈ F and Z f = X f otherwise. The separation set S(X , Y ) of covectors X , Y are the elements e ∈ E such that (X e , Y e ) ∈ {(+, -), (-, +)}.

Acknowledgements

We are very grateful to Keiichi Handa, who sent us a copy of his Ph.D. thesis manuscript. We also want to thank Raul Cordovil, Kolja Knauer, Jean-Philippe Labbé, Germain Poullot, Francisco Santos, and Raman Sanyal for their helpful comments on previous versions of this manuscript. Finally, we would like to thank the anonymous reviewers for their detailed comments and suggestions to improve our presentation.

Funding Open Access funding provided thanks to the CRUE-CSIC agreement with Springer Nature.

Supported by the project CAPPS (ANR-17-CE40-0018) of the French National Research Agency ANR, the French -Austrian project PAGCAP (ANR 21 CE48 0020 and FWF I 5788), the project PID2019-106188GB-I00 of MCIN/AEI/10.13039/501100011033, and the project CLaPPo (21.SI03.64658) of Universidad de Cantabria and Banco Santander.

Data Availability Data sharing not applicable to this article as no datasets were generated or analysed during the current study.

Proof of Theorem 6. [START_REF] Andrzejak | In between k-sets, j-facets, and i-faces: (i, j)-partitions[END_REF] To simplify the exposition, we denote by P = (M lit , + n ) the poset of pseudo-sweeps of M lit with respect to + n , by S = (M sw ) the poset of sweeps of M sw , and by Q = [0, + n ) the half-open interval between 0 and + n in the face lattice of M lit (this is its Edmonds-Mandel lattice without the top element).

By Lemma 6.7 it suffices to show that the inclusion map ι : S → P induces a homotopy equivalence. As in the proof of Lemmas 6.11 and 6.13, let f : P → Q be the map that sends a pseudo-sweep (I 1 , . . . , I m ) to the non-negative covector with zero-set I 1 .

For any covector Z ∈ Q with zero-set F, we have that ( f • ι) -1 (Q ≥Z ) = (M sw ) ⊆F , which is contractible by Lemma 6.13. We conclude by Quillen's Theorem 6.9 that f • ι : S → Q induces a homotopy equivalence with a homotopy inverse g :

We will show that g • f : P → S is a homotopy inverse of the inclusion map ι : S → P. We trivially have that g • f • ι ∼ id S from the fact that ( f • ι) and g are homotopy inverses.

It remains to show that ι • g • f ∼ id P . Now, for σ in the order complex of P, let

where F is the first part of the smallest ordered partition in σ . It is therefore contractible by Lemma 6.11. We claim that id p and ι • g • f are both carried by C , and thus that they must be homotopy equivalent by Lemma 6.8. Indeed, id P is trivially carried by C ; and so is ι

The same proof works if we restrict to non-trivial sweeps in S and P.

Allowable Graphs of Permutations and Sweep Acycloids

In this section we present an alternative generalization of allowable sequences to high dimensions that is closer to the original formulation, in terms of moves between permutations. As we will see, the resulting objects naturally have the structure of acycloids, and we recover sweep oriented matroids as a special case.

Allowable Graphs of Permutations

In this setting it is useful to see a permutation σ ∈ S n as the word [σ (1), . . . , σ (n)] on the alphabet [n]. A substring of σ is then a contiguous sequence of characters, of the form [σ ( j), σ ( j + 1), . . . , σ (k)] for certain 1 ≤ j < k ≤ n. Such a substring is said to be increasing if σ ( j) < σ ( j + 1) < . . . < σ (k).

Definition 7.1 Let ⊆ S n be a set of permutations, and σ, σ ∈ . We define an allowable sequence in from σ to σ as a sequence of permutations of : σ = σ 0 , . . . , σ l = σ such that (M1) for each 1 ≤ k ≤ l the move from σ k-1 to σ k consists of reversing a set m k of one or more disjoint substrings of σ k-1 ; (M2) each pair i, j is reversed at most once along the path. In other words, there is at most one move m k such that i and j are in the same substring of m k .

A move is simple if it consists of a single substring of two elements; and an allowable sequence is simple if all its moves are.

For example, (1, 3, 2, 6, 5, 4) [START_REF] Alon | The number of small semispaces of a finite set of points in the plane[END_REF][START_REF] Athanasiadis | Monotone paths on polytopes[END_REF], [START_REF] Andrzejak | In between k-sets, j-facets, and i-faces: (i, j)-partitions[END_REF][START_REF] Athanasiadis | Monotone paths on zonotopes and oriented matroids[END_REF][START_REF] Angel | Random sorting networks[END_REF] -------→ (1, 2, 3, 4, 5, 6) and (6, 5, 4, 3, 1, 2)

--→ (6, 5, 4, 3, 2, 1) are valid moves, the second being moreover simple. The sequence

is an allowable sequence from (1, 2, 3, 4, 5) to (3, 4, 2, 5, 1) in S 5 ; whereas

is not an allowable sequence in S 5 , because the pair {2, 3} is reversed twice. In fact, in an allowable sequence from the identity permutation, only increasing substrings can be reversed. Note that if there is a move m from σ to γ , then from γ to σ there is the reverse move m whose substrings are s = [s k , . . . , s 0 ] for each substring s = [s 0 , . . . , s k ] of m. This way, every allowable sequence can be reversed.

Another way to describe allowable sequences is by looking at the set of pairs that are reversed at each move. For a permutation σ , we denote by inv(σ ) its set of inversions; that is, the set of pairs (i, j) ∈ [n] 2 such that i < j and σ (i) > σ( j). We denote by the symmetric difference operation on sets. Definition 7.2 If there is a move m from a permutation σ to a permutation γ , we define the set of inversions of the move m by inv m = inv(σ ) inv(γ ).

For example, for the move (1, 3, 2, 6, 5, 4) [START_REF] Alon | The number of small semispaces of a finite set of points in the plane[END_REF][START_REF] Athanasiadis | Monotone paths on polytopes[END_REF], [START_REF] Andrzejak | In between k-sets, j-facets, and i-faces: (i, j)-partitions[END_REF][START_REF] Athanasiadis | Monotone paths on zonotopes and oriented matroids[END_REF][START_REF] Angel | Random sorting networks[END_REF] -------→ (1, 2, 3, 4, 5, 6) we obtain the set of inversions {(2, 3), (4, 5), (4, 6), (5, 6)}.

The conditions defining allowable sequences become:

Note also that inv m = inv m . Remark 7. [START_REF] Alon | The number of small semispaces of a finite set of points in the plane[END_REF] An allowable sequence in the sense of Goodman and Pollack in [START_REF] Goodman | On the combinatorial classification of nondegenerate configurations in the plane[END_REF][START_REF] Goodman | A theorem of ordered duality[END_REF][START_REF] Goodman | Semispaces of configurations, cell complexes of arrangements[END_REF][START_REF] Goodman | Allowable sequences and order types in discrete and computational geometry[END_REF] is exactly what we call an allowable sequence from id = (1, 2, . . . , n) to id = (n, n -1, . . . , 1) in S n .

We need to introduce another concept before our main definition.

Following [START_REF] Handa | A characterization of oriented matroids in terms of topes[END_REF], we introduce acycloids in terms of its topes, which are subsets of sign-vectors. We use the same notation for the notions of reorientation, support and parallelism classes of oriented matroids from Sect. 3.1, which carry on verbatim to arbitrary subsets of sign vectors. Definition 7.10 A collection of sign-vectors T ⊆ {+, -, 0} E is the set of topes of an acycloid if and only if it satisfies the following axioms 4 :

These three axioms are satisfied by the topes of an oriented matroid but they are not sufficient; there are examples of acycloids that are not oriented matroids, see [START_REF] Handa | Topes of oriented matroids and related structures[END_REF]Sec. 7].

To describe the link between allowable graphs of permutations and acycloids, we associate a sign-vector X σ in {+, -} ( [n] 2 ) to each permutation σ ∈ S n via the map (5). For simplicity, we will sometimes implicitly identify permutations and sign-vectors when it is clear from the context. For a set of permutations ⊆ S n , we denote

2 ) .

Lemma 7.11 Let ⊆ S n form an allowable graph of permutations, and let T ⊆ {+, -} ( [n]

2 ) be the set of sign-vectors associated to its permutations. Then the inversion sets of the moves in L coincide with the parallelism classes of T . Proof First, the fact that is symmetric and the existence of a valid path between σ and σ for any σ ∈ implies that any pair {i, j} is in the inversion set of at least one move in L, which is necessarily unique by the disjointness condition (P3). Hence, the inversion sets of the moves in L define equivalence classes on the pairs [n] 2 . It is straightforward to check that these coincide with the parallelism classes of T .

Theorem 7.12 Let

⊆ S n form an allowable graph of permutations. Then T ⊂ {+, -, 0} ( [n] 2 ) is the set of topes of an acycloid.

Proof

The support of all the covectors is [n] 2 , and we have symmetry by definition. Hence, it suffices to verify that T satisfies the reorientation property (T3). Let X , Y ∈ T and σ, γ ∈ be the associated permutations. Let σ = γ 0 , . . . , γ l = γ be an allowable sequence from σ to γ . S(X , Y ) corresponds to the pairs reversed along this path. Let Z be the sign-vector associated to γ 1 by the map [START_REF] Athanasiadis | Monotone paths on zonotopes and oriented matroids[END_REF]. Then Z is in T and Z = -inv m X where m is the move from σ to γ 1 . Lemma 7.11 shows that inv m is the parallelism class of any pair {i, j} reversed by m.

We can characterize which acycloids arise from allowable graphs of permutations. We do it in a slightly more general context.

Appendix A. Another Fiber Polytope Construction

In this section we present another way to construct sweep polytopes as fiber polytopes. As we will see, it is strongly related to the monotone path construction we gave in Sect. 2.3.3.

Define the Lawrence polytope of a point configuration A ∈ R d× [n] as

Then the intersection of ( Ā) with the subspace induces chains of projections between the corresponding Lawrence polytopes and associated zonotopes, respectively, that can be arranged in the following commutative diagram:

Note that Z( n-1 ) is just the cube n , and Z( Ō) a segment, and hence (Z( n-1 ), s) and Z( Ā), h are the n-permutahedron and the sweep polytope S P( A) by Example 2.6 and Proposition 2.8, respectively.

Moreover, ( n-1 ) and ( Ō) are the (non-standard) (2n -1)-simplex conv e i ± e i+n i ∈ [n] and a prism over n-1 , respectively. The same proof as in [START_REF] De Loera | Triangulations: structures for algorithms and applications[END_REF]Thm. 6.2.6] shows that ( ( n-1 ), id ×s) is a homothety of the n-permutahedron embedded into R 2n . By Lemma 2.7 we obtain that:

Corollary A. [START_REF] Angel | The local limit of random sorting networks[END_REF] The fiber polytope ( Ā), id ×h is a homothety of the sweep polytope S P( A) embedded into R n+d+1 .

Appendix B. Proofs of Theorem 4.1 and Corollary 4.10

We include below the technical details of the proof of Theorem 4.1. We first recall the notations and the statement of the theorem.

For a covector X of a sweep oriented matroid, let p X : [n] → [l X ] be the surjection associated to the corresponding ordered partition. For each 1

2 ) be the sign-vector:

Theorem (4.1) If M is the set of covectors of a sweep oriented matroid, then

is the set of covectors of an oriented matroid.

parallel elements (i, j) = (i, j) f for (i, j) ∈ δ( f ). The restriction of M to [n] 2 is a sweep oriented matroid, as it fulfills the transitivity condition from Lemma 3.8 by hypothesis. We want to apply Theorem 4.1 to find the associated big oriented matroid. While Theorem 4.1 is only stated to extend a matroid from [n] 2 to [n] ∪ [n] 2 , the same proof carries on almost verbatim to extend a matroid from F ∪ [n] 2 to F ∪ [n] ∪ [n] 2 . We associate a family of covectors X k on F ∪ [n] ∪ [n] 2 to every covector X of M in the very same way, just ignoring the entries in F when generating the values for [n] in X k . These are the covectors of an oriented matroid M (by the same argument as in Theorem 4.1), and its restriction to [n] ∪ F is the desired oriented matroid M.

Publisher's Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.