Lagrangian Matroids and Cohomology

Lagrangian Matroids and Cohomology Richard F. Booth Israel M. Gelfand Alexandre V. Borovik David A. Stone∗ Abstract We prove that ∆-matroids associated with maps on compact closed surfaces are representable, with the space of representation provided by cohomology of the surface with punctured points. 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 [10] (or Lagrangian symplectic matroids in the terminology of [6], necessary definitions can be found in the next section). ∆-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 [18] to Lagrangian symplectic matroids. It appears that the proper setting for the representation is provided by cohomology of the surface with punctured vertices and covertices of the map. This observation is a part of an emerging pattern of underlying cohomological structures in representations of matroids and Coxeter matroids; more results in this direction will be published elsewhere [19]. Maps on surfaces also known as ‘fat graphs’, and the present work is a part of an attempt to develop a combinatorial setting for Kontsevich’s graph (co)homology [16, 17] in the context of fat graphs. Some preliminary discussion can be found in [1]. Representability of a Lagrangian symplectic matroid associated with a fat graph with n edges allows us to represent it as a vertex in a very interesting simplicial complex Ωn which we call the combinatorial flag variety of type Cn [7]. There are indications that combinatorial flag varieties are very suitable for cohomological calculations. See, for example, the forthcoming paper [20] which contains the detailed study of cohomology of the combinatorial flag varieties in the closely related case An . More detail will be published elsewhere. ∗ Partially supported by PSC-CUNY Research Awards 667411 and 559437 and by EPSRC grant GR/M24707. 1 1 1.1 Orthogonal matroids and maps Maps on compact surfaces Let S be a connected compact, closed, orientable 2-manifold, with a fixed orientation. A map X on S is a regular CW -complex on S (this means that the closure of every 2-cell is a topological disk). Then a dual complex, X ∗ , is also a regular CW -complex; it is called the dual map for the map X. The vertex-set (or 0-skeleton) of X will be denoted V . The edge-set of X is E; and X 1 is the 1-skeleton of X; [ X1 = {e | e ∈ E }. We assume that the edges of E are oriented in some arbitrary but fixed manner. The vertex-set and edge-set of X ∗ will be denoted V ∗ and E ∗ respectively, their elements will be sometime called covertices and coedges of the map X. There is a natural bijection E ←→ E ∗ such that e∗ is the unique edge of X ∗ such that int e ∩ int e∗ 6= ∅. The edges of E ∗ are oriented so that, at w, the orientation of e followed by that of e∗ , equals the given orientation of S. For F ⊆ E we define F ∗ := { e∗ | e ∈ F } and F := E r F . We call a set F ⊂ E ∪ E ∗ admissible if F ∩ F ∗ = ∅. It will be convenient to index edges in E by elements of 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 [6] and the forthcoming book [8]. 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 if K ∩ K ∗ = ∅. We denote by Jk the set of all admissible k-subsets of J. 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 symplectic 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) r (A ∩ B). This axiom is due to Bouchet [9], Dress and Havel [11, 14], 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 2 elements of Jk for some k. An appropriate axiom system is given in [6]. In this paper, we shall only be concerned with Lagrangian 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. S We say that an admissible set F ⊂ E ∪ E ∗ is independent if S r ( F ) is connected. A basis of the map X is a maximal independent admissible set of (co)edges. Bouchet [10] proved that the set B = B(X) of all bases of a map X 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.3. Theorem 1.1 Let X be a map with n edges on a orientable compact closed surface S. Then (a) all bases of X have cardinality n and (b) 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 ([18], the exposition can be found in any book on matroid theory, see, for example, [22]). Our Theorem 1.1 is a generalisation of this result. Moreover, the orthogonal representation of the matroid B over Q allows to introduce on B a structure of an oriented even ∆-matroid in the sense of Wenzel [23, 24]), or a more refined structure of oriented orthogonal Lagrangian matroid , see Booth [3] for futher discussion. It is also worth mentioning at this point that the classical Spanning Tree Algorithm for graphs, which corresponds to the Greedy Algorithm of matroid theory, also has a natural elementary analogue for maps, as a local procedure for peeling off the surface in one ring-shaped peel [4]. This procedure is the immediate application of the Greedy Algorithm for ∆-matroids (Bouchet [9]) to the Lagrangian matroid asssociated with the map. 1.3 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 , ej 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 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 X aij ej + n X j=1 j=1 3 bij e∗j . It is easy to see that L is a Lagrangian subspace in V if and only if AB t 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 (a) X ∈ Jn and (b) 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 1.2 (A. Vince and N. White [21]) If L is a Lagrangian subspace in V then (a) every independent subset in J belongs to a basis in B, and (b) B is the set of bases of an orthogonal Lagrangian matroid. For a proof that the axioms used to define Lagrangian matroids in [21] are equivalent to the Symmetric Exchange Axiom, see Wenzel [23] or the book [8]. We call an orthogonal matroid arising from a Lagrangian subspace L written by a matrix (A, B) with AB t skew-symmetric an orthogonally representable orthogonal matroid, and say that (A, B) is an orthogonal representation of it over the field K. Note in passing that there is also another way of representing Lagrangian matroids, by Lagrangian subspaces in a symplectic vector space [6]. In the more general setting of Coxeter matroids [5] the fact that every orthogonally representable Lagrangian matroid is a symplectic Lagrangian matroid is explained by the canonical embedding of the corresponding Coxeter groups Dn < Bn = Cn and an observation that the complex of flags of totally isotropic subspaces in an orthogonal space has the natural structure of a non-thick Bn -building [12, pp. 126–127]. 2 Matroids, Representations and Maps Let X 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 r (V ∪ V ∗ ) with coefficients in Q. For a cycle c in H = H1 (S r (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 4 denote by ê the corresponding linear functional ê : c 7→ (c, e) from H ∗ . Thus ê is a cocycle in H 1 (S r (V ∪ V ∗ )). Notice that this H 1 (S r (V ∪ V ∗ )) can be identified with H1 (S, V ∪ V ∗ ) by Poincare-Lefschetz duality [13, VIII.7]. Lemma 2.1 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 Y = V ∪ V ∗ ∪ S f ∈F f . Then we have the triple V ∪V∗ ⊂Y ⊂X of CW -complexes. The lemma immediately follows from the long exact homological sequence for this triple: · · · −→ β2 α 2 H2 (Y, V ∪ V ∗ ) −→ H2 (X, V ∪ V ∗ ) −→ H2 (X, Y ) ∂ α 2 1 −→ H1 (Y, V ∪ V ∗ ) −→ H1 (X, V ∪ V ∗ ) −→ · · · Since H2 (Y, V ∪V ∗ ) = 0, β2 is an injection. If X rY is connected then H2 (X, Y ) is 1-dimensional, 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 (Y, 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 X (c, e)e. ι(c) = e∈E∪E ∗ The main technical result of the paper is: Theorem 2.2 The image ι(H) of H = H1 (Sr(V ∪V ∗ )) under the map c 7→ ι(c) ∗ is an isotropic subspace of the orthogonal space QE ⊕ QE . We postpone the proof of Theorem 2.2 until the next section, and meanwhile deduce from it the main result of the paper, Theorem 1.1. Theorem 2.3 The isotropic subspace ι(H) is Lagrangian, and the Lagrangian orthogonal matroid corresponding to ι(H) has bases which correspond to the bases of the map X. Proof. Notice first that the map X has at least one basis of cardinality n. To construct it, take a spanning tree T in the 1-skeleton X 1 (T can be empty), then ∗ B = T ∪ T is rather obviously a basis of the map X and has cardinality n [10]. If now b1 , . . . , bn are the (co)edges in B then the linear functionals b̂1 , . . . , b̂n on 5 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 ∗ subspace in QE ⊕ QE , it is a Lagrangian subspace. Notice that if we represent ι(H) by a 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 2.1 the columns of M are linearly independent if and only if the correspondent set of (co)edges is independent in X. Hence the bases of the Lagrangian matroid associated with ι(H) are exactly the bases of the map X.  Now Theorem 1.1 is an immediate corollary of Theorem 2.3. 3 Proof of Theorem 2.2 In the proof we shall use H 1 (S, V ∪ V ∗ ) instead of H1 (S r (V ∪ V ∗ )); they are isomorphic by Lefshetz duality. Throughout the proof all coefficients are taken in Q. We need to systematise our notation and bring it closer to conventions of algebraic topology. Recall that S is a connected compact, closed, orientable 2-manifold, with a fixed orientation. Let X be a regular CW -complex on S and X ∗ the dual complex X ∗ . Let X̃ be the cubical complex on S whose cells are the intersections of cells of X and X ∗ . Notation for X. The vertex-set (or 0-skeleton) of X will be denoted V . The edge-set of X is E; and X 1 is the 1-skeleton of X; [ X1 = {e | e ∈ E }. The edges of E are oriented in some arbitrarily but fixed manner. Notation for X ∗ . The vertex-set and edge-set of X ∗ will be denoted V ∗ and E ∗ respectively. There is a natural bijection E ←→ E ∗ such that e∗ is the unique edge of X ∗ such that int e ∩ int e∗ 6= ∅. In this case, int e ∩ int e∗ . consists of a single point, which will be denoted w = w(e) = w(e∗ ). The edges of E ∗ are oriented so that, at w, the orientation of e followed by that of e∗ , equals the given orientation of S. Notation for X̃. Set W = { w(e) | e ∈ E }. Then the vertex-set of X̃ is V ∪ W ∪ V ∗ . The edge-set of X̃ is { e+ , e− , e∗+ , e∗− | e ∈ E }, where (see Figure 1): if e = hv0 , v1 i with ∂e = v1 − v0 then (with w = w(e)) e+ = hw, v1 i, ∂e+ = v1 − w, and 6 e− = hv0 , wi, ∂e− = w − v0 ; ③ v3∗ ✏✏P∗PP ✏✏ PP✄ e ✏ ❈ ✏ P ✻ ✄ ❈ ✲ ✄ v1 v0 ❈ e ❈ ✄ P✄P ✏ ❈ ✏ ✄ PPP ✏✏ ❈ ✏ P✏ v3∗ ✏✏PP ✏ PP e∗+ PP ✄ ❈✏✏ ✏ ✻ ✄ ❈ w ✄ v1 v0 ❈ ✲ e− e+ ❈ ✄ ∗ e− P✄P ✏ ❈ ✏ ✻ ✄ PPP ✏✏ ❈ ✏ P✏ orientation of S v2∗ v2∗ X X̃ Figure 1: Notation for edges of X̃. if e∗ = hv2∗ , v3∗ i with ∂e∗ = v3∗ − v2∗ , then e∗+ = hw, v3∗ i, ∂e∗+ = v3∗ − w, e∗− = hv2∗ , wi, and ∂e∗− = w − v2∗ . Let B be the set of all 2-cells of X̃. Each b ∈ B is oriented consistently with the surface S. Lemma 3.1 For every b ∈ B, there exist unique e1 (b), e2 (b) ∈ E and signs λ1 , λ2 ∈ { +, − } such that, setting ∂1 b = −λ1 e1 (b)λ1 , ∂1∗ b = −λ1 e1 (b)∗−λ1 , ∂2 b = +λ2 e2 (b)λ2 , ∂2∗ b = −λ2 e2 (b)∗+λ2 , then ∂b = ∂1 b + ∂1∗ b + ∂2∗ b + ∂2 b. Proof. See Figure 2.  Lemma 3.2 In this notation, (a) H 1 (X 1 , V ) ≃ C 1 X (which equals QE ). ∗ (b) H 1 (X ∗ 1 , V ∗ ) ≃ C 1 X ∗ (which equals QE ). (c) H 1 (X̃ 1 , V ∪ W ∪ V ∗ ) ≃ C 1 X̃. (d) H 1 (S, V ∪ W ∪ V ∗ ) ≃ Z 1 X̃. Here Z 1 X̃ is the space of 1-cocycles of X̃, in other words, Z 1 X̃ = ker(d1X̃ : C 1 X̃ −→ C 2 X̃). 7 ❈ e1 (b)∗ ✏✏ ❈ ❈❖ e1 (b) ❈ b ❈ ❈ ✧ ✲ ❈✧ ❜ ✄❜ e2 (b) ✄ ✄✄ ✮✏ ✏✏ ❈ ❈ ❈ ❈ ❈ ❜ ❜❈ ✧❈ ✧ ❈ ❈❈ e2 (b)∗ ✻ ❈ ∂1∗ (b) = +e1 (b)∗ ✏ + ✏✏ ❈ ✮ ❈ ✏ ✏ ❈ ∂ (b) ❈ ❈❖ 1= +e1 (b)− ❈ ∗ ∗ b ❈ ❈ ∂2 (b) = −e2 (b)+ ❄ ❈ ❈ ❜ ✧ ❜❈ ✲ ❈✧ ✧❈ ✧ ❜ ∂2 (b) = +e2 (b)+ ✄❜ ❈ ✄ ❈❈ ✄✄ ③ orientation of S Figure 2: For Lemma 3.1: λ1 = −, λ2 = +. Proof. (a) follows by using the cell complex X 1 to compute H 1 (X 1 , V ). The other parts are similar.  Let the map ρ : H 1 (S, V ∪ V ∗ ) −→ H 1 (X 1 , V ) be induced from the inclusion (X 1 , V ) ⊆ (S, V ∪ V ∗ ). Let ρ∗ : H 1 (S, V ∪ V ∗ ) −→ H 1 (X ∗ 1 , V ∗ ), τ : H 1 (X̃ 1 , V ∪ W ∪ V ∗ ) τ ∗ : H 1 (X̃ 1 , V ∪ W ∪ V ∗ ) −→ H 1 (X 1 , V ), −→ H 1 (X ∗ 1 , V ∗ ) be induced likewise from inclusion maps. Set −→ H 1 (X 1 , V ) ⊕ H 1 (X ∗ 1 , V ∗ ), −→ H 1 (X 1 , V ) ⊕ H 1 (X ∗ 1 , V ∗ ). ρ̄ = (ρ, ρ∗ ) : H 1 (S, V ∪ V ∗ ) τ̄ = (τ, τ ∗ ) : H 1 (X̃ 1 , V ∪ W ∪ V ∗ ) Set Σ = im ρ̄. Let Q be the symmetric inner product on C 1 X ⊕ C 1 X ∗ (which is isomorphic to H 1 (X 1 , V ) ⊕ H 1 (X ∗ 1 , V ∗ )), where Q : (C 1 X ⊕ C 1 X ∗ )⊗2 −→ Q is defined by Q(ei , ej ) = Q(e∗i , e∗j ) = 0, Q(ei , e∗j ) = Q(e∗j , ei ) = δij . 8 ∗ The canonical isomorphism from QE ⊕ QE onto C 1 X ⊕ C 1 X ∗ sends ι(H) onto Σ and transforms the inner product h , i into Q( , ). Therefore Theorem 2.2 immediately follows from the following result. Theorem 3.3 The subspace Σ 6 C 1 X ⊕ C 1 X ∗ is isotropic with respect to Q; in other words, the restriction of Q on Σ is identically 0. Proof. Consider the following diagram, in which τ̄ and ρ̄ have been defined above, and f and g are induced by inclusions. By naturality, the diagram commutes. H 1 (S, V ∪ W ∪ V ∗ ) f H 1 (S, V ∪ V ∗ ) −→ ↓g (1) ↓ ρ̄ H 1 (X̃ 1 , V ∪ W ∪ V ∗ ) τ̄ −→ H 1 (X 1 , V ) ⊕ H 1 (X ∗ 1 , V ∗ ) The homomorphism f fits into the long cohomology exact sequence of the triple V ∪ V ∗ ⊆ V ∪ W ∪ V ∗ ⊆ S, namely: H 0 (S, V ∪ V ∗ ) −→ δ H 0 (V ∪ W ∪ V ∗ , V ∪ V ∗ ) −→ H 1 (S, V ∪ W ∪ V ∗ ) f −→ H 1 (S, V ∪ V ∗ ) −→ H 1 (V ∪ W ∪ V ∗ , V ∪ V ∗ ). Now H 0 (S, V ∪V ∗ ) = 0 since S is connected; H 0 (V ∪W ∪V ∗ , V ∪V ∗ ) ≃ H 0 (W ); and H 1 (V ∪ W ∪ V ∗ , V ∪ V ∗ ) = 0 for dimensional reasons. So we have the exact sequence f 0 −→ H 0 W −→ H 1 (S, V ∪ W ∪ V ∗ ) −→ H 1 (S, V ∪ V ∗ ) −→ 0. Applying Lemma 3.2 to commutative diagram (1) now gives 0 −→ H 0 W −→ Z 1 (X̃) ↓g C 1 (X̃) f −→ τ̄ −→ H 1 (S, V ∪ V ∗ ) ↓ ρ̄ C 1 (X) ⊕ C 1 (X ∗ ) −→ 0 (2) Here g is just the inclusion of a subspace, and we shall suppress g from the notation. Lemma 3.4 In this notation, τ̄ (Z 1 X̃) = Σ. Proof. Since f is surjective, Σ = im ρ̄ = im (ρ̄ ◦ f ) = im τ̄ .  9 We shall now define a quadratic form Q̃ on C 1 X̃. First, define ∪1 , ∪2 : (C 1 X̃)⊗2 −→ C 2 X̃ by (α̃ ∪1 β̃)(b) = (α̃ ∪1 β̃)(b) = α̃(∂1 b) · β̃(∂1∗ b) − α̃(∂2 b) · β̃(∂2∗ b); −β̃(∂1 b) · α̃(∂1∗ b) + β̃(∂2 b) · α̃(∂2∗ b). Also define [s] : C 2 X̃ −→ Q by [s] X  X ni b i = ni . Actually, we may identify C 2 X̃ = Z 2 X̃ and (since S has a fixed orientation) Q = H 2 X̃; then [s] is identified with the quotient map Z 2 X̃ −→ Z 2 X̃/B 2 X̃ = H 2 X̃. Now set Q̃ = [s] · (∪1 − ∪2 ) : (C 1 X̃)⊗2 −→ Q. Lemma 3.5 The following diagram commutes: (C 1 X̃)⊗2 τ̄ ⊗2 −→ (C 1 X ⊕ C 1 X ∗ )⊗2 ∪1 − ∪2 ↓ C 2 X̃ ↓Q [s] −→ Q Corollary 3.6 Σ 6 C 1 X ⊕ C 1 X ∗ is isotropic for Q if and only if Z 1 X̃ is isotropic for Q̃. Proof of Lemma 3.5. We must show: (a) Q̃(ei± , ej ± ) = Q̃(e∗i ± , e∗j ± ) = 0 for all i, j; (b) Q̃(ei± , e∗j ± ) = Q̃(e∗j ± , ei± ) = 0 for all i 6= j; (c) Q̃(ei± , e∗i ± ) = Q̃(e∗i ± , ei± ) = 1 for all i. Now (a) and (b) follow from the formulae for ∪1 and ∪2 and from Lemma 3.1. As for (c), writing e for ei , we find (see Figure 3) e+ ∪1 e∗+ = b1 e− ∪1 e∗− = b3 e− ∪1 e∗+ = b2 e+ ∪1 e∗− = b4 10 ✄ ❈ ✄ ✏❈ P ✏ P ✄ ❈ ✏ PP PP✏✏✏ ✄ ❈ ✄ ❈ ③ ✄ ❈ b2 b1 e∗+ orientation of S ✄ ❈ ✻ ✄ ❈ ❍❍ ✄ ❈ ✧✧ ❍✄ ✲ ✲ ❈✧ ✟ ✟ e− e+ ❈ ✄❜❜ ✟ ❜ ❈ ✄ ∗ e ✻− ❈ ✄ b3 b4 ❈ ✄ ✄ ❈ ❈ ✄ ✏✏PPP ✏ ❈ ✄ ✏ PP P✄ ❈✏✏ ❈ ✄ ❈ ✄ Figure 3: For the proof of Lemma 3.5. while e± ∪2 e∗± = 0. Likewise e∗+ ∪2 e+ = −b1 e∗+ ∪2 e− = −b2 e∗− ∪2 e− = −b3 e∗+ ∪2 e+ = −b4 while e∗± ∪1 e± = 0. So Q̃(e∗± , e± ) = 1.  The following lemma completes the proof of the theorem. Lemma 3.7 The subspace Z 1 X̃ is isotropic for Q̃. Proof. Let θ1 : Z 1 X̃ −→ Z 1 X̃/B 1 X̃ = H 1 X̃ ≃ H 1 S and θ2 : Z 2 X̃ = C 2 X̃ −→ Z 2 X̃/B 2 X̃ = H 2 X̃ ≃ H 2 S 11 be the natural projections. Let ∪ : H 1 S ⊗2 −→ H 2 S be the standard cup product. It is known that, for i = 1 and 2, the diagram commutes: ∪i −→ C 2 X̃ Z 1 X̃ ⊗2 (θ1 )⊗2 ↓ ↓ θ2 ∪ H 1 S ⊗2 −→ (3) H 2S (See [15, § 9.3].) As we said before, the orientation of the surface S determines an isomorphism ϕ : H 2 S −→ Q, under which θ2 corresponds to [s] (that is, ϕ ◦ θ2 = [s]). So, for α̃, β̃ ∈ Z 1 X̃, Q̃(α̃, β̃) = [s](α̃ ∪1 β̃ − α̃ ∪2 β̃) = = ϕ ◦ θ2 (α̃ ∪1 β̃ − α̃ ∪2 β̃) ϕ(θ1 (α̃) ∪ θ1 (β̃) − θ1 (α̃) ∪ θ1 (β̃)) = 0.  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 4.1 The image ι(H) of H = H1 (Sr(V ∪V ∗ )) under the map c 7→ ι(c) E∗ is an isotropic subspace of the symplectic space FE 2 ⊕ F2 . Theorem 4.2 If X is a map on a compact surface S then the set B of its bases is a representable over F2 symplectic Lagrangian matroid. References [1] T. V. Alekseyevskaya, A. V. Borovik, I. M. Gelfand and N. White, Matroid homology, to appear. [2] E. Artin, Geometric Algebra, Interscience Publishers, 1957. [3] R. F. Booth, Oriented Lagrangian orthogonal matroids, in preparation. 12 [4] R. F. Booth, A. V. Borovik and I. M. Gelfand, Lagrangian matroids associated with maps on orientable surfaces, Manchester Centre for Pure Mathematics, preprint 1999/, 14 pp. [5] A. V. Borovik and I. M. Gelfand, W P -matroids and thin Schubert cells on Tits systems, Advances Math. 103 (1994) 162–179. [6] A. V. Borovik, I. M. Gelfand and N. White, Symplectic matroids, J. Algebraic Combinatorics 8 (1998) 235–252. [7] A. V. Borovik, I. M. Gelfand and N. White, Combinatorial geometry in characteristic 1, in preparation. [8] A. V. Borovik, I. M. Gelfand and N. White, Coxeter Matroids, Birkhäuser, Boston, in preparation. [9] A. Bouchet, Greedy algorithm and symmetric matroids, Mathematical Programming 38 (1987) 147–159. [10] A. Bouchet, Maps and ∆-matroids, Discrete Math. 78 (1989) 59–71. [11] A. Bouchet, A. Dress, and T. Havel, ∆-matroids and metroids, Advances in Math. 91 (1992) 136–142. [12] K. S. Brown, Buildings, Springer-Verlag, 1988. [13] A. Dold, Lectures on Algebraic Topology, 2nd edition, Springer-Verlag, Berlin a. o., 1980. [14] A. W. Dress and T. F. Havel, Some combinatorial properties of discriminants in metric vector spaces, Advances Math. 62 (1986) 285–312. [15] P. J. Hilton and S. Wylie, Homology Theory, Cambridge, At the University Press, 1960. [16] M. Kontsevich, Formal (non)-commutative symplectic geometry, The Gelfand Mathematical Seminars, 1990–1992, Birkhäuser, 1993, pp. 173–187. [17] M. Kontsevich, Feynman diagrams and low-dimensional topology, First European Congress of Mathematics, Paris, July 6–10, 1992 , Birkhäuser, 1994, vol. 2, pp. 97–122. [18] R. Rado, Note on independence functions, Proc. London math. Soc. (3) 7 (1957) 300–320. [19] D. A. Stone, in preparation. [20] D. A. Stone, On the topology of the combinatorial flag varieties, in preparation. [21] A. Vince, N. White, Orthogonal Matroids, in preparation. [22] D. J. A. Welsh, Matroid Theory, Academic Press, London a.o., 1976. [23] W. Wenzel, Geometric algebra of ∆-Matroids and related combinatorial geometries, Habilitationsschrift, Bielefield, 1991. [24] W. Wenzel, Pfaffian forms and ∆-matroids, Discrete Math. 115 (1993) 253–256. 13