A homotopy theorem on oriented matroids

Discrete Mathematics North-Holland 111 (1993) 131-136 A homotopy matroids 131 theorem on oriented R. Cordovil zyxwvutsrqponmlkjihgfedcbaZYXWVUTSRQPONMLKJIHGFEDCBA Centro de M atemirtica e Aplica@ es Fundamentais, Au. Prof. Gama Pinto, 2. 1699 Lisboa Codex, Portugal M.L. Moreira” Centro de M atemirtica da Unio. do Porte, P. Games Teixeira, 4000 Porte, Portugal Received 22 July 1991 Abstract Cordovil, R. and M.L. Moreira, 111 (1993) 131-136. A homotopy theorem on oriented matroids, Discrete Mathematics Consider a finite family of hyperplanes _%?= {Hi, . _., H,} in the finite-dimensional vector space IWd. We call chambers (determined by 2) the connected components of W”\ U y=, Hi. Galleries are finite families of chambers (C,,,C,, , C,), where exactly one hyperplane separates Ci+i from Ci, for O <i<m, and exactly m hyperplanes separate C, from C,. Using oriented matroid theory, we prove that any two galleries with the same extremities can be derived from each other by a finite number of deformations of the same kind (elementary deformations). When the chambers are simplicial cones, this is a result of Deligne (1972). Our theorem generalizes also a result of Salvetti (1987). 1. Introduction and notations Let 2={CH,,H2,... a real vector space ,H,} be a finite family of homogeneous hyperplanes of V of finite dimension. Call Vc the complexification of V. H. When the chambers (i.e., connected Let X= K\IJHEX He: and Y= V\u,,, components) of Y are simplicial cones, Deligne ([7]) has proved that ni(X)=O for i> 1, i.e., the space X is a K(rc, 1). A combinatorial result that turns out to be important in this paper is that any two galleries (i.e., minimal paths) linking chambers of Y with the same extremities can be obtained from each other using a finite number of deformations of a certain kind, called elementary deformations (see zyxwvutsrqponmlkjihgfedcbaZYXWVUTSRQPONMLKJIHGFEDCBA C71). *Partially supported 0012-365X/93/$06.00 by a grant Q from I.N.I.C. 1993-Elsevier Science Publishers B.V. All rights reserved 132 R. Cordovil, M.L. Moreira zyxwvutsrqponmlkjihgfedcbaZYXWVUTSRQPONMLKJIHGFEDCBA Our theorem generalizes for oriented matroids Deligne’s ticular that his restriction-‘the chambers of Y are simplicial Note that the ‘realizable oriented matroid’ case was proved Arrangement of hyperplanes occurs in several branches result, showing in par- cones’-is not essential. by Salvetti [14]. of mathematics (see [13-151). We suppose that the basic notions and results from oriented matroid theory are familiar to the reader (see [l, 9, ll]), and we recall here only those which are directly related to this paper. We begin by associating with the set Y of chambers an oriented matroid in the following way: We fix a point a chamber ldidn, &E Y; to each CE Y, we assign a zyxwvutsrqponmlkjihgfedcbaZYXWVUTSRQPONMLKJIH signed vector QE { +, - }“, where, for any i, (Vc)i=+Ox(C) x(C) in the interior and x(C,) of each chamber are in the same connected component C of Y and of V\Hi. The family of signed vectors w = { Vc: CEY} is the family of maximal elements of the cocircuit span of the (realizable) oriented matroid Jz’ of the linear dependencies on a set u2/ of vectors orthogonal to the hyperplanes of the arrangement 2, ,n, such that uilHi for every i=l,..., n. q={“i}i=l,. The elements of w have been studied in oriented matroid theory under the name of of oriented matroids using this topes or non-Radon partitions ([2,8]). A xiomatizations family are also well known ([4, 5, 10, 121). In what follows, the elements of w= “K(A) will be called maximal covectors or, shortly, covectors of the oriented matroid &‘. By rank ofW we will mean the rank of the matroid JH and note by v the signed covector whose entries are symmetric to those of VGT. It is known that -Ilr itself is symmetric, i.e., ?.V= “@ = { v: VFW ” }. We will suppose w.1.o.g. that w has no parallel elements, i.e., for each i, 1 <i < n, there are two covectors V and V’ in w, with I/‘ # v satisfying K=- Vi. 2. The results Let ?V c { +, -}” be the family of maximal covectors of a simple (i.e., with no loops, parallel or antiparallel elements) oriented matroid on the set E. Definition 2.1. A family G = ( V,, VI, . . . , V,,) of n + 1 covectors of -1y- is a gallery with initial point VO,endpoint V, and length n if: (1) vi+ 1 differs from K in exactly one entry, for any i, 1 < i < n; (2) V, differs from V, in exactly n entries. Definition 2.2. Two galleries with the same extremities G =( VO, VI, . . . , Vn) and G’=( V0 = V,, Vi, . . , Vn= Vn) can be obtained from each other by an elementary deformation if: (1) There are two integers p and q, with O<p < q < n, such that vj= Vi, for any j satisfying O<j<p or qdj<n; A homotopy theorem on oriented matroids 133 (2) The two galleries G1 = ( zyxwvutsrqponmlkjihgfedcbaZYXWVUTSRQPONMLKJIHGFEDCBA VP, VP+1, . . . , V,) and G I= ( Vb= VP, VP+ 1, . . . , Vb = V,) are unique in w with these extremities. Two galleries in -ly- are equivalent if they can be obtained number of elementary deformations. Remark 2.3. Note that (1) for any two covectors from each other by a finite V and v’ of @‘“, there is always a gallery in YY linking them ([3, Lemma 3.71); (2) given two covectors V and v’ of %‘“,there are exactly two galleries with them as extremities if and only if, with A={eEE: V,=- Vk} and B=(eEE: a rank 2 face of the acyclic oriented matroid BJ&‘. Theorem 2.4. Any two galleries covectors of an oriented with the same extremities A is V,=-}, in the set $T of the maximal matroid _4? are equivalent. For the particular case rank(w)= 3, Theorem 2.4 is implicit in [3], Theorem 2.1. Indeed, the following theorem, which is stronger than our theorem for rank 3, is also implicit therein. Theorem 2.5. Let TUTbe the family with n points and 1 lines. Let a gallery linking equivalent of maximal V be a covector V to v. W ith G’ =( Vb = v,, and can be obtained from each covectors of a rank 3 oriented matroid of PY and G=( V= V,, VI, . . . , V,= v) V; = v,_ 1, . . . , V:, = &), G and G’ are other by using exactly 1 elementary deformations. Note that, under the conditions of Theorem 2.5, 1 is the minimal number of elementary deformations required to obtain one of the galleries from the other. This result also suggests the following problem, for which a positive answer would allow us to generalize Theorem 2.4 in the spirit of Theorem 2.5. Problem 2.6. Let w = w(A) be the family of maximal covectors of an oriented matroid A&’ with rank, at least, three; let G be any gallery in YY linking two opposite covectors V and l? Is there any subset PV’ of covectors of -1y- containing the covectors of G and being the family of maximal covectors of a rank 3 oriented matroid A’? 3. Proofs Let A’(E) be a simple and acyclic oriented matroid and ~2 = {ACE: a_&’ is With each AE~, we associate a graph G(A) whose vertices (edges) are the flats of & with rank 1 (rank 2) included in A and belonging to &‘. acyclic}. 134 R. Cordooil. ML. Moreira Proposition 3.1. G(A) zyxwvutsrqponmlkjihgfedcbaZYXWVUTSRQPONMLKJIHGFEDCBA is a connected graph. We remark extremal that, when all the acyclic reorientations points (the hypothesis considered of AZ”have exactly rank(A) by Deligne [7]), the connectivity of G(A) can be easily proved; indeed, in this case G(A) is a complete graph. Note also that if A is a flat of &, since Ad, A is a face of A’, i.e., A is a union of positive cocircuits of A; thus, the graph G(A) is the l-skeleton of the face lattice of the submatroid A’(A). This lattice being a combinatorial its l-skeleton is connected (see, e.g., [6]). manifold, Proof of Proposition 3.1. We will prove it by induction it is well known that on )A I. When 1A 1Q 2, there is nothing left to prove. Suppose now that the proposition is true for any Aed with 1A I< n and let B be any element of d such that IBI = n + 1. We assume that B is not a face of the matroid A! since otherwise, as we noted, the result follows. Now take a vertex x of G(B) and let p be the Mobius function on d, thought of as a partially ordered set by inclusion. It is known (see [S] and the extension to oriented matroids in [4, Corollary 2.101) that, for each XL&, . L- l)rank(X) zt,“,r;is; P(8, x)= face of A, i It follows from the definition La a=- 1 P(0, of the Mobius function that X) XfB and, in particular, J, A02Xl= c zyxwvutsrqponmlkjihgfedcbaZYXWVUTSRQPONMLKJIHGFEDCBA A02X)=0. XCB\(xJ ac XX Using these equalities and the result above, we have xsFfB F zyxwvutsrqponmlkjihgfedcbaZYXWVUTSRQPONMLKJIHGFEDCBA is a face of .X and, thus, as B is not a face of A!, c XEFFB F is a face 148,F)=O of .X Since ~(0, {x})=1, there must be a face F, of A strictly containing {x> and being strictly contained in B. Therefore, by the Jordan-Dedekind property of the lattice of faces of an oriented matroid (see [ 1 l]), we may say that there is a face F : of A! such that XEF;G F, and rank(F:)=2. 135 A homotopy theorem on oriented matroids This means that there is an edge of G(B) with x for vertex, i.e., G(B) has no isolated vertices. In view of [3, Lemma 3.71, since BE&, we can choose XEG(B) such that B\ (x}E&‘. By induction, G(B\ (x}) IS connected. Since all the edges of G( B\(x)) are edges of G(B) and connected. 0 G(B) has only one more, nonisolated, vertex, it must also be Proof of Theorem 2.4. We proceed by induction on the length of the galleries. Let G and G’ be two different galleries with the same extremities V, and V2. Its length must be at least equal to three. If it is equal to three, clearly G=( V,, A, V2) and G’ = ( VI, B, V2) are unique with these extremities and they can be obtained from each other by one elementary deformation. Suppose now that the theorem is true when the length of the galleries is less or equal to n- 1, and take any two different galleries G =( Ve, Vi, . . . , V,) and G’=(&=V,, I’;,..., VI,= V,) with the same extremities and length n. By taking, if necessary, a reorientation of the matroid &‘, we can suppose, w.l.o.g., that all entries of the covector V, are positive. We call AE& the set of negative entries of V, and a (b) the unique negative entry of Vi ( VI). By the connectivity graph. of G(A), it is sufficient to consider the case where {a, b} is an edge of this Let U be the covector of W whose negative entries are the elements of E belonging to the 2-face {a, b} of JZ. According to Remark 2.3(2), there are exactly two galleries Gi and G2 with extremities VOand U. Call Gr3 and Gz3 to the galleries linking V, with V, and obtained by composing, respectively, Gi and G2 with some gallery G3 joining U to V,. It is clear that Gr3 and Gz3 can be obtained from each other by one elementary deformation. Noting that the galleries G and Gr3 have the two first vertices in common, it follows from the induction hypothesis that they are equivalent; the same argument galleries. 0 yields for the galleries G’ and Gz3. Hence, G and G’ are equivalent References [1] A. Bjorner, M. Las Vergnas, B. Sturmfels, N. White and G.M. Ziegler, Oriented Matroids, Cambridge University Press, to appear. [Z] R.G. Bland and M. Las Vergnas, Orientability of matroids, J. Combin. Theory Ser. B 24 (1978) 94-123. [3] R. Cordovil, Sur les matroi’des orient& de rang trois et les arrangements de pseudodroites dans le plan projectif reel, European J. Combin. 3 (1982) 307-318. [4] R. Cordovil, A combinatorial perspective of the non-Radon partitions, J. Combin. Theory Ser. A 38 (1985) 38-47. [5] R. Cordovil and W. Bienia, An axiomatic of the non-Radon partitions, European J. Combin. 8 (1987) l-4. [6] R. Cordovil and K. Fukuda, Oriented matroids and combinatorial manifolds, European J. Combin., to appear. [7] P. Deligne, Les immeubles des groupes de tresses generalises, Invent. Math. 17 (1972) 273-302. 136 R. Cordovil, M.L. Moreira [S] P. Edelman, A partial order on the regions of Iw”dissected by hyperplanes, Trans. Amer. Math. Sot. 283 (1984) 617-631. [9] J. Folkman and J. Lawrence, Oriented matroids, J. Combin. Theory Ser. B 25 (1978) 199-236. [lo] K. Handa, A characterization of oriented matroids in terms of topes, European J. Combin. 11 (1990) 41-45. [11] M. Las Vergnas, Convexity in oriented matroids, J. Combin. Theory Ser. B 29 (1980) 231-243. 1121 J. Lawrence, Lopsided sets and orthant-intersection by convex sets, Pacific J. Math. 104 (1983) 155-173. [13] P. Orlik, Introduction to arrangements, CBMS Lecture Notes, Vol. 72 (Amer. Math. Sot., Providence, RI, 1989). 1141 M. Salvetti, Topology of the complement of real hyperplanes in C”, Invent. Math. 88 (1987) 603-618. [15] G.M. Ziegler, Algebraic combinatorics of hyperplane arrangements, Ph.D. Dissertation, M.I.T., 1987.