%% 2/28/97 \input amstex \documentstyle{amsppt} %\NoRunningHeads \mag=1200 \magnification=\magstep1 \hcorrection{.25in} \advance\vsize-.75in \input epsf.tex %%%%%%%%%%%%%%%%%%%%% author macros %%%%%%%%%%%%%%%%% \def\Fig#1#2#3{\medskip\vbox{\epsfysize=#1truein \centerline{\epsfbox{#2}} \centerline{\bf Figure #3}}\medskip} \def\blk{{$\underline{\qquad}$}} \def\bcite{\cite{$\underline{\qquad}$}} \def\what{\widehat} \def\wtil{\widetilde} \def\hatN{\widehat N} \def\hatP{\widehat P} \def\hatQ{\widehat Q} \def\rint{\text{\rm int }} \def\nhd{\text{\rm nhd}} \def\bp{\text{\bf p}} \def\bq{\text{\bf q}} \def\ep{\varepsilon} \def\real{{\Bbb R}} \def\que{{\Bbb Q}} \def\zed{{\Bbb Z}} \def\B{{\Cal B}} \def\C{{\Cal C}} \def\D{{\Cal D}} \def\W{{\Cal W}} \def\chix{\raise.5ex\hbox{$\chi$}} \def\scoprod{\ \raise.5ex\hbox{$\scriptstyle\coprod$}\ } %%%%%%%%%%% end of author macros %%%%%%%%%%%%%%%%% \topmatter \title Combinatorial methods in Dehn surgery\endtitle \author C. McA. Gordon\endauthor \leftheadtext{C. M{\fiverm c}A. GORDON} %\affil The University of Texas at Austin\endaffil \address Department of Mathematics, The University of Texas at Austin, Austin, TX 78712-1082 \endaddress \curraddr MSRI, 1000 Centennial Dr., Berkeley, CA 94720 \endcurraddr \email gordon\@math.utexas.edu\endemail \thanks Partially supported by NSF Grant DMS-9626550.\endthanks \thanks Research at MSRI supported in part by NSF grant \#DMS 9022140. \endthanks \thanks To appear in the Proceedings of the Workshop of {\it Knots '96}, the fifth MSJ International Research Institute in Knot Theory, Waseda University, Tokyo, Japan, 1996. \endthanks \abstract This is an expository paper, in which we give a summary of some of the joint work of John Luecke and the author on Dehn surgery. We consider the situation where we have two Dehn fillings $M(\alpha)$ and $M(\beta)$ on a given 3-manifold $M$, each containing a surface that is either essential or a Heegaard surface. We show how a combinatorial analysis of the graphs of intersection of the two corresponding punctured surfaces in $M$ enables one to find faces of these graphs which give useful topological information about $M(\alpha)$ and $M(\beta)$, and hence, in certain cases, good upper bounds on the intersection number $\Delta(\alpha, \beta)$ of the two filling slopes. \endabstract \endtopmatter \document \head 1. Introduction\endhead This expository paper is an expanded version of part of the author's lectures at the Workshop. The remaining part of the lectures covered material that is discussed in Sections~2 and 3 of the survey article \cite{Go}. Here, we give an introductory account of the combinatorial methods developed by John Luecke and the author (mainly in the proof of the Knot Complement Conjecture \cite{GL2}) for studying various questions about Dehn surgery. For more details, see [GL2], [GL3] and [GL4]. The setting is that we have two Dehn fillings $M(\alpha)$, $M(\beta)$ on a 3-manifold $M$, which contain surfaces $\hatP,\hatQ$ respectively, and the main goal is to obtain sharp upper bounds on the intersection number of $\alpha$ and $\beta$, under certain hypotheses on $\hatP$ and $\hatQ$. In Section 2 we describe how $\hatP$ and $\hatQ$ give rise to labelled intersection graphs $G_P \subset \hatP$, $G_Q\subset \hatQ$. The idea of using such graphs in the context of Dehn surgery is due to Litherland \cite{L}. In Section 3 we introduce the algebraic notion of a {\it type\/}, which plays a key role in the theory. In Section 4 we show how certain faces or collections of faces of $G_P$ give topological information about $M(\beta)$ (and/or $\hatQ$), and of course similarly for $G_Q$. Section 5 contains the main combinatorial assertion, Theorem 5.1, which says that, if $G_P$ and $G_Q$ are graphs as in Section~2, then either $G_P$ represents all types or $G_Q$ contains a configuration we call a {\it $(p-\chix (\hatP))$-web\/}. Finally, Section 6 contains some applications, mainly to Dehn surgery on knots in $S^3$, although we also say something about the case where $M(\alpha)$ and $M(\beta)$ are reducible. We have tried to keep the discussion as general as possible, allowing $\hatP$ and $\hatQ$ to have arbitrary genus until the last part of Section~5. It must be admitted that this generality is somewhat bogus, inasmuch as in all the applications in Section~6, $\hatQ$ is a 2-sphere and $\hatP$ is either a 2-sphere or a torus. (For statements which apply to surfaces of arbitrary genus see \cite{T} and \cite{R}.) The main point is that if $\hatQ$ is a 2-sphere then, if $G_Q$ contains a $(p-\chix(\hatP))$-web, it contains one that is innermost in the obvious sense, and in such a {\it great\/} web one can find useful faces, namely Scharlemann cycles. Nevertheless, we hope that presenting the material in this way clarifies the logical structure of the argument. \head 2. Graphs of surface intersections\endhead Let $M$ be a compact, orientable, irreducible 3-manifold with torus boundary. Let $\alpha$ be a {\it slope\/}, that is, the isotopy class of an essential embedded circle, on $\partial M$. Then the result of {\it $\alpha$-Dehn filling\/} on $M$ is the manifold $M(\alpha) = M\cup V_\alpha$, where $V_\alpha$ is a solid torus, glued to $M$ via a homeomorphism $\partial M\to \partial V_\alpha$ taking $\alpha$ to the boundary of a meridian disk of $V_\alpha$. If $\alpha$ and $\beta$ are two slopes on $\partial M$, then $\Delta(\alpha, \beta)$ will denote the minimal geometric intersection number of $\alpha$ and $\beta$. One finds in practice that statements of the following form tend to hold, and this is the main type of result that we shall be seeking: \smallskip \itemitem{} {\it if $M(\alpha)$ and $M(\beta)$ have certain special properties, then $\Delta (\alpha,\beta)$ is bounded above by some $\Delta_0$.} \smallskip \noindent The bound $\Delta_0$ will depend on the properties in question. The situation in which we are particularly interested, and to which our methods apply, is when $M(\alpha)$ and $M(\beta)$ contain certain kinds of surfaces. So suppose that $\hatP ,\hatQ$ are (closed, orientable) surfaces in $M(\alpha)$, $M(\beta)$ respectively. We may assume that $\hatP$ meets $V_\alpha$ in a finite collection of meridian disks, so that $P = \hatP\cap M$ is a surface in $M$ each of whose boundary components has slope $\alpha$. Similarly, $\hatQ$ gives rise to a surface $Q$ in $M$ whose boundary components have slope $\beta$. For our machinery to be applicable, it is important that $\partial P$ and $\partial Q$ be non-empty. So, we may state our basic assumption as follows: \roster \item"(A1)" {\it there are properly embedded surfaces $(P,\partial P)$, $(Q,\partial Q) \subset (M,\partial M)$ such that $\partial P$ and $\partial Q$ are non-empty, and each component of $\partial P$ (resp. $\partial Q$) has slope $\alpha$ (resp. $\beta$).} \endroster By an isotopy of (say) $P$ we may assume in addition that \roster \item"(A2)" {\it $P$ and $Q$ intersect transversely, and each component of $\partial P$ meets each component of $\partial Q$ in exactly $\Delta (\alpha, \beta)$ points.} \endroster It is clear, however, that for any $\alpha$ and $\beta$ we can always find surfaces $P$ and $Q$, of arbitrary genus, satisfying (A1) and (A2), and therefore we must impose some additional conditions if we are to extract any non-trivial information from this situation. The technical assumption which enables us to do this is: \roster \item"(A3)" {\it each arc component of $P\cap Q$ is essential in $P$ and in $Q$.} \endroster By (A2), $P\cap Q$ consists of a finite disjoint union of circles and properly embedded arcs, the endpoints of the arcs being the points of intersection of $\partial P$ with $\partial Q$. Condition (A3) says that for no arc component $\gamma$ of $P\cap Q$ is there an arc $\delta \subset \partial P$, with $\partial \gamma=\partial \delta$, and a disk $D\subset P$ such that $\partial D= \gamma\cup\delta$ (and similarly for $Q$). We now describe some conditions under which (A3) holds. Recall that a closed orientable surface $S$ in a 3-manifold $N$ is {\it essential\/} if either $S$ has positive genus, is incompressible in $N$, and is not parallel to a component of $\partial N$, or $S$ is a 2-sphere which does not bound a 3-ball in $N$. First suppose \roster \item"(a)" {\it $\hatP$ is essential in $M(\alpha)$ and $M$ contains no essential surface homeomorphic to $\hatP$.} \endroster Let $K_\alpha \subset M(\alpha)$ denote the core of the solid torus $V_\alpha$. We choose $\hatP$ (among all essential surfaces in $M(\alpha)$ homeomorphic to $\hatP$) so that $p= |\partial P| = |\hatP\cap K_\alpha|$ is minimal. Then $p>0$ by hypothesis. Also, standard arguments show that $P$ is incompressible and boundary incompressible in $M$. In particular, we may assume that no circle component of $P\cap Q$ bounds a disk in $Q$. If $\hatQ$ also satisfies (a) (with $M(\alpha)$ replaced by $M(\beta)$), and is chosen to minimize $q= |\partial Q| = |\hatQ \cap K_\beta|$, then, again by standard arguments, we may assume that condition (A3) holds. Another case of interest is \roster \item"(b)" {\it $\hatP$ is a Heegaard surface for $M(\alpha)$ and $K_\alpha$ cannot be isotoped to lie on $\hatP$.} \endroster If $\hatP$ satisfies (a) and $\hatQ$ satisfies (b) (for $M(\beta)$), then Gabai \cite{Ga2} shows that (A3) can be achieved if $K_\beta$ is put in {\it thin position\/} with respect to $\hatQ$. (Gabai explicitly treats the case when $M(\beta) \cong S^3$ and $\hatQ \cong S^2$, but his argument carries over verbatim to any Heegaard surface $\hatQ$.) Finally, if $\hatP$ and $\hatQ$ both satisfy (b) (for $M(\alpha)$ and $M(\beta)$ respectively), then Rieck has shown \cite{R}, using thin position, that again (A3) can be assumed to hold. (The case $M(\alpha) \cong M(\beta) \cong S^3$, $\hatP,\hatQ\cong S^2$ is done in \cite{GL2}, and was also proved independently by Gabai (unpublished).) Given surfaces $P,Q$ in $M$ satisfying (A1), (A2) and (A3), we focus on the arc components of $P\cap Q$, as they lie in $P$ and in $Q$. We regard these arcs as defining graphs $G_P$ and $G_Q$ in $\hatP$ and $\hatQ$ respectively, in the obvious way. Thus the (fat) vertices of $G_P$ are the disks $\hatP -\rint P$, the edges of $G_P$ are the arc components of $P\cap Q$ as they lie in $P$, and similarly for $G_Q$. We now encode some additional structure, as follows. Number the components of $\partial P$\ \ $1,2,\ldots,p$ in the order in which they appear on $\partial M$, and similarly number the components of $\partial Q$\ \ $1,2,\ldots,q$. This gives a corresponding numbering of the vertices of $G_P$ and $G_Q$. Consider an arc component of $P\cap Q$. Its endpoints are points of $\partial P\cap \partial Q$, the intersections of (say) the $i$th component of $\partial P$ with the $j$th component of $\partial Q$, and the $i'$th component of $\partial P$ with the $j'$th component of $\partial Q$. We then label the endpoints of the corresponding edge of $G_P$ with $j$ and $j'$ at vertices $i$ and $i'$ respectively, and similarly for $G_Q$. See Figure~1. \bigskip \Fig{.75}{fig1_ds.eps}{1} We next give a {\it sign\/}, $+$ or $-$, to each vertex of $G_P$, according to the direction on $\partial M$ of the orientation of the corresponding component of $\partial P$, induced by some chosen orientation of $P$. Equivalently, this is the sign of the corresponding intersection point of $K_\alpha$ with $\hatP$ (with respect to some chosen orientations of $M,\hatP$ and $K_\alpha$). In particular, if $\hatP$ separates $M(\alpha)$ then the signs of the vertices $1,2,\ldots,p$ of $G_P$ alternate. Similarly, we give a sign to each vertex of $G_Q$. Note that around each vertex of $G_P$ the edge-endpoint labels occur in order $1,2,\ldots,q$, $1,2,\ldots,q,\ldots$, repeated $\Delta=\Delta(\alpha,\beta)$ times, the ordering being (say) anticlockwise at a positive vertex and clockwise at a negative vertex. See Figure~2. Similarly, around each vertex of $G_Q$ we see the labels $1,2,\ldots,p$, $1,2,\ldots,p,\ldots,$ repeated $\Delta$ times. \bigskip \Fig{2.5}{fig2_ds.eps}{2} Since $M,P$ and $Q$ are orientable, an arc component of $P\cap Q$ joins points of intersection of $\partial P$ with $\partial Q$ of opposite sign. Hence we have the {\it parity rule\/}: if an edge of $G_P$ joins vertices $i$ and $i'$ and the corresponding edge of $G_Q$ joins vertices $j$ and $j'$, then $i$ and $i'$ have the same sign if and only if $j$ and $j'$ have opposite signs. (See Figure~1.) Condition (A3) becomes, in graph-theoretic language, the condition that $G_P$ and $G_Q$ contain no trivial loops. We will denote by $\bq$ the set of (edge-endpoint) labels $\{1,2,\ldots,q\}$ of $G_P$. We also have the associated {\it $\bq$-intervals\/} $(1,2),(2,3),\ldots, (q-1,q),(q,1)$. \bigskip \Fig{2.5}{fig3_ds.eps}{3} Note that if $D$ is a disk face of $G_P$, then $\partial D$ consists of an alternating sequence of {\it edges\/} and {\it corners\/}, where the edges are edges of $G_P$ (i.e., arc components of $P\cap Q$), and the corners are $\bq$-intervals $(i,i+1)$ (i.e., arcs in $\partial P$ between consecutively labelled components $i,i+1$ of $\partial Q$. See Figure~3. Similar remarks apply to $G_Q$. We may describe the philosophy behind our approach as consisting of two parts: \medskip \noindent {\bf Combinatorial:} use the one-one correspondence between the edges of the labeled graphs $G_P$ and $G_Q$ to show that either $G_P$ contains certain configurations or $G_Q$ contains certain (perhaps other) configurations. \smallskip \noindent{\bf Topological:} use the existence of certain collections of faces of $G_P$ (resp. $G_Q$) to get topological information about the pair $(M(\beta),\hatQ)$ (resp. $(M(\alpha),\hatP))$. These will be elaborated in Sections 5 and 4 respectively. \remark{Remark} For simplicity we have assumed that $\partial M$ is a torus, but everything carries over without much change if we allow $M$ to have additional boundary components (with $\alpha$ and $\beta$ being slopes on some fixed torus component of $\partial M$). In this more general setting, we may also allow $\hatP$ and/or $\hatQ$ to have non-empty boundary. \endremark \head 3. Types\endhead We now introduce a purely algebraic concept, that of a {\it type\/}, which plays an important role in the theory under discussion. The reader may choose to skip to Section~4 and return to the present section when necessary. Let $q$ be a positive integer. A {\it $q$-type\/} is a $q$-tuple ($\ep_1,\ep_2,\ldots,\ep_q)$, where $\ep_i=\pm$, $1\le i\le q$. We say that $a= (a_1,a_2,\ldots,a_q) \in \zed^q$ {\it represents\/} the $q$-type $\tau = (\ep_1,\ep_2,\ldots,\ep_q)$ if and only if \roster \item"(1)" for some $\eta=\pm$, sign $a_i = \eta\ep_i$ for each $i$ such that $a_i\ne0$; and \item"(2)" $\sum\limits_{i=1}^q |a_i|\ge2$. \endroster Condition (2) merely excludes the zero vector, together with vectors all of whose co-ordinates are zero except one, which is $\pm1$. Note that $a$ represents $\tau$ if and only if it represents $-\tau$. Also, there are $2^{q-1}$ $q$-types up to sign, including the {\it trivial\/} type, which by definition has $\ep_1=\ep_2 =\cdots = \ep_q$. \example{Example} There are $2^2=4$ 3-types (up to sign): $+++$, $-++$, $+-+$, and $++-$. $(1,0,-2)$ represents $-++$ and $++-$. \endexample A set $A\subset \zed^q$ {\it represents all $q$-types\/} if and only if, for each $q$-type $\tau$, there exists $a\in A$ such that $a$ represents $\tau$. \example{Examples} \roster \item"(1)" If $|k|\ge2$, then $\{(0,\ldots,0,k,0,\ldots,0)\}$ represents all $q$-types. \item"(2)" $\{(1,0,1),(-1,1,0),(1,1,-1)\}$ represents all 3-types. \item"(3)" If $1\le r\le q$, then $A\subset\zed^q$ represents all $q$-types if and only if \item"{}" $\{(a_1,\ldots,a_r,0,a_{r+1},\ldots,a_q): (a_1,\ldots,a_q)\in A\}$ represents all $(q+1)$-types. \endroster \endexample For $A\subset \zed^q$, let $c(A)$ be the number of co-ordinates $1\le i\le q$ such that $a_i\ne0$ for some $a\in A$. Then we may regard $A\subset \zed^{c(A)} \subset \zed^q$ in the obvious way. By (3) above, $A$ represents all $c(A)$-types if and only if it represents all $q$-types. Thus we may use the phrase $A$ {\it represents all types\/} without ambiguity. The key property of types is the following ``all types implies torsion'' theorem due to Parry \cite{P}. \proclaim{Theorem 3.1 {\rm (Parry)}} If $A\subset \zed^q$ represents all types then there exists $A_0 \subset A$ such that $\zed^q$ modulo the subgroup generated by $A_0$ has non-trivial torsion. \endproclaim We remark that it is not true that $A_0$ can be chosen to represent all types; equivalently, it is not true that if $A\subset \zed^q$ is a minimal set of representatives of all types then $\zed^q/(A)$ has non-trivial torsion. (Here, {\it minimal\/} means that no proper subset of $A$ represents all types.) For example, $A= \{(1,2,1), (-1,1,1), (1,-1,2), (1,1,-1)\}$ is clearly a minimal set of representatives of all types, but $\zed^3 /(A)=0$. A useful fact, proved in \cite{GL4, Lemma 4.4}, is that if $A\subset \zed^q$ represents all types then either $A$ contains a basis for $\real^q$ or there exists $A_1\subset A$ such that $c(A_1) 1-\chix (\hatP)/p$. Then either $G_P$ represents all types or $G_Q$ contains a $(p-\chix (\hatP))$-web. \endproclaim Most of the remainder of this section will be devoted to a sketch of the proof of Theorem~5.1. First we deal with the case of the trivial type, which is different from the general case. Define $\Lambda$ to be the subgraph of $G_Q$ consisting of all edges of $G_Q$ joining vertices of the same sign. If some component of $\Lambda$ is not a $(p-\chix (\hatP))$-web, then $G_Q$ contains more than $(p-\chix (\hatP))$ edges joining vertices of opposite sign. By the parity rule, the corresponding edges of $G_P$ join vertices of the same sign. Let $\Sigma$ be the subgraph of $G_P$ consisting of all vertices of $G_P$, and all edges of $G_P$ joining vertices of the same sign. Then $$\align \chix (\hatP) & = V-E + {\textstyle\sum} \chix (f) \ \text{ (summed over all faces $f$ of $\Sigma$ )}\\ & < p- (p-\chix (\hatP)) + {\textstyle\sum} \chix (f)\ . \endalign$$ Hence $\sum\chix (f) >0$, implying that $\Sigma$ has a disk face. This face is then a face of $G_P$ whose vertices all have the same sign, and which therefore represents the trivial $\bq$-type. For non-trivial $\bq$-types we proceed as follows. Define a graph $\Gamma \subset \hatP$ by: $\bullet$ the {\it vertices\/} of $\Gamma$ consist of the {\it fat\/} vertices (i.e., the vertices of $G_P$), together with {\it dual\/} vertices $v(D)$, one in the interior of each face $D$ of $G_P$; $\bullet$ the {\it edges\/} of $\Gamma$ join each dual vertex $v(D)$ to the fat vertices in the boundary of the corresponding face $D$. See Figure 8. \bigskip \Fig{1.5}{fig8_ds.eps}{8} Now let $\tau$ be a $\bq$-type. We define the directed graph $\Gamma (\tau) \subset \hatP$ to be the graph $\Gamma$, with edges oriented according to the following rule. Let $e$ be an edge of $\Gamma$, with one endpoint at the fat vertex $v$, lying in a $\bq$-interval $(i,i+1)$ at that vertex. Then we orient $e$ \roster \item"{}" {\it inwards\/} at $v$ if $(\tau|(i,i+1))\cdot\text{sign }v=+$, and \item"{}" {\it outwards\/} at $v$ if $(\tau|(i,i+1))\cdot\text{sign }v=-$. \endroster As an example, if $q=6$ and $\tau = +-+- - -$, then around the vertices of $G_P$ the edges of $\Gamma(\tau)$ are oriented as shown in Figure~9. \bigskip \Fig{2.00}{fig9_ds.eps}{9} The reason for defining the orientation on the edges of $\Gamma (\tau)$ in this way is the following, which is immediate from the definition. \proclaim{Proposition 5.2} A disk face $D$ of $G_P$ represents $\tau$ if and only if the corresponding dual vertex $v(D)$ is a sink or source of $\Gamma (\tau)$. \endproclaim Our search for representatives of types is thus translated into the study of the directed graphs $\Gamma (\tau)\subset \hatP$. Here we will use the following very elegant combinatorial formulation of the Poincar\'e-Hopf Index Theorem, due to Glass \cite{Gl}. Consider any directed graph $\Omega$ in a closed surface $S$. For each vertex $v$ of $\Omega$, let $s(v)$ be the number of {\it switches\/} (i.e., changes in orientation of successive edges) around $v$, and for each face $f$ of $\Omega$, let $s(f)$ be the number of switches around $\partial f$. See Figure~10. \bigskip \Fig{1.5}{fig10_ds.eps}{10} Define the {\it index\/} of a vertex or face by $$I(v) = 1- {s(v)\over2}\quad ,\quad I(f) = \chix(f)- {s(f)\over2}\ .$$ In particular, a vertex of positive index is a sink or source $(I(v)=1)$, and a face of positive index is a disk whose boundary is a cycle $(I(f)=1)$. \proclaim{Lemma 5.3} {\rm (Glass).} Let $\Omega$ be a directed graph in the closed surface $S$. Then $\sum I(v) + \sum I(f) = \chix (S)$. \endproclaim \demo{Proof} (See \cite{Gl}.) Each corner between adjacent edges at a vertex contributes exactly 1 to $\sum s(v) + \sum s(f)$. Hence $$\eqalignno{ \chix (S) & = V-E+{\textstyle\sum}\chix(f)\cr &= V- {\#\text{ corners}\over2} + {\textstyle\sum}\chix(f)\cr &= V - {(\sum s(v) + \sum s(f))\over2} +{\textstyle\sum}\chix(f) \cr &= {\textstyle\sum}I(v) + {\textstyle\sum}I(f)\ .&\qed\cr}$$ \enddemo A label $i$ which at a fat vertex lies immediately between oppositely oriented edges of $\Gamma (\tau)$ is a {\it switch label\/} of $\tau$. (Equivalently, $i$ is a switch label if and only if $\tau |(i-1,i)$ and $\tau|(i,i+1)$ have opposite signs.) If the edges of $\Gamma(\tau)$ adjacent to $i$ are oriented in a clockwise (resp. anticlockwise) direction around $i$, then $i$ is a {\it clockwise\/} (resp. {\it anticlockwise\/}) switch label. Note that this is well-defined, i.e., independent of the sign of the fat vertex under consideration; see Figure~9. Let $C(\tau),A(\tau)\subset \bq$ be the set of clockwise and anticlockwise switch labels of $\tau$, respectively. As an example, for the type $\tau$ illustrated in Figure~9, $C(\tau) = \{2,4\}$, $A(\tau)=\{1,3\}$. An edge $e$ of $G_P$ is a {\it clockwise\/} (resp. {\it anticlockwise\/}) {\it switch edge\/} if the labels at the endpoints of $e$ both belong to $C(\tau)$ (resp. $A(\tau)$). A {\it switch edge\/} is an edge of $G_P$ that is either a clockwise or an anticlockwise switch edge. Note that the faces of $\Gamma (\tau)$ are in one-one correspondence with the edges of $G_P$, and that under this correspondence, faces of $\Gamma(\tau)$ of index~1 correspond to switch edges of $G_P$. See Figure~11. \bigskip \Fig{.75}{fig11_ds.eps}{11} Now let $\tau$ be a non-trival $\bq$-type, and write $c(\tau) = |C(\tau)|$, $a(\tau) = |A(\tau)|$. Thus $c(\tau) = a(\tau)>0$. If $v$ is a fat vertex of $\Gamma (\tau)$, then $$s(v) = \Delta (c(\tau) + a(\tau))= 2\Delta c(\tau)\ .$$ Therefore $$I(v) = 1 - {s(v)\over2} = 1-\Delta c(\tau)\ .$$ Assume that $G_P$ does not represent $\tau$. Then by Proposition~5.2, $\sum_{v\text{ dual}} I(v)\le 0$. Therefore, by Lemma~5.3, $${\textstyle\sum}I(f)\ge\chix (\hatP) - {\textstyle\sum}_{v\text{ fat}} I(v) = \chix (\hatP) - p(1-\Delta c(\tau))\ .$$ Note that since $c(\tau) \ge1$ and $\Delta >1-\chix (\hatP)/p$ by hypothesis, the last quantity above is $>0$. By the remark above following the definition of a switch edge, the number of switch edges of $G_P \ge \sum I(f)$. Hence we may assume without loss of generality that there are at least $\sum I(f)\over2$ clockwise switch edges, and so the number of endpoints of clockwise switch edges $\ge \sum I(f) \ge p\Delta c(\tau) - (p-\chix (\hatP))$. Now there are $\Delta c(\tau)$ clockwise switch labels at each vertex of $G_P$, giving a total of $p\Delta c(\tau)$ such labels in $G_P$, and so there are at most $(p-\chix (\hatP))$ of these labels that are not endpoints of clockwise switch edges of $G_P$. Let $\Lambda$ be the subgraph of $G_Q$ consisting of those edges that correspond to clockwise switch edges of $G_P$. (In particular, the vertices of $\Lambda$ correspond to a subset of $C(\tau)$.) As noted above, $\Lambda$ is non-empty. Also, there are at most $(p-\chix (\hatP))$ occurrences of labels at vertices of $\Lambda$ that are not endpoints of edges of $\Lambda$. Hence if $$\align \text{\it all elements of $C(\tau)$ have the same sign,}&\qquad (*c)\cr \text{and {\it all elements of $A(\tau)$ have the same sign,}}&\qquad (*a) \endalign$$ then all the vertices of $\Lambda$ have the same sign, and so (a connected component of) $\Lambda$ is a $(p-\chix (\hatP))$-web, as desired. (Note that we need to make both assumptions $(*c)$ and $(*a)$, as we have no control over whether there are at least $\sum I(f)\over2$ clockwise or anticlockwise switch edges.) If at least one of $(*c)$ and $(*a)$ does not hold, then we take {\it derived types\/} until both do hold, and then work backwards. We now briefly discuss this inductive procedure. For this, we have to work in the following more general setting. Consider a non-empty set of labels $L\subset \bq$. Associated with $L$ is the set of {\it $L$-intervals\/}, which are the intervals $(\ell_1,\ell_2)$ between successive elements of $L$. An {\it $L$-type\/} is defined in the obvious way, to be an $|L|$-type where the $i$th co-ordinate is formally associated with the $i$th $L$-interval. Define $G(L)$ to be the subgraph of $G_P$ consisting of all edges of $G_P$ with at least one endpoint label belonging to $L$. Thus $G(L)$ and $G_P$ have the same vertices, and $G(\bq) =G_P$. Note that although the corners of the faces of $G(L)$ are not necessarily $L$-intervals, each is contained in a unique $L$-interval. Hence, for each disk face $D$ of $G(L)$, by taking the algebraic sum of the $L$-intervals containing the corners of $D$ we get an element $[D]\in\zed^{|L|}$. Then, very much as before, we say that $D$ {\it represents\/} the $L$-type $\tau$ if and only if \roster \item"(1)" $[D]$ represents $\tau$ (in the sense of Section 3); and \item"(2)" ({\it coherence condition\/}) no $L$-interval occurs as the $L$-interval containing a corner of $D$ at two vertices of $D$ of opposite sign. \endroster We define the directed graph $\Gamma (\tau)$ as before (starting with $G(L)$), orienting each edge according to the restriction of $\tau$ to the $L$-interval containing the corresponding corner (and the sign of the fat vertex in question). Proposition~5.2 continues to hold with $G_P$ replaced by $G(L)$. Let $\tau$ be a non-trivial $L$-type. We have $C(\tau), A(\tau)\subset L$, the set of clockwise (resp. anticlockwise) switches of $\tau$, as before. The argument we have just given above carries over verbatim to our present more general setting, so we have the following lemma. \proclaim{Lemma 5.4} Let $\tau$ be a non-trivial $L$-type, satisfying $(*c)$ and $(*a)$, such that $G(L)$ does not represent $\tau$. Then $G_Q$ contains a $(p-\chix (\hatP))$-web. \endproclaim The {\it derivative\/} of a non-trivial $L$-type $\tau$ is the $C(\tau)$-type $d\tau$ defined as follows. Let $(c,c')$ be a $C(\tau)$-interval. Then $(c,c')$ contains a unique element $a\in A(\tau)$. We define $d\tau$ by $$d\tau | (c,c') = \text{sign }a\ .$$ \example{Example} Taking $q=16$ and starting with the $\bq$-type $\tau = + - + + - + - - + - +++ - - +$, Figure~12 below illustrates how one obtains $d\tau$ and $d^2\tau$. \endexample \topinsert {\epsfysize=7.5truein \centerline{\epsfbox{fig12_ds.eps}}} \centerline{\bf Figure 12} \endinsert The key property of the definition of the derivative of a type is the following proposition, which says that to find a representative of $\tau$ it is enough to find a representative of $d\tau$. \proclaim{Proposition 5.5} Let $\tau$ be a non-trivial $L$-type. Then any face of $G(C(\tau))$ representing $d\tau$ contains a face of $G(L)$ representing $\tau$. \endproclaim \demo{Sketch Proof} We shall give enough of the proof to at least explain the reason for the definition of $d\tau$. Let $D$ be a face of $G(C(\tau))$ representing $d\tau$. Let $\Gamma_D (\tau) = \Gamma (\tau) \cap D$. \enddemo \proclaim{Claim} $\Gamma_D(\tau)$ has either a face of index $1$ or a dual vertex of index $1$. \endproclaim \demo{Proof of Claim} This is proved by doubling $(D,\Gamma_D(\tau))$ along the boundary, and applying Lemma~5.3 to the double $2\Gamma_D(\tau)\subset 2D\cong S^2$. Note that the faces of $2\Gamma_D(\tau)$ are the faces of $\Gamma_D(\tau)$ (each appearing twice), together with a face $f_e$ for each edge $e\subset \partial D$ (with $e\subset f_e$). Hence the conclusion will follow if we show that $$|\{ \text{fat vertices of $2\Gamma_D(\tau)$ of index 1}\}| \le |\{ \text{faces $f_e$ of index $-1$}\}|\ .$$ But this in turn follows from the fact that, by definition of $G(C(\tau))$, each $e\subset \partial D$ has at least one endpoint label $\in C(\tau)$ (see \cite{GL2, p.398} for details). A dual vertex of $\Gamma_D(\tau)$ of index 1 will correspond to a face of $G(L)$, contained in $D$, representing $\tau$. So, by the claim above, we are done once we show that no face of $\Gamma_D(\tau)$ has index~1. Such a face corresponds to a switch edge $e$ of $G(L)$. Now $e$ cannot be a clockwise switch edge, for such edges are edges of $G(C(\tau))$, and hence cannot lie in the interior of the face $D$ of $G(C(\tau))$. So assume that $e$ is an anticlockwise switch edge, with endpoint labels $a_1,a_2\in A(\tau)$ at vertices $v_1,v_2$ respectively; see Figure~13. Then, by the parity rule, $(\text{sign }v_1)(\text{sign }a_1) \ne (\text{sign }v_2)(\text{sign }a_2)$. But, recalling the definition of $d\tau$, this contradicts the fact that $D$ represents $d\tau$.\qed \enddemo \bigskip \Fig{.75}{fig13_ds.eps}{13} Returning to the proof of Theorem 5.1, suppose that one of the conditions $(*c),(*a)$ fails for the $\bq$-type $\tau$. Note that $C(\tau) = A(-\tau)$. Hence, if we define $$\tau_0 = \cases \hphantom{-}\tau\ ,&\text{if $\tau$ does not satisfy $(*a)$}\cr -\tau\ ,&\text{if $\tau$ satisfies $(*a)$ but not $(*c)$,} \endcases$$ then $(*a)$ fails for $\tau_0$. Hence $d\tau_0$ is a non-trivial type. If $d\tau_0$ satisfies $(*c)$ and $(*a)$, stop. If not, define $$\tau_1 = \cases \hphantom{-}d\tau_0 \ ,&\text{if $d\tau_0$ does not satisfy $(*a)$}\cr -d\tau_0\ ,&\text{if $d\tau_0$ satisfies $(*a)$ but not $(*c)$} \endcases$$ Continuing in this way, we obtain a sequence $\tau_0,\tau_1,\ldots,\tau_n$, $n\ge1$, where $\tau_0 =\pm\tau$, $\tau_i = \pm d\tau_{i-1}$ is a non-trivial $C(\tau_{i-1})$-type, $1\le i\le n$, and $\tau_n$ satisfies $(*c)$ and $(*a)$. If $G(C(\tau_{n-1}))$ does not represent $\tau_n$, then, by Lemma~5.4, $G_Q$ contains a $(p-\chix (\hatP))$-web. If $G(C(\tau_{n-1}))$ does represent $\tau_n$, then successive applications of Proposition~5.5 show that $G_P$ represents $\tau$. This completes our sketch of the proof of Theorem 5.1. \medskip We have seen, in Section 4, that if $G_P$ represents all types then we get useful topological information about $(M(\beta),\hatQ)$. What if $G_Q$ contains a $(p-\chix (\hatP))$-web? One idea is that a web might give rise to Scharlemann cycles in $G_Q$ (which then in turn give useful topological information about $(M(\alpha),\hatP))$. In order to make this work, however, we must impose a further condition. Namely, we define a {\it great\/} $k$-web in $G_Q$ to be a $k$-web $\Lambda$ which is contained in the interior of a disk $D_\Lambda \subset\hatQ$ with the property that any vertex of $G_Q$ lying in $D_\Lambda$ is a vertex of $\Lambda$. See Figure~14. \bigskip \Fig{3.0}{fig14_ds.eps}{14} \noindent To guarantee that such objects exist, we need to specialize to the case where $\hatQ$ is a 2-sphere. It turns out that one can then prove the following theorem. \proclaim{Theorem 5.6} Assume that $\Delta >1-\chix (\hatP)/p$, and that $\hatQ\cong S^2$. Then either $G_P$ represents all types or $G_Q$ contains a great $(p-\chix (\hatP))$-web. \endproclaim The proof proceeds as follows. By Theorem 5.1, if $G_P$ does not represent all types then $G_Q$ contains a $(p-\chix(\hatP))$-web $\Lambda$. Let $U$ be a component of $\hatQ-\nhd (\Lambda)$, and let $D$ be the disk $\hatQ-U$, containing $\Lambda$. If $\Lambda$ is not a great web, then there are vertices of $G_Q$ in $D$ that are not vertices of $\Lambda$. These vertices correspond to a non-empty subset $L\subset \bq$. One then proves by induction on $|L|$ that either $G_Q$ contains a great $(p-\chix (\hatP))$-web or $G(L)$ represents all $L$-types. (The last step of the induction, which is the desired statement, is the degenerate case where $\Lambda =\emptyset$, $L=\bq$, and $D$ is a disk in $\hatQ$ containing $G_Q$.) This inductive argument is quite subtle, and in particular involves relativizing the notion of the derivative of a type. We refer to \cite{GL3, proof of Theorem~2.5} (which does the case where $\hatP$ is a torus), and thence to \cite{GL2, Section~2}, for more details. \head 6. Applications\endhead In this section we sketch the proofs of some results which use the methods we have discussed. The first three are about Dehn surgery on knots in $S^3$, and the proofs of these will all be based on the following statement, which is an immediate consequence of Theorem~5.6 and (Ta) of Section~4. \proclaim{Theorem 6.1} Suppose that $M(\beta)\cong S^3$ and that $\hatQ$ is a Heegaard 2-sphere. If $\Delta >1-\chix (\hatP)/p$ then $G_Q$ contains a great $(p-\chix(\hatP))$-web. \endproclaim When $M(\beta) \cong S^3$, we shall make a slight change of notation, writing $K$ for $K_\beta$, a non-trivial knot in $S^3$, $M_K$ for $M$, the exterior of $K$, and $\mu_K$ for $\beta$, the meridian of $K$. The following theorem is proved in \cite{GL2}. It implies that knots in $S^3$ are determined by their complements. \proclaim{Theorem 6.2} Let $K$ be a non-trivial knot in $S^3$. If $M_K(\alpha) \cong S^3$ then $\alpha = \mu_K$. \endproclaim \demo{Proof} Suppose that $M_K (\alpha) \cong S^3$, with $\Delta (\alpha,\mu_K)\ge1$. Let $\hatP$ be a Heegaard 2-sphere in $M_K(\alpha)$. By Theorem 6.1, $G_Q$ contains a great $(p-2)$-web, $\Lambda$. Hence there exists a label (in fact at least two labels) $i\in \bp$ such that every occurrence of $i$ at a vertex of $\Lambda$ is the endpoint of an edge of $\Lambda$. Moreover, since all the vertices of $\Lambda$ have the same sign, no edge of $\Lambda$ can have the same label at both endpoints, by the parity rule. Hence, by always leaving a vertex of $\Lambda$ along an edge of $\Lambda$ with label $i$ at that vertex, we see that $\Lambda$ contains an {\it $i$-cycle\/}, that is, a cycle of edges which can be consistently oriented so that the tail of each edge has label $i$ (and all the vertices in the cycle have the same sign). See Figure~15. \bigskip \Fig{2.0}{fig15_ds.eps}{15} \noindent Now it is easy to see that a cycle of this kind which is innermost in the disk $D_\Lambda$ (allowing the label $i$ to be an arbitrary element of $\bp$) is a Scharlemann cycle in $G_Q$. Since $\hatP$ is a 2-sphere the edges of this Scharlemann cycle necessarily lie in a disk in $\hatP$. But since $\hatP$ is a Heegaard 2-sphere, this is a contradiction, by (Sa) in Section~4 (here, the roles of $P$ and $Q$ are interchanged).\qed \enddemo \remark{Remark} We observed in the above proof that a great $(p-2)$-web in $G_Q$ always contains a Scharlemann cycle. So we may state \endremark \proclaim{Theorem 6.3} If $\hatP$ and $\hatQ$ are 2-spheres, and $\Delta\ge1$, then either $G_P$ represents all types or $G_Q$ contains a Scharlemann cycle. \endproclaim If $\Delta\ge2$ then the following stronger conclusion holds. \proclaim{Theorem 6.4} If $\hatP$ and $\hatQ$ are 2-spheres, and $\Delta\ge2$, then either $G_P$ or $G_Q$ contains a Scharlemann cycle. \endproclaim This is an immediate consequence of \cite{CGLS, Proposition 2.5.6} (which deals with the case where $\hatP$ and $\hatQ$ are disks). Theorem 6.4 already shows that if $M(\alpha)\cong M(\beta)\cong S^3$ then $\Delta (\alpha,\beta)\le1$, implying that there are at most two inequivalent knots with homeomorphic complements (a fact first proved, by a different argument, in \cite{CGLS}). However, there are examples of graphs $G_P,G_Q$ with $\Delta =1$ for which the conclusion of Theorem~6.4 fails, illustrating the necessity of introducing the more general concept of representing all types. The next application addresses the question of when a reducible manifold can be obtained by Dehn surgery on a knot in $S^3$. \proclaim{Theorem 6.5} Let $K$ be a non-trivial knot in $S^3$. If $M_K(\alpha)$ is reducible then \roster \item"(1)" $M_K(\alpha)$ has a lens space summand; and \item"(2)" $\Delta (\alpha,\mu_K)=1$. \endroster \endproclaim Part (1) was proved in \cite{GL2}; part (2) was proved in \cite{GL1} (by an argument different from that outlined below). Part (1) implies the Property $R$ Conjecture, proved by Gabai \cite{Ga2}. \proclaim{Corollary 6.6 {\rm (Gabai)}} If $K$ is a non-trivial knot in $S^3$ then $M_K(0)$ is irreducible. \endproclaim Part (1) also implies \proclaim{Corollary 6.7} Any homology 3-sphere obtained by Dehn surgery on a knot in $S^3$ is prime. \endproclaim We remark that Auckly, using results from gauge theory, has shown that there are prime homology 3-spheres which cannot be obtained by Dehn surgery on any knot in $S^3$ \cite{A}. The situation described in Theorem 6.5 can occur: if $K$ is a torus knot or cable knot then there is a slope $\alpha$ such that $M_K(\alpha)$ is reducible. However, the Cabling Conjecture \cite{GS} asserts that these are the only knots with this property. This is still open. \demo{Sketch Proof of Theorem 6.5} Here we take $\hatP$ to be an essential 2-sphere in $M_K(\alpha)$. (Note that $M_K$ is irreducible.) By Theorem 6.1, $G_Q$ contains a great $(p-2)$-web $\Lambda$. As in the proof of Theorem~6.2 above, this implies that $G_Q$ contains a Scharlemann cycle, and hence that $M_K(\alpha)$ has a lens space summand (see (Sc) in Section~4). This proves (1). To prove (2), assume that $\Delta (\alpha,\mu_K)>1$. Then, for homological reasons, $\hatP$ separates $M_K(\alpha)$, and hence $p$ is even. If $p=2$ then $P$ is an annulus, and hence $K$ is a cable of a knot $K'$ (which may be trivial). Now it is not hard to show (see the first four lines of the proof of Theorem~3 in \cite{GL1}) that if $M_K(\alpha)$ is reducible for some $\alpha$ with $\Delta (\alpha,\mu_K)>1$ then $M_{K'}(\alpha')$ is reducible for some $\alpha'$ with $\Delta (\alpha',\mu_{K'})>1$. Hence, by induction it suffices to prove the result when $K$ is not cabled. So assume $p\ge4$. As in the proof of Theorem 6.2 above, there is a label in $\bp$ such that each of the $\Delta$ occurrences of that label at each vertex of $\Lambda$ is the endpoint of an edge of $\Lambda$. One can then show, using the fact that $\Delta \ge2$, that $\Lambda$ contains Scharlemann cycles of $G_Q$ on distinct $\bp$-intervals $(i,i+1)$, $(j,j+1)$ (see \cite{GL4, Proof of Theorem 2.3}). This allows one to construct a new essential 2-sphere $\hatP' \subset M_K(\alpha)$ such that $|\hatP'\cap K_\alpha|