Advances in Pure Mathematics, 2012, 2, 119123 http://dx.doi.org/10.4236/apm.2012.22017 Published Online March 2012 (http://www.SciRP.org/journal/apm) Homology Curve Complex Ningthoujam Jiban Singh1*, Himadri Kumar Mukerjee2 1Department of Mathematics, Assam University, Silchar, India 2Department of Mathematics, NorthEastern Hill University, NEHU Campus, Shillong, India Email: {njiban, himadrinehu}@gmail.com Received October 22, 2011; revised November 1, 2011; accepted November 12, 2011 ABSTRACT A homological analogue of curve complex of a closed connected orientable surface is developed and studied. The dis tance in this complex is shown to be quite computable and an algorithm given (Theorem 3.5). As an application of this complex it is shown that for a closed orientable 3manifold, and any of its Heegaard splittings, one can give an algo rithm to decide whether the manifold contains a 2sided, nonseparating, closed incompressible surface (Theorem 1.1). Keywords: Homology Curve Complex; Heegaard Splittings; Incompressible Surface 1. Introduction Jaco and Oertel ([1]) gave an algorithm to decide if a 3manifold is a Haken manifold. Their algorithm is an offshoot of an algorithm given by Haken himself. Haken has developed in 1960’s ([2]) an algorithm to decide if a fundamental normal surface of a given presentation of a compact irreducible 3manifold is injective. Any normal surface can be constructed from these fundamental nor mal surfaces and if the input is a normal surface then by successive application of the above algorithm one can check if the normal surface is injective. But one does not know for how many normal surfaces (finite or infinite) this algorithm has to be run. Jaco and Oertel ([1]) pro duced a finite collection of constructible normal surfaces (test surfaces) only on which this algorithm has to be run. Results of similar flavour has been found by Jaco, Let scher, and Rubinstein [3] and many others. We, on the other hand, give here an algorithm whose input is any Heegaard splitting of the given manifold. We develop a homological version of curve complex, which we call “homology curve complex”. The term homology curve complex used in this paper is inspired by the term used in the set of open problems posed by Joan Birman in the arXiv preprint [4], page no. 8, line 12, but is different from what she meant there. This term has also been used recently by Ingrid Irmer in his arXiv preprint [5] with a different meaning. We prove that for surfaces of genus greater than one, this complex is connected (3.3), hence a notion of dis tance between vertices, which we call “Hdistance” can be defined. We give an algorithm which returns Hdis tance of two given vertices, theorem (3.5). Using this complex we define an analogue of the Hempel distance of a Heegaard splitting of a 3manifold. This distance is then used to decide if the manifold contains a closed, twosided incompressible surface or not, a homological analogue of Johnson and Patel ([6], lemma 4), which also extends to genus 2 in our case. Finally an algorithm is given which takes as its input a Heegaard splitting of a given closed connected orientable 3manifold and decides if this distance is zero or not in polynomial time. Every closed connected orientable 3dimensional mani fold M admits a Heegaard splitting, i.e. , a decomposition into two orientable handlebodies V and V′ which meet along their boundary. This common boundary is called a Heegaard surface. Alternately, we may view M as ob tained from the two handlebodies by identifying their boundaries under a homeomorphism f : ∂V → ∂V′. Hee gaard splittings are a convenient way to define a 3 manifold, but a priori it is difficult to get structural in formation about the manifold from them. It is in this light the following result assumes importance. Theorem (Theorem 4.1) Given a closed, connected, orientable 3 manifold M and a Heegaard splitting g VV of genus g > 1, there is an algorithm, which runs in poly nomial time, to decide whether M contains a nonsepa rating, 2sided, closed incompressible surface. In Section 2 we give a brief recollection of complex of curves and some related concepts. We introduce in Sec tion 3 an analogue of curve complex, “homology curve complex”, associated with the surface and a notion of distance, “Hdistance”, and prove several results de *The first author acknowledges CSIR, India, for financial supports under grant F. No. 9/347(159)/2k3EMRI dated 13.09.2003. C opyright © 2012 SciRes. APM
N. J. SINGH ET AL. 120 scribing their properties including a result giving an al gorithm to compute the Hdistance between a pair of ver tices: see lemma (3.2), lemma (3.3), theorem (3.5), pro position (3.6), proposition (3.7). Section 4 starts with the introduction of the notion of an analogue of the Hempel distance of a Heegaard splitting followed by a recollec tion of complete meridian systems and some results re lated to these. Finally, we complete the proof of theorem (1.1) giving an algorithm which takes as its input a Hee gaard splitting of the given 3manifold and decide in po lynomial time if the manifold contains a nonseparating, 2sided, closed, incompressible surface. 2. Preliminaries For standard 3manifold terminologies, we refer the reader to Jaco [7]. The curve complex C() for a compact, con nected, closed, orientable surface is the abstract sim plicial complex whose vertices are isotopy classes of essential, simple closed curves in and whose sim plices correspond to sets of distinct isotopy classes which are represented by pairwise disjoint circles (simple closed curves) in . If C() is connected we can define an integer valued distance d(x, y) between a pair of vertices x, y as the number of edges in the shortest edge path be tween them. Given a handlebody V and a homeomor phism f: ∂V, the handlebody set (or a disk complex) is the set of (isotopy classes of) circles in that bound properly embedded essential discs in V. The genus g boundary set is the set of nonseparating circles in such that each bounds a properly embedded, 2sided, incompressible, genus g surface in V and the boundary set is the union =∪g 0 . The Hempel distance, denoted by d(V, V′), of the Heegaard splitting (V, V′; ) as defined in Hempel [8] is given by d(V, V′) = inf{d(x, y): x is a vertex of , y is a vertex of }. The boundary distance as defined in Johnson and Patel [6] is given by ,dd . 3. Homology Curve Complex Let denote a closed, connected and oriented surface of genus g > 1. It is wellknown that H1( ;) has the standard bilinear intersection form ,, which is sym plectic (i.e., x, x = 0, x H1( ;) and the form establishes a selfduality on H1( ;) (i.e. an isomor phism H1( ;) → H1(Hom ;), )), see for example Johnson [9]. For x, y H1( ;), the integer x, y is called the algebraic intersection number between x and y. A basis of H1( ;)) (which is a free  module of rank 2g) is called canonical or symplectic if it is of the form {a1, ···, ag, b1, ···, bg} with ai, aj = bi,bj = 0, and ai, bj = ij (Kronecker delta), i, j {1, 2, ···, g}. It is wellknown that H1( ;) has the standard canonical basis (see Figure 1). A nontrivial element x H1( ;) is said to be primitive (relative to the canonical basis) if its coordi nates are relatively prime. 3.1. Definition We define the homology curve complex of the surface , denoted by HC( ), to be an abstract simplicial complex whose vertices are the primitive elements of H1( ;) and a collection {c1, ···, cm} of m distinct vertices form an (m − 1)simplex if the algebraic inter section numbers ci, cj = 0, i, j {1, ···, m}. In the following, we shall represent a vertex of HC( ) by its coordinates relative to the standard canonical (ordered) basis B. 3.2. Lemma For g > 1, if x, y are distinct vertices of HC( ), then there is a vertex z of HC( ) such that x, z = 0 = y, z. Proof. The standard intersection form , on H1( ;) induces a module homomorphism f: H1( ;) → × defined by t ( t, x, t, y). Since is a PID, ker(f) and im(f) are free submodules of the free modules H1( ;) and × respectively and the sequence 0 → ker(f) → H1( ;) → im(f) → 0 is splitexact. So, H1( ;) = ker(f) im(f). Since di (ker(f)) = H1( m dim ;) − (im(f)) ≥ 2g − 2 ≥ 2, we get a nontrivial element z H1( dim ;) satisfying x, z = 0 = y, z and so by dividing each of the coordinates of z by their gcd, if necessary, we can always take z to be a primitive element. 3.3. Lemma For g > 1, HC( ) is an infinite dimensional, connected abstract simplicial complex and if the integer valued distance dH(x, y) between a pair of vertices x, y is the number of edges in the shortest edge path between them, then dH is explicitly given by 0, if ; 1, if and ,0; 2, otherwise = . , H xy xdxy yyx Proof. It is easy to see that m , the set Am = {(1, x, 0, ···, 0) 2g: 1 ≤ x ≤ m, x } of vertices of HC( ) forms an (m − 1)simplex in HC( ). There Figure 1. A representative of a canonical basis for H1(g;). Copyright © 2012 SciRes. APM
N. J. SINGH ET AL. 121 HC( ) is infinite dimensional. To see that HC( ) is connected, let x, y be distinct vertices of HC( ). If x, y = 0, then they can be joined by an edge by definition; otherwise by lemma (3.2), there is a vertex z such that x can be joined to z by an edge and then z can be joined to y by another edge. Notice that a circle α on is separating if and only if its homology class is zero. There is a characterization of the vertex set of HC( ). 3.4. Lemma (Meyerson [10]) A nontrivial element of H1( ;) can be represented by a nonseparating circle on if and only if it is primitive relative to the standard canonical (ordered) basis of H1( ; ). 3.5. Theorem For g > 1, there is an explicit algorithm which takes as input , a canonical ordered basis B = {a1, ···, ag, b1, ···, bg} for the homology H1( ;), a pair of verti ces α, β of HC( ) and returns the distance between them. Proof. By part (f) of Theorem 1 in [11], there is an al gorithm to compute the algebraic intersection number α, β and also the coordinates of α and β relative to the basis B in polynomial time. If α = β then by lemma 3.3 dH(α, β) = 0. If α β by lemma 3.3 again, dH(α, β) = 1 if and only if the algebraic intersection number between α and β = 0. If neither of these hold, then by lemma 3.3 again dH(α, β) = 2. 3.6. Proposition With the same notations as above, every simplicial auto morphism : HC( ) → HC( ) induces an isometry on the metric space (HC0( ), dH), where HC0( ) de notes the set of vertices of HC( ). Proof. Let x, y be vertices of HC( ) with dH(x, y) = k, where k = 0, 1, or 2. For k = 0, 1, the result follows from the fact that a simplicial automorphism maps m simplices to msimplices and in particular if x y and x, y = 0, thereby dH(x, y) = 1, then x, y form an edge. So, λ(x) λ(y) will also form an edge, so λ(x), λ(y) = 0 thereby dH(λ(x), λ(y)) = 1. If k = 2, i.e. if x, y 0, by lemma (3.2) there is a vertex z of HC( ) such that x, z = 0 = y, z. So, λ(x), λ(z) = 0 = λ(y), λ(z). This gives, by triangle inequality, dH(λ(x), λ(y)) ≤ 2. However, dH(λ(x), λ(y)) < 2 implies that dH(λ(x), λ(y)) = 0 or 1. This implies that λ(x), λ(y) = 0 and so x, y = 0, which is a contradiction. So, dH(λ(x), λ(y)) = 2. 3.7. Proposition Let k {0, 1, 2}. For g > 1, the set {( x, y) HC0( ) × HC0( )dH(x, y) = k} is infinite. Proof. For k = 0, 1, the result follows from lemma (3.3). For k = 2, there are vertices a, b in the vertex set of HC( ) with algebraic intersection number 1, which also have respective representative circles with geometric intersection number 1. Consider the positive Dehn twist Ta. Now, n , a(b), b = b + na, ba, b = na, ba, b + b, b = n and so by definition, n T n a dH(T (b), b) = 2, whenever n 0. This proves the result. 4. Applications As an application of the concepts developed in the pre vious sections we shall present a complexity measure for Heegaard splitting using the homology curve complex and prove. 4.1. Theorem (Theorem 1.1) Given a closed, connected, orientable 3 manifold M and a Heegaard splitting g VV of genus g > 1, there is an algorithm, which runs in polyno mial time, to decide whether M contains a nonsepa rating, 2sided, closed incompressible surface. Before giving the proof we need to introduce some more notations and definitions: 4.2. Definition For a Heegaard splitting (V, V′; ), let D (resp. D′) denote the set of vertices in HC( ), each represented by a circle whose homology class is nontrivial in , but trivial in V (resp. V′). Then, we define the Hdistance, denoted by dH(V, V′), for the splitting (V, V′; ) to be the inf{dH(x, y): x D, y D′}. As immediate consequence of lemma (3.3), we have the following. 4.3. Lemma For (g > 1), the Hdistance of the Heegaard splitting g VV takes only the finite values 0, 1 or 2. 4.4. Remark For any Heegaard splitting g VV of genus 3 or greater, Johnson and Patel [6] showed, using complex of curves (different from homology curve complex), an analogous result that distance d( ) is equal to 0, 1 or 2. 4.5. Definition A complete meridian system (or simply cms) for a han dlebody V is a set L = {D1, ···, Dg} of pairwise disjoint properly embedded discs on V such that the manifold obtained by cutting V open along L is a 3ball. The Copyright © 2012 SciRes. APM
N. J. SINGH ET AL. 122 boundaries of the discs of a cms for V form a meridian system for the surface ∂V. Given a cms L = {D1, ···, Dg} for a handlebody V, let α be a simple arc on the boundary ∂V connecting ∂Di and ∂Dj (i j) with int (α) disjoint from L. Let N denote a regular neighbourhood of ∂Di ∪ ∂Dj ∪ α in . Then, ∂N has three components, one is a copy of ∂Di, one is a copy of ∂Dj and the other one is called a band sum of ∂Di and ∂Dj along α on ∂V which gives arise to a compress ing disc Dij in V (after slight pushing the interior of the disc inside V) with boundary ∂Dij being the band sum. Denote L′ = {D1, ···, Di−1, Dij, Di+1, ···, Dg}. We say that L′ is obtained from L by an elementary slide (and Dij is also called a disc slide). If a cms L′ on V is obtained from a cms L on V via a finite number of elementary slides and isotopies, we say that L and L′ are equivalent and denoted by L L′. We also say that L slides to L′. The following fact about cmss of discs on a handlebody V is well known (see for example [12]), which tells us how two cmss of discs for a handlebdy are related. 4.6. Proposition Assume that L is a cms of discs for a handlebody V and L slides to L′, then L′ is also a cms of discs for V. Con versely, any two cmss of discs for V are equivalent. 4.7. Remark It is wellknown that if D is a nonseparating properly embedded compressing disc for a genus g handlebody V, then {D} can be extended algorithmically to a cms of discs for V in g many steps. Proof of the theorem (4.1). We will begin with the following characterization of a closed connected orien table 3manifold which is an extension of JohnsonPatel ([6], lemma 4) to the setting of homology curve complex. 4.8. Theorem Let M be a closed connected orientable 3manifold with a Heegaard splitting (V, V′; ) of genus g > 1. Then for any pair of cmss L = {D1, ···, Dg}, L′ = {1 D , ···, D } for the respective handlebodies V and V′, the following statements are equivalent: 1) M contains a nonseparating, twosided, closed in compressible surface; 2) H1(M) is infinite; 3) The matrix A = (aij), where aij is the algebraic in tersection number of Di and D , is singular; 4) d( ) = 0; 5) dH(V, V′) = 0. Proof. 1 2 is a classical result (see Jaco [7], or JohnsonPatel [6]). 2 3 4 is due to Johnson Patel ([6], lemma 4). By definition D is a quotient of , consisting of homology classes of elements of , so d( ) = 0 implies dH(V, V′) = 0, or 4 5. Now we prove that 5 1. If dH(V, V′) = 0 then there exists x D ∩ D′ HC( ). Pick two disjoint simple closed curves and ′ on , each of which represents x. Then, and ′ bound twosided, nonseparating properly em bedded compact surfaces F V and F′ V′ respectively. Since and ′ are homologous in , they cobound a compact subsurface S of . The union F ∪ S ∪ F′ is a twosided, nonseparating closed surface embedded in M. By compressing repeatedly, if necessary, we eventu ally find a closed, nonseparating, twosided incompre ssible surface in M. We are ready to complete the proof of theorem (4.1). Proof. (Completion of proof of theorem (4.1)) By theorem (4.8), existence of a nonseparating, two sided, closed incompressible surface in M is reduced to examining if dH(V, V′) = dH(D, D′) = d( ) = 0, which in turn reduced to examining if the matrix A = (aij) is singular, where aij is the algebraic intersection number of Di and ∂Dj. One can compute the entries aij of the matrix A in polynomial time (see for example [11] theorem 1 (f)) and the nonsingularity of a matrix can be determined in polynomial time (see for example section 2.3 of [13]). This completes the proof of the theorem (4.1). 4.9. Problem It will be interesting to characterize those closed ori entable 3manifolds which possess Heegaard splittings having Hdistance 1 and/or 2. 5. Acknowledgements We acknowledge Prof. Joan Birman for her useful com ments on an earlier version of the draft of our paper. We also acknowledge the anonymous referees for their useful comments. REFERENCES [1] W. Jaco and U. Oertel, “An Algorithm to Decide If a 3 Manifold Is a Haken Manifold,” Topology, Vol. 23, No. 2, 1984, pp. 195209. doi:10.1016/00409383(84)900399 [2] W. Haken, “Theorie der Normalflachen,” Acta Mathe matica, Vol. 105, No. 34, 1961, pp. 245375. doi:10.1007/BF02559591 [3] W. Jaco, D. Letscher and J. H. Rubinstein, “Algorithms for Essential Surfaces in 3Manifolds,” Contemporary Mathematics, Vol. 314, 2002, pp. 107124. doi:10.1090/conm/314/05426 [4] J. Birman, “The Topology of 3Manifolds, Heegaard Dis tances and the Mapping Class Group of a 2Manifold,” arXiv.org, 2005. http://arxiv.org/abs/math/0502545 Copyright © 2012 SciRes. APM
N. J. SINGH ET AL. Copyright © 2012 SciRes. APM 123 [5] I. Irmer, “Geometry of the Homology Curve Complex,” arXiv.org, 2011. http://arxiv.org/abs/1107.3547 [6] J. Johnson and T. Patel, “Generalized Handlebody Sets and NonHaken 3Manifolds,” Pacific Journal of Mathe matics, Vol. 235, No. 1, 2005, pp. 3541. [7] W. Jaco, “Lectures on ThreeManifold Topology,” CBMS Regional Conference Series in Mathematics, American Mathematical Society, Providence, 1980. [8] J. Hempel, “3Manifolds as Viewed from the Curve Com plex,” Topology, Vol. 40, No. 3, 2001, pp. 631657. doi:10.1016/S00409383(00)000331 [9] D. Johnson, “An Abelian Quotient of the Mapping Class Group Ig,” Mathematische Annalen, Vol. 249, No. 3, 1980, pp. 225242. doi:10.1007/BF01363897 [10] M. D. Meyerson, “Representing Homology Classes of Closed Orientable Surfaces,” Proceedings of AMS, Vol. 61, No. 1, 1976, pp. 181182. [11] M. Schaefer, E. Sedgwick and D. Stefankovic, “Algori thms for Normal Curves and Surfaces,” Lecture Notes in Computer Science, Springer, 2002, New York, pp. 370 380. [12] F. C. Lei, “Complete Systems of Surfaces in 3Mani folds,” Mathematical Proceedings of the Cambridge Phi losophical Society, Vol. 122, No. 1, 1997, pp. 185191. doi:10.1017/S0305004196001545 [13] D. Saunders and Z. D. Wan, “Smith Normal Form of Dense Integer Matrices, Fast Algorithms into Practice,” Proceedings of the 2004 International Symposium on Sym bolic and Algebraic Computation, 47 July 2004, San tander.
