text:
\begin{document}
    \maketitle

    \begin{abstract}The main result of this paper is that for every closed, connected, orientable, irreducible 3-manifold $M$, there is an integer $ n_M$ such that for any graph $\gamma$ which has a 3-connected minor whose genus is greater than $n_M$, if $\gamma$ has no involution then every embedding of $\gamma$ in $M$ is chiral. By contrast, the paper also proves that for every graph $\gamma$, there are infinitely many closed, connected, orientable, irreducible 3-manifolds $M$ such that some embedding of $\gamma$ in $M$ is pointwise fixed by an orientation reversing involution of $M$.

\end{abstract}

\section{Introduction}

	We say that a graph $\Gamma$ embedded in a $3$-manifold $M$ is {\it achiral}, if there is an orientation reversing homeomorphism $h$ of $M$ leaving $\Gamma$ setwise invariant.  If such an $h$ exists, we say that it is a homeomorphism of the pair $(M,\Gamma)$.  If no such homeomorphism exists, we say that the embedded graph $\Gamma$ is {\it chiral}.

	We can think of a knot as an embedding of a circular graph with some number of vertices in $S^3$.  Independent of the number of vertices on the graph, some embeddings of it are chiral while others are achiral.  By contrast, there exist graphs which have the property that all of their embeddings in $S^3$ are chiral.  Such a graph is said to be {\it intrinsically chiral} in $S^3$ because its chirality depends only on the intrinsic structure of the graph and not on the extrinsic topology of an embedding of the graph.  The following theorem provides a method of constructing graphs that are intrinsically chiral in $S^3$.

\begin{theorem}
\cite{fl4}
\label{IC} Every non-planar graph $\gamma$ with no order $2$ automorphism is intrinsically chiral in $S^3$.
\end{theorem}

Since chirality is defined for graphs embedded in any 3-manifold, it is natural to  ask whether a graph which is intrinsically chiral in $S^3$ would necessarily be intrinsically chiral in other 3-manifolds.  Our first result shows that no graph can be intrinsically chiral in every 3-manifold, or even in every ``nice'' $3$-manifold.

\begin{theorem}   For every graph $\gamma$, there are infinitely many closed, connected, orientable, irreducible 3-manifolds $M$ such that some embedding of $\gamma$ in $M$ is pointwise fixed by an orientation reversing involution of $M$.
\end{theorem}

Theorem~\ref{theorem1} can be thought of as a generalization of the fact that every planar graph has an embedding in $S^3$ which is pointwise fixed by a reflection of $S^3$.

On the other hand, our main result is a generalization of Theorem \ref{IC}, which shows that for any given ``nice'' 3-manifold $M$, there are infinitely many graphs with no automorphism of order $2$ are intrinsically chiral in $M$.  In particular, a graph $\gamma$ is said to be {\it $3$-connected}, if at least three vertices together with the edges containing them must be removed to disconnect $\gamma$ or reduce $\gamma$ to a single vertex.  A graph $\gamma_1$ is said to be a {\it minor} of a graph $\gamma_2$, if $\gamma_1$ can be obtained from $\gamma_2$ by deleting and/or contracting some number of edges.  Our main result is as follows.

\begin{theorem}\label{ICManifolds}  For every closed, connected, orientable, irreducible 3-manifold $M$, there is an integer $ n_M$ such that any graph with no order $2$ automorphism which has a 3-connected minor $\lambda$ with $\mathrm{genus}(\lambda)>n_M$ is intrinsically chiral in $M$.
\end{theorem}

Note that by contrast with Theorem~\ref{ICManifolds} which is for $3$-manifolds without boundary, Ikeda  \cite{Ik} has shown in the theorem below that for ``nice'' 3-manifolds with aspherical boundary, any graph with large enough genus which has a certain type of  automorphism of order $2$  has an achiral hyperbolic embedding in the double of the manifold.

\begin{ikeda} \cite{Ik}  Let $M$ be a compact, connected, orientable, 3-manifold with non-empty aspherical boundary.  Then there is an integer $n_M$ such that for any abstract graph $\lambda$ with $\mathrm{genus}(\lambda)>n_M$ and no vertices of valence 1, any automorphism of order $2$ of $\lambda$ that does not restrict to an orientation preserving automorphism of a cycle in $\lambda$ can be induced by an orientation reversing involution of some hyperbolic embedding of $\lambda$ in the double of $M$.\end{ikeda}

Since the word ``graph'' is used in different ways by different authors, we note here that in the current paper as well as in \cite{fl4} a {\it graph} is defined to be a connected $1$-complex consisting of a finite number of vertices and edges such that every edge has two distinct vertices and there is at most one edge with a given pair of vertices.

 In Section 2, we prove Theorem~\ref{theorem1}.  In Section 3, we prove Theorem~\ref{ICManifolds} making use of a proposition, which we then prove in Section 4.  Throughout the paper we work in the smooth category.

\bigskip

\section{Achiral embeddings}

The goal of this section is to prove Theorem~\ref{theorem1}.  To that end, we prove the following proposition.
Note that we use $\mathrm{dim}_{\mathbb{Z}}(H_1(M,\mathbb{Z}))$ to denote the dimension of the first $\mathbb{Z}$-homology group of $M$ and we use $\mathrm{dim}_{\mathbb{Z}_2}(H_1(M,\mathbb{Z}_2))$ to denote the dimension of the first $\mathbb{Z}_2$-homology group of $M$.

\setcounter{prop}{0}
\begin{prop}  Let $S$ be a closed, orientable surface.
Then for infinitely many closed, connected, orientable, irreducible 3-manifolds $Q$ such that $\mathrm{dim}_{\Z_2} (H_1 (Q,\Z_2)) = \mathrm{genus}(S)$, there is an embedding of $S$ in $Q$ which is pointwise fixed by an orientation reversing involution of $Q$.
\label{prop:inf}
\end{prop}

The proof of Proposition~\ref{prop:inf} will make use of the idea of a {\em disk-busting} curve, which is a simple closed curve in a handlebody that intersects every essential, properly embedded disk in the handlebody.   For example, a core of a solid torus is disk busting in the solid torus.  For a genus 2 handlebody with fundamental group generated by $a$ and $b$ an example of a disk-busting curve is one that includes into the fundamental group of the handlebody as $abab^{-1}$ (see Figure~\ref{diskbust}).  All handlebodies have disk-busting curves and Richard Stong \cite{S} gives an algorithm to recognize them.  For more on disk-busting curves see  \cite{H2} or  \cite{S}.

\begin{figure}[here]
\begin{center}
\includegraphics[width=.4\textwidth]{diskbust.eps}
\caption{A disk-busting curve in a genus 2 handlebody.}
\label{diskbust}
\end{center}
\end{figure}

\begin{proof}
 Let $g$ be the genus of a closed orientable surface $S$.  Let $M$ be the manifold obtained by gluing genus $g$ handlebodies $V_1$ and $V_2$ together along $S$ in such a way that there is an orientation reversing involution $h$ interchanging $V_1$ and $V_2$ which pointwise fixes the surface $S$.  Now $M$ is a closed, connected, orientable 3-manifold $M$ such that $\mathrm{dim}_{\Z_2} (H_1 (M,\Z_2)) = \mathrm{genus}(S)$.  However, $M$ is reducible.

In order to create an irreducible 3-manifold, we first remove neighborhoods $N_1$ and $N_2$ of identical disk busting curves $C_1$ and $C_2$ in the interiors of the handlebodies $V_1$ and $V_2$ such that $N_1$ and $N_2$ are interchanged by the involution $h$.
Note that since $ \mathrm{cl}(M-(S \cup  N_1 \cup  N_2))$ consists of two identical handlebodies from which neighborhoods of disk busting curves have been removed, the inclusion of $S$ in each component of $ \mathrm{cl}(M-(S \cup  N_1 \cup  N_2))$ is incompressible.  Now we sew in identical non-trivial knot complements $Q_1$ and $Q_2$ along $\partial N_1$ and $\partial N_2$ respectively so that the Seifert surfaces of the $Q_i$ are glued in where the meridians of the $N_i$ were.

Let $Q$ denote the 3-manifold obtained in this way.  Then the restriction $ h| \mathrm{cl}(M-( N_1 \cup  N_2))$ can be extended to an orientation reversing involution of $Q$ that pointwise fixes $S$.  Note that the components of $\mathrm{cl}(Q-(S \cup \partial Q_1 \cup  \partial Q_2))$
 that contain $S$ are homeomorphic to the corresponding components of $\mathrm{cl}(M-(S \cup  \partial N_1 \cup  \partial N_2))$ that contain $S$.
\medskip

\noindent{\bf Claim 1:}  The surfaces $S$, $\partial Q_1$, and $\partial Q_2$ are each incompressible in $Q$

\medskip

\noindent{\bf Proof of Claim 1:} Assume one of $S$, $\partial Q_1$, or $\partial Q_2$ is compressible in $Q$.  Then there is a compressing disk $D$ for one of these surfaces that meets $S \cup \partial Q_1 \cup \partial Q_2$ transversally in a minimal number of components.  If the interior of $D$ intersects one of the surfaces $S$, $\partial Q_1$, or $\partial Q_2$, then an innermost loop on $D$ bounds a compressing disk $\Delta$ for that surface whose interior is disjoint from the other surfaces.  Now since each $Q_i$ is a knot complement, $\Delta$ cannot be contained in $Q_i$.  Thus $\Delta$ must be contained in some component of $\mathrm{cl}(Q-(S \cup  Q_1 \cup  Q_2))$.  Also, since the $C_i$ are disk busting for  the $V_i$, $\partial \Delta$ cannot be in $S$.  So $\Delta$ is a compressing disk for one of the $\partial N_i$ in $\mathrm{cl}(V_i-N_i)$.  By compressing along $\Delta$ we obtain a sphere in $\mathrm{cl}(V_i-N_i)$.  Hence $N_i$ is contained in a ball in $V_i$, contradicting the fact that $C_i$ was disk busting.

\bigskip

\noindent{\bf Claim 2:}  $Q$ is irreducible.

\medskip

\noindent{\bf Proof of Claim 2:} Let $F$ be a sphere in $Q$ and assume without loss of generality that $F$ intersects $S \cup \partial Q_1 \cup \partial Q_2$ transversally in a minimal number of components.  If $F$ intersects any of $\partial Q_1$, $\partial Q_2$, or $S$, then there is an innermost loop on $F$ bounding a disk $D$ that is a compressing disk for $\partial Q_1$, $\partial Q_2$, or $S$ in  $ \mathrm{cl}(Q-(S \cup \partial Q_1 \cup \partial Q_2))$. But this violates Claim 1.  Thus $F$ is contained in some $Q_i$ or $V_i - Q_i$.  However, the $Q_i$ and the $V_i - Q_i$ are  irreducible.  Therefore $Q$ is irreducible.
\bigskip

Now, recall that $\mathrm{dim}_{\Z_2} (H_1 (M,\Z_2)) = \mathrm{genus}(S)$.  Also, it can be seen using a Mayer-Vietoris sequence that replacing the handlebodies $N_1$ and $N_2$ by the knot complements $Q_1$ and $Q_2$ does not change the first homology, since a meridional disk of $N_i$ is replaced by a Seifert surface in $Q_i$.  Thus $\mathrm{dim}_{\Z_2} (H_1 (Q,\Z_2)) = \mathrm{genus}(S)$, and hence $Q$ has the properties required by the proposition.

In order to prove that we can find infinitely many such 3-manifolds $Q$, we first show as follows that if $Q_i$ is the complement of a connected sum of distinct knots $K_1 \# K_2 \# \dots \# K_n$, then $Q$ contains at least $2n$ disjoint non-parallel incompressible tori.  The first such torus is a boundary parallel torus in $Q_i$.  The second such torus is a follow-swallow torus that swallows $K_1$ and follows the other $n-1$ tori.  The third swallows  $K_1 \# K_2$ and follows the other $n-2$ and so on, each time swallowing one more knot and following one less until the $n^{th}$ torus swallows all of the $K_j$ with $j\not =n$. Since we have $n$ such disjoint tori in each $Q_i$, this gives us $2n$ such disjoint tori in $Q$. These tori cannot be parallel to each other since they bound distinct knot complements in $Q_i$.

 To see that these $2n$ tori are incompressible in $Q$, suppose there is a compressing disk for one of the tori that intersects $\partial Q_1 \cup \partial Q_2 \cup  S$ transversally in a minimal number of components. An innermost loop on the disk would be a compressing disk for $\partial Q_1$, $\partial Q_2$ or $S$, again contradicting Claim 1.  Thus the torus would have to be compressible in one of the $Q_i$.  But it is well known that follow-swallow tori are incompressible in knot complements, so the $2n$ tori must be incompressible in $Q$ as well.

Thus $Q$ contains $2n$ disjoint, non-parallel, incompressible tori. On the other hand, it follows from Kneser-Haken finiteness, that for a given compact, orientable manifold, such as $Q$, there is some finite constant $t_1$ such that $Q$ cannot contain more than $t_1$ disjoint closed, non-parallel, incompressible surfaces (for example, see Proposition 1.7 in \cite{Ha} or see \cite{KH}).  Thus $t_1>2n$.

To get a manifold $Q'$ which is not homeomorphic to $Q$, we replace each $Q_i$ by the complement of a knot that is the connected sum of more than $\frac{1}{2}t_1$ knots.  Now $Q'$ will contain $t_2$ disjoint, non-parallel, incompressible tori with $t_2 > t_1$, and thus $Q'$ is distinct from $Q$.  By repeating this process, we can create an infinite sequence of such manifolds each containing more disjoint, non-parallel, incompressible tori than the previous manifold did.  \end{proof}
\bigskip

Since every graph embeds in a closed orientable surface, the following theorem is an immediate consequence of Proposition~\ref{prop:inf}.

\setcounter{theorem}{1}
\begin{theorem}  \label{theorem1} For every graph $\gamma$, there are infinitely many closed, connected, orientable, irreducible 3-manifolds $M$ such that some embedding of $\gamma$ in $M$ is pointwise fixed by an orientation reversing involution of $M$.

\end{theorem}

\bigskip

\begin{comment}
\section{Determining the value of $n_M$ for a given $M$}

Let $M$ be a closed, connected, orientable, irreducible 3-manifold.  We will associate several constants with $M$ that will help us determine the value of $n_M$.  First, observe that we can apply the characteristic decomposition theorem of Jaco-Shalen \cite{JS} and Johannson \cite{Jo} to $M$ to find a unique minimal family $\Omega$ of disjoint incompressible tori such that the closures of the components obtained by splitting $M$ along $\Omega$ are atoroidal or Seifert fibered.  If $\Omega\not =\emptyset$ let $t=|\Omega|$, and otherwise let $t=1$.

For each Seifert fibered component $M_i$, let $g_i$ denote the genus of the base surface $F_i$,  let $b_i$ denote the number of boundary components of $F_i$, and let $w_i=\max\{b_i+3g_i -3,1\}$.
By using a standard pants decomposition argument (see, for example, \cite{Ha2}), we see that the surface $F_i$ can contain at most $w_i$ disjoint, non-parallel, non-boundary parallel, essential circles.  This implies that $M_i$ contains at most $w_i$ disjoint, non-parallel, non-boundary parallel, incompressible vertical tori (see Figure~\ref{SF}).    Let $w=\sum w_i$ taken over all Seifert fibered components $M_i$.  Then $M$ contains at most $w$ disjoint, non-parallel, non-boundary parallel, incompressible tori which are vertical in some Seifert fibered component.

\begin{figure}[here]
\begin{center}
\includegraphics[width=.7\textwidth]{SF.eps}
\caption{A vertical torus in a Seifert fibered component.}
\label{SF}
\end{center}
\end{figure}

Now let $T$ be an incompressible torus in $M$.  Then $T$ can be isotoped to be disjoint from the tori in the characteristic family $\Omega$ (see for example \cite{Ha3}).  Thus without loss of generality, we assume that $T$ is contained in either an atoroidal or a Seifert fibered component of $M-\Omega$.  If $T$ is in an atoroidal component, then $T$ is parallel to a torus in $\Omega$.  Hence there are at most $t=|\Omega|$ disjoint, non-parallel, such tori in $M$.  If $T$ is in a Seifert fibered component, then by Waldhausen \cite{Wa1}, $T$ must be parallel to either a vertical or horizontal torus.  As we saw above there are at most $w$ disjoint, non-parallel, such tori which are vertical in some Seifert fibered component.  If $T$ is parallel to a horizontal torus in some Seifert fibered component, then $M$ is Seifert fibered with base surface a torus.  In this case, there is only one such torus, and $w=w_i=\max\{b_i+3g_i -3,1\}=1$.  Thus  there are at most $w$ disjoint, non-parallel tori in $M$ which are either parallel to either a vertical or horizontal torus in some Seifert fibered component.  Hence altogether, $M$ has at most $N_M=t+w$ disjoint, non-parallel incompressible tori.  Note that since $w\geq 1$ and $t\geq 1$, we have $N_M\geq 2$.

\medskip

 Now for any closed, orientable, connected, irreducible 3-manifold $M$, we define $n_M=\mathrm{dim} _{\mathbb{Z}_2} (H_1 (M,\mathbb{Z}_2))+N_M$.  We will refer to the constants $n_M$ and $N_M$ in the statements and proofs of Theorem~\ref{ICManifolds} and Proposition~\ref{mainprop}.

\bigskip
\end{comment}

\section{Intrinsic Chirality}

The goal of this section is to prove our main result.  We begin with the following definition.

\begin{definition} We define the {\it genus of a closed surface} $S$ by $$\frac{2-\chi(S)}{2}=\frac{\mathrm{dim}_{\mathbb{Z}_2} (H_1 (S,\mathbb{Z}_2))}{2}.$$

Then the {\it genus of a graph} is defined as the minimum genus of any closed surface in which the graph embeds.

\end{definition}

  It is worth pointing out that the genus of a non-orientable surface is not consistently defined in the literature.  Some papers use our definition, while others define the projective plane as having genus 1 instead of $\frac{1}{2}$.
  \medskip

Let $M$ be a closed, connected, orientable, irreducible 3-manifold.  Then by Kneser-Haken finiteness \cite{KH}, $M$ contains at most finitely many non-parallel disjoint incompressible tori.  Let $N_M$ denote either the maximal possible number of non-parallel disjoint incompressible tori in $M$ or 2, whichever is larger.  Now we define $n_M=\mathrm{dim} _{\mathbb{Z}_2} (H_1 (M,\mathbb{Z}_2))+N_M$.  We will refer to the constants $n_M$ and $N_M$ in the statements and proofs of Theorem~\ref{ICManifolds} and Proposition~\ref{mainprop}.

\begin{mainprop} Let $\gamma$ be a 3-connected graph with genus at least 2, and let $\Gamma$ be an embedding of $\gamma$  in a closed, connected, orientable, irreducible 3-manifold $M$ such that $(M,\Gamma)$ has an orientation reversing homeomorphism fixing every vertex of $\Gamma$.

Then there is an embedding $\Gamma'$ of $\gamma$ in a closed, connected, orientable 3-manifold $M'$ such that $(M',\Gamma')$ has an orientation reversing involution pointwise fixing $\Gamma'$ and $\mathrm{dim} _{\mathbb{Z}_2} (H_1 (M',\mathbb{Z}_2))\leq n_M$
  \end{mainprop}
\medskip

The point of this proposition is that if we have an embedding $\Gamma$ of a graph $\gamma$ in a manifold $M$ such that $(M, \Gamma)$ has an orientation reversing {\it homeomorphism}, then we can find a (possibly different) manifold $M'$ and an embedding $\Gamma'$ of $\gamma$ in $M'$ such that $(M',\Gamma')$ has an orientation reversing {\it involution}.  Furthermore, even though $M'$ might be homologically more complicated than $M$, there is a bound on $\mathrm{dim} _{\mathbb{Z}_2} (H_1 (M',\mathbb{Z}_2))$ which depends only on $M$ and not on the graph $\gamma$ or the particular embedding of $\gamma$ in $M$.

Note that the orientation reversing homeomorphism in the hypothesis of Proposition~\ref{mainprop}, leaves each edge  of $\Gamma$ setwise invariant since, according to our definition of a graph, there is at most one edge between any pair of vertices.  While this homeomorphism does not necessarily pointwise fix $\Gamma$, it is isotopic to a homeomorphism which does fix $\Gamma$ pointwise.

Proposition~\ref{mainprop} will be proved in the next section.  We now prove Theorem~\ref{ICManifolds} (restated below) by making use of Proposition~\ref{mainprop} together with the following result of Kobayashi.

\begin{kobayashi}\cite{Ko}  Let $X$ be a closed, orientable, 3-manifold admitting an orientation reversing involution $h$.  Then
 $$ \mathrm{dim}_{\mathbb{Z}_2} (H_1 (\mathrm{fix}(h),\mathbb{Z}_2)) \leq \mathrm{dim} _{\mathbb{Z}_2} (H_1 (X,\mathbb{Z}_2)) + \mathrm{dim} _{\mathbb{Z}} (H_1 (X,\mathbb{Z})).$$
  \end{kobayashi}
  \bigskip

\setcounter{theorem}{2}
\begin{theorem}   For every closed, connected, orientable, irreducible 3-manifold $M$, there is an integer $ n_M$ such that any abstract graph with no order $2$ automorphism which has a 3-connected minor $\lambda$ with $\mathrm{genus}(\lambda)>n_M$ is intrinsically chiral in $M$.\end{theorem}

\begin{proof}  Let $\gamma$ be a graph with no order $2$ automorphism.  Suppose for the sake of contradiction that $\gamma$ has an achiral embedding $\Gamma$ in the manifold $M$.  Let $n_M$ and $N_M$ be the constants associated with $M$ that were defined at the beginning of the section.  Let $\lambda$ be a 3-connected minor of $\gamma$.  We will now show that $\lambda$ satisfies the inequality

$$\mathrm{genus}(\lambda)\leq \mathrm{dim} _{\mathbb{Z}_2} (H_1 (M,\mathbb{Z}_2))+N_M=n_M.$$

\smallskip
 First observe that if $\mathrm{genus}(\lambda)<2$, then the above inequality is immediate since $N_M\geq 2$.  Thus we assume that $\mathrm{genus}(\lambda)\geq 2$.

Since $\Gamma$ is an achiral embedding of $\gamma$ in $M$, there is an orientation reversing homeomorphism $f$ of the pair $(M,\Gamma)$.  Let $\varphi$ denote the automorphism that $f$ induces on the graph $\Gamma$.  Now even though $f$ does not necessarily have finite order, $\varphi$ has finite order because $\Gamma$ has a finite number of vertices.  Hence we can express the order of $\varphi$ as $2^rq$, where $r\geq 0$ and $q$ is odd.  Now since $f$ is orientation reversing and $q$ is odd, $g=f^{q}$ is also an orientation reversing homeomorphism of $(M,\Gamma)$.  Also,  $g$ induces the automorphism $\varphi^q$ on $\Gamma$ and $\mathrm{order}(\varphi^q)=2^r$.  In particular, $g^{2^r}$ fixes every vertex of $\Gamma$.

If $r\geq 1$, then $g^{2^{r-1}}$ would induce an order two automorphism on $\Gamma$.  As we assumed that no such automorphism exists, we must have $r=0$.  Thus $g=g^{2^r}$ is an orientation reversing homeomorphism of $(M,\Gamma)$ which fixes every vertex of $\Gamma$.

Since $\lambda$ is a  minor of the abstract graph $\gamma$, by deleting and/or contracting some edges of the embedding $\Gamma$ of $\gamma$ in $M$, we obtain an embedding $\Lambda$ of $\lambda$ in $M$.  Furthermore, by composing the homeomorphism $g$ with an isotopy in a neighborhood of each edge that was contracted, we obtain an orientation reversing homeomorphism of $(M,\Lambda)$ which fixes every vertex of $\Lambda$.

Since $\lambda$ is a 3-connected graph with $\mathrm{genus}(\lambda)\geq 2$, we can now apply Proposition~\ref{mainprop} to get an embedding $\Lambda'$ of $\lambda$ in a closed, connected, orientable, 3-manifold $M'$ such that $(M',\Lambda')$ has an orientation reversing involution $h$ pointwise fixing $\Lambda'$ and

$$\mathrm{dim} _{\mathbb{Z}_2} (H_1 (M',\mathbb{Z}_2))\leq n_M=\mathrm{dim} _{\mathbb{Z}_2} (H_1 (M,\mathbb{Z}_2))+N_M.$$

\smallskip

Let $F$ be the component of the fixed point set $\mathrm{fix}(h)$ containing $\Lambda'$, and let $x\in\Lambda'$.  We put a metric $d$ on $M'$, and define a new metric $d'$ by $d'(x,y) = d(x,y) + d(h(x), h(y))$.  Then any neighborhood of $x$ with respect to the metric $d'$ will be setwise invariant under $h$.  Now we can pick a neighborhood $N(x)$ with respect to $d'$ such that $N(x)$ is homeomorphic to a ball. Then by Smith theory \cite{Sm}, since $h|N(x)$ is an orientation reversing involution of the ball $N(x)$, the fixed point set of $h|N(x)$ is either a single point or a properly embedded disk.  Since $N(x)\cap \Lambda$ contains more than one point, $\mathrm{fix}(h|N(x))$ is a properly embedded disk, and hence $F$ is a closed surface.  Thus

$$\mathrm{genus}(\lambda)\leq \mathrm{genus}(F)=\frac{2-\chi(F)}{2}$$

$$=\frac{\mathrm{dim}_{\mathbb{Z}_2}(H_1(F, \mathbb{Z}_2))}{2}\leq \frac{\mathrm{dim}_{\mathbb{Z}_2}(H_1(\mathrm{fix}(h), \mathbb{Z}_2))}{2}.$$

\smallskip

\noindent Hence we have the inequality $$2\mathrm{genus}(\lambda)\leq \mathrm{dim}_{\mathbb{Z}_2}(H_1(\mathrm{fix}(h), \mathbb{Z}_2).$$

Also, since $h$ is an orientation reversing involution and $M'$ is a closed orientable manifold, we can apply Kobayashi's Theorem \cite{Ko} to obtain the inequality $$ \mathrm{dim}_{\mathbb{Z}_2} (H_1 (\mathrm{fix}(h),\mathbb{Z}_2)) \leq \mathrm{dim} _{\mathbb{Z}_2} (H_1 (M',\mathbb{Z}_2)) + \mathrm{dim} _{\mathbb{Z}} (H_1 (M',\mathbb{Z})).$$

\noindent It follows that $$ \mathrm{dim}_{\mathbb{Z}_2} (H_1 (\mathrm{fix}(h),\mathbb{Z}_2))\leq 2\mathrm{dim} _{\mathbb{Z}_2} (H_1 (M',\mathbb{Z}_2)).$$

\smallskip

\noindent Combining the above inequalities, we now have $$\mathrm{genus}(\lambda)\leq \mathrm{dim} _{\mathbb{Z}_2} (H_1 (M',\mathbb{Z}_2)).$$

\noindent But $M'$ was given by Proposition~\ref{mainprop} such that $$\mathrm{dim} _{\mathbb{Z}_2} (H_1 (M',\mathbb{Z}_2))\leq \mathrm{dim} _{\mathbb{Z}_2} (H_1 (M,\mathbb{Z}_2))+N_M.$$

\noindent Hence we obtain the required inequality $$\mathrm{genus}(\lambda)\leq \mathrm{dim} _{\mathbb{Z}_2} (H_1 (M,\mathbb{Z}_2))+N_M=n_M.$$

\noindent It now follows that if $\gamma$ has a 3-connected minor whose genus is greater than $n_M$, then $\gamma$ must be intrinsically chiral in $M$.  \end{proof}

\bigskip

\section{Proof of Proposition~\ref{mainprop}}
\begin{comment}
For the sake of completeness, we begin by proving the following elementary lemma that we will use in the proof of Proposition~\ref{mainprop}.

\begin{lemma}
Let $S$ be a punctured sphere with $n\geq 3$ boundary components $\{c_1, c_2 \dots c_n \}$.
Let $\{s_1, s_2 \dots s_m \}$ be disjoint embedded loops on $S$ each parallel to some $c_i$ and let $\{\alpha_1,\dots, \alpha_t\}$ be  disjoint annuli on $S -\bigcup_{i=1}^m s_i$. Then the closure of some component of $S -(\bigcup_{i=1}^m s_i \cup\bigcup_{i=1}^t \alpha_i)$ is a sphere with at least three holes.
\label{lemma:spherewithholes}
\end{lemma}

\begin{proof}  First note that $\mathrm{cl}(S-\bigcup_{i=1}^m s_i)$ consists of $m$ annuli and a sphere with $n \geq 3$ holes.  Call the closure of this sphere with holes $F_1$.    Any annuli $\alpha_i$ that are not in $F_1$ are thrown out of the collection $\{\alpha_1,\dots, \alpha_t\}$ to get a possibly smaller collection $\{\alpha_1,\dots, \alpha_r\}$. Now it suffices to prove that the closure of some component of $F_1 -(\bigcup_{i=1}^m s_i \cup\bigcup_{i=1}^r \alpha_i)$ is a sphere with at least three holes.

Observe that the total number of boundary components of $\mathrm{cl}(F_1- \alpha_1)$ is $n+2$.  There are three possible cases for these components.  First, one component of $\mathrm{cl}(F_1- \alpha_1)$ could be a disk $D_1$.  In this case, the total number of boundary components of $\mathrm{cl}(F_1-(\alpha_1\cup D_1))$ is $n+1\geq 3$.  Second, one component of $\mathrm{cl}(F_1- \alpha_1)$ could be an annulus $A_1$, in which case the total number of boundary components of $\mathrm{cl}(F_1-(\alpha_1\cup A_1))$ is still $n\geq 3$.  Finally, if neither component of $\mathrm{cl}(F_1- \alpha_1)$ is a disk or an annulus, then $\alpha_1$ splits $F$ into two punctured spheres each with at least three boundary components.  Let $F_2$ denote the closure of one of these spheres with at least three holes.

We repeat the above paragraph inductively to conclude that the closure of some component of $S -(\bigcup_{i=1}^m s_i \cup\bigcup_{i=1}^t \alpha_i)$ is a sphere with at least three holes. \end{proof}
\medskip
\end{comment}

In the course of the proof of Proposition~\ref{mainprop}, we will use the well known  ``Half Lives, Half Dies" Theorem, which we state below.
 See \cite{H1} or \cite{Ha} for a proof of this theorem.

\begin{theorem} {\em (Half Lives, Half Dies)}  Let $M$ be a compact orientable $3$-manifold.  Then the following equation holds with any field coefficients
\[ \dim \left( Kernel (H_1(\partial M) \to H_1(M)) \right) = \frac{1}{2} \dim H_1(\partial M). \]
\label{thm:hlhdhom}
\end{theorem}

\begin{corollary}
Let $M$ be a manifold which has a torus boundary component $T$.  Then for any pair of generators $a$ and $b$ of $H_1(T,\mathbb{Z}_2)$, at least one of $a$ and $b$ is non-trivial in $H_1(M,\mathbb{Z}_2)$.
\label{cor:hlhd}
\end{corollary}

\begin{proof}
Suppose for the sake of contradiction that the generators $a$ and $b$ are both trivial in $H_1(M,\mathbb{Z}_2)$.  Attach handlebodies to all boundary components of $M$ except $T$ to form a new manifold $J$ with a single boundary component.  Then $a$ and $b$ are both trivial in $H_1(J,\mathbb{Z}_2)$.   Since $a$ and $b$ generate the homology of the only boundary component of $J$, we see that $\dim \left( Kernel (H_1(\partial J,\mathbb{Z}_2)) \to H_1(J,\mathbb{Z}_2) \right) =  \dim_{\Z_2} (H_1(\partial J,\mathbb{Z}_2)) = 2$.  But this contradicts the Half Lives, Half Dies Theorem.  Thus at least one of the generators of $H_1(T,\mathbb{Z}_2)$ must have been non-trivial in $M$.\end{proof}

\medskip

Note that it is tempting to assume that the Half Lives, Half Dies Theorem implies that one of $a$ or $b$ must be trivial in $J$.  But this is not always true. In particular, let $M$ denote the product of a torus and an interval.  Then no non-trivial curve in the boundary of $M$ is in the kernel.

\bigskip

Now we are ready to prove Proposition~\ref{mainprop}.  Recall that the definition of the constant $n_M$ is given in Section 3.

\begin{prop}\label{mainprop}  Let $\gamma$ be a 3-connected graph with genus at least 2, and let $\Gamma$ be an embedding of $\gamma$  in a closed, connected, orientable, irreducible 3-manifold $M$ such that $(M,\Gamma)$ has an orientation reversing homeomorphism $g$ fixing every vertex of $\Gamma$.

Then there is an embedding $\Gamma'$ of $\gamma$ in a closed, connected, orientable 3-manifold $M'$ such that $(M',\Gamma')$ has an orientation reversing involution pointwise fixing $\Gamma'$ and $\mathrm{dim} _{\mathbb{Z}_2} (H_1 (M',\mathbb{Z}_2))\leq n_M.$
\end{prop}

\medskip

\begin{proof} Let $\Lambda$ denote either $\Gamma$ or $\Gamma$ with one edge deleted, and suppose that $\Lambda$ is contained in a ball $B$ in $M$.  Since $g(B)$ is isotopic to $B$ in $M$, we can assume that $g$ leaves $B$ setwise invariant.  Also, since $g$ fixes every vertex of $\Lambda$ and $\Lambda$ has at most one edge between any pair of vertices, $g$ takes each edge to itself.  Thus $g|B$ is isotopic to a homeomorphism which pointwise fixes $\Lambda$.  So we assume that $g$ leaves $B$ setwise invariant and pointwise fixes $\Lambda$.   Let $f$ be an embedding of $(B, \Lambda)$ in $S^3$.  Then $f\circ g\circ f^{-1}$ is an orientation reversing homeomorphism of $f(B)$ pointwise fixing $f(\Lambda)$.   Now, $f\circ g\circ f^{-1}$ can be extended to an orientation reversing homeomorphism of $S^3$ pointwise fixing $f(\Lambda)$.

However, Jiang and Wang \cite{JW} showed that no graph containing $K_{3,3}$ or $K_5$ has an embedding in $S^3$ which is pointwise fixed by an orientation reversing homeomorphism of $S^3$.  Thus $\Lambda$ cannot contain $K_{3,3}$ or $K_5$, and hence is abstractly planar.  But this implies that $\mathrm{genus}(\Gamma)\leq 1$, which is contrary to hypothesis.  Thus neither $\Gamma$ nor $\Gamma$ with an edge deleted can be contained in a ball in $M$.  We will use this result later in the proof.

\medskip

 Since the remainder of the proof is quite lengthy, we break it into steps.

\bigskip

\noindent{\bf Step 1:  We define a neighborhood $N(\Gamma)$. }
\bigskip

 Let  $V$ and $E$ be the sets of vertices and edges of $\Gamma$ respectively. For each vertex $v\in V$, define $N(v)$ to be a ball around $v$ in $M$ (i.e., a 0-handle containing $v$), and let $N(V)$ denote the union of the balls around the vertices.  Also, for each edge $e\in E$, let $N(e)=D \times I$ be a solid tube around $\mathrm{cl}(e-N(V))$ in $M$ (i.e., a 1-handle containing the portion of $e$ outside of the 0-handles). Let $N(E)$ denote the union of the tubes around the edges.  Then for each $e$ in $N(E)$ the intersection $N(V)  \cap  N(e)$ follows the standard convention for attaching 1-handles to 0-handles.  In other words, in $N(e)$ this intersection consists of the disks $D \times \{0\}$ and $D \times \{1\}$ and in $\partial N(V)$.   Then $N(\Gamma)=N(E)\cup N(V)$ is a neighborhood of $\Gamma$.

 For convenience we introduce the following terminology.  For each vertex $v$, we let $\partial' N(v)$ denote the sphere with holes $\partial N(v)\cap \partial N(\Gamma)$, and for each edge $e$ we let $\partial' N(e)$ denote the annulus $\partial N(e)\cap \partial N(\Gamma)$.  Thus $\partial N(\Gamma)=\partial' N(E)\cup\partial 'N(V)$.

Now since $g(\Gamma)=\Gamma$ fixing each vertex of $\Gamma$, we know that $g(N(\Gamma))$ is isotopic to $N(\Gamma)$ setwise fixing $\Gamma$ and fixing each vertex.  Thus we can modify $g$ by an isotopy (and by an abuse of notation, still refer to the map as $g$) so that $g(\Gamma)=\Gamma$ for each vertex $v$ and edge $e$ we have $g(N(v))= N(v)$ and $g(N(e))= N(e)$.  Because this modification was by an isotopy, our new
$g$ is still orientation reversing.

 \bigskip

\noindent{\bf Step 2:  We split $\mathrm{cl}(M - N(\Gamma))$ along a family $\tau$ of JSJ tori and choose an invariant component $X$.}

\bigskip

Since $M$ is irreducible and we have assumed that $\Gamma$ is not contained in a ball, $\mathrm{cl}(M - N(\Gamma))$ is irreducible.  Thus we can apply the Characteristic Decomposition Theorem of Jaco-Shalen \cite{JS} and Johannson \cite{Jo} to get a minimal  family of incompressible tori $\tau$ for $\mathrm{cl}(M - N(\Gamma))$ such that each closed up component of $M - (N(\Gamma) \cup \tau)$ is either Seifert fibered or atoriodal.  Since the characteristic family $\tau$ is unique up to isotopy, we can again modify $g$ by an isotopy (and again by an abuse of notation still refer to the map as $g$) so that $g(\tau)=\tau$ and still have $g(\Gamma)=\Gamma$, $g(N(v))= N(v)$ and $g(N(e))= N(e)$ for each vertex $v$ and edge $e$.  Let $X$ be the closed up component of $M - (N(\Gamma) \cup \tau)$ containing $\partial N(\Gamma)$ (see for example Figure~\ref{JSJ}).   Then $g(X)=X$.

\begin{figure}[here]
\begin{center}
\includegraphics[width=.75\textwidth]{JSJ.eps}
\caption{$X$ is the closed up component of $M - (N(\Gamma) \cup \tau)$ between the grey incompressible torus and the black $\partial N(\Gamma)$.}
\label{JSJ}
\end{center}
\end{figure}

 Also, since $\Gamma$ is 3-connected, $\mathrm{genus}(\partial N(\Gamma))>1$.  Thus the component $X$ is not Seifert fibered, and hence is atoriodal.  Let $P $ denote the set of torus boundary components of $X$ together with the annuli that make up the components of $\partial 'N(E)$.  Since $\Gamma$ is 3-connected, $\partial X-P=\partial N(\Gamma) - \partial' N(E)=\partial 'N(V)$ is incompressible in $\mathrm{cl}(M - N(\Gamma))$.  It follows that $\partial X-P$ is incompressible in $X$.  Furthermore, $X$ is irreducible since $\mathrm{cl}(M - N(\Gamma))$ is irreducible and $X$ is a component of the JSJ decomposition of $\mathrm{cl}(M - N(\Gamma))$.

\bigskip

\noindent{\bf Step 3:  We show that any sphere obtained by capping off an annulus $A$ in  the JSJ decomposition of $(X,P)$ bounds a ball $B\subseteq M$ such that if the components of $\partial A$ are in different components of $\partial N(V)$, then $B$ meets $\Gamma-N(V)$ in a single edge, and otherwise $B$ is disjoint from $\Gamma-N(V)$.}
\bigskip

We now apply the Characteristic Decomposition Theorem for Pared Manifolds \cite{JS, Jo, Mor} to the pared manifold $(X,P)$. Since $X$ is atoroidal, this gives us a characteristic family $\sigma$ of incompressible annuli in X with boundaries in $\partial X - P$ such that if $W$ is the closure of any component of $X-\sigma$, then the pared manifold $(W, W \cap (P \cup \sigma))$ is either simple, Seifert fibered, or I - fibered (see \cite{Bo1} for the necessary definitions).  Once again, since the characteristic family $\sigma$  is unique up to isotopy, we can modify $g$ by an isotopy (and again by an abuse of notation, still refer to the map as $g$) so that $g(\sigma)=\sigma$.

Let $A$ be an annulus component of $P\cup \sigma$, and let $S$ denote the sphere obtained by capping off $A$ by a pair of disjoint disks $D_1$ and $D_2$ in $ N(v_1)$ and $\partial N(v_2)$, where $v_1$ and $v_2$ may or may not be distinct vertices.  Suppose that each component of $M-S$ intersects more than one edge of $\Gamma-N(V)$.  Then by removing the vertices $v_1$ and $v_2$ and the edges that contain them we would obtain two non-empty subgraphs (see Figure~\ref{Annulus}).  But this contradicts our hypothesis that $\Gamma$ is 3-connected.  Thus one of the components of $M-S$ meets $\Gamma-N(V)$ in at most one edge of $\Gamma$.

\begin{figure}[here]
\begin{center}
\includegraphics[width=.5\textwidth]{Annulus.eps}
\caption{There is more than one edge on each side of this capped off annulus.  }
\label{Annulus}
\end{center}
\end{figure}
\bigskip

Now, since $M$ is irreducible, one of the closed up components of $M-S$ is a ball $B$.  However, we assumed at the beginning of our proof that neither $\Gamma$ nor $\Gamma$ with an edge removed can be contained in a ball in $M$.  Thus $B$ must be the closed up component of $M-S$ intersecting at most one edge of $\Gamma-N(V)$.

Now since the annulus $A$ is incompressible in $X$, if $v_1\not =v_2$ then there is some edge $e$ with vertices $v_1$ and $v_2$ such that $B$ contains $\mathrm{cl}(e-(N(v_1)\cup N(v_2)))$. On the other hand, suppose that $v_1=v_2$.  Then by our definition of a graph, every edge in  $\Gamma$ has two distinct vertices.  Thus the component of $M-S$ which meets $\Gamma-N(V)$ in at most one edge, is actually disjoint from $\Gamma-N(V)$.  In this case, $B$ must be disjoint from $\Gamma-N(V)$ as illustrated in Figure~\ref{v1v2}.

\begin{figure}[here]
\begin{center}
\includegraphics[width=.5\textwidth]{Newv1=v2.eps}
\caption{The component $B$ of $M-S$ is disjoint from $\Gamma-N(V)$.  }
\label{v1v2}
\end{center}
\end{figure}

Note that since a ball cannot contain an incompressible torus, no torus boundary component of $X$ can occur inside of $B$.  It follows that every torus boundary component of $ X$ must also be a boundary component of $X-B$.

\bigskip

\noindent{\bf Step 4:  We define a collection of balls $U_{e_1}$, \dots, $U_{e_n}$, $V_{F_1}$, \dots, $V_{F_m}$ in $M$ such that the manifold $W=\mathrm{cl}(X-(U_{e_1}\cup\dots\cup U_{e_n}\cup V_{F_1}\cup \dots\cup V_{F_m}))$ is the closure of a single component of $X-(\sigma\cup P)$.}
\bigskip

Let $A$ be an annulus in $P\cup \sigma$ with one boundary in $\partial N(v_1)$ and the other boundary in $\partial N(v_2)$ where $v_1\not =v_2$.  By capping off $A$ with disks in $\partial N(v_1)$ and $\partial N(v_2)$ we obtain a sphere which (as we saw in Step 3) bounds a ball $B$ that meets $\Gamma$ in $\mathrm{cl}(e-(N(v_1)\cup N(v_2)))$ for some edge $e$.

Note that by our definition of a graph, $e$ is the only edge of $\Gamma$ whose vertices are $v_1$ and $v_2$.  Thus we can let $\mathcal{C}_e$ denote the collection of all annuli in $P\cup \sigma$ with one boundary in $\partial N(v_1)$ and the other boundary in $\partial N(v_2)$.  Now we can cap off the annuli in $\mathcal{C}_e$ with disks in $\partial N(v_1)$ and $\partial N(v_2)$ to obtain a collection of spheres which bound nested balls containing $\mathrm{cl}(e-(N(v_1)\cup N(v_2)))$.  Let $A_e$ denote the annulus in $\mathcal{C}_e$ which, when capped off in this way, is outermost with respect to the nested balls.

Observe that the boundaries of $A_{e}$ bound disks $D_1\subseteq \partial N(v_1)$ and $D_2\subseteq \partial N(v_2)$ which each meet $\Gamma$ in a single point of $e$, and the sphere $A_{e}\cup D_1\cup D_2$ bounds a ball $U_{e}$ which contains $\mathrm{cl}(e-(N(v_1)\cup N(v_2)))$ and all of the other annuli in $\mathcal{C}_{e}$.  Furthermore, as we saw at the end of Step 3, no torus boundary component of $X$ can be contained in $U_e$.

We see as follows that $U_e$ does not separate $X$.  If $A_e=\partial'N(e)$, then $U_e=N(e)$ and hence $\mathrm{cl}(X-U_e)=X$.  Thus we assume that $A_e\not =\partial'N(e)$.  In this case, $U_e'=U_e \cap X$ is obtained by removing the interior of the $1$-handle $N(e)$ from the ball $U_e$.   For each $i$, let $\Delta_i=D_i-N(e)$.  Then each $\Delta_i$ is adjacent to both $A_e$ and $\partial' N(e)$.  Now $\partial U_e'=\partial' N(e)\cup A_e\cup \Delta_1\cup \Delta_2$, and hence $\partial U_e'-\partial'N(e)$ consists of a single component.  Since $\partial'N(e)\subseteq \partial X$, it now follows that $X-U_e=X-U_e'$ has a single component.  We will use this at the end of this step.

We repeat the above construction for each annulus in $P\cup \sigma$ with boundaries in distinct components of $\partial N(V)$.  This gives us a collection of pairwise disjoint balls $U_{e_1}$, \dots, $U_{e_n}$. Observe that for every edge $e_j$, the annulus $\partial'N(e_j)$ is in $P$ and its boundaries are in distinct components of $\partial N(V)$.  Thus every edge $e_j$ in $\Gamma$ is contained in some $U_{e_j}$.
It follows that $U_{e_1}\cup\dots \cup U_{e_n}$ contains $\mathrm{cl}(\Gamma-N(V))$ and contains every annulus in $P\cup \sigma$ with boundaries in distinct components of $\partial N(V)$.

Next we consider an annulus $F$ in $\sigma$ both of whose boundaries are in a single $\partial N(v)$.  We saw in Step 3 that if we cap off $F$ by a pair of disjoint disks in $N(v)$, we obtain a sphere which bounds a ball that is disjoint from $\Gamma-N(v)$.  Thus the components of $\partial F$ are parallel in $\partial' N(v)$.  We now cap off every such annulus to obtain a collection of spheres which bound balls that are either nested or disjoint.
Thus we can choose an annulus $F\in\sigma$ which, when capped off with disks in $N(v)$, bounds an outermost ball $V_F$ with respect to this nesting (see Figure \ref{Fi}).

\begin{figure}[here]
\begin{center}
\includegraphics[width=.3\textwidth]{Fball.eps}
\caption{$V_F$ is an outermost ball.}
\label{Fi}
\end{center}
\end{figure}

Observe that, as we saw for the $U_{e_j}$, the ball $V_F$ cannot contain any torus boundary components of $X$.  However, in this case $V_F'=V_F\cap X$ is obtained by removing the interior of the $2$-handle $V_F\cap N(v)$ from the ball $V_F$.   Thus $\partial V_F'=F\cup S_F$ where $S_F$ is an annulus in $\partial'N(v)\subseteq \partial X$.  This means that $\partial V_F'-\partial X$ has a single component, and hence $X-V_F=X-V_F'$ also has a single component.

Now for each annulus $F\in \sigma$ with both components of $\partial F$ in a single $\partial N(v)$ such that $F$ is not contained in one of the balls $U_{e_j}$, we use the above argument to define a ball $V_{F}$.    In this way, we obtain a collection of pairwise disjoint balls $U_{e_1}$, \dots, $U_{e_n}$, $V_{F_1}$, \dots, $V_{F_m}$.  Furthermore, each of the sets $X-U_{e_j}$ and $X-V_{F_i}$ has a single component, and each $\partial U_{e_j}-\partial X$ and $\partial V_{F_i}-\partial X$ is an annulus in $\sigma\cup P$.  Now it follows that the manifold $$W=\mathrm{cl}(X-(U_{e_1}\cup\dots\cup U_{e_n}\cup V_{F_1}\cup \dots\cup V_{F_m}))$$ is the closure of a single component of $X-(\sigma\cup P)$ (see Figure~\ref{annulus}).

\begin{figure}[h]
\begin{center}
\includegraphics[width=.55\textwidth]{Wnew.eps}
\caption{$W$ is the closure of a single component of $X-\sigma$.}
\label{annulus}
\end{center}
\end{figure}

\bigskip

\noindent{\bf Step 5: We show that $g(W)=W$ and the pared manifold $(W, W \cap (P \cup \sigma))$ is simple.}
\bigskip

Recall that $g$ fixes each vertex and leaves each edge setwise invariant.  Also, $g(N(\Gamma))=N(\Gamma)$, $g(P)=P$, and $g(\sigma)=\sigma$.  Now, since the sets of balls $\{U_{e_1}, \dots, U_{e_n}\}$ and $\{V_{F_1}, \dots, V_{F_m}\}$ were chosen to be outermost, each of these sets is also invariant under $g$.  Furthermore, we know from Step 4 that each $U_{e_j}$ intersects $\Gamma- N(V)$ only in $e_j$.  Now since $g$ leaves each $e_j$ setwise invariant, $g$ must also leave each $U_{e_j}$ setwise invariant.  It follows that $A_{e_j}$ must also be setwise invariant under $g$; and since each vertex is fixed by $g$, each boundary component of $A_{e_j}$ is also setwise invariant under $g$.

Now let $v$ be a vertex such that some $F_i$ has both its boundary components in $\partial N(v)$.  Since $F_i$ is incompressible in $X$, the components of $\partial F_i$ bound disjoint disks in $\partial N(v)$ which each nest at least one edge of $\Gamma$.  Since every vertex of $\Gamma$ is fixed by $g$, it follows that $F_i$ and its boundary components are also setwise invariant under $g$.  Thus $V_{F_i}$ is setwise invariant under $g$.  Finally, since all of the $U_{e_j}$ and $V_{F_i}$ are setwise invariant under $g$, we know that $W$ must be setwise invariant under $g$ as well.

  To show that the pared manifold $(W, W \cap (P \cup \sigma))$ is simple, first recall that $W$ is the closure of a single component of $X-\sigma$.  Hence by JSJ for pared manifolds \cite{JS, Jo}, $(W, W \cap (P \cup \sigma))$ is either $I$-fibered, Seifert fibered, or simple as a pared manifold.  We see that  $(W, W \cap (P \cup \sigma))$ cannot be Seifert fibered or $I$-fibered as follows.

First observe that for every vertex $v$, there is some edge $e$ such that the ball $U_e$ meets $\partial N(v)$. It follows that $\partial W$ meets every component of $\partial N(V)$.  Furthermore, since every vertex $v$ has valence at least three, $\partial' N(v)$ is a sphere with at least three holes.  Also each $U_{e_j}$ contains at most one boundary component of $\partial' N(v)$, and each $V_{F_i}$ contains no boundary components of  $\partial' N(v)$.  Note that if $F_i$ has its boundaries in $\partial N(v)$, then $V_{F_i}$ separates $\partial'(N(v))$ into two components.

This means that for each vertex $v$, $W\cap \partial N(v)$ is homeomorphic to $\partial' N(v)$ possibly with the interior of a set of pairwise disjoint annuli deleted.   Since $\partial' N(v)$ is a sphere with at least three holes, deleting a collection of annuli may create new components, but some component must still be a sphere with at least three holes.  It follows that the component of $\partial W$ meeting $\partial N(\Gamma)$ has genus more than one, and thus the pared manifold $(W, W \cap (P \cup \sigma))$ cannot be Seifert fibered.

Next, suppose for the sake of contradiction that the pared manifold $(W, W \cap (P \cup \sigma))$ is $I$-fibered.  By definition of $I$-fibered for pared manifolds, this means that there is an
$I$-bundle map of $W$ over a base surface $Y$ such
that $W \cap (P \cup \sigma)$ is in the pre-image of $\partial
Y$.  It follows that $Y$ must be homeomorphic to a component of  $\partial 'N(V)\cap W$.  This means that the base surface $Y$ must be a sphere with holes.  In particular, the base surface $Y$ is orientable.

Now since $W$ is an orientable $3$-manifold which is $I$-fibered over the orientable surface $Y$, it follows that $W$ must actually be a product $Y\times I$.  Thus
$W\cap (P\cup \sigma )=\partial Y \times I$, and $Y_{0}=Y\times \lbrace
0\rbrace $ and $Y_{1}=Y\times \lbrace 1\rbrace $ are the only components of $\partial' N(V)\cap W$.  However, since $\partial W$ meets every component of $\partial N(V)$, this means that $\Gamma$ contains at most two vertices.  But this contradicts our hypothesis that $\Gamma$ is 3-connected.  Therefore, the pared $(W, W \cap (P \cup \sigma))$ is not $I$-fibered, and since it is also not Seifert fibered, it must be simple.

 \bigskip

 \noindent{\bf Step 6: We prove that $g|W$ is isotopic to an orientation reversing involution $h$ of $(W, W\cap (P\cup \sigma ))$.}

\bigskip

 Now it follows from Thurston's Hyperbolization
Theorem for Pared Manifolds \cite{Th} applied to the simple pared manifold $(W, W\cap (P\cup
\sigma ))$ that $W-(W\cap (P\cup \sigma ))$ admits a finite volume
complete hyperbolic metric with totally geodesic boundary.  Let $D$
denote the double of $W-(W\cap (P\cup \sigma ))$ along its boundary.
Then $D$ is a finite volume hyperbolic manifold, and $g|W$ can be doubled to obtain an orientation reversing  homeomorphism of $D$ (which we still call $g$) taking each copy of $W-(W\cap (P\cup \sigma ))$ to itself.
Now by Mostow's Rigidity Theorem~\cite{Mo} applied to $D$, the homeomorphism $g:D\to D$ is homotopic to an orientation reversing finite order isometry $h:D\to D$
that restricts to an isometry of $W- (W\cap(P\cup \sigma ))$. By removing
horocyclic neighborhoods of the cusps of $W-(W\cap(P\cup \sigma ))$,
we obtain a copy of the pair $(W, W\cap (P\cup \sigma ))$ which is
contained in $W-(W\cap(P\cup \sigma))$ and is setwise invariant under $h$.  We abuse notation and now consider $h$ to
be an orientation reversing finite order isometry of $(W, W\cap (P\cup \sigma ))$ instead of this copy.  Furthermore, $h$ induces isometries on the collection of tori and annuli in
$W\cap (P\cup \sigma )$ with respect to a flat metric.  Furthermore, the sets
$\partial' N(V)\cap W$, $\partial'N(E)\cap W$, and $\tau \cap W$ are
each setwise invariant under $h$.  Finally, it follows from
Waldhausen's Isotopy Theorem~\cite{Wa} that $h$ is
isotopic to $g|W$ by an isotopy leaving
$W\cap (P\cup \sigma )$ setwise invariant.

 Now, recall that the boundary components of $W$ consist of tori in $\tau$, and the union of spheres with holes in $\partial' N(V)\cap W$ together with annuli in $P\cup \sigma$. Recall from the first paragraph in Step 5 that $g$ setwise fixes each annulus $A_{e_j}\subseteq \partial U_{e_j}$ with boundaries in distinct components of $\partial N(V)$, each annulus $F_i\subseteq \partial V_{F_i}$ with both boundaries in a single component of $\partial N(V)$, each component of $\partial A_{e_j}$, and each component of $\partial F_i$.  Since $h$ is
isotopic to $g|W$ by an isotopy leaving
$W\cap (P\cup \sigma )$ setwise invariant, $h$ leaves invariant the same sets as $g$.  It follows that for each vertex $v$, we have $h(\partial' N(v))\cap W)=\partial' N(v)\cap W$, and $h$ takes
each component of $W\cap \partial N(v)$ to itself, leaving each boundary component setwise invariant.

Since $h$ has finite order, $h$ restricts to a finite order homeomorphism of every component of $W\cap \partial N(V)$.  We saw in Step 5 that for every vertex $v$, at least one component $C_v$ of $W\cap \partial N(v)$ is a sphere with at least three holes.  Since $h$ restricts to a finite order homeomorphism of $C_v$ taking each boundary component of $ C_v$ to itself, $h$ must be a reflection of $C_v$ which also reflects each component of $\partial C_v$. Now $h^2$ is a finite order, orientation preserving isometry of $W$ that pointwise fixes the surface $C_v$.  It follows that $h^2$ is the identity, and hence $h$ is an involution of $W$.

\bigskip

 \noindent{\bf Step 7: We extend $h$ to an orientation reversing involution of $X\cup N(\Gamma)$ which pointwise fixes an embedding $\Gamma'$ of $\gamma$.}

\bigskip

Observe that since every annulus in $P\cup \sigma$ is incompressible in $W$, no component of $W\cap \partial N(V)$ can be a disk.  Thus every component of $W\cap \partial N(V)$ is a sphere with two or more holes.

As we saw in Step~6, for each vertex $v$, $h$ reflects some component $C_v$ of $W\cap \partial N(v)$ which is a sphere with at least three holes, and $h$ reflects every component of $\partial C_v$.  Let $b_0$ denote some boundary component of $C_v$.   Then $b_0$ is also a boundary component of either an annulus $A_{e_j}$ or an annulus $F_i$.  Since $h$ reflects $b_0$, we know that $h$ must also reflect the annulus $A_{e_j}$ or $F_i$, whichever contains $b_0$ in its boundary.  Since the boundaries of the annulus are not interchanged, $h$ must also reflect each boundary component of $A_{e_j}$ or $F_i$.  Below we extend $h$ to $U_{e_j}$ or $V_{F_i}$.

First we consider the case where $b_0$ is in the boundary of an annulus $A_{e_j}\subseteq \partial U_{e_j}$.   Let $D_j$ and $D'_j$ denote the disks whose union is in $\mathrm{cl}(\partial U_{e_j}-A_{e_j})$.  Then $D_j$ and $D_j'$ each meet $\Gamma$ in a single point of $e_j$. Since $h$ reflects the annulus $A_{e_j}$ together with each boundary component of $A_{e_j}$, we can extend $h$ radially to the disks $D_j$ and $D_j'$ to get a reflection of the sphere $A_{e_j}\cup D_j\cup D_j'$ pointwise fixing a circle containing the points $D_j\cap e_j$ and $D_j'\cap e_j$.  Recall that the sphere $A_{e_j}\cup D_j\cup D_j'$ bounds the ball $U_{e_j}$ in $M$.  Now, we can express $U_{e_j}$ as a product $D_j\times I$ whose core $\overline{e_j}$ has endpoints $D_j\cap e_j$ and $D_j'\cap e_j$  (see Figure~\ref{knotted}).  Now we extend $h$ from a reflection of the sphere $A_{e_j}\cup D_j\cup D_j'$ to a reflection of the product $D_j\times I$ which pointwise fixes the core $\overline{e_j}$.

\begin{figure}[here]
\begin{center}
\includegraphics[width=.55\textwidth]{Knotted2.eps}
\caption{We can think of $U_{e_j}$ as a product $D_j\times I$ with core $\overline{e_j}$.}
\label{knotted}
\end{center}
\end{figure}

  Next we consider the case where $b_0$ is a boundary component of an annulus $F_i\subseteq \partial V_{F_i}$ which has both boundaries in a single $\partial N(v)$.  Recall that $\mathrm{cl}(\partial V_{F_i}-F_i)$ consists of disks $D_i$ and $D_i'$ properly embedded in $N(v)$.  Since $h$ reflects the annulus $F_i$ together with each of its boundary components, we can extend $h$ radially to the disks $D_i$ and $D_i'$ to get a reflection of the sphere $F_i\cup D_i\cup D_i'$ pointwise fixing a circle containing the points of $\Gamma\cap D_i$ and $\Gamma\cap D_i'$.  Thus we can extend $h$ to a reflection of the ball $V_{F_i}$ which pointwise fixes a disk containing $V_{F_i}\cap \Gamma$ (see Figure~\ref{Bi}).

\begin{figure}[here]
\begin{center}
\includegraphics[width=.4\textwidth]{VFi.eps}
\caption{We extend $h$ to a reflection of the ball $V_{F_i}$ which pointwise fixes $\Gamma\cap V_{F_i}$.  }
\label{Bi}
\end{center}
\end{figure}

Now the extension of $h$ reflects the sphere with holes $C_v$, and one of the balls $U_{e_j}$ or $V_{F_i}$ depending on whether $b_0$ is a boundary component of $A_{e_j}$ or $F_i$, respectively.  Next we let $S_1$ denote the union of $C_v$ together with the annulus $A_{e_j}$ or $F_i$ glued along $b_0$.  Now $h$ reflects $S_1$ taking every boundary component of $S_1$ to itself, and hence reflecting every boundary component of $S_1$.  Let $b_1$ be a boundary component of $S_1$. If $b_1$ is not the other boundary of the annulus $A_{e_j}$ or $F_i$, then we repeat the above argument with $b_1$ in place of $b_0$.  If $b_1$ is the other boundary of the annulus $A_{e_j}$ or $F_i$, then $b_1$ is also a boundary of some other component $S_1'$ of $W\cap \partial N(V)$, as illustrated in Figure~\ref{induction}.

\begin{figure}[here]
\begin{center}
\includegraphics[width=.45\textwidth]{Induction.eps}
\caption{In this illustration, we have three choices for the boundary component $b_2$ of $S_2=S_0\cup A_{e_j} \cup S_1'$.  }
\label{induction}
\end{center}
\end{figure}

In this case, since $b_1$ is reflected by $h$ and every boundary component of $S_1'$ is setwise invariant under $h$, we know that $h$ must reflect $S_2=S_1\cup S_1'$.  Now let $b_2$ denote a boundary component of $S_2$, and repeat the above argument with $b_2$ in place of $b_0$.

In general, for a given surface $S_n$ obtained in this way, the surface $S_{n+1}$ is the union of $S_n$ together with either an annulus of the form $A_{e_j}$ or $F_i$ or a sphere with at least two holes contained in $W\cap \partial N(V)$.  Furthermore, $S_{n+1}$ is reflected by $h$. This process will only stop when the surface that we obtain has no boundary components.  Since $\partial W$ has only one component which intersects $\partial N(V)$, the closed surface that we obtain in this way must be $\partial W$.  Thus we have extended $h$ to an orientation reversing involution of each of the balls $U_{e_1}$, \dots, $U_{e_n}$, $V_{F_1}$, \dots, $V_{F_m}$.

Now let $N=N(V)-(V_{F_1}\cup\dots\cup V_{F_m})$.  Then $N$ is a collection of disjoint balls (for example in Figure \ref{Bi}, $N(v)-V_{F_i}$ is two balls one of which contains $v$).  Also, $h$ is a reflection of each component of $\partial N$ that fixes each point in $\partial N \cap \Gamma$.
 Now we extend $h$ radially to a reflection of each ball of $N$ in such a way that $h$ pointwise fixes each component of $N \cap \Gamma$.  Thus $h$ is defined as a reflection of each component of $N(V)$ which pointwise fixes $N(V)\cap \Gamma$.

We have now extended $h$ to an orientation reversing involution of the manifold

$$Y=W\cup V_{F_1}\cup\dots\cup V_{F_m}\cup U_{e_1}\cup\dots\cup U_{e_n}\cup N.$$

Recall from the end of Step 4 that $\partial X$ and $\partial W$ have the same collection of tori in their boundary components.  Furthermore, we have filled in the boundary component of $W$ meeting $\partial N(\Gamma)$ with a collection of balls in $X$ and $N(\Gamma)$.  Thus in fact $Y=X\cup N(\Gamma)$.

Finally, we define a new embedding $\Gamma'$ of $\gamma$ in $X\cup N(\Gamma)$ as follows. Let $\Gamma'\cap N(V)=\Gamma \cap N(V)$.  Then for each edge $e_j$ define an embedding of $e_j-N(V)$ in $\Gamma'$ as the core $\overline{e_j}$ of $U_{e_j}=D_j\times I$, which we know is pointwise fixed by $h$ according to the way we extended $h$ to $U_{e_j}$ (recall Figure~\ref{knotted}).
\bigskip

\begin{comment}
\noindent{\bf Step 10: We show that some component $S$ of $\partial W$ bounds a handlebody $H$ in $Y$ and a solid $Q$ in $M$ such that a curve on $S$ is trivial in $H_1 (H,\mathbb{Z}_2)$ if and only if it's trivial in $H_1 (Q,\mathbb{Z}_2)$.}

\bigskip

Observe that $W$ has one more boundary component than $Y$ which is a surface $S$ with $\mathrm{genus}(S)>1$.  The surface $S$ is made up of a collection of punctured spheres that are subsets of $\partial' N(V)$ together with annuli of the forms $A_{e_j}$ and $F_i$.  Recall that when we constructed $Y$, we started with $W$ and capped off the annuli $A_{e_j}$ and $F_i$ with a pair of disks in $N(V)$ to obtain a collection of spheres; then we filled in each of these spheres with a ball, and finally we filled in the rest of $N(V)$ with a collection of balls.

 In $M$, the surface $S$ bounds a solid $Q$ containing $N(\Gamma)$ such that the interior of $Q$ is disjoint from $W$.
 Let $H$ denote the solid in $Y$ that is bounded by $S$.  We see as follows that $H$ is a handlebody.   We can form $H$ from the closed orientable surface $S$ by first adding 2-handles $\overline{U}_{e_j}$ and $B_i$ to $S$ along the annuli $A_{e_j}$ and $F_i$, respectively.  Now the boundary of each ball $\overline{U}_{e_j}$ is $A_{e_j}$ together with two disks in $\partial N(V)$, and the boundary of each ball $B_i$ is $F_i$ together with a pair of disks properly embedded in $N(V)$.   Thus after gluing the 2-handles $\overline{U}_{e_j}$ and $B_i$ to $W$ along $A_{e_j}$ and $F_i$, we have a collection of spherical boundary components which correspond to the boundary components of $N(V)-(B_1\cup\dots\cup B_m)$.  We then add the components $N$ as 3-handles along these boundary components.  It follows that $H$ is a a handlebody.

Observe that every curve on any of the annuli $A_{e_j}$ or $F_i$ is isotopic in $S$ to a curve on $\partial 'N(V)$. Thus we can pick a set of generators for $H_1 (S,\mathbb{Z}_2)$ with half of the generators contained in $\partial'N(V)$ and the other half of the generators intersecting elements in the first half.  Now every curve on $S$ contained in $\partial' N(V)$ bounds disks in both $H$ and $N(V)\subseteq Q$.  Thus the generators of $H_1 (S,\mathbb{Z}_2)$ that are in $\partial'N(V)$ are trivial in both $H$ and $Q$.
In particular, exactly half the generators of $H_1 (S,\mathbb{Z}_2)$ are trivial in both $H$ and $Q$.  By the Half-Lives Half-Dies Theorem, there cannot be any additional generators of $H_1 (S,\mathbb{Z}_2)$ that are trivial in either $H$ or $Q$.  In particular, this means that a curve on $S$ is trivial in $H_1 (H,\mathbb{Z}_2)$ if and only if it's trivial in $H_1 (Q,\mathbb{Z}_2)$.

\bigskip

\end{comment}

 \noindent{\bf Step 8:  We prove that if an essential curve in a component of $\partial (X\cup N(\Gamma))$ compresses in $M$, then it compresses in $X\cup N(\Gamma)$.}
\bigskip

 Let $\{T_1,\dots, T_r\}$ denote the set of boundary components of $X\cup N(\Gamma)$.  These tori are contained in the characteristic family $\tau$, and hence are incompressible in $\mathrm{cl}(M-N(\Gamma))$.

 Suppose that an essential curve $\lambda_i$ on some $T_i$ compresses in $M$.   Let $D_i$ be a compressing disk for $\lambda_i$ whose intersection with the set of tori $\{T_1,\dots, T_r\}$ is minimal.  Let $D=D_i$ if the interior of $D_i$ is disjoint from $T_i$.  Otherwise, there exists some $D$ in the interior of $D_i$ such that $D$ is a compressing disk for $T_i$ whose interior is disjoint from $T_i$.  In either case, the intersection of $D$ with $\{T_1,\dots, T_r\}$ is minimal.

 Suppose that $D$ contains at least one curve of intersection in its interior.  Hence there is an innermost disk $\Delta$ on $D$ which is a compressing disk for some $T_j$ with $j\not=i$.  Since $T_j$ compresses in $M$ but is incompressible in $\mathrm{cl}(M-N(\Gamma))$, we know that $\Delta$ intersects $\Gamma$.

 Since $M$ is irreducible, any compressible torus is separating in $M$.  Thus we can let $X_j$ denote the closed up component of $M-T_j$ containing $X$ and let $V_j$ denote the closed up component of $M-T_j$ whose interior is disjoint from $X$.  Now let $S$ denote the region of $D$ which is adjacent to the innermost disk $\Delta$.  Then $S\subseteq V_j$, since $\Delta\subseteq X_j$.  Also, $\partial D\subseteq T_i\subseteq X\subseteq X_j$ implies that $S$ is adjacent to another region of $D$ which is contained in $X_j$.  In particular, there must be another circle of intersection $\alpha$ of $D\cap T_j$ which bounds a disk $\overline{D}\subseteq D$ such that $\overline{D}$ contains $\Delta\cup S$.   We illustrate the abstract disk $D$ and its intersections with $T_j$ in Figure~\ref{disk}.  The white regions in the figure are contained in $V_j$, and the grey regions are contained in $X_j$.  Note we do not illustrate any circles of intersection of $D$ with any $T_k$ with $k\not =j$.

\begin{figure}[here]
\begin{center}
\includegraphics[width=.3\textwidth]{Disk.eps}
\caption{A picture of the abstract disk $D$ and its circles of intersection with  $T_j$.  }
\label{disk}
\end{center}
\end{figure}

Now, since the intersection of $D$ with the tori $T_1$,\dots, $T_r$ is minimal, all of the curves of intersection of $D\cap T_j$ must be essential on $T_j$.  In particular, $\partial \Delta$ and $\alpha$ must both be essential on $T_j$.  Since there cannot be two essential, disjoint, non-parallel curves on a torus, this means that $\alpha$ is parallel to $\partial \Delta$ on $T_j$.  It follows that $\alpha$ must bound a disk $\overline{\Delta}$ which is parallel to $\Delta$ in $M$.  In particular, since the interior of $\Delta$ is disjoint from $T_1$,\dots, $T_r$, the interior of $\overline{\Delta}$ is as well.  But now by replacing the disk $\overline{D}$ with the disk $\overline{\Delta}$ in the compressing disk $D$ we obtain a new compressing disk $D'$ for $T_i$ which has fewer curves of intersection with $T_1$,\dots, $T_r$ than $D$ has.  From this contradiction we conclude that the interior of $D$ must be disjoint from $T_1\cup\dots\cup T_r$, and hence $D\subseteq X\cup N(\Gamma)$.

If $\partial D=\lambda_i$, then $\lambda_i$ compresses in $X\cup N(\Gamma)$ as required.  Otherwise, the compression disk $D$ was contained in the interior of the original disk $D_i$ and $\partial D\subseteq T_i$.  In this case, since the intersection of $D_i$ with the set of tori $\{T_1,\dots, T_r\}$ was minimal, $\partial D$ is essential in $T_i$.  But now $\partial D$ and $\lambda_i$ are disjoint essential curves on $T_i$.  Hence as we saw above, the disks $D$ and $D_i$ must be parallel in $M$.  Now, since $D\subseteq X\cup N(\Gamma)$, it follows that $\lambda_i$ must compress in $X\cup N(\Gamma)$ as well.

\bigskip

 \noindent{\bf Step 9: We fill each component $T_i$ of $\partial (X\cup N(\Gamma))$ with a solid torus such that the resulting manifold $M'$ satisfies the condition below.}
\bigskip

\noindent {\bf Condition:} {\it  If $T_i$ is compressible in $M$, then every element of $H_1 (T_i,\mathbb{Z}_2)$ is trivial in $H_1 (M',\mathbb{Z}_2)$, and if $T_i$ is incompressible in $M$ then at least one non-trivial element of $H_1 (T_i,\mathbb{Z}_2)$ is trivial in $H_1 (M',\mathbb{Z}_2)$.}
\bigskip

Let $T_i$ be a component of $\partial (X\cup N(\Gamma))$.  By Corollary~\ref{cor:hlhd} at the beginning of Section 4 there is a curve $\mu_i$ on $T_i$ which is non-trivial in $H_1( X\cup N(\Gamma),\mathbb{Z}_2)$.  Also, we know from Step 8 that if some essential curve $\lambda_i$ on $T_i$ compresses in $M$, then $\lambda_i$ also compresses in $X\cup N(\Gamma)$.  In particular, $\lambda_i$ is not homologous in $T_i$ to $\mu_i$.

Now suppose that for some $j\not =i$, the involution $h$ interchanges $T_i$ and $T_j$.  Since $h:X\cup N(\Gamma)\to X\cup N(\Gamma)$ is a homeomorphism and $\mu_i$ is a curve on $T_i$ which is non-trivial in $H_1( X\cup N(\Gamma),\mathbb{Z}_2)$, we know that $h(\mu_i)$ is a curve on $T_j$ which is also non-trivial in $H_1(X\cup N(\Gamma),\mathbb{Z}_2)$.  Now we fill $X\cup N(\Gamma)$ along $T_i$ by adding a solid torus $V_i$ with its meridian attached to the non-trivial curve $\mu_i$, and we fill along $T_j$ by adding a solid torus $V_j$ with its meridian attached to $h(\mu_i)$.  Then we extend the involution $h$ radially in $V_i\cup V_j$ (abusing notation and still calling the involution $h$).   We repeat this process for every boundary component of $X\cup N(\Gamma)$ which is not setwise invariant under $h$.

Thus    for every $T_i$ along which we have glued a solid torus $V_i$, the curve $\mu_i$ on $T_i$ is now trivial in $H_1 (X\cup N(\Gamma)\cup V_i,\mathbb{Z}_2)$.  Furthermore, if $T_i$ is compressible in $M$, then there is an essential curve $\lambda_i$ on $T_i$ which compresses in $X\cup N(\Gamma)$.  Hence, $\lambda_i$ is not homologous to $\mu_i$ in $H_1 (T_i,\mathbb{Z}_2)$, and together they generate $H_1 (T_i,\mathbb{Z}_2)$.  Furthermore, both $\lambda_i$ and $\mu_i$ are trivial in $H_1 (X\cup N(\Gamma)\cup V_i,\mathbb{Z}_2)$.

Let $Z$ be the manifold that we have obtained by filling all of the boundary components of $X\cup N(\Gamma)$ which are not setwise fixed by $h$, and let $T_i$ be a component of $\partial Z$.  Recall from Step 7 that $\Gamma'$ is an embedding of $\gamma$ in $X\cup N(\Gamma)$ which is pointwise fixed by $h$.   Now $h:Z\to Z$ is an orientation reversing involution pointwise fixing $\Gamma'$, and $T_i$ is setwise invariant under $h$.  Furthermore, by the proof of Step~6, $h|T_i$ is an isometry with respect to a flat metric.  Since $h$ is an orientation reversing involution of $Z$ and $T_i$ is a boundary component of $Z$, $h|T_i$ is also an orientation reversing involution. Thus $h|T_i$ is either a reflection pointwise fixing two parallel circles on $T_i$, or a composition of a reflection and an order $2$ rotation of $T_i$. In either case, for any non-trivial element $a_i\in H_1( T_i,\mathbb{Z})$, there is a non-trivial curve $b_i\in H_1( T_i,\mathbb{Z})$ such that $a_i$ and $b_i$ meet transversely in a single point and $h(b_i)$ is homologous to $\pm b_i$ in $H_1( T_i,\mathbb{Z})$.

Now suppose that some essential curve $\lambda_i$ on $T_i$ compresses in $M$.  Then by Step 8, $\lambda_i$ also compresses in $X\cup N(\Gamma)$, and hence in $Z$.  Pick a non-trivial curve $b_i$ on $T_i$ that intersects $\lambda_i$ in a single point such that $h(b_i)$ is homologous to $\pm b_i$ in $H_1( T_i,\mathbb{Z})$.  Then $\langle \lambda_i, b_i\rangle=H_1( T_i,\mathbb{Z})$.  Also, since $\lambda_i$ is null homologous in $H_1( Z,\mathbb{Z}_2)$, by Corollary~\ref{cor:hlhd}, $b_i$ is non-trivial in $H_1( Z,\mathbb{Z}_2)$.  Now we fill $Z$ along $T_i$ by adding a solid torus $V_i$ with its meridian attached to the non-trivial curve $b_i$.  Since $h(b_i)$ is homologous to $ \pm b_i$ in $H_1( T_i,\mathbb{Z})$, we can extend $h$ radially to an orientation reversing involution of the solid torus $V_i$.  Then $h:Z\cup V_i\to Z\cup V_i$ is an orientation reversing involution, and both $\lambda_i$ and $b_i$ are trivial in $H_1( Z\cup V_i,\mathbb{Z}_2)$.

On the other hand, suppose that some $T_i$ is incompressible in $M$.   By Corollary~\ref{cor:hlhd}, there is some curve $b_i$ on $T_i$ which is non-trivial in $H_1( Z,\mathbb{Z}_2)$, and $b_i$ is homologous to $\pm h(b_i)$ in $H_1( T_i,\mathbb{Z})$.  Now we fill $T_i$ by adding a solid torus $V_i$ with its meridian attached to the curve $b_i$, and then extend $h$ to $V_i$.  Then $h:Z\cup V_i\to Z\cup V_i$ is again an orientation reversing involution, and $b_i$ is trivial in $H_1( Z\cup V_i,\mathbb{Z}_2)$.

In this way, we glue a solid torus to each of the $T_i$ in $\partial(X\cup N(\Gamma))$ to obtain a closed manifold $M'$ satisfying the required condition.  Since $\Gamma'\subseteq X\cup N(\Gamma)$, this gives us an embedding $\Gamma'$ of $\gamma$ in $M'$.  Furthermore, we have extended $h$ to an orientation reversing involution of $(M', \Gamma')$ which pointwise fixes $\Gamma'$.

\bigskip

 \noindent{\bf Step 10: We prove that at most $N_M$ of the tori in $\partial (X\cup N(\Gamma))$ are incompressible in $M$.}
\bigskip

Recall from Section~3 that $N_M$ is either the number of non-parallel disjoint incompressible tori in $M$ or $2$, whichever is larger.  If no pair of distinct tori of $\partial(X\cup N(\Gamma))$ are parallel in $M$, then at most $N_M$ of the components  of $\partial (X\cup N(\Gamma))$ are incompressible in $M$.

Thus we assume that some pair of distinct tori $T_i$ and  $T_j$ of $\partial (X\cup N(\Gamma))$ are parallel in $M$.  Then $T_i$ and $T_j$ co-bound a region $R$ in $M$ which is homeomorphic to a product of a torus and an interval.  However, since $T_i$ and $T_j$ are in the characteristic family for $\mathrm{cl}(M-N(\Gamma))$, they cannot be parallel in $\mathrm{cl}(M-N(\Gamma))$.  Thus $R$ intersects $\Gamma$.  But since $\partial R=T_i\cup T_j$ and $\Gamma$ is disjoint from $T_i\cup T_j$, this implies that $\Gamma\subseteq R$.  It now follows that $X\cup N(\Gamma)\subseteq R$.

Now suppose that some component $T_k$ of $\partial(X\cup N(\Gamma))$ is incompressible in $M$ and distinct from $T_i$ and $T_j$.  Then  $T_k\subseteq R$.   But since $R\cong T_j\times I$, either $T_k$ is parallel in $R$ to both  $T_i$ and $T_j$, or $T_k$ is compressible in $R$.  However, since $R\subseteq M$, the latter would imply that $T_k$  is compressible in $M$.

Thus $T_k$ must be parallel to both $T_i$ and $T_j$ in $R\subseteq M$.  Since $T_k$ does not intersect $\Gamma$,  this means that $T_k$ is parallel to one of $T_i$ or $T_j$ in $\mathrm{cl}(M-N(\Gamma))$.  But this is impossible since $T_i$, $T_j$, and $T_k$ are all in the characteristic family for $\mathrm{cl}(M-N(\Gamma))$.   Thus the only components of $\partial (X\cup N(\Gamma))$ which could be incompressible in $M$ are $T_i$ and $T_j$.  Hence $\partial (X\cup N(\Gamma))$ has at most $2\leq N_M$ components which are incompressible in $M$.

\begin{comment}Thus we can assume that no pair of distinct components of $\partial(X\cup N(\Gamma))$ are parallel in $M$.  Hence there are at most $N_M$ components of $\partial (X\cup N(\Gamma))$ which are incompressible in $M$.

Since $\Omega$ is the characteristic family of tori for $M$, we know that $T_i$ can be isotoped to be disjoint from $\Omega$ (see for example \cite{Ha3}).

 Thus, without loss of generality, we can assume that $T_i$ is contained in a closed up component of $M-\Omega$ which is either atoroidal or Seifert fibered.  If $T_i$ is in an atoroidal component, then $T_i$ is parallel to a torus in $\Omega$.  If $T_i$ is in a Seifert fibered component, then it follows from Waldhausen  \cite{Wa1} that $T_i$ is parallel to either a torus in $\Omega$ or a vertical or horizontal torus of the fibration.

Since no pair of distinct components of $\partial(X\cup N(\Gamma))$ are parallel in $M$, there are at most $t=|\Omega|$ incompressible tori in $\partial (X\cup N(\Gamma))$ that are parallel to a torus in $\Omega$, and at most $w$ (see Section 3 for the definition of $w$) incompressible tori in $\partial(X\cup N(\Gamma))$ that are parallel to a vertical or horizontal torus in some Seifert fibered closed up component of $M-\Omega$. Hence there are at most $N_M=t+w$ tori in $\partial (X\cup N(\Gamma))$ that are incompressible in $M$.
\end{comment}

\bigskip

 \noindent{\bf Step 11: We prove the inequality $\mathrm{dim} _{\Z_2} (H_1 (M',\Z_2))\leq n_M.$}
\bigskip

Recall that $M'$ is obtained from $X\cup N(\Gamma)$ by adding a collection of solid tori $V_1$, \dots, $V_r$ along the components $T_1$, \dots, $T_r$ of $\partial (X\cup N(\Gamma))$.  Also, by the condition in Step 9, we know that if $T_i$ is compressible in $M$, then every element of $H_1 (T_i,\mathbb{Z}_2)$ is trivial in $H_1 (M',\mathbb{Z}_2)$; and if $T_i$ is incompressible in $M$ then there exists some curve $\beta_i$ on $T_i$ such that $\beta_i$ is non-trivial in $H_1 (T_i,\mathbb{Z}_2)$ but trivial in $H_1 (M',\mathbb{Z}_2)$.  It follows that for every $T_i$ which is incompressible in $M$, there is at most one curve $\alpha_i$ in $T_i$ which is non-trivial in $H_1 (M',\mathbb{Z}_2)$.  Thus every curve in  $H_1 (T_i,\mathbb{Z}_2)$ is either trivial in $H_1 (M',\mathbb{Z}_2)$ or homologous to $\alpha_i$ in $H_1 (M',\Z_2)$.

Now let $\alpha$ be a curve in $M'$ which is non-trivial in $H_1 (M',\Z_2)$, and for each solid torus $V_i$, let $C_i$ denote its core.  Then by general position, we can choose $\alpha$ to be disjoint from $C_1\cup \dots \cup C_r$, and hence disjoint from $V_1\cup \dots\cup V_r$.  Now since $\alpha\subseteq X\cup N(\Gamma)\subseteq M$, we can also consider $\alpha$ in $ H_1 (M,\Z_2)$.

Suppose that $\alpha$ is trivial in $H_1 (M,\Z_2)$. It follows that $\alpha$ is homologous in $ X\cup N(\Gamma)$ to a collection of curves on $T_1\cup \dots \cup T_r$ which are trivial in $H_1 (M,\Z_2)$ but non-trivial in $H_1 (M',\Z_2)$.   Since for any $T_i$ which is compressible in $M$ every element of $H_1 (T_i,\mathbb{Z}_2)$ is trivial in $H_1 (M',\mathbb{Z}_2)$, $\alpha$ is homologous in $H_1 (M',\Z_2)$ to a collection of curves on only those $T_i$ which are incompressible in $M$.  It now follows that $\alpha$ is homologous in $H_1 (M',\Z_2)$ to a sum of $\alpha_i$'s on $T_i$'s that are incompressible in $M$.  But by Step 10, there are at most $N_M$ such tori.  Hence there are at most $N_M$ distinct $\alpha_i$ which are non-trivial in $H_1 (M',\Z_2)$.  It follows that these $N_M$ curves generate every non-trivial element of $H_1 (M',\Z_2)$ which is trivial in $H_1 (M,\Z_2)$. This gives us the required inequality:

  $$\mathrm{dim} _{\Z_2} (H_1 (M',\Z_2))\leq \mathrm{dim} _{\mathbb{Z}_2} (H_1 (M,\mathbb{Z}_2))+N_M=n_M.$$
  \medskip

  Hence the proposition follows.\end{proof}

\bigskip\bigskip

\centerline{\textsc{References cited}}

\bigskip\bigskip

\catcode`\@=11
\def\@biblabel#1{\@ifnotempty{#1}{[\bfseries #1]}}

\renewenvironment{thebibliography}[1]{

   \normalfont
   \labelsep .5em\relax
   \renewcommand\theenumiv{\arabic{enumiv}}\let\p@enumiv\@empty
   \list{\@biblabel{\theenumiv}}{\settowidth\labelwidth{\@biblabel{#1}}
     \leftmargin\labelwidth \advance\leftmargin\labelsep
     \usecounter{enumiv}}
   \sloppy \clubpenalty\@M \widowpenalty\clubpenalty
   \sfcode`\.=\@m
}{
   \def\@noitemerr{\@latex@warning{Empty `thebibliography'
environment}}
   \endlist
}

\newcommand{\bibsub}[1]{${}_{\mathbf{#1}}$}

\catcode`\@=12


TITLE: sketch a interval
QUESTION [0 upvotes]: In general, how do you do when you sketching a interval? I know how to sketch a function $y=x+1$ for example, then I just have some inputs for example:
for $y=2$ gives $x=1$, and then just plot it out in a graph.
but how do you do that when it comes to interval like this: $1 \le x^2 \le 2$ ?
and if we have $1 \le x^2 + y \le 2$

REPLY [0 votes]: $\{x: 1 \leq x^{2} \leq 2\}=[1,\sqrt 2] \cup [-\sqrt 2, -1]$.
$y=1-x^{2}$ and $y=2-x^{2}$ are parabolas with vertices  $(0,1)$ and $(0,2)$ and axes along the $y-$ axis and $\{1\leq x^{2}+y \leq 2\}$ is the region between these two parabolas.


TITLE: Closed form for a formula with a summation over $i\binom{n-i}{k-1}$, and combinatorial proof?
QUESTION [3 upvotes]: I was trying to simply an expression in an exercise related to randomized algorithms. Here is the expression which I have obtained at the end.
$$ \displaystyle\frac{\displaystyle\sum_{i=1}^{n+k-1} i \binom{n-i}{k-1}}{ \displaystyle{n \choose k}}$$
Is there any way to simplify the numerator so that the whole expression simplifies into a nice closed formula? A combinatorial approach would be greatly appreciated.

REPLY [0 votes]: $\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle}
 \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack}
 \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,}
 \newcommand{\dd}{{\rm d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\dsc}[1]{\displaystyle{\color{red}{#1}}}
 \newcommand{\expo}[1]{\,{\rm e}^{#1}\,}
 \newcommand{\fermi}{\,{\rm f}}
 \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,}
 \newcommand{\half}{{1 \over 2}}
 \newcommand{\ic}{{\rm i}}
 \newcommand{\iff}{\Longleftrightarrow}
 \newcommand{\imp}{\Longrightarrow}
 \newcommand{\Li}[1]{\,{\rm Li}_{#1}}
 \newcommand{\norm}[1]{\left\vert\left\vert\, #1\,\right\vert\right\vert}
 \newcommand{\pars}[1]{\left(\, #1 \,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\pp}{{\cal P}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,}
 \newcommand{\sech}{\,{\rm sech}}
 \newcommand{\sgn}{\,{\rm sgn}}
 \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}}
 \newcommand{\ul}[1]{\underline{#1}}
 \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$
$\ds{{\ds{\sum_{j\ =\ 1}^{n\ +\ k\ -\ 1}j{n - j \choose k - 1}}\over
     \ds{n \choose k}}:\ {\large ?}.\qquad}$ Lets $\ds{\quad n + k - 1 \equiv m}$.

\begin{align}&\color{#66f}{\large\sum_{j\ =\ 1}^{m}j{n - j \choose k - 1}}
=\sum_{j\ =\ 1}^{m}j\oint_{\verts{z}\ =\ 1^{-}}{\pars{1 + z}^{n - j} \over z^{k}}
\,{\dd z \over 2\pi\ic}
\\[5mm]&=\oint_{\verts{z}\ =\ 1^{-}}
{\pars{1 + z}^{n} \over z^{k}}\sum_{j\ =\ 1}^{m}j\pars{1 \over z + 1}^{j}
\,{\dd z \over 2\pi\ic}
\\[5mm]&=\oint_{\verts{z}\ =\ 1^{-}}
{\pars{1 + z}^{n} \over z^{k}}\bracks{%
{1 + z \over z^{2}} - {\pars{1 + z}^{-m + 1} \over z^{2}}
-m\,{\pars{1 + z}^{-m} \over z}}\,{\dd z \over 2\pi\ic}
\\[5mm]&={n + 1 \choose k + 1} - {n - m + 1 \choose k + 1} - m{n - m \choose k}
\\[5mm]&=\color{#66f}{\large{n + 1 \choose k + 1} - {2 - k \choose k + 1}
-\pars{n + k - 1}{1 - k \choose k}}\,,\qquad
\boxed{\ds{\quad n + k \geq 2\quad}}
\end{align}


TITLE: Given two vertices and incenter find third vertex
QUESTION [0 upvotes]: $u=(3,1)$, $v=(3,6)$, $i=(2,3)$, need find $w\in \mathbb{R}^2$ such that $i$ is the incenter of the triangle $[u,v,w]$.
I have looked at some other people's approaches to this problem, but I think those approaches are too complicated, and are more like for some advanced intuitive geometer. With the fact that I'm just taking a course in geometry, my approach is probably not so elegant, but it should work. The problem is that I'm still not getting the correct answer.

Let $\alpha, \beta, \gamma$ be the three angles of $[u,v,w]$. Then bisect the three angles to assume $\alpha/2, \beta/2, \gamma/2$.
We can find that $a=(3,3)$ is the point closest to $i$ on the edge $[u,v]$.
We can now set up the following equations:

$$\alpha/2 = \arccos\left(\frac{(v-u)\cdot (v-a)}{\|v-u\|\|v-a\|}\right)=\arccos\left(\frac3{\sqrt{10}}\right)\implies \alpha = 2\arccos\left(\frac3{\sqrt{10}}\right)$$
$$\gamma/2 = \arccos\left(\frac{(v-w)\cdot (w-u)}{\|v-w\|\|w-u\|}\right)=\arccos\left(-\frac{9}{10}\right)\implies \gamma = 2\arccos\left(-\frac9{10}\right)$$
  $$\beta = \pi-\alpha-\beta$$
$$ \cos\alpha =  \frac{(v-u)\cdot (w-u)}{\|v-u\|\|w-u\|}
$$

Can someone please suggest what is wrong with my approach? Is there an additional equation missing? Also, I'm getting some "crazy" expression for $\beta$, which even WolframAlpha finds difficult to deal with. Is this geometric problem really that complicated?

REPLY [0 votes]: I would use the double able formula for tangent to get the slopes of $uw$ and $vw$, where $w$ is the third vertex.  Here I do $AC$,  as $BC$ would be similar.
The counterclockwise angle from $uv$ to $ui$ is given by $\tan \theta=1/2$ which you can easily see from the slopes of the two rays ($uv$ is straight up, $ui$ has slope $-2$.  Then the counterclockwise angle from $uv$ to $uw$ is $2\theta$ and from the double angle formula for tangent we get $\tan 2\theta=4/3$.  With $uv$ directed straight up the slope of $uw$ is $-3/4$.
The reader can similarly compute the slope of $vw$.  The answer will be a $3-4-5$ right triangle.


TITLE: True/False Real Analysis Qualifying Exam Questions
QUESTION [1 upvotes]: The following is from a practice real analysis qualifying exam, and I had a couple questions about some of them.

$a$) I think this one is true, but I'm not sure how to prove it.
$b$) I know that $\partial^{\alpha}\hat{f} = \hat{[(-2\pi ix)^\alpha f]} (\xi)$. I don't necessarily see any reason that setting this equal to $0$ implies that $f=0$, so that would lead me to believe it might be false, but I'm unable to construct a counterexample.
$c$) We haven't done this yet, so skip.
$d$) True -- HW problem
$e$) Should be false if $d$ is true, but can't construct counterexample
$f$) I believe it's false and that $X=[0,1]$ with $f = \frac{1}{\sqrt x}\chi_{[0,1]}$ works.
$g$) I believe it's true using a comparison test argument
$h$) I believe it's false using $X = [0,1], M = \mathbb{B}_{X}, \mu_1 =$ Lebesgue measure, \mu_2 = $ counting measure
So I primarily need help with a,b,e and just want to verify that my answers for d,f,g,h are correct. Thank you!

REPLY [1 votes]: $(a)$ is false, for a counterexample I'd suggest to look at an infinite dimensional space, say $\ell^2(\mathbb{N})$. (Recall that the unit ball is not compact)
$(b)$ is true: the Fourier Transform maps Schwartz functions into Schwartz functions. The only constant Schwartz function is $0$. This also implies that $f = 0$ by Plancherel's equality, for example.
$(e)$ Let's disprove the statement: assume the space is only complete wrt one of the two norms. If it is complete wrt $\|\cdot\|_2$ then it is complete wrt $\|\cdot\|_1$ using the inequality given, a contradiction. Then it must be complete wrt $\|\cdot\|_1$. Assume that it is possible to prove the other inequality, then it would be complete wrt $\|\cdot\|_2$ arguing as before.
$(f),(g)$: you are correct.
$(h)$: You can also take a look at this


TITLE: Pullback of line bundles and existence of divisors representing line bundles
QUESTION [7 upvotes]: I am studying the proof of Lemma 7.2. on page 108 in Dolgachev's "Lectures on invariant theory". It states (everything is done over the field $k = \overline{k}$):

Let $X$ be a normal affine variety (for example, nonsingluar) and $G$ is a connected affine algebraic group. Let $L$ be a line bundle on $G \times X$. Then there exist line bundles $L_1 \in Pic(G)$, $L_2 \in Pic(X)$ such that $L \cong pr_1^*(L_1) \otimes pr_2^*(L_2)$ (where $pr_i$ is the $i$-th projection of $G \times X$).

The proof uses the following facts about algebraic groups:

$G$ containes a Zariski open set $U$, which is isomorphic to $(\mathbb{A}^1 \setminus \{0\})^N$.
$pr_2^* \colon Pic(X) \to Pic((\mathbb{A}^1 \setminus \{0\}) \times X)$ is an isomorphism.

Then it is clear that $L$ restricted to $U \times X$ is isomorphic to $pr_2^*(L_2)$ for some $L_2 \in Pic(X)$.
The following is said afterwards:
Let $D$ be a Cartier divisor on $G \times X$ representing $L$.
Question 1: Why does such a $D$ exist? $X$ is not projective, so I don't quite see why $D$ should exist.
The proof continues as follows:

Then the preceding isomorphism implies that there exists a Cartier Divisor $D_2$ on $X$  such that $D' = D-pr_2^*(D_2)|_{U \times X} = 0$.

Question 2: Why exactly does $D_2$ exist?
Now, take any irreducibly component $D_i'$ of $D'$ and consider the projection $D_i' \to G$. The image is contained in $G \setminus U =: Z$. By the theorem on the dimension of fibres, the fibres of this projection have dimension equal to $\dim X$. Then the last part which I don't understand follows:

This easily implies that $D_i' = pr_1^*(D_i)$, where $D_i \subset  Z$.

Question 3: Why?
Thanks in advance for any help.

REPLY [2 votes]: Question 1: Maybe there's some subtlety I'm missing here, but isn't there a Cartier divisor attached to any line bundle?  You just pick an affine where it's trivial, and let the trivialization be your rational section (using the definition here).
Question 2: Since $pr_2^*$ is an isomorphism to $\operatorname{Pic}(U\times X)$, it's surjective.
Question 3: Because $Z\times X$ is already a divisor.  Thus, the only divisor that could be supported on it is a sum of the components of $Z\times X$.


TITLE: Trouble understanding cardinality
QUESTION [1 upvotes]: Hi guys I am having trouble understanding cardinality. I am given this practice question.
1) Use Cantor-Schroder-Bernstein Theorem to prove that the intervals $(0,1)$ and $[0,1]$ have the same cardinality?
My attempt :
I know the CSB theorem is
Let $A, B$ be sets and if $f: A \rightarrow B$ , and $g: B \rightarrow A$ are both injections, then there exists a bijection from $A$ to $B$
I have to show that $|(0,1)| = |[0,1]| $ so we need $f: (0,1) \rightarrow [0,1]$ and we can set $f(x) = x$ and also we need $g: [0,1] \rightarrow (0,1)$ and we can let $g(x) = \frac{1}{2}x + \frac{1}{4}$
but after I get stuck I dont know what to do i know have to set these equations up but get confused after.
Please help out any help or hints will be greatly appreciated
Thank you

REPLY [3 votes]: You’re done as soon as you verify that the maps $f$ and $g$ are injections, that the range of $f$ is a subset of $[0,1]$, and that the range of $g$ is a subset of $(0,1)$: at that point you have an injection $f:(0,1)\to[0,1]$ and an injection $g:[0,1]\to(0,1)$, and the CSB theorem tells you outright that there exists a bijection $h:[0,1]\to(0,1)$ and hence that $\left|[0,1]\right|=\left|(0,1)\right|$.


TITLE: Number theory question to establish a relation
QUESTION [0 upvotes]: Suppose we have $$p^2 + q^2 + r^2 +pq + qr + pr=3$$ so can we use only this relation to find $$\frac{p^2 +2q^2+r^2}{q^2}$$?

REPLY [2 votes]: Hint: The equation can be rewritten as
$$
(p+q)^2+(p+r)^2+(q+r)^2=6.
$$
But I would still be skeptical, because the roles of $p,q,r$ are symmetric (as also pointed out by Ross). Rewriting does reduce it to a finite set of possibilities.

 Six can be written as a sum of three squares in relatively few ways. When you take into account sign variations, 24 ways, unless I made a mistake. Solve the resulting systems, and see what you get :-)


TITLE: absolute or conditional convergence
QUESTION [2 upvotes]: I am doing an exercise but in the middle I am stuck.
$$\sum_{k=2}^\infty \frac{[\ln(k+1)-\ln k]^a}{\ln^2k}$$
I have rewritten this as:
$$\sum_{k=2}^\infty \frac{[\ln(k+1)/k)]^a}{\ln^2k}$$
Now $a_k=\frac{\ln^a(k+1)/k)}{\ln^2k}$, and apply a Taylor series expansion.
Now I wrote: $a_k = \frac{1}{\ln^2k}\left[\frac{1}{k}-\frac{1}{2k^2} + O\left( \frac 1 {3k^3}\right)\right]^a$. By dividing by $\frac{1}{k}$, and applying the binomial expansion, obtaining
$$a_k=\frac{1}{k^a \ln^2k}(1-\frac{a}{2k}+\cdots)$$
But how to proceed? Perhaps I started completely wrong?

REPLY [1 votes]: HINT:
Using the inequalities
$$\frac{x}{x+1}\le \log(1+x)\le x$$
we see that
$$\frac{1}{(k+1)^a\log^2(k)} \le \frac{\log^a\left(1+\frac1k\right) }{\log^2(k)}\le \frac{1}{k^a\log^2(k)}$$
Can you conclude now?


TITLE: Natural computation based on fundamental forces
QUESTION [9 upvotes]: Well-known examples of computation inspired by natural phenomenon are quantum computers and DNA computers.
What is known about the potential and/or limitations of computing with Maxwell's laws or gravity?
That is, incorporating nature's "quick" solutions to Maxwell's equations or the n-body problem directly into a general-purpose algorithm?

REPLY [2 votes]: Here's one interpretation of your question, which you may or may not have intended, but for which I have an answer.
Computers are obviously real physical devices and therefore can be modeled by the laws of physics.  But we don't use the laws of physics that would be needed to describe a real computer as a model of computation because it's too complex.  To make a model of computation, we define something like a Turing machine that is simple enough to be mathematically tractable. However, now we've untethered the model from the physical world, because we don't say how the Turing machine is built or what forces drive it to run.
So can we devise some simple models that capture "computation", but whose fundamental rules are physical in nature?  My answer to this would be to check out the Feynman Lectures on Computation: http://www.amazon.com/Feynman-Lectures-Computation-Richard-P/dp/0738202967
He talks about a lot of different simple physical systems that carry out a computation.  For example, there is the billiard ball model of Fredkin and Toffoli (http://en.wikipedia.org/wiki/Billiard-ball_computer), where the point was to explicitly account for energy requirements and to design a computer that can run for arbitrarily many steps for arbitrarily little energy.  In particular, the chapter on reversible computing has a lot of these kinds of examples.
We think about this issue a lot in my lab.  For example, we've done some work on what it means for chemical reaction networks to do computation: http://www.dna.caltech.edu/DNAresearch_publications.html#DeterministicCRNs and http://www.dna.caltech.edu/DNAresearch_publications.html#ComputationalCRNs
We also think about how seeded crystal formation can carry out computation: http://www.dna.caltech.edu/DNAresearch_publications.html#Simulations as well as actually trying to make it happen experimentally: http://www.dna.caltech.edu/DNAresearch_publications.html#OrigamiSeed, and some other work based on computing using a physical phenomenon called DNA strand displacement: http://www.dna.caltech.edu/DNAresearch_publications.html#DNALogicCircuits


TITLE: Extensions of branches to nonstandard trees
QUESTION [0 upvotes]: This is sort of inspired by the "cute" nonstandard proof of the fact that an infinite but finitely branched rooted tree has an infinite branch. An infinite branch is found by taking nonstandard element in a nonstandard extension of the tree and looking at all the elements which lie below it. I am wondering when that initial element is in the nonstandard extension of that branch.
To be more precise:
Suppose we have a rooted tree $T$ with vertices arbitrarily far from the base point. Also note that rooted trees have a natural partial order with $v\leq w$ when $v$ lies on the shortest path from $w$ to the base.
Let $^*T$ denote the nonstandard enlargement of $T$. Since $T$ has vertices of arbitrary distance from the root, there is a vertex $v$ in the enlargement which is some nonstandard distance (i.e. infinite distance) from the root. Viewing $T$ as a subtree of $^*T$, let $B$ be the branch of $T$ given by those $t\in T$ such that $t {\leq^*} v$.
The set $B$ has a nonstandard extension $^*B$ which we can view as a subset of $^*T$. When is it the case that $v$ is in $^*B$?

I don't think $v$ has to be in $^*B$, and it seems like there is a chance it never is.
Since being a branch is first-order, $^*B$ is also a branch. Let's say we have $v\rightarrow v'$ and $v'' \rightarrow v'$ in $^*T$. Then branch $B$ described above which lies below $v$ is the same as the one lying below $v''$. But because $^*B$ is a branch, only one of $v,v''$ could be in $^*B$. I don't see how either possibility could be distinguished! Is it possible that, with the construction above $v$ is never in $^*B$?

REPLY [1 votes]: Fix an infinite, finitely-branching tree $T$. Let $X\mapsto {}^*X$ be the usual "nonstandard analogue" map. For $v\in {}^*T\setminus T$, let $\mu(v)=\{w\in T: w<_{{}^*T}v\}$ be the standard part of the original tree $T$ lying below $v$. Finally, let $P(v)={}^*\mu(v)$. You're asking about when we have $v\in P(v)$.
The key point is this:

$P(v)$ is always a maximal path in ${}^*T$. Moreover, every maximal path $B$ in $T$ has exactly one extension to a maximal in the range of $P(v)$, namely ${}^*B$ itself.

The first sentence is just an application of transfer to the property "is a maximal path:" since $\mu(v)$ is a maximal path in $T$, its nonstandard analogue will be a maximal path in $T$'s nonstandard analogue. The second point is basically just a rephrasing of the definition of $P$ itself, the point being that (per the argument this question was motivated by) such a $B$ has some nonstandard extension $v$ which satisfies $P(v)={}^*B$.
This gives us the following:

Suppose $v,w\in {}^*T\setminus T$. If $w\in P(v)$ then $P(w)=P(v)$ and so $w\in P(w)$.

This tells us that while a given nonstandard node may not lie in the nonstandard branch it creates, all nonstandard nodes on any nonstandard branch so created will in fact generate that branch.
In the other direction, via overspill the "$v\not\in P(v)$"-phenomenon is essentially describing the non-isolated paths:

The following are equivalent, for $v\in {}^*T\setminus T$:

There are infinitely many splitting nodes in $\mu(T)$.
There are infinitely many maximal paths through ${}^*T$ extending $\mu(T)$.
There is some $u$ with $\mu(u)=\mu(v)$ (and so $P(u)=P(v)$) but $u\not\in P(u)$.


TITLE: Would increasing the window size of an observation plane, like a camera, increase resolution?
QUESTION [0 upvotes]: I have a diffraction pattern emanating from a source and incident upon an observation plane. If I increase the size of the observation plane, it would increase the number of spatial frequencies in the tangential direction hitting the plane.
However, I don't intuitively understand how this is possible. How can increasing the observation plane of something, when it already fits the entire image, further increase its resolution?

REPLY [0 votes]: No, if the size of the observation plane is increased, one would not increase the spatial frequencies in that plane (Unless you consider the image in that plane as the spectrum, since it is in the far field. I'm going to assume this is not the case), however, since the size of the resolvable point in that plane stays fixed, one would get more of those points if one increases the size of that plane. To increase the resolution in that plane (to increase the number of spatial frequencies and thus reduse the size of the resolvable points), one would need to increase the size of the aperture of the Fourier plane prior to the observation plane. Perhaps, that aperture would be the diameter of the lens that images the light onto the observation plane.


TITLE: How do I solve the IVP $Y^{''}-8Y^{'}+16Y = 2\cos(x)$ with $y(0)=1$ & $y^{'}(0)=2$?
QUESTION [0 upvotes]: I have gotten as far as getting the complimentary function :
$$y(x) = (A_1x+A_2)e^{4x}$$
But I don't know how to go about the particular solution?

REPLY [1 votes]: A more rigorous method to evaluating the solution of a non-homogeneous linear ODE is using Variation of Parameters. Essentially, the methodology is identical to what others have shown (Method of Undetermined Coefficients), however without having to 'guess' the form of the particular solution $y_p$.
This video link shows an example using Variation of Parameters for the differential equation $\frac{d^2{y}}{dx^2}-\frac{dy}{dx}-2y=4x^2$.
Alternatively, there are also written notes for the method, with some examples.
Note: The Wronskian determinant matrix is of the form:
$W= \begin{vmatrix}
f_1(x) & f_2(x) & \cdots & f_n(x) \\
f_1'(x) & f_2'(x) & \cdots & f_n' (x)\\
\vdots & \vdots & \ddots & \vdots \\
f_1^{(n-1)}(x)& f_2^{(n-1)}(x) & \cdots & f_n^{(n-1)}(x)
\end{vmatrix}$


TITLE: How do observers in inertial frames explain fictitious forces?
QUESTION [6 upvotes]: Suppose a ball is thrown upwards, from the surface of the Earth. After some time, it will obviously fall down back on the surface. However, it would be deflected slightly to the sides of the initial point from which it was launched. From a person, on the Earth, this appears to be a fictitious force, called the Coriolis force, that is responsible for this deflection. However, I've learnt that this force arises because the observer is in a non-uniform reference frame i.e. the spinning Earth. Hence, they perceive this fictitious force.
However, for an observer in space, an inertial frame, how does one explain the deflection of the ball? Is it because of the ball's inertia, that it falls back to the same place, but the Earth has rotated a bit by then ? That is why it seems to be deflected in the direction opposite to the direction of rotation ?
Similarly, a compartment is orbiting a point and is connected by a thread. Inside the compartment, we have a human being. From outside, there is only the tension of the string, that acts as the centripetal force, causing the circular motion. However, it has been said, that the man inside the compartment, feels an outward deflection, that he attributes to the centrifugal force. The compartment itself does not feel any force, because it is stationary in its own frame, but the man inside feels this deflection.
How can the outside observer, explain why the man inside is feeling an outward deflection ?

REPLY [3 votes]: Intuition
Heres the best way to understand inertial forces:
If the room is being accelerated in one direction, it is as if there is an extra “gravity” pulling everything in the room the opposite direction. If room is accelerating at $+\vec{a}$, everything is pulled on with force of $-m ~ \vec{a}$
Example: normally in a room, gravity pulls on everything. If the room is falling, theres is no gravity, zero g. Where did the gravity go? The acceleration downward of the room created a fake gravity upward.
So all that matters is the acceleration of the frame. Not velocity.
Application
Step one find net fake gravity
Figure out the acceleration of the frame, as a vector $+\vec{a}$. Take the opposite of that vector $-\vec{a}$ as added fake gravity in the frame. Then add that to the real gravity vector (which is $-g \hat{j} $) to get the net fake gravity $\vec{g_\text{eff}}=\vec{g}-\vec{a}$. Pulling on everything with force $mg_{\text{eff}}$ or with direction $m \vec{g_\text{eff}}$. Spinning frames move tangentially, but accelerate towards the center.
Step two solve the problem
Ignore that the frame is moving. Solve the problem incl $\vec{g_\text{eff}}$. Conservation of mass and momentum and angular momentum still apply. Friction works the same. All the same. (Note: these conservation laws are still being true from a still frame too, but not your concern).