arXiv:math/0010236v1 [math.CO] 25 Oct 2000 Lagrangian Matroids Associated with Maps on Orientable Surfaces Alexandre V. Borovik Department of Mathematics UMIST PO Box 88 Manchester M60 1QD United Kingdom Richard F. Booth Department of Mathematics UMIST PO Box 88 Manchester M60 1QD United Kingdom Israel Gelfand Department of Mathematics Rutgers University New Brunswick NJ 08903 USA 28 January 1999∗ Introduction The aim of this paper is to clarify the nature of combinatorial structures associated with maps on closed compact surfaces. These are fairly classical objects; however, not long ago it was discovered by A. Bouchet that maps are associated with ∆-matroids [7] (or Lagrangian matroids in the terminology of [4]). ∆-matroids are related to maps in almost the same way as ordinary matroids to graphs. In this paper we explore this parallel further and show that the resulting Lagrangian matroids are representable by matrices in a sense analogical to representability of ordinary matroids, thus tranferring the classical Rado’s theorem [12] to Lagrangian matroids. The proper setting for the representation is provided by cohomology of the surface. Our proof is very elementary. It is worth mentioning that David Stone [13] found a cohomological proof of the main technical result of the paper, Theorem 5. His proof is not much shorter than ours but promises a possible generalisation of our result to higher dimension. Our next observation is that the classical ‘spanning tree algorithm’ for graphs (which becomes the ‘greedy algorithm’ of matroid theory and the theory of ∆-matroids [6]) can be interpreted in our setting in a most elementary way, as a ‘peeling off’ procedure which cuts the (connected) surface into one closed ring-shaped peel, or, in some degenerate cases, to a 2-cell peel. This procedure is local, that is, at every step uses information only about a small part of the surface around the knife. ∗ updated 2000/10/18 for the web 1 R. F. Booth et al., Lagrangian Matroids and Maps on Orientable Surfaces 2 1 Orthogonal matroids and maps 1.1 Maps on compact surfaces A graph is a compact space G partitioned into a finite set E = E(G) of open 1-cells called edges and a finite set V = V (G) of points called vertices such that every edge has a vertex at each end (possibly the same vertex at both ends, in which case we say that the edge is a loop). If S is a compact surface and G ⊆ S we say that the graph is drawn on the surface S. We shall be concerned only with orientable connected compact surfaces in this paper. If connected components of S\G are open 2-cells, then we say that M := (G, S) is a map, and the the connected components of S \ G are called the faces or countries of the map. Thus a map M introduces on S a structure of a 2dimensional cell complex. We assume that the set of edges (correspondingly, coedges) of M is non-empty, excluding from consideration a trival map on a sphere with one vertex and no edges. A dual map M ∗ = (G∗ , S) is defined in the usual way. Its vertices are in one-to-one correspondence with the faces of M ; for each face of M , we choose a point inside it as the corresponding vertex of M ∗ . The edges are chosen such that every edge of e of G is disjoint from every edge of G∗ except for its dual edge, e∗ , which has with e exactly one point in common. We call the e∗ the coedges. Then it can be shown that the faces of M ∗ correspond to the vertices of M : every face of M ∗ contains a unique vertex of M , and every vertex of M belongs to a unique face of M ∗ . The vertices of M ∗ are called covertices and the set of covertices is denoted by V ∗ . Finally, notice that M is a dual map to M ∗ . For F ⊆ E we define F ∗ := { e∗ | e ∈ F } and F := E\F. We call a set F ⊂ E ∪ E ∗ / It will be convenient to index edges in E by elements of admissible if F ∩ F ∗ = 0. I = { 1, . . . , n } and the coedges in E ∗ by the corresponding elements of I ∗ , so that E = { e1 , . . . , en } and E ∗ = {e1∗ , . . . , en∗ }. 1.2 Symplectic and orthogonal matroids For a fuller exposition of the theory and definitions of symplectic matroids, see [4] and the forthcoming book [5]. Let I = {1, 2, . . ., n} and I ∗ = {1∗ , 2∗ , . . . , n∗ } and J = I ∪ I ∗ . Define maps ∗ : I → I ∗ by i 7→ i∗ and ∗ : I ∗ → I by i∗ 7→ i, so that ∗ is an involutive permutation of J. Then we say that a subset K ⊂ J is admissible if and only / We denote by Jk the set of all admissible k-subsets of J. if K ∩ K ∗ = 0. Let B ⊆ Jn be a a set of admissible n-subsets of J and let M be the triple (J, ∗ , B ). Then M is a Lagrangian matroid if it satisfies the Symmetric Exchange Axiom: For any A, B ∈ B and k ∈ A△B there exists some i ∈ A△B such that A△{k, k∗ , i, i∗ } ∈ B . Here △ is the symmetric difference; A△B := (A ∪ B)\(A ∩ B). This axiom is due to Bouchet [6], Dress and Havel [8, 11], where Lagrangian symplectic matroids appeared, cryptomorphically, under the names of ∆-matroids or metroids. We call B the set of bases of M. A Lagrangian matroid is a special case of a symplectic matroid; in a general symplectic matroid, the bases are elements of Jk for some k. An appropriate axiom system is given in [4]. In this paper, we shall only be concerned with Lagrangian R. F. Booth et al., Lagrangian Matroids and Maps on Orientable Surfaces 3 matroids. An orthogonal matroid or even matroid is a symplectic matroid in which the difference between the number of starred elements in any two bases is always even. We say that an admissible set F ⊂ E ∪ E ∗ is independent if S\cl(F) is connected. A basis of M is a maximal independent admissible set. Bouchet [7] proved that the set B = B (M) of all bases of a map M is a even Lagrangian matroid on the set E ∪ E ∗ . This paper provides another proof of Bouchet’s result with a important improvement of representability; necessary terms are explained in Subsection 1.4. Theorem 1 Let M be a map with n edges on a orientable compact closed surface S. Then • all bases of M have cardinality n and • the set B of all bases is an orthogonally representable over Q, orthogonal Lagrangian matroid. It is well-known that (ordinary) matroids associated with graphs are representable by matrices ([12], the exposition can be found in any book on matroid theory, see, for example, [15]). Our Theorem 1 is a generalisation of this result. We shall see in the next subsection that the classical Spanning Tree Algorithm for graphs, which corresponds to the Greedy Algorithm of matroid theory, also has a natural analogue for maps. 1.3 The greedy algorithm and peeling the skin. Draw on each face of M the segments connecting the covertex with the vertices of this face, we shall call them diagonals. Edges, coedges and diagonals define a baricentric subdivision of M. Each of the triangles of this subdivision has one side a diagonal, one side a half-edge of the map, and one side a half-coedge. It can be immediately seen that, when cutting along the edges and coedges of a basis, we obtain a ring (topologically, a punctured 2-cell) or a 2-cell. This is due to the fact that, in view of Theorem 1, the basis forms an admissible set of n elements, and thus every triangle of the baricentric subdivision is cut along precisely one edge. This means that each triangle has two neighbors in the modified surface; hence it is a ring or a 2-cell. The procedure for peeling is the following. We construct a sequence of triangles S0 , S1 , . . . , Sn in the baricentric subdivision in which Si and Si−1 , i = 1, 2, . . ., are adjacent, i.e. have in common an edge, coedge or diagonal. P EELING OFF P ROCEDURE 0◦ Start at arbitrary triangle S0 in the subdivision. 1◦ Assume that we have constructed S0 , S1 , . . . , Si . • If neither edge e nor coedge e∗ which bound Si has been cut along at the previous steps of the procedure, cut the surface along the entire edge e or coedge e∗ chosing e or e∗ so that the surface remains connected. Take for Si+1 the triangle which has a common with Si coedge (correspondingly, edge) which was not cut. • If either edge e or coedge e∗ has been cut along at one of the previous steps of the procedure, take for Si+1 the triangle which lies across the diagonal or noncut (co)edge from Si and is different from Si−1 . R. F. Booth et al., Lagrangian Matroids and Maps on Orientable Surfaces 4 2◦ If step 1◦ cannot be made or if Si+1 defined by rule 1◦ is one of the triangles S0 , S1 , . . . , Si−1 , stop. We may reformulate this description in terms of independent sets. By definition, an independent set of (co)edges is characterised by the property that it is admissible and its closure does not disconnect the surface. Now the condition of Step 1◦ is that we must make a cut which leaves the set of cuts made an independent set. By Theorem 1 maximal independent sets (bases) have cardinality n and form a Lagrangian matroid on E ∪ E ∗ . Notice that, due to our definition of a basis of a map, independent subsets of (co)edges are just subsets of bases. We use a simplified version of the greedy algorithm for Lagrangian matroids as described by the following procedure. Let B be the set of bases of a Lagrangian matroid on J. Let I be the set of all independent subsets, that is all subsets of bases from B . Let i1 , . . . , in be the elements 1, . . . , n written in some order i1 ≺ . . . ≺ in . G REEDY A LGORITHM / B := 0; for j = 1, 2, . . . , n do if B ⊔ { i j } ∈ I then B := B ⊔ { i j } else B := B ⊔ { i∗j }; end Since every basis of a Lagrangian matroid contains, for every i = 1, . . . , n, one of the elements i, i∗ , it is immediately obvious that the greedy algorithm returns a basis in B. A stronger version of a greedy algorithm, due to Bouchet [6], can be used for characterisation of Lagrangian matroids; we do not use it here. The greedy algorithm allows us to prove that the peeling-off procedure described produces the set of cuts which is a basis of the map. Let us pause the procedure at some stage when we have chosen the triangles S0 , S1 , . . . , Sk and let the set of cuts already made be B. Notice that B is an independent set. If Sk has a cut (co)edge we have to select for Sk+1 the triangle lying across the diagonal or non-cut (co)edge from Sk ; we can do this unless Sk+1 is one of the triangles S0 , . . . , Sk ; but in this case one can immediately see that Sk+1 = S0 and we cut a closed ribbon from the surface. Since cuts along B do not disconnect the surface, the ribbon covers the whole surface. Hence we can assume that neither edge ei nor coedge ei∗ bounding the triangle Sk has not been cut yet. We may define an ordering ≺ on { 1, . . . , n } in which nonstarred elements in B ∪ B∗ preceed all other elements in { 1, . . . , n }. Obviously, the greedy algorithm for ≺ will at some stage produce B. Furthermore, we may assign i to immediately succeed B in the ordering ≺, then the greedy algorithm says that we can cut along one of the edges ei or ei∗ retaining the surface connected, and thus continue the process as desired. Therefore we have proven the following result. Theorem 2 Every simplex in the triangulation of the map M = (S, G) appears in the sequence S0 , S1 , . . . , Sn exactly once. The surface S̄ obtained by all cuts is homeomorphic to a ring (punctured 2-cell) or 2-cell. R. F. Booth et al., Lagrangian Matroids and Maps on Orientable Surfaces 5 1.4 Representability of Lagrangian matroids Let V be the vector space over a field K of characteristic 6= 2 whose basis is { ei , e∗i | i ∈ I }. Define a symmetric bilinear form on V by hei , e∗i i = 1, hei , e j i = 0 for all i ∈ I and j ∈ J with i∗ 6= j, so that the basis { ei , e∗i | i ∈ I } is a hyperbolic basis in V .L is a Lagrangian subspace of V if it is a totally isotropic subspace (that is, hk, li = 0 for every k, l ∈ L) of maximal dimension. If f1 , . . . , fn is a basis in a n-dimensional subspace L in V , then we can associate with it a n × 2n matrix C written as (A, B) for two n × n matrices A and B such that fi = n n j=1 j=1 ∑ ai j e j + ∑ bi j e∗j . It is easy to see that L is a Lagrangian subspace in V if and only if ABt is a skew symmetric matrix. Let us index the columns of A with I and those of B with I ∗ , so that the columns of C are indexed by J. We say that an admissible subset F ∈ J is independent if the corresponding columns of C are linearly independent. Define the set of bases B ⊆ Jn by putting X ∈ B if and only if • X ∈ Jn and • the n × n minor consisting of the i-th column of C for all i ∈ X is non-zero. Notice that change of a basis in L is equivalent to conducting row operations on the matrix (A, B) and leaves the pattern of dependencies of the columns unchanged. Therefore the set B depends only on L and not on choice of basis in L. Theorem 3 (A. Vince and N. White [14]) If L is a Lagrangian subspace in V then • every independent subset in J belongs to a basis in B , and • B is the set of bases of an orthogonal Lagrangian matroid. For a proof that the axioms used to define Lagrangian matroids in [14] are equivalent to the Symmetric Exchange Axiom, see Wenzel [16] or the book [5]. We call an orthogonal matroid arising from a Lagrangian subspace L written by a matrix (A, B) with ABt skew-symmetric an orthogonally representable orthogonal matroid, and say that (A, B) is an orthogonal representation of it over the field K.1 2 Matroids, Representations and Maps Let M be a map on a compact connected orientable surface S, with the edge and coedge sets E = { ei | i ∈ I } and E ∗ = { e∗i | i ∈ I ∗ }, I = { 1, . . . , n }, vertex set V and covertex set V ∗ . We orient edges e ∈ E in an arbitrary way and choose orientation of coedges e∗ so that the intersection index (e, e∗ ) = 1 for all e ∈ E. We shall use homology of S and S\(V ∪V ∗ ) with coefficients in Q. 1 Note in passing that there is also another way of representing Lagrangian matroids, by Lagrangian subspaces in a symplectic vector space [4]. In the more general setting of Coxeter matroids [3] the fact that every orthogonal Lagrangian matroid is a symplectic Lagrangian matroid is explained by the canonical embedding of the corresponding Coxeter groups Dn < Cn and an observation that the thick Dn -building of isotropic subspaces in an orthogonal space has the natural structure of a thin Cn -building [9]. R. F. Booth et al., Lagrangian Matroids and Maps on Orientable Surfaces 6 For a cycle c in H = H1 (S\(V ∪V ∗ )) we have the well-defined intersection index, denoted here by (c, e), of c with an edge (or coedge) e ∈ E ∪ E ∗ . We shall denote by ê the corresponding linear functional ê : c 7→ (c, e) from H ∗ . Thus ê is a cocycle in H 1 (S \ (V ∪V ∗ )). Notice that this H 1 (S \ (V ∪V ∗ )) can be identified with H1 (S,V ∪V ∗ ) by Poincare-Lefschetz duality [10, VIII.7]. Lemma 4 An admissible set of (co)edges F ⊂ E ∪ E ∗ is independent if and only if the linear functionals fˆ, f ∈ F, are linearly independent over Q. Proof Denote X = V ∪ V ∗ ∪ f ∈F f . Then we have the triple W ⊂ X ⊂ S of cell complexes. The lemma immediately follows from the long exact homological sequence for this triple: S β α 2 2 H2 (S, X) · · · −→ H2 (X,V ∪V ∗ ) −→ H2 (S,V ∪V ∗ ) −→ ∂ α 2 1 −→ H1 (X,V ∪V ∗ ) −→ H1 (S,V ∪V ∗ ) −→ · · · Since H2 (X,V ∪ V ∗ ) = 0, β2 is an injection. If S \ X is connected then H2 (S, X) is 1dimensional, and, from comparing dimensions, we see that β2 is a surjection. Hence ∂2 = 0 and α1 is an injection. We need to notice only that H1 (X,V ∪V ∗ ) is generated by (co)edges in F. ⋄ ∗ Introduce the vector space QE ⊕ QE over Q with the basis E ∪ E ∗ . ∗ Define a symmetric bilinear form on QE ⊕ QE by he, e∗ i = 1, and he, f i = 0 for all ∗ e, f ∈ E ∪ E ∗ such that e∗ 6= f , so that E ∪ E ∗ is a hyperbolic basis in QE ⊕ QE . ∗ For c ∈ H, the incidence vector of c, denoted ι(c) ∈ QE ⊕ QE , is defined by ι(c) = ∑ (c, e)e. e∈E∪E ∗ The main technical result of the paper is: Theorem 5 The image ι(H) of H = H1 (S\(V ∪ V ∗ )) under the map c 7→ ι(c) is an ∗ isotropic subspace of the orthogonal space QE ⊕ QE . We postpone the proof of Theorem 5 until the next section, and meanwhile deduce from it the main result of the paper, Theorem 1. Theorem 6 The isotropic subspace ι(H) is Lagrangian, and the Lagrangian orthogonal matroid corresponding to ι(H) has bases which correspond to the bases of the map M. Proof Notice first that the map M = (G, S) has at least one basis of cardinality n. To ∗ construct it, take a spanning tree T in the graph G (T can be empty), then B = T ∪ T is rather obviously a basis of M and has cardinality n [7]. If now b1 , . . . , bn are the (co)edges in B then the linear functionals B̂1 , . . . , b̂n on H are linearly independent, hence the n functionals b̃i on ι(H) defined by the rule b̃i (ι(c)) = b̂i (c) are also linearly independent. Therefore dim ι(H) ≥ n, and being an isotropic sub∗ space in QE ⊕ QE , it is a Lagrangian subspace. Notice that if we represent ι(H) by a R. F. Booth et al., Lagrangian Matroids and Maps on Orientable Surfaces 7 n × 2n-matrix M in the basis e1 , . . . , en , e∗1 , . . . e∗n , the columns of M will represent the functionals ẽi , ẽ∗i . By Lemma 4 the columns of M are linearly independent if and only if the correspondent set of (co)edges is independent in M . Hence the bases of the Lagrangian matroid associated with ι(H) are exactly the bases of the map M . ⋄ Now Theorem 1 is an immediate corollary of Theorem 6. 3 Proof of Theorem 5 . We shall prove Theorem 5 by a naive geometric argument: we shall gradually simplify the map M and use induction on the total number of vertices and covertices in the map. David Stone [13] offered a cohomological proof of the same result. R EDUCTION , STEP 1. Notice that if an edge e ∈ E is a contractible loop, i.e. the endpoints of e coincide and the closure cl(e) is a contractible cycle on S then (c, e) = 0 for every c ∈ H and thus the contribution (c, e)(d, e∗ ) + (c, e∗ )(d, e) of e-th and e∗ -th coordinates of the incidence vectors ι(c) and ι(d) to their scalar product hι(c), ι(d)i is 0. Hence we can assume without loss of generality that the graph G (and, analogously, the dual graph G∗ ) contains no contractible loops. R EDUCTION , STEP 2. Introduce the scalar product h , i on H by setting hc, di = hι(c), ι(d)i. Our aim is to prove that h , i vanishes on H. Consider the kernel K of the canonical map H1 (S \ (V ∪V ∗ )) −→ H1 (S). It is well-known that K is isomorphic to H0 (V ∪ V ∗ ) and generated by small cycles around vertices and covertices in V ∪V ∗ . Lemma 7 hK, Hi = 0. Proof Indeed, let c be a small cycle around a covertex v∗ ∈ V ∗ (for vertices the proof is analogous). Let e∗1, . . . , e∗k be the oriented edges exiting from or entering v; notice that we count loops with both ends at v∗ twice, but with opposite signs. The corresponding edges e1 , . . . , ek form the boundary of the country C around v; again, edges corresponding to loops e∗i appear twice, with opposite orientations. Now if d is an arbitrary cycle in H then hc, di = hι(c), ι(d)i = (c, e∗1 )(d, e1 ) + · · · + (c, e∗k )(d, ek ). Without loss of generality we can change the orientation of edges and co-edges in such a way that (c, e∗i ) = 1 for all coedges e∗i , i = 1, . . . , k which are not loops and e1 + · · ·+ ek is the boundary cycle ∂C of the country C around v∗ . Then the right hand side of the previous equation is exactly the index of intersection of d and ∂C, and hence equals 0. ⋄ 8 R. F. Booth et al., Lagrangian Matroids and Maps on Orientable Surfaces Lemma 7 allows us to transfer the scalar product h , i from H1 (S \ (V ∪ V ∗ )) to H1 (S): if c, d ∈ H1 (S) and c′ , d ′ are any preimages of c and d in H1 (S \ (V ∪ V ∗ )), then we set hc, di = hc′ , d ′ i. The theorem which we are proving amounts to saying that hc, di = 0 for all c, d ∈ H1 (S). We can work with cycles in H1 (S) instead of H1 (S \ (V ∪V ∗ )) which gives us the necessary degree of flexibility in geometric construction we shall use in the proof. Now we can start the induction on |V ∩V ∗ |. BASIS OF INDUCTION . For the basis of induction assume that the map M and the dual map M ∗ both contain exactly one vertex, v and v∗ , correspondingly. The orientable connected compact surface S is a sphere with m handles. Then there are n = 2m edges and 2m coedges, from the Euler formula. We can treat the edges ei and coedges e∗i , i ∈ I = { 1, . . . n } of the map as elements of H1 (S). Consider again the kernel K of the canonical surjective map H1 (S \ (V ∪V ∗ )) −→ H1 (S); K is generated by two cycles k1 and k2 around v and v∗ . It is easy to see that ι(k1 ) = ∗ ι(k2 ) = 0, hence K ≤ ker ι and ι can be lifted to a linear map from H1 (S) to QE ⊕ QE which we denote by the same symbol ι. Thus hc, di = hι(c), ι(d)i for c, d ∈ H1 (S) and in our computations we can work with elements of H1 (S) instead of H1 (S \ (V ∪V ∗ )). The intersection index H1 (S) × H1(S) −→ H0 (S) = Q is a non-degenerate skew symmetric form on H1 (S). From the definition of orientation of co-edges we have (ei , e∗j ) = δi j for i, j ∈ I. Since dim H1 (S) = 2m = |I|, it follows from elementary linear algebra that { ei } and { e∗i } are dual bases in H1 (S). If c ∈ H1 (S) then we may express c = ∑i∈I ci ei , for some coefficients ci . Now we have ι(c) expressed as a sum of ι(ei ). So, if we can show that the space generated by the ι(ei ) is totally isotropic, we have completed the proof. Now, from the definition of an incidence vector,
ι(ei ) = ∑ (ei , e j )e j + (ei , e∗j )e∗j . j∈I Now, taking i, k ∈ I, we have, since (ei , e∗j ) = δi j , hι(ei ), ι(ek )i = = = = * * ∑ (ei , e j )e j + e∗i j∈I ∑ (ei , e j )e j , e∗k j∈I + ! + ∑ (ek , e j )e j + e∗k , j∈I * e∗i , ∑(ek , e j )e j j∈I !+ + (ei , ek ) + (ek , ei ) 0. Thus ι(H) is generated by a set of elements with zero pairwise scalar products, so the theorem follows. R. F. Booth et al., Lagrangian Matroids and Maps on Orientable Surfaces 9 T HE INDUCTIVE STEP. Assume that we have a map M with |V ∪ V ∗ | > 2. Then M has a contractible edge or coedge, say, edge f . Let M ′ be a map on the same surface S obtained by contracting the edge e ( in the way shown on Figures 1 and 2) V ′ and V ′ ∗ its sets of vertices and covertices. We identify E ′ with E \ { f } and E ′ ∗ with ′ ′∗ ∗ E ∗ \ { f ∗ }, correspondingly, and QE ⊕ QE with a subspace of QE ⊕ QE , so that the ∗ ′ ′ ∗ scalar product h , i on QE ⊕ QE is the restriction of the scalar product on QE ⊕ QE . ′ The map M defines the linear map ′ ∗ ′∗ ι′ : H1 (S \ (V ′ ∪V ′ )) −→ QE ⊕ QE , ′ ′∗ which allows to lift the scalar product from QE ⊕ QE to scalar products h , i′ on H1 (S) and H ′ = H1 (S \ (V ′ ∪V ′ ∗ )). Lemma 8 Contracting a contractable edge f does not affect the scalar product h , i in the following sense: given two cycles c, d ∈ H we can contract f in such way that, for the new map M ′ and appropriate c′ , d ′ ∈ H ′ , hc, d, i = hc′ , d ′ i′ . Proof Figures 1 and 2 depict the process of contraction. x∗ ✦❛ ✯ ✒ ■ ❅ ✦✦ ✻∗❛❛❛ ❅ ✦ f ❛ ❅ ✦✦ ❛❛ ★✥ ✦✦❅ ❛❛ ✦ f ✦ ❛❥ ✉v k ✦ ❛ ❅✉✛ u ❛ ✦ ❨❛ ❅ ✻✦✦✦ ❛❛ ✧✦ ❛❛ ❅✦ ❛❛ ✦✦ ❅ ✦ ❛❛ ✦ ❅ ❛✙ ✦✦ ❘ ❅ ✠ ∗ y ❘ d c✠ Figure 1: Fragment of the map M before contraction. When contracting the edge f we wish to keep all changes restricted to the closure of the union of two countries of the dual map M ∗ containing the endpoints u and v of the contracted edge f . Figure 1 is pre-contraction and Figure 2 is post-contraction. The horizontal edge f = (uv) has been contracted to a point u′ = v′ combining the vertices at its ends, and the corresponding coedge f ∗ = (x∗ y∗ ) has disappeared. The cycles c′ and d ′ are canonical images of c and d in H1 (S \ (V ′ ∪V ′ ∗ )). As a result, c′ , in comparision with c, has lost its intersections with the coedge f ∗ and edge f but has attained intersections with every edge e 6= f which had exited from v prior to contraction; notice, however, that the sign of the index of intersection has changed: (c, e) = −(c′ , e). 10 R. F. Booth et al., Lagrangian Matroids and Maps on Orientable Surfaces x′ ∗ ✦ ✯❛❛ ✒ ■ ❅ ✦✦ ❛❛ ❅ ✦ ❛❛ ❅ ✦✦ ❛❛ ✦✦❅ ❛❛ ✦✦ ′ ′ ❅ ✉ ❥ ✦ ❛ ❛❛ u = v ❨ ✦✦ ❛❛ ✦ ❅ ✦ ❛❛ ❅✦ ✦ ❛❛ ✦ ❅ ❛❛ ✦✦ ❅ ✠ ✙✦ ❛✦ ❘ ❅ y′ ∗ ❘ ′ ✠ c′ d Figure 2: Map M ′ after contraction. Hence ∑ ι′ (c′ ) = ι(c) − (c, f ∗ ) f ∗ − (c, f ) f − (c, f ) · e e exits from v, e6= f = ι(c) − (c, f ∗ ) f ∗ − (c, f ) · ∑ e. e exits from v If k is a small circle around v, as shown on Figure 1, then ∑ e = ι(k) e exits from v and ι′ (c′ ) = ι(c) − (c, f ∗ ) f ∗ − (c, f )ι(k). Analogously ι′ (d ′ ) = ι(d) − (d, f ∗ ) f ∗ − (d, f )ι(k). Notice that hι(c), ι(k)i = hι(d), ι(k)i = hι(k), ι(k)i by Lemma 7 and compute: hc′ , d ′ i′ h f ∗, f ∗i = 0 by definition of the scalar product h , i . Now we can = hι(c) − (c, f ∗ ) f ∗ − (c, f )ι(k), ι(d) − (d, f ∗ ) f ∗ − (d, f )ι(k)i = hι(c), ι(d)i − (d, f ∗ )hι(c), f ∗ i − (c, f ∗ )h f ∗ , ι(d)i +(c, f ∗ )(d, f )h f ∗ , ι(k)i + (c, f )(d, f ∗ )hι(k), f ∗ i. But hι(c), f ∗ i = (c, f ), h f ∗ , ι(d)i = (d, f ), h f ∗ , ι(k)i = 1, hence we can simplify: hc′ , d ′ i′ = hι(c), ι(d)i − (d, f ∗ )(c, f ) − (c, f ∗ )(d, f ) +(c, f ∗ )(d, f ) + (c, f )(d, f ∗ ) = = hι(c), ι(d)i hc, di. R. F. Booth et al., Lagrangian Matroids and Maps on Orientable Surfaces 11 ⋄ Since contraction of an edge (coedge) does not change the scalar product h , i on H1 (S), we can complete the proof of Theorem 5 by induction on |V ∪V ∗ |. 4 Non-orientable surfaces Obviously in the case when S is a not necessary orientable compact surface, we can make all homological computations modulo 2. Symmetric scalar product in that case is also skew symmetric, and, using obvious modifications in terminology and notation, one can prove the following two results. Theorem 9 The image ι(H) of H = H1 (S\(V ∪ V ∗ )) under the map c 7→ ι(c) is an ∗ isotropic subspace of the symplectic space FE2 ⊕ FE2 . Theorem 10 If M is a map on a compact surface S then the set B of its bases is a representable over F2 symplectic Lagrangian matroid. Acknowledgement The authors thank David Stone and Peter Symonds for valuable discussions. References [1] E. Artin, Geometric Algebra, Interscience Publishers, 1957. [2] R. F. Booth, Oriented Lagrangian orthogonal matroids, in preparation. [3] A. V. Borovik and I. M. Gelfand, W P-matroids and thin Schubert cells on Tits systems, Advances Math. 103 (1994) 162–179. [4] A. V. Borovik, I. M. Gelfand and N. White, Symplectic matroids, J. Algebraic Combinatorics 8 (1998) 235–252. [5] A. V. Borovik, I. M. Gelfand and N. White, Coxeter Matroids, Birkhäuser, Boston, in preparation. [6] A. Bouchet, Greedy algorithm and symmetric matroids, Mathematical Programming 38 (1987) 147–159. [7] A. Bouchet, Maps and ∆-matroids, Discrete Math. 78 (1989) 59–71. [8] A. Bouchet, A. Dress, and T. Havel, ∆-matroids and metroids, Advances in Math. 91 (1992) 136–142. [9] K. S. Brown, Buildings, Springer-Verlag, 1988. [10] A. Dold, Lectures of Algebraic Topology, 2nd edition, Springer-Verlag, Berlin a. o., 1980. [11] A. W. Dress and T. F. Havel, Some combinatorial properties of discriminants in metric vector spaces, Advances Math. 62 (1986) 285–312. [12] R. Rado, Note on independence functions, Proc. London math. Soc. (3) 7 (1957) 300–320. R. F. Booth et al., Lagrangian Matroids and Maps on Orientable Surfaces 12 [13] D. Stone, private communication. [14] A. Vince, N. White, Orthogonal Matroids, in preparation. [15] D. J. A. Welsh, Matroid Theory, Academic Press, London a.o., 1976. [16] W. Wenzel, Geometric algebra of ∆-Matroids and related combinatorial geometries, habilitationsschrift, Bielefield, 1991.