    \documentclass[12pt]{article}
      \usepackage{amsmath,amssymb,amsthm,setspace}
      \usepackage[pdftex]{graphicx}
      \usepackage[top=1in, bottom=1in, left=1in, right=1in]{geometry}

      \renewcommand{\thefigure}{\arabic{figure}}
%	  \renewcommand{\thefigure}{\thesection.\arabic{figure}}
      \theoremstyle{plain}
      \newtheorem{thm}{Theorem}[section]
      \newtheorem{proposition}[thm]{Proposition}
      \newtheorem{lemma}[thm]{Lemma}
      \newtheorem{cor}[thm]{Corollary}
      \theoremstyle{remark}
      \newtheorem{remark}{Remark}[section]    
      \theoremstyle{definition}
      \newtheorem{defn}[remark]{Definition}
      \newtheorem{example}{Example}
      \numberwithin{equation}{section}
      
      \title{Hyperbolic 3-Manifolds as Discretized Configuration Spaces of Simple Graphs}%{3-Dimensional Discretized Configuration Spaces of three Points in Simple Graphs}
      \author{Michelle Chu}

	  \doublespacing

\begin{document}

\pagestyle{empty}
%\begin{abstract}
%\begin{center} Hyperbolic 3-Manifolds as Discretized Configuration Spaces of Simple Graphs
%\\ By Michelle Chu \end{center}
%A discretized configuration space is a topological space of possible configurations of particles in which multiple particles are not allowed in neighbouring edges. In this paper, we consider discretized configuration spaces of three particles on 1-dimensional simple graphs, in particular, the discretized configuration spaces $D_3(K_7)$ and $D_3(K_{4,4})$. We prove that in both cases, removing certain vertices from the discretized configuration spaces on three particles results in complete finite-volume hyperbolic 3-manifolds. We describe their construction and triangulations by cubes and tetrahedra. We also discuss their commensurability class in relation to each other and to the complement of the figure-8 knot. 
%\end{abstract} 


%\date{\today}
%\maketitle

%\newpage
\setcounter{page}{-2}
\pagestyle{empty}
\tableofcontents

\newpage
\listoffigures

\newpage
\pagestyle{myheadings} 
\begin{section}{Introduction}
\label{intro}
The topic of this paper is the study of the hyperbolic 3-manifolds that arise as the discretized configuration spaces of three particles on simple graphs. We think of the particles as robots moving on the graphs. These spaces related to motion-planning on graphs were first studied by Abrams and Ghrist in \cite{Abrams, Abrams Ghrist}.

Before indulging in the study of these manifolds, we must first understand some basic concepts which we describe in Section \ref{prereqs}. We involve only necessary detail to explain graphs, manifolds, hyperbolic geometry, cell-complex structures, and algebraic topology.


In Section \ref{prelim} we introduce the preliminaries to this work. This section begins with an example graph with its corresponding configuration space and discretized configuration space. It moves on to formally define a discretized configuration space and provide the framework for the rest of the paper. This section also provides the motivation. In particular, Proposition \ref{prop} in Section \ref{motivation} produces a clear course of action for the rest of the work. 

At last we reach the main topic of the paper in Sections \ref{K7} and \ref{K44}. Section \ref{K7} provides a detailed study of the discretized 3-space of the graph $K_7$. It begins with a short study of its predecessor, the discretized 2-space of the graph $K_5$. We then describe in detail the construction of $D_3(K_7)$ and the nice properties it has. This section also contains many new things we learned about this space throughout the course of this work. 
Section \ref{K44} proceeds in a similar fashion to the previous section. It begins with the study of the discretized 2-space of the graph $K_{3,3}$ and continues with the construction and study of $D_3(K_{4,4})$.

In Section \ref{relationship}, we relate the two spaces $D_3(K_7)$ and $D_3(K_{4,4})$ and conclude the paper with some questions for further study.
\end{section} 
 
\newpage
\begin{section}{Prerequisites}
\label{prereqs}

\begin{subsection}{Graphs}
We begin with a brief introduction to graph theory. A graph consists of a set of vertices, 0-cells, and a set of edges, 1-cells, between pairs of vertices. A simple graph is one in which no two edges share the same two  boundary vertices and also no edges are loops both starting and ending on the same vertex.

The \emph{order} of a graph is the number $n$ of vertices. The degree of a vertex is the number of edges connected to such a vertex. We can represent graphs with diagrams in the plane as in Figure \ref{examplegraph}. 

\begin{figure}[ht]
\begin{center}\includegraphics[height=1in]{examplegraph}\end{center}
\caption[A graph of order 4]{A graph of order 4.}
\label{examplegraph}
\end{figure}

A graph is \emph{complete} when each pair of distinct vertices are the endpoints of an edge. A complete graph of order $n$ has $\binom{n}{2}=n(n-1)/2$ edges and is denoted $K_n$. Note that sometimes when drawing a representation of a graph, we are forced to draw intersecting edges where forced intersections do not form a vertex. Examples of this are the graphs $K_5$, $K_6$, and $K_7$ in Figure \ref{completegraphs}.

\begin{figure}[ht]
\begin{center}\includegraphics[height=2.4in]{completegraphs}\end{center}
\caption[Complete graphs]{Complete graphs $K_1$, $K_2$, $K_3$, $K_4$, $K_5$, $K_6$, $K_7$.}
\label{completegraphs}
\end{figure}

A complete \emph{bipartite} graph $K_{m,n}$ is a graph with two sets of vertices, one with $m$ elements and another with $n$ elements where each vertex is connected to all vertices in the opposite set and to no vertices in the same set. Figure \ref{bipartitegraphs} shows the bipartite graphs $K_{3,3}$ and $K_{4,4}$. Figure \ref{8K44} shows an additional representation of $K_{4,4}$.

\begin{figure}[ht]
  \centerline{
    \mbox{\includegraphics[height=.6in]{K33}}
    \hspace{.8in}
    \mbox{\includegraphics[height=.6in]{K44}}}
\caption[Bipartite graphs]{Bipartite graphs $K_{3,3}$ and $K_{4,4}$.}
\label{bipartitegraphs}
\end{figure}

\begin{figure}[ht]
\begin{center}\includegraphics[height=1.2in]{8K44}\end{center}
\caption[A representation of $K_{4,4}$]{A representation of the graph $K_{4,4}$.}
\label{8K44}
\end{figure}

\end{subsection}

\begin{subsection}{Manifolds and Hyperbolic Geometry}\label{hyperbolic}
A manifold is a mathematical space that locally resembles Euclidean space of some dimension. The dimension of the Euclidean space is also the dimension of the manifold. More specifically, a 3-\emph{manifold} is a space in which every point is contained in a neighbourhood homeomorphic $\mathbb{R}^3$. These neighbourhoods fit together nicely to cover the space.

Here, the word homeomorphic means that one can be continuously deformed into the other by an invertible mapping called a homeomorphism. Roughly speaking, a homeomorphism is a continuous stretching and bending of one object into another. For example, a solid cube is homeomorphic to a solid ball. Although they do not share the same geometry, they share the same intrinsic topological properties. A doughnut and a ball are not homeomorphic. However, a doughnut and a coffee cup are homeomorphic.


The \emph{topology} of a space refers to the properties of that space that are unaffected by continuous deformation like bending, stretching, or twisting, but not tearing or gluing. In this way, a sphere and
a cube are topologically equivalent, but a sphere and a doughnut are not.

The \emph{geometry} of a space refers to the properties that are affected by deformation, such as curvature, volume, distance, and angle. These properties can help us determine the topology of the space since not any space can
admit, or be given, any geometry. A space is hyperbolic if it can be made smoothly out of chunks of hyperbolic space by gluing together along faces.

Hyperbolic geometry is a non-Euclidean geometry in which the angles of a triangle add up to less than $\pi$. In fact, the area of a triangle in hyperbolic space is determined solely by its angles. The following Theorem is a modified version of Corollary 2.4.15 in \cite{Thurston}.

\begin{thm} The area of a planar hyperbolic polygon with $n$ sides is equal to $(n-2)\pi-S$ where $S$ is the sum of the interior angles.
\label{area} \end{thm}

The hyperbolic plane $\mathbb{H}^2$ is homeomorphic to $\mathbb{R}^2$. However, the geometry is very different. As we have seen, the area of a polygon in the hyperbolic plane is not calculated in the same way as it is calculated in the Euclidean plane $\mathbb{R}^2$. ``Straight lines", or curves which minimize the distances between its points, are also different, and we refer to them as \emph{geodesics}, to not confuse them with the Euclidean counterpart.

It is difficult to picture the hyperbolic plane. Instead, we model hyperbolic geometry with Euclidean models. There are many models of the hyperbolic plane in the Euclidean plane, but throughout this paper we will use the \emph{upper half-plane} model. It consists of the upper half-plane together with a hyperbolic metric that models hyperbolic geometry. The boundary line of the upper half-plane together with the point at infinity model the circle at infinity of the hyperbolic plane. Geodesics are given by semicircles orthogonal to the line at infinity or by vertical Euclidean lines. This upper half-plane model of the hyperbolic plane is particularly nice because it preserves the angles in the hyperbolic plane.

In hyperbolic spaces, including the hyperbolic plane, polygons with finite area (and also polyhedra with finite volume) need not be closed and bounded as in Euclidean space. Polygons (and also polyhedra) in hyperbolic space which have all vertices at infinity are said to be \emph{ideal} polygons with ideal vertices. Polygons can be either ideal, non-ideal, or semi-ideal, when at least one but not all vertices are ideal. In Figure \ref{triangle} we see two examples of congruent ideal triangles in the upper half-plane model of the hyperbolic plane. Although they look different, their angles add to 0 and they share the same area equal to $\pi$. They are in fact isometric and we will see how.

\begin{figure}[ht]
  \centerline{
    \mbox{\includegraphics[height=1.3in]{triangle1}}
    \hspace{.8in}
    \mbox{\includegraphics[height=1.3in]{triangle2}}}
\caption[Regular ideal hyperbolic triangles]{Two regular ideal triangles in the upper half-plane model of the hyperbolic plane.}
\label{triangle}
\end{figure}

The 3-dimensional hyperbolic space $\mathbb{H}^3$ is also homeomorphic to its Euclidean counterpart $\mathbb{R}^3$. In a similar way, we can model this space in Euclidean space with the \emph{upper half-space} model which we denote \emph{UHS}. The UHS model consists of the upper half-space together with a point at infinity and a metric which models hyperbolic geometry. The bounding plane and the point at infinity constitute the sphere of infinity in this model. Planes in hyperbolic space are given by half-spheres orthogonal to the plane at infinity in the UHS model or by vertical planes.

In Euclidean space, an \emph{isometry} is a map that preserves congruences. That is, reflections, rotations, and translations in that preserve shape, size, and angles. Similarly, we have isometries in hyperbolic space. In the upper-half space model, hyperbolic isometries are given by M\"obius transformations. Refer to Section 2.2 of \cite{Thurston}. Hyperbolic isometries preserve shape, size, and angles. In fact, for any three ideal points in hyperbolic space, there is a unique isometry taking those three points to any choice of three ideal points. Therefore, all ideal triangles in $\mathbb{H}^2$ are congruent, or isometric, but all ideal tetrahedra are not. Since we can take any three ideal points to any three, and the fourth point must follow along, we describe the shape of a tetrahedron with a single complex number corresponding to the fourth vertex when vertices 1, 2, and 3 are taken to the point at infinity and 0 and 1 on the plane at infinity.

The triangles in Figure \ref{triangle} are also regular. Polygons in 2-dimensions and polyhedra in higher dimensions of hyperbolic space are \emph{regular} when every combinatorial symmetry is realized by a hyperbolic isometry. In particular, we can take any vertex to any other vertex by a hyperbolic isometry. This definition of regular polyhedra implies that all dihedral angles of a regular polyhedron are the same, since isometries preserve angles.

Analogous to the area of a hyperbolic polygon, the volume of a 3-dimensional convex hyperbolic polyhedron is determined by solely its dihedral angles. This volume however, is much more difficult to calculate. A straightforward way to find this volume is to triangulate, which is basically to divide, the polyhedra into tetrahedra. The volume of a regular ideal tetrahedron is well-known to be roughly 1.0149. Finding the volume of not so nicely shaped tetrahedra is complicated. However, a computer can easily calculate the volume by using a formula given in \cite{Volume} which takes as inputs the six dihedral angles of a tetrahedron. Figure \ref{tetrahedron} shows an example of the regular ideal tetrahedron in the UHS model of hyperbolic space. All dihedral angles are $\pi/3$. Notice that high enough cross sections are Euclidean equilateral triangles.

\begin{figure}[ht]
\begin{center}\includegraphics[height=2in]{tetrahedron}\end{center}
\caption[A regular ideal hyperbolic tetrahedron]{A regular ideal tetrahedron in the UHS model of hyperbolic space.}
\label{tetrahedron}
\end{figure}

Another model of hyperbolic space is the Poincar\'{e} ball model. In two dimensions, the interior of a disk models the hyperbolic plane. The boundary circle models infinity just as the line at infinity together with the point at infinity in the upper half plane model. Similarly, the interior of a 3-dimensional ball models 3-dimensional hyperbolic space. In this case, the boundary sphere models infinity. We will not refer back to this model in this paper except for a small part in Section \ref{geoK7}.

More discussion on M\"obius transformations, hyperbolic isometries, and different models of hyperbolic space can be found in Chapter 2 of \cite{Thurston}.
\end{subsection}

\begin{subsection}{Cell Complexes}
A \emph{cell-complex} is a space built out of cells, where each cell is homeomorphic to an \emph{open $n$-ball} $B\subset\mathbb{R}^n$ for some dimension $n$, called $n$-cell. To build a cell-complex, sometimes denoted a CW complex, we start with a set of discrete points or vertices. These are the 0-cells because they have dimension 0. We then add edges, or 1-cells, by specifying how to attach their endpoints to the 0-cells already in place. We continue inductively to attach the $n$-cells by specifying how to attach the boundary of each $n$-cell to the $(n-1)$-skeleton, where the $k$-skeleton is the union of all cells of dimension up to $k$. We will not worry about infinite-dimensional cell complexes. Also, for the purpose of this paper, we need only be concerned with cell complexes in which the set of $k$-cells, for each $k$, is finite.

\end{subsection}


\begin{subsection}{Group Theory and Algebraic Topology}
A \emph{group} is a set together with an operation that takes two elements from the set into another element in the set. A group has an identity element, distributive laws, and inverses for each element. In general, group operations need not be commutative. Those with commutative operations are called \emph{abelian} groups. For example, $\mathbb{Z}/n$ is an abelian group with the $n$ elements $\{0,1,\dots,n-1\}$ and the operation of addition $\mod n$. We refer to the number of elements in a group as the \emph{order} of the group.

A \emph{subgroup} is a subset of a group which is also a group under the same operation. If $H$ is a subgroup of $G$ we say that $H$ is a \emph{normal subgroup} if it is invariant under conjugations. That is, for any $g\in G$ with $g^{-1}$ the inverse of $g$, $gHg^{-1}=H$. The \emph{index} of the subgroup $H$ in $G$ is the number of copies, called \emph{cosets}, of $H$ that fill $G$. Whenever $H$ is a normal subgroup, the set of distinct cosets $G/H=\{gH:g\in G\}$ is in fact a group, called the \emph{quotient group} of $G$ by $H$. The quotient group is an identification of elements in a larger group. For more on group theory, refer to Part 1 of \cite{Dummit}.

	A topological space $X$ has a \emph{covering space} $\tilde{X}$ if there is a continuous map $p:\tilde{X}\rightarrow X$ such that each point in $X$ has an evenly covered neighbourhood. More rigorously, there exists an open cover $\{U_\alpha\}$ of $X$ such that for each $\alpha$, the inverse image $p^{-1}(U_\alpha)$ is a disjoint union of open sets in $\tilde{X}$, each mapped by $p$ homeomorphically onto $U_\alpha$. In particular, a covering map is a local homeomorphism and $\tilde{X}$ is called a covering space of $X$. There is an induced homomorphism of the fundamental groups of these spaces. A \emph{homomorphism} is a map between two groups satisfying specific conditions, and the \emph{fundamental group} is the group associated with each topological space. For more on homomorphisms, refer to Section 1.6 of \cite{Dummit}. The fundamental group of a path-connected space $X$ is denoted $\pi_1(X)$. Refer to Chapter 1 of \cite{Hatcher} for more on fundamental groups and covering spaces.

Given a group $G$ and a set $Y$, a \emph{group action} of $G$ on the set $Y$ is a homomorphism $\rho:G\rightarrow\text{Homeo}(Y)$ where $\text{Homeo}(Y)$ is the group of homeomorphisms  from $Y$ to itself. So each element of $G$ is associated with a homeomorphism from $Y$ to itself. If the map $\rho$ is injective, then $G$ is identified with a subgroup of $\text{Homeo}(Y)$. If $g\in G$ then we think of $g$ as the homeomorphism from $Y$ to itself. If for all $y\in Y$ and all nontrivial $g\in G$, $g(y)\neq y$, then the group action of $G$ on $Y$ is a \emph{free action}. That is, an action is free if it has no fixed points. We introduce this concept of free actions because they provide a way to find quotient spaces. If $Y$ is some simply connected space and $G$ acts freely on $Y$, then $Y/G$ is a quotient space of $Y$ with fundamental group $G$. Refer to Section 1.3 of \cite{Hatcher}.
	
	For the purpose of this paper, we consider two compact manifolds as \emph{commensurable} if one has a finite cover homeomorphic to a finite cover of the other. Actually, commensurability is more general. It is a an equivalence class, for example if $N_1$ shares a finite cover with $N_2$, which shares a finites cover with $N_3$, which shares a finite cover with $N_4$, then all of $N_1$, $N_2$, $N_3$, and $N_4$ are commensurable. Two groups are \emph{commensurable} if one has a finite index subgroup that is isomorphic to a finite index subgroup of the other, or similarly as in the manifold case, if they are in the same commensurability class.  A cover of a space $X$ is uniquely determined by the corresponding conjugacy class of a subgroup of the fundamental group of $X$. The definition of commensurability between two manifolds can be equivalently defined by saying that their fundamental groups are commensurable.

\end{subsection}

\end{section}


\begin{section}{Preliminaries and Definitions}\label{prelim}

\begin{subsection}{Motion-Planning}\label{example}
As a motivation for our project, we begin with a simple problem that illustrates the general questions of configuration spaces. We will formally define these spaces in Section \ref{conf}.

\begin{figure}[ht]
\begin{center}\includegraphics[height=1.2in]{K3}\end{center}
\caption[A labelling of the vertices of $K_3$]{A labelling of the vertices of $K_3$.}
\label{K3}
\end{figure}

Imagine two robots moving inside the graph of $K_3$ labelled as in Figure \ref{K3}. Obviously, these two robots cannot occupy the same position at the same time. Consider all the possible positions of two robots with the property that the two robots are never on the same position. This creates a topological space known as the configuration space of two agents in $K_3$, or $\mathcal{C}_2(K_3)$. The set of positions where the robots coincide is the pairwise diagonal $\Delta$. Thus $\mathcal{C}_2(K_3)=K_3\times K_3-\Delta$.

An edge cross an edge yields a square, or 2-cell. The product graph $K_3\times K_3$ consists then of 9 squares glued together. Of these, 6 correspond to configurations in which the robots are on distinct edges. The remaining three squares correspond to configurations in which the robots are in the same edge. But these are each divided into 2 triangles by deleting the diagonal $\Delta$ corresponding to configurations in which both robots occupy the same position. We then make identifications corresponding to the fact that once a robot has travelled from vertex $a$ to $b$ to $c$, it comes back to vertex $a$. Therefore, we arrive at the space demonstrated in Figure \ref{example1} on the left, before the making the identifications, and on the right after the identifications. 

\begin{figure}[ht]
  \centerline{
    \mbox{\includegraphics[height=1.7in]{example1a}}
    \hspace{.8in}
    \mbox{\includegraphics[height=1.7in]{example1}}}
\caption[The space of $\mathcal{C}_2(K_3)$]{The configuration space $\mathcal{C}_2(K_3)$ before identifications on the left and embedded in $\mathbb{R}^3$ after identifications on the right. Dotted lines are in the diagonal.}
\label{example1}
\end{figure}

If instead, we add another restriction by not allowing the two robots to lie on neighbouring edges, that is on two edges who share a vertex, we get the discretized configuration space $\mathcal{D}_2(K_3)$. This space is a subset of the configuration space above, with the space near the diagonal removed. This space is demonstrated in Figure \ref{example2}.

\begin{figure}[ht]
  \centerline{
    \mbox{\includegraphics[height=1.7in]{example2a}}
    \hspace{.8in}
    \mbox{\includegraphics[height=1.7in]{example2}}}
\caption[The space of $\mathcal{D}_2(K_3)$]{The discretized configuration space $\mathcal{D}_2(K_3)$ before identification on the left and smoothly deformed after identification to fit nicely on the right.}
\label{example2}
\end{figure}

Another way to construct this space, which will also end in the same space $\mathcal{D}_2(K_3)$, is to start with the 0-cells and inductively attach the next dimension of cells. In this case, there is only one other dimension, as we have seen, however, it would make sense to check for 2-dimensions since it is the highest dimension a space on two robots can be, since we can have an edge cross an edge. This construction is described as follows:
\\ 0-cells: The 0-cells correspond to having both robots on vertices of $K_3$. Once one of the robots is placed on one of three vertices, there are two vertices remaining in which the second robots can be positioned. Therefore, our space has $(3)(2)=6$ 0-cells. These are obviously  $(A,B)$, $(A,C)$, $(B,C)$, $(B,A)$, $(C,A)$, and $(C,B)$.
\\ 1-cells: The 1-cells correspond to having one robot on a vertex and another on an edge of $K_3$. Once one of the robots is placed on one of three vertices, the other robot only has one available edge to be on. See Figure \ref{example2b}. However, we also add a factor of 2 to account for which robot is placed on a vertex first. In other words, we could have either vertex$\times$edge or edge$\times$vertex. Therefore, we have $(2)(3)(1)=6$ edges. Knowing this, it is easy to see which 0-cells bound each of these 1-cells, and therefore easy to attach the 1-cells to the 0-cells and form the space on the right of Figure \ref{example2}.
\begin{figure}[ht]
\begin{center}\includegraphics[height=1in]{example2b}\end{center}
\caption[A 1-cell of $D_2(K_3)$]{Placing a robot on the filled vertex of $K_3$ leaves the remaining grey areas for the placement of the second robot.}
\label{example2b}
\end{figure}
\\ 2-cells: These cells would correspond to both robots being on an edge. However, once a robot is placed on an edge, the only availability for the second robot is the remaining vertex and not the interior of any edges. Thus, there are no 2-cells and we are finished with the construction of $D_2(K_3)$.


\end{subsection}


\begin{subsection}{Formal Definition of Configuration Spaces}\label{conf}
The configuration space of a graph $\Gamma$ is defined as follows:
\begin{equation*} \mathcal{C}_N(\Gamma):=(\Gamma\times\cdots\times\Gamma)-\Delta. \end{equation*}

It is important to notice that $C_N(\Gamma)$ is not a manifold for a non-trivial graph $\Gamma$. Since $\Gamma$ itself is usually not locally euclidean, then neither are the products of this graph. 

A graph $\Gamma$ has a cellular structure of vertices and edges. The $N$-fold product of $\Gamma$ with itself inherits a cell structure consisting of products of $N$-cells, or $N$-dimensional cubes from $\Gamma$. The diagonal $\Delta$ slices product cells with repeated factors. These partial cells and all other cells with closures intersecting the diagonal could be collapsed onto an essential skeleton of the configuration space. This skeleton is a cell complex of dimension at most $N$ and is formally defined as the discretized configuration space:
\begin{equation*} \mathcal{D}_N(\Gamma):=(\Gamma\times\cdots\times\Gamma)-\overline{\Delta} \end{equation*}
where $\overline{\Delta}$ is the set of all product cells whose closures intersect the diagonal $\Delta$.

In $D_n(\Gamma)$, all $k$-cells are $k$-dimensional cubes. As we saw in \ref{example}, we can construct the discretized space in more than one way. In the remainder of the paper, we will construct these spaces similarly to the second construction of $D_2(K_3)$ starting with the 0-cells and attaching the $k$-cells to the $(k-1)$-cells as defined by the combinatorics of the space. This way of constructing the discretized spaces will work better for more discretized configuration spaces of more complicated graphs.

\end{subsection}

\begin{subsection}{The Premise}\label{motivation}
We saw in the example in Section \ref{example} that $D_2(K_3)$ is homeomorphic to a circle. However, discretized configuration spaces of graphs are not generally manifolds. If $D_3(\Gamma)$ is to be a 3-manifold away from the vertices there are limited options as to what $\Gamma$ can be. We have the following result from \cite{Abrams}.

\begin{proposition}\label{prop}
If $\Gamma$ is a connected simple graph, then $D_3(\Gamma)$ is never a 3-dimensional manifold.
\end{proposition}

	The interiors of cubes are always manifold points. The only points that may fail to be manifold points are those on the faces, edges, and vertices. These points are manifold points if their neighbourhoods are homeomorphic to a 3-dimensional ball.
	Suppose that $D_3(\Gamma)$ is a 3-manifold. Then points in the faces are manifold points and therefore each face is contained in exactly two 3-cells. In other words, if $A$ is a set of two disjoint edges, then each vertex of $\Gamma-A$ has degree exactly 2. We refer to $\Gamma-A$ as the subset graph of $\Gamma$ with $A$ deleted and also all edges connected to vertices in $A$ deleted as well. In particular, this means that $\Gamma-A$ is a disjoint union of cycles. Each cycle must have length at least 3, since no loops or multiple edges are allowed in simple graphs.
	
\begin{lemma} \label{lemma1} For any set of two disjoint edges $A$ in $\Gamma$, if $D_3(\Gamma)$ is a 3-manifold, then $\Gamma-A$ is connected. \end{lemma}
\begin{proof}
For any set of disjoint edges $A$ in $\Gamma$, we know that $\Gamma-A$ is a disjoint union of cycles. Suppose that $\Gamma-A$ is disconnected, that is, it has more than one disjoint cycle. Let $B$ be one of those cycles. We can then choose different choices of $A'$ to be any set of two disjoint edges in $\Gamma-B$ to see that none of the vertices in $\Gamma-B$ are joined to any vertex in $B$. That is, we pick $A'$ to be an edge in $A$ and an edge in $\Gamma-A-B$ or two edges in $\Gamma-A-B$. Since $B$ will already be a cycle in $\Gamma-A'$, $B$ is disjoint from any vertices in $\Gamma-B$. Then $\Gamma$ is a union of disjoint graphs and $D_3(\Gamma)$ is disconnected. We can conclude that $\Gamma-A$ is a connected cycle.
\end{proof}	
	
\begin{lemma} \label{lemma2} For any set of two disjoint edges $A$ in $\Gamma$, if $D_3(\Gamma)$ is a 3-manifold, then $\Gamma-A$ is a cycle of length 3 or 4.  \end{lemma}
\begin{proof}
From Lemma \ref{lemma1}, we know that given a set of two disjoint edges $A$ in $\Gamma$, $\Gamma-A$ is a single cycle of length at least 3. Suppose that $\Gamma-A$ is a cycle of length at least 5 as in the leftmost diagram of Figure \ref{5cycle}. Choosing a different set $A'$ of two known disjoint edges and including the edges in $\Gamma-A$ disjoint from $A'$ results in the middle diagram of Figure \ref{5cycle}, since $\Gamma-A'$ must also be a cycle. Choosing yet another set $A''$ of two known disjoint edges of $\Gamma$ and including the edges known from both $\Gamma-A$ and $\Gamma-A'$ results in the rightmost diagram of Figure \ref{5cycle}.
\begin{figure}[ht]
  \centerline{
    \mbox{\includegraphics[height=1in]{5cycle1}}
    \hspace{.8in}
    \mbox{\includegraphics[height=1in]{5cycle2}}
    \hspace{.8in}
   	\mbox{\includegraphics[height=1in]{5cycle3}}}
\caption[Discovery of $\Gamma$ through the complements of $A$, $A'$, and $A''$]{Discovery of $\Gamma$ through the complements of $A$, $A'$, and $A''$ in $\Gamma$.}
\label{5cycle}
\end{figure}
	
	Choosing yet a fourth set $A^*$ of two known disjoint edges as in Figure \ref{5cycleend} results in a contradiction. $\Gamma-A^*$ is  not a cycle, as shown by the drawn edges which are known from $\Gamma-A$, $\Gamma-A'$, and $\Gamma-A''$. Therefore, $\Gamma-A$ is a cycle of length 3 or 4.
\begin{figure}[ht] 
\begin{center}\includegraphics[height=1.1in]{5cycle4}\end{center}
\caption[$A^*$ and known edges in $\Gamma-A^*$]{$A^*$ and known edges in $\Gamma-A^*$.}
\label{5cycleend}
\end{figure}
\end{proof}


\begin{proof}[\textbf{Proof of Proposition \ref{prop}}]
	Following the results of Lemma \ref{lemma1} and Lemma \ref{lemma2}, it suffices to show that $D_3(\Gamma)$ is not a manifold when for any set of two disjoint edges $A$ in $\Gamma$, $\Gamma-A$ is a cycle of length 3 or 4.

If the length of $\Gamma-A$ is 3, then we have Figure \ref{3cycle}. Choosing other combinations of two edges in Figure \ref{3cycle} results in Figure \ref{3cycles}. Notice that combinatorially, the choices made in this figure are the only choices. It is then easy to see that $\Gamma$ must be $K_7$. 
\begin{figure}[ht] 
\begin{center}\includegraphics[height=1in]{3cycle1}\end{center}
\caption[$\Gamma-A$ and $A$ when $\Gamma-A$ is a 3-cycle]{$\Gamma-A$ and $A$ when $\Gamma-A$ is a 3-cycle.}
\label{3cycle}
\end{figure}
\begin{figure}[ht]
\begin{center}\includegraphics[width=4.2in]{3cycles}\end{center}
\caption[Choices of $A_i$ and the corresponding 3-cycles $\Gamma-A_i$]{Other choices of $A_i$ and the corresponding 3-cycles $\Gamma-A_i$.}
\label{3cycles}
\end{figure}
	
	If the length of $\Gamma-A$ is 4, then we have Figure \ref{4cycle}. Choosing other combinations of two edges in Figure \ref{4cycle} results in Figure \ref{4cycles}. Notice that combinatorially, the choices made in this figure are the only choices. It is then easy to see that $\Gamma$ must be $K_{4,4}$.
\begin{figure}[ht]
\begin{center}\includegraphics[height=1in]{4cycle1}\end{center}
\caption[$\Gamma-A$ and $A$ when $\Gamma-A$ is a 4-cycle]{$\Gamma-A$ and $A$ when $\Gamma-A$ is a 4-cycle.}
\label{4cycle}
\end{figure}
\begin{figure}[ht]
\begin{center}\includegraphics[width=5.7in]{4cycles}\end{center}
\caption[Choices of $A_i$ and the corresponding 3-cycles $\Gamma-A_i$]{Other choices of $A_i$ and the corresponding 3-cycles $\Gamma-A_i$.}
\label{4cycles}
\end{figure}
	
	We have narrowed the list of possible graphs to $K_7$ and $K_{4,4}$. It is straight-forward to check that a neighbourhood of a 1-cell is homeomorphic to a Euclidean 3-ball. Thus, the 1-cells in $D_3(K_7)$ and $D_3(K_{4,4})$ are manifold points as well.

Consider now the vertices of $D_3(K_7)$. If a vertex was locally Euclidean, then its neighbourhood would have a boundary  homeomorphic to a 2-dimensional sphere. This boundary is the link of the vertex. We know that each vertex in $D_3(K_7)$ is incident to 24 3-cells. We can take a neighbourhood of each vertex and look at how its boundary intersects the 24 3-cells around the vertex. Each 3-cell will be intersected in a triangle. The gluing of these 24 triangles is determined by the gluing of the 3-cells and results in the boundary of the neighbourhood of the vertex. In this case, this boundary is homeomorphic to a torus, and not a 2-sphere. It has a cell structure as in Figure \ref{24cusp}. Therefore, $D_3(K_7)$ is not a manifold.
	
\begin{figure}[ht]
\begin{center}\includegraphics[height=1.5in]{24cusp}\end{center}
\caption[Boundary of the neighbourhood a vertex of $D_3(K_7)$]{Cell structure of the boundary of the neighbourhood of a vertex of $D_3(K_7)$.}
\label{24cusp}
\end{figure}	

When considering the vertices of $D_3(K_{4,4})$, there are two types of vertices as described in \ref{K44blocs}. We can check to see that neighbourhoods of type $B$ vertices are locally Euclidean, however neighbourhoods of type $A$ vertices have torus boundaries with the same cellular structure as the boundaries of neighbourhoods of vertices in $D_3(K_7)$. Therefore, $D_3(K_{4,4})$ is not a manifold.
\end{proof}

The proof of Proposition \ref{prop} shows that $K_7$ and $K_{4,4}$ are the only simple graphs whose discretized configuration spaces on three robots are manifolds away from the vertices. We devote the rest of this paper to the study of these two spaces, $D_3(K_7)$ and $D_3(K_{4,4})$.
\end{subsection}

\end{section}


\newpage
\begin{section}{Discretized Space of $K_7$}\label{K7}
	\begin{subsection}{2-dimensional forerunner: $D_2(K_5)$}
	Consider the complete graph $K_5$. The discretized configuration space of two points on this graph is a 2-dimensional complex. We can use simple counting arguments to determine the structure of this complex. It will become clear following the construction that this complex is a 2-manifold. $K_5$ has 5 vertices and 10 edges. 
	\\ \emph{0-cells:} 0-cells correspond to a vertex cross a vertex. This is when the two robots are at different vertices. Therefore, we have $(5)(5-1)=20$ 0-cells.
	\\ \emph{1-cells:} 1-cells correspond to an edge cross a vertex. This is when one robot is on a vertex and the other robot is on an edge disjoint from the vertex of the first robot. Placing first a robot on one of five vertices, we see that there are six possible edges for the other robot. We include also a factor of 2 for the two distinct points. This is since we can have vertes$\times$edge or edge$\times$vertex. Therefore, there are $(2)(5)(6)=60$ 1-cells.
		\\ \emph{2-cells:} 2-cells correspond to an edge cross an edge. This occurs when the points are at disjoint edges. Once the first point is placed on any of the ten edges, there are three possible edges in which to place the second robot. Therefore, we have $(10)(3)=30$ 2-cells.
	
	Notice that each 1-cell is incident to exactly two 2-cells connected along the 1-cell. We can see this by considering a 1-cell in $D_2(K_5)$. This corresponds to an edge cross a vertex in $K_5$. This 1-cell is a boundary of the 2-cells corresponding to the same edge on $K_5$ together with a second edge which is joined to the specific vertex. We can then see that once the first edge for one of the robots is removed, the second robot currently on a vertex has exactly two options of edges to go on. Refer to Figure \ref{22-cells}. Similarly, each 0-cell is incident to six 1-cells, of which two adjacent 1-cells form a corner of a 2-cell. Refer to Figure \ref{K5vx}. $D_2(K_5)$ is a connected, orientable manifold.

\begin{figure}[ht]
\begin{center}\includegraphics[height=1.2in]{22-cells}\end{center}
\caption[Connected 2-cells in $D_2(K_5)$]{A 1-cell in $D_2(K_5)$ is shared by two 2-cells corresponding to the choice of grey edge.}
\label{22-cells}
\end{figure}

\begin{figure}[ht]
  \centerline{
    \mbox{\includegraphics[height=1.7in]{K5vx}}
    \hspace{.8in}
    \mbox{\includegraphics[height=1.7in]{61-cells}}}
\caption[Neighbourhood of a vertex in $D_2(K_5)$]{The neighbourhood of a vertex in $D_2(K_5)$.}
\label{K5vx}
\end{figure}
	
	The classification theorem for surfaces tells us that we can determine our space using its Euler characteristic, where $g$ is the genus of the surface. 
	\begin{equation*} 2-2g = \chi = (\text{no. of vertices}) -(\text{no. of edges}) +(\text{no. of faces}) = 20-60+30=-10 \end{equation*}
	Therefore, $D_2(K_5)$ is a closed orientable surface of genus six. It is made from 10 triangular tubes glued on their boundary triangles. Figure \ref{K5space} shows an embedding of $D_2(K_5)$ in $\mathbb{R}^3$.
	
\begin{figure}[ht]
\begin{center} \includegraphics[width=5.5in]{K5space} \end{center}
\caption[Space of $D_2(K_5)$]{The views are different angles of an embedding of the cell complex of $D_2(K_5)$ as a polyhedron in $\mathbb{R}^3$. On the bottom is the ``x-ray" version of $D_2(K_5)$.}
\label{K5space}
\end{figure}	
	
	In $D_2(K_5)$, 2-cells fit six around a vertex. Each of these 2-cells can be given the geometry of a regular quadrilateral in hyperbolic space. Each interior angle is equal to $\pi/3$. By Theorem \ref{area}, the area of $D_2(K_5)$, is $(30)(2\pi-4\pi/3)=20\pi$, roughly 62.832.
	%%%% If we start in the center of some 2-cell in $D_2(K_{5})$ and leave along one of the edges into an adjacent 2-cell and then leave from there through the opposite edge and so one, we come back to the original after going through exactly three 2-cells.
	\end{subsection}
	
	\begin{subsection}{Building Blocks}
	We now consider the space $D_3(K_7)$. In Section \ref{motivation} we saw that the discretized configuration space of $K_7$ is a 3-dimensional complex homeomorphic to a 3-manifold away from the vertices. We can use simple counting arguments to determine the structure of this complex. $K_7$ has 7 vertices and 21 edges. 
	\\ \emph{0-cells:} 0-cells correspond to a vertex cross a vertex cross a vertex. Therefore, we have $(7)(6)(5)=210$ 0-cells.
	\\ \emph{1-cells:} 1-cells correspond to an edge cross a vertex cross a vertex. This is when one robot is on an edge but the other two robots are at vertices disjoint from the boundaries of the edge where the first robot is. Placing first the two robots on vertices in $K_7$ we see that the remaining 5 vertices form a subset $K_5$ where the third robot is allowed to be. Therefore, the number of 1-cells is $(3)(7)(6)(10)=1260$. We include a factor of 3 for the three distinct robots. This factor of 3 makes up for vertex$\times$vertex$\times$edge, vertex$\times$edge$\times$vertex, or edge$\times$vertex$\times$vertex.
	\\ \emph{2-cells:} 2-cells correspond to an edge cross an edge cross a vertex. Once a robot is placed on any of the 7 vertices, and a second robot is placed on any of the edges in the remaining $K_6$, there is a remaining $K_4$ disjoint from the 3 vertices corresponding to the first robot and the second robot. Therefore, we have $(3)(7)(15)(6)=1890$ 2-cells. Again, we include a factor of 3 for vertex$\times$edge$\times$edge, edge$\times$vertex$\times$edge, or edge$\times$edge$\times$vertex.
	\\ \emph{3-cells:} 3-cells correspond to an edge cross an edge cross an edge. Once a robot is placed on any of the 21 edges, there remains a $K_5$ of possibilities for the second and third robot. Therefore, we have $(21)(10)(3)=630$ 3-cells.

	Notice that each 2-cell borders exactly two 3-cells in our complex. This shows that small neighboorhoods of the faces are homeomorphic to Euclidean balls, which is consistent with the definition of manifold on the faces. Also notice that each 1-cell borders six 2-cells. Locally, an edge of $D_3(K_7)$ looks like a vertex in $D_2(K_5)$ cross an interval. Refer to Figure \ref{K7e}.
	
\begin{figure}[ht]
\begin{center}\includegraphics[height=2.2in]{K7e}\end{center}
\caption[An edge of $D_3(K_7)$]{An edge of $D_3(K_7)$.}
\label{K7e}
\end{figure}

From Proposition \ref{prop}, we know that the vertices of $D_3(K_7)$ are not manifold points. However, $D_3(K_7)$ with its vertices deleted is a 3-manifold. We denote this manifold $M_1$.
	
\end{subsection}

\begin{subsection}{Geometric Properties of $M_1$} \label{geoK7}
	We want to build $M_1$ out of regular ideal cubes in hyperbolic space. Let $C$ be the ideal cube in $\mathbb{H}^3$ with vertices forming a Euclidean cube in the boundary sphere of $\mathbb{H}^3$ as the Poincar\'{e} ball model. Through this construction, we notice that the dihedral angles of $C$ coincide with the dihedral angles of the circles in the boundary sphere of $\mathbb{H}^3$. Thus we have dihedral angles of $\pi/3$. We consider our cube $C$ in the Upper Half Space model of Hyperbolic Space where the point at infinity is vertex 0 on the cube on Figure \ref{cube}. If vertices 1 and 2 are two points on the plane at infinity, the line connecting the two is at an angle of $\pi/3$ from the lines connecting vertices 1 and 3 and vertices 2 and 3. We can reflect to choose the line with vertices 2 and 3, which then determines vertex 3. 

\begin{figure}[ht]
\begin{center}\includegraphics[height=2in]{cube}\end{center}
\caption[A labelled cube]{A cube with labelled vertices.}
\label{cube}
\end{figure}	

	Vertices 4, 5, and 7 lie on the same plane as vertex 1. Vertices 5, 6, 7 must lie on the same plane as vertex 3, and vertex 4, 6, and 7 lie on the same plane as vertex 2. This means that vertices 4 and 5 are at the same distance from 1, vertices 5 and 6 are at the same distance from 3, and vertices 4 and 6 are at the same distance from 2. Since vertex 7 must on all three planes corresponding to vertices 1, 2, and 3, this means that three circles at infinity, each containing exactly one of vertices 1, 2, and 3 must meet at a point. But also, every pair of these circles meets at exactly two points. For instance, the circle containing vertex 1 and the circle containing vertex 2 must meet at exactly two points, those corresponding to vertex 4 and to vertex 7. In this way each vertex is determined. We have a hyperbolic regular ideal cube which can be modelled in the Upper Half Space model as in Figure \ref{idealcube}.

\begin{figure}[ht]
  \centerline{
    \mbox{\includegraphics[height=2.2in]{K7s}}
    \hspace{.8in}
    \mbox{\includegraphics[height=2.2in]{K73}}}
\caption[A regular ideal hyperbolic cube]{The plane at infinity of the Upper Half Space model of the hyperbolic regular ideal cube on the left, and the UHS model of the cube on the right.}
\label{idealcube}
\end{figure}

	Notice that every symmetry of $C$ is realized by a hyperbolic isometry.  Therefore, our cube $C$ is regular and every regular ideal cube in $\mathbb{H}^3$ is isometric to $C$. We give $M_1$ a hyperbolic structure.
	
	Now that we have determined the shape of the regular ideal cube in hyperbolic space, we know that each dihedral angle is $\pi/3$. Therefore, we can triangulate our cube into five regular ideal tetrahedra, whose volume is finite and well-known. We divide our cube as in Figure \ref{cube5}.
	
\begin{figure}[ht]
\begin{center}\includegraphics[height=2.2in]{cube5}\end{center}
\caption[A triangulation of a cube into 5 tetrahedra]{A triangulation of a cube into 5 tetrahedra. Since our cube is a regular ideal hyperbolic cube, all five tetrahedra are regular ideal hyperbolic tetrahedra.}
\label{cube5}
\end{figure}		
	
	Recall from Section \ref{hyperbolic} that there is at most one isometry taking 4 points at infinity to 4 points at infinity. Therefore, there is only one way to glue the faces of our cubes in $M_1$. This determines completeness of the manifold as defined in Chapter 3 of \cite{Thurston}. The gluing is determined. We have the following Theorem.
	
	\begin{thm}\label{M1}
	$M_1$ is a complete hyperbolic 3-manifold with 210 cusps and volume $(630)(5)=3150$ times the volume of a regular ideal tetrahedron, or roughly 3197.067.
	\end{thm}
	\end{subsection}
	
	\begin{subsection}{Other Discoveries}\label{endK7}

\begin{figure}[ht]
\begin{center}\includegraphics[height=1.4in]{fig8}\end{center}
\caption[The figure-8 knot]{The figure-8 knot.}
\label{fig8}
\end{figure}

	Consider the space $K$ of the figure-8 knot complement, the space obtained from the 3-sphere by deleting the figure-8 knot embedded in $S^3$ (see Figure \ref{fig8}). This space is studied extensively in Chapter 1 of \cite{Thurston}. $K$ is a complete finite-volume hyperbolic 3-manifold with 1 cusp and a structure with two regular ideal tetrahedra. It is conceivable that our manifold $M_1$ is a 1575 sheeted cover of $K$, where each point in $K$ is 1575 identified points on $M_1$. If this were the case, 210 cusps in $M_1$ cover the 1 cusp in $K$. However, although our cubes can be triangulated into regular ideal tetrahedra to compute the exact volume of our manifold, our entire space cannot be consistently triangulated into tetrahedra in that way. This is because when we look at one of our cubes, the way we divide it into 5 tetrahedra determines the way the adjacent cubes are divided into tetrahedra so that the faces of the tetrahedra match.
	
	There are exactly two ways in which to divide a cube into 5 tetrahedra. If we start with a cube divided in a certain way, the adjacent cubes must be divided in the opposite way in order to fit in the faces nicely. Now consider some cube in $D_3(K_7)$. This cube is defined by choosing three edges in the graph of $K_7$, call it cube 1. We can pick face $a$ of this cube to find the adjacent cube 2 sharing the face $a$. The opposite face in cube 2, face $b$ then defines cube 3. On cube 3, the face opposite face $b$ is face $c$ which defines the next cube. However, this next cube is again cube 1. These moves correspond to one robot moving around a $K_3$ subset of $K_7$ while the other two robots remain stagnant and determines the stacking of cubes. Refer to Figure \ref{3cubes}.

	Therefore, if cube 1 has the first triangulation into 5 tetrahedra, then cube 2 has the second, and then cube 3 has again the first triangulation. But this would make cube 1 have the second triangulation, and this is a contradiction. Therefore, the triangulation into 5 tetrahedra is inconsistent with the gluing pattern. In fact, an argument due to Thurston shows that $M_1$ does not cover $K$. We will omit the proof in this paper. Refer to \cite{MathOverflow}.

\begin{figure}[ht]
\begin{center}\includegraphics[width=5in]{3cubes}\end{center}
\caption[The stacking of cubes in $M_1$.]{The cycle of one robot in a $K_3$ subset of $K_7$ determines the stacking of cubes in $M_1$.}
\label{3cubes}
\end{figure}
	
	We then considered another question. Are $K$ and $M_1$ commensurable? It is conceivable that a two-sheeted cover of $M_1$ could be consistently triangulated into regular ideal tetrahedra. In fact, in \cite{MathOverflow}, there is an argument that the smallest cover of $M_1$ which is also a cover of $K$ would have to be at least an 8-sheeted cover. Finding a common cover of $M_1$ and $K$ is not necessarily to show the two spaces are commensurable.  We can construct a two-sheeted cover of $M_1$ which can be triangulated into 6300 regular ideal tetrahedra. We notice that there is a tiling of $\mathbb{H}_3$ by regular ideal tetrahedra whose symmetry group contains an index 2 subgroup with quotient $K$ and an index 6300 subgroup with quotient the two-sheeted cover of $M_1$. Therefore, $M_1$ and $K$ are commensurable.
	\end{subsection}
\end{section}



\newpage
\begin{section}{Discretized Space of $K_{4,4}$}\label{K44}
	\begin{subsection}{2-dimensional forerunner: $D_2(K_{3,3})$}
	Consider the complete graph $K_{3,3}$. The discretized configuration space of two points on this graph is a 2-dimensional complex. As in the case of $D_2(K_5)$, we can use simple counting arguments to determine the structure of this complex. It will become clear following the construction that this complex is also a 2-manifold. Our cell complex has $(6)(5)=30$ 0-cells, $(2)(6)(6)=72$ 1-cells, and $(9)(4)=36$ 2-cells.

\begin{figure}[ht]
  \centerline{
    \mbox{\includegraphics[height=.5in]{K33vxA}}
    \hspace{1in}
    \mbox{\includegraphics[height=.5in]{K33vxB}}}
\caption[Vertex types of $D_2(K_{3,3})$]{A vertex of type $A$ on the left and a vertex of type $B$ on the right. These are both based on Figure \ref{bipartitegraphs}. In particular, vertices on the top are not joined to other vertices on the top through edges, and similarly for vertices on the bottom with vertices on the bottom.}
\label{K33vx}
\end{figure}	

	Notice that we have two distinct types of vertices, which we will denote type $A$ and type $B$ as in Figure \ref{K33vx}. A vertex of type $A$ is incident to six edges and, thus six 2-cells, while a vertex of type $B$ is incident to four edges, and thus four 2-cells. Also, each edge is incident to exactly two 2-cells. The Euler characteristic tells us that $D_2(K_{3,3})$ is a closed orientable surface of genus four.  Figure \ref{K33space} shows an embedding of $D_2(K_{3,3})$ in $\mathbb{R}^3$.

\begin{figure}[ht]
\begin{center} \includegraphics[width=6in]{K33space} \end{center}
\caption[Space of $D_2(K_{3,3})$]{The views are different angles of an embedding of the cell complex of $D_2(K_{3,3})$ as a polyhedra in $\mathbb{R}^3$. On the bottom is the "x-ray" version of $D_2(K_{3,3})$.}
\label{K33space}
\end{figure}	
	
	
	Consider any 2-cell, or ``square" in $D_2(K_{3,3})$. We can pick an edge of the square and move to the next square. We then pick the edge of this second square that is opposite from the edge we just came from and move through that edge on to the next square. If we continue to do this, we return to the starting square after visiting three others, so four squares in total, regardless of which square we pick or which edge on that square we pick. These moves correspond to having one robot moving around a 4-cycle subset of $K_{3,3}$ while the other robot remains in place. We can redraw the edges of $D_2(K_{3,3})$ consistently by drawing ``straight" lines between vertices of type A and making these the edges of new regular quadrilaterals. Then, six squares fit around a vertex. Also, a quarter of the new regular quadrilateral occupies half the area of an old quadrilateral. It might seem strange to change the structure of the complex in the same space, however, this serves as a foreshadow to a construction of the space of $D_3(K_{4,4})$. Exactly 18 regular quadrilaterals tile the discretized space of $K_{3,3}$. Each interior angle is equal to $\pi/3$, since they fit six around a vertex. Thus by Theorem \ref{area}, the area of $D_2(K_{3,3})$, is $(18)(2\pi-4\pi/3)=12\pi$, roughly 37.699. 
	\end{subsection}
	
	\begin{subsection}{Building Blocks} \label{K44blocs}
	We now consider the space $D_3(K_{4,4})$. In Section \ref{motivation} we saw that the discretized configuration space of $K_{4,4}$ is a 3-dimensional complex homeomorphic to a 3-manifold away from the vertices. We can use simple counting arguments to determine the structure of this complex. $K_{4,4}$ has 8 vertices and 16 edges. 
	\\ \emph{0-cells:} 0-cells correspond to a vertex cross a vertex cross a vertex. Therefore, we have a total of $(8)(7)(6)=336$ 0-cells. However, we differentiate between two different types of vertices. Type $A$ vertices and type $B$ vertices are as in Figure \ref{K44vx}.
	
\begin{figure}[ht]
  \centerline{
    \mbox{\includegraphics[height=.5in]{K44vxA}}
    \hspace{1in}
    \mbox{\includegraphics[height=.5in]{K44vxB}}}
\caption[Vertex types of $D_3(K_{4,4})$]{A vertex of type $A$ on the left and a vertex of type $B$ on the right. These are both based on Figure \ref{bipartitegraphs}. In particular, vertices on the top are not joined to other vertices on the top through edges, and similarly for vertices on the bottom with vertices on the bottom.}
\label{K44vx}
\end{figure}		
	
	We have $(8)(3)(2)=48$ type $A$ vertices and $(3)(8)(4)(3)=288$ type $B$ vertices. Recall from Section \ref{motivation} that the neighbourhoods of $B$ vertices are balls but neighbourhoods of $A$ vertices have torus boundaries.
	\\ \emph{1-cells:} 1-cells correspond to an edge cross a vertex cross a vertex. Placing the first robot on an edge, we see that the remaining 6 vertices form a subset $K_{3,3}$ where the second and third robots are allowed to be on. We include a factor of 3 for vertex$\times$vertex$\times$edge, vertex$\times$edge$\times$vertex, or edge$\times$vertex$\times$vertex. Therefore, the number of 1-cells is $(3)(16)(6)(5)=1440$. However, we differentiate between two different types of edges. Type $\alpha$ edges connect between an $A$ and a $B$ vertex. Type $\beta$ edges connect between two $B$ vertices. These are as in Figure \ref{K44e}.
	
\begin{figure}[ht]
  \centerline{
    \mbox{\includegraphics[height=.5in]{K44ea}}
    \hspace{1in}
    \mbox{\includegraphics[height=.5in]{K44eb}}}
\caption[Edge types of $D_3(K_{4,4})$]{An edge of type $\alpha$ on the left and an edge of type $\beta$ on the right.}
\label{K44e}
\end{figure}		
	
	We have $(3)(16)(6)(2)=576$ type $\alpha$ edges and $(3)(16)(3)(3)=864$ type $\beta$ edges. There is annother important distinction between these edges. Type $\alpha$ edges have 6 cubes around them, while type $\beta$ edges have only 4 cubes around them.
	\\ \emph{2-cells:} 2-cells correspond to an edge cross an edge cross a vertex. Placing the first robot on an edge, we see that the remaining 6 vertices form a subset $K_{3,3}$ where the second and third robots are allowed to be on, one on an edge and the other on a vertex. Again we include a factor of 3 for vertex$\times$edge$\times$edge, edge$\times$vertex$\times$edge, or edge$\times$edge$\times$vertex. Therefore, we have $(3)(16)(9)(4)=1728$ 2-cells. Notice that all 2-cells are combinatorially the same. They have one type $A$ vertex and three type $B$ vertices.
	\\ \emph{3-cells:} 3-cells correspond to an edge cross an edge cross an edge. Once a robot is placed on any of the 16 edges, there remains a $K_{3,3}$ of possibilities for the second and third robot. Therefore, we have $(16)(9)(4)=576$ 3-cells. Notice that all 3-cells are combinatorially the same. They have two type $A$ vertices and six type $B$ vertices.
		
	Similar to the case of $D_3(K_7)$, we can delete the vertices of type $A$ from $D_3(K_{4,4})$ which are not manifold points. We then have a 3-manifold which we will denote $M_2$.


\end{subsection}

\begin{subsection}{Geometric Properties of $M_2$} \label{geoK44}
	Since each cube has two deleted vertices, we want to build $M_2$ out of nice geometric semi-ideal cubes. We would like to show that there exists a semi-ideal cube in $\mathbb{H}^3$ with two opposite ideal vertices, 6 non-ideal vertices, and dihedral angles suitable for building $M_2$ Let $D$ be the cube with two opposite type $A$ vertices and six type $B$ vertices. Type $A$ vertices are ideal while type $B$ vertices are not. We consider our cube $D$ in the Upper Half Space model of Hyperbolic Space where the point at infinity is one of the vertices of type $A$ and a point on the plane at infinity is the other type $A$ vertex of the cube. $D$ has six type $\alpha$ edges with six cubes fitting around each and six type $\beta$ edges with cubes cubes fitting around each. The geometry of $D$ in Hyperbolic Space is determined by the angles of $\pi/3$ for type $\alpha$ edges and $\pi/2$ for type $\beta$ edges. We build our semi-ideal cube as in Figure \ref{sic}.
	
\begin{figure}[ht]
  \centerline{
    \mbox{\includegraphics[height=2.2in]{sic1}}
    \hspace{.8in}
    \mbox{\includegraphics[height=2.2in]{sicfin}}}
\caption[Hyperbolic semi-ideal cube]{The plane at infinity of the Upper Half Space model of the hyperbolic semi-ideal cube on the left, and the UHS model of the cube on the right.}
\label{sic}
\end{figure}
	
	Notice that the dihedral angles of the edges of type $\alpha$ (those connecting between a type $A$ and a type $B$ vertex) are $\pi/3$ on the model. The $\beta$ edges are intersection of half spheres with vertical planes that go through the center of the spheres. Then, the dihedral angles of the $\beta$ edges are $\pi/2$ on the model. This is good because it means that we can make $M_2$ out of cubes in $\mathbb{H}^3$, giving it a hyperbolic structure. We also know $M_2$ is complete from the definition in Chapter 3 of \ref{Thurston}. Therefore, we have the first part of the following Theorem.
	
	\begin{thm}\label{M2}
	$M_2$ is a complete hyperbolic 3-manifold with 48 cusps and volume 864 times the volume of a regular ideal tetrahedron, or roughly 876.910. 
	\end{thm}
	
	To determine the volume, we can triangulate our cube into six semi-ideal tetrahedra by cutting along the geodesic connecting the two type $A$ vertices. In this way, all six tetrahedra are congruent, with two ideal vertices, and two non ideal vertices. The tetrahedron has angles $\pi/6,\pi/3,\pi/3,\pi/6,\pi/2,\pi/2$ as in Figure \ref{cube6}.
	
\begin{figure}[ht]
\begin{center}\includegraphics[height=2.2in]{cube6}\end{center}
\caption[A triangulation of a cube into 6 tetrahedra]{A triangulation of a cube into 6 tetrahedra. The open vertices represent ideal vertices in our semi-ideal cube.}
\label{cube6}
\end{figure}	
	
	Using the formula described in \cite{Volume}, we calculated the volume of this tetrahedron to be a fourth of the volume of a regular ideal tetrahedron. In fact, cutting an edge from the midpoint of one edge of the regular ideal tetrahedron to the midpoint of the opposite edge and declaring those two points as the non-ideal vertices divides the regular ideal tetrahedron into four tetrahedra of the type we are looking for. Six of these semi-ideal tetrahedra make up our semi-ideal cube by rotating around the geodesic. We can imagine our cube made out of a fourth of each of six regular ideal tetrahedra as in Figure \ref{tet4}. 
	
\begin{figure}[ht]
  \centerline{
    \mbox{\includegraphics[height=2.2in]{tet}}
    \hspace{.8in}
    \mbox{\includegraphics[height=2.2in]{tet4}}}
\caption[A triangulation of a tetrahedron into four tetrahedra]{Before and after a triangulation of a regular ideal tetrahedron into four semi-ideal tetrahedra. The dotted lines are new edges in the triangulation of the tetrahedron. The open vertices represent ideal vertices.}
\label{tet4}
\end{figure}
	
	There is only one way to glue the faces of our cubes in $M_2$. The gluing is determined, again because there is at most one hyperbolic isometry taking 4 points to 4 points. Then, $M_2$ is a complete finite-volume hyperbolic 3-manifold with 48 cusps. Its volume is $(576)(3/2)=864$ times the volume of a regular ideal tetrahedron.
	\end{subsection}
	
	\begin{subsection}{Other Discoveries} \label{endK44}
	In an effort to get a better understanding of $M_2$, we study a related manifold, which we will call $UM_2$. $UM_2$ is the manifold we get by unlabelling the three robots. $UM_2$ is obtained as a quotient space of $M_2$ which has $1/6$ the number of cubes; that is, it is constructed from 96 semi-ideal cubes. This is because there are 6 ways to label the three robots. This also means that $UM_2$ has the volume of $(96)(3/2)=144$ regular ideal tetrahedra.
	
	Consider the non-ideal vertices of $UM_2$. These are the vertices which we referred to as type $B$ in $D_3(K_{4,4})$ (see Figure \ref{K44vx}). They can be divided into two types, those with two robots on the top row (and only one in the bottom row), and those with two robots on the bottom row (and only one in the top row).
	In $UM_2$ after unlabelling the robots, there are $\binom{4}{2}$ ways to choose two top vertices on $K_{4,4}$ and 4 ways to choose a vertex on the bottom row. Thus, we have have 24 non-ideal vertices of the two-on-top type in $UM_2$. For each of these there are 6 choices of edges to connect them to a two-on-bottom non-ideal vertex which makes $(24)(6)=144$ edges. These 144 edges are the edges that cut through a regular ideal tetrahedron separating it into four tetrahedra, each of which makes up one sixth of the semi-ideal cube (refer to \ref{K44blocs}). Notice that these non-ideal edges define the ideal tetrahedra, as in Figure \ref{4cubestet}, in a way that different tetrahedra do not intersect.

\begin{figure}[ht]
  \centerline{
    \mbox{\includegraphics[height=2.2in]{4cubestet}}
    \hspace{.8in}
    \mbox{\includegraphics[height=2.2in]{6cubestet}}}
\caption[Regular ideal tetrahedra in cubes]{A regular ideal tetrahedron defined by a non-ideal edge. The open vertices represent ideal vertices. On the left is a regular ideal tetrahedron defined on 4 cubes. On the right is two adjacent regular ideal tetrahedra in 6 cubes.}
\label{4cubestet}
\end{figure}

	 There is a 1-to-1 correspondence between these edges and the tetrahedra. In particular, this implies that $UM_2$ can be triangulated with tetrahedra, 144 of them. Furthermore, since $UM_2$ is a quotient space of $M_2$, the triangulation of $UM_2$ by regular ideal tetrahedra lifts to a cover of $M_2$ by regular ideal tetrahedra. A chunk made out of twelve cubes of $M_2$ and also of $UM_2$ looks like the image in Figure \ref{chunkUM2}. However, in $UM_2$ some of the open vertices are identified and this figure may be misleading.
	 
\begin{figure}[ht]
\begin{center}\includegraphics[height=2.4in]{chunkUM2}\end{center}
\caption[A chunk of $M_2$ or $UM_2$]{A chunk of $M_2$ or $UM_2$ from twelve semi-ideal cubes. The open vertices represent ideal vertices. The long edge between ideal vertices that runs through the center is a part of six regular ideal tetrahedra, each of which contains that edge together with two adjacent ideal vertices from the middle and all the points in between.}
\label{chunkUM2}
\end{figure}
		
	The fact that $M_2$ and $UM_2$ can be triangulated by regular ideal tetrahedra shows that $M_2$ and $UM_2$ are commensurable with the figure-8 knot complement $K$ described in Section \ref{endK7}. This is because the symmetry group of the tiling of $\mathbb{H}_3$ by regular ideal tetrahedra contains finite index subgroups with quotients $M_2$, $UM_2$, and $K$.	
	
	The group $\mathbb{Z}_8$ acts on $M_2$ and $UM_2$. The action is given by $\frac{1}{8}$ rotation of the representation of $K_{4,4}$ given on Figure \ref{8K44}. We can check that this action is free by checking that it has no fixed points. It is straight forward to see that given a 3-cell of the discretized space, that is three disjoint edges in $K_{4,4}$, only the identity rotation will give the same 3-cell. This shows that the interiors of the cube are not fixed by the action. In the same way, we can check that 0-cells of the discretized space are not fixed. In this case, each of these is a choice of 3 vertices of $K_{4,4}$. Since 3 and 8 are relatively prime, only the identity rotation will give the same 0-cell. This shows that the 0-cells of the discretized space are not fixed by the action. The only thing left to show is that the 1-cells and the 2-cells of the discretized space are not fixed. The 1-cells would be fixed only if the boundary 0-cells are interchanged by the rotation. Once again, it is easy to see that this does not happen. Rotation does not fix 2-cells either because rotation by eighths does not fix 3 vertices on $K_{4,4}$. A 2-cell is defined by two edges in $K_{4,4}$ (each of which takes 2 vertices) and one extra vertex. Thus, the three left over vertices are not fixed by rotation since 3 and 8 are relatively prime. We conclude that the action given by $\frac{1}{8}$ rotation is a free action.
	
	Since the action by rotation on the graph of $K_{4,4}$ is free, we can mod out $UM_2$ by the group $\mathbb{Z}_8$. We call the quotient $M_2^*$. $M_2^*$ is made from 12 3-cells, 36 2-cells, 30 1-cells, and 7 0-cells. One of the 0-cells is the cusp, while each of the remaining 6 corresponds to 8 0-cells in $UM_2$. This smaller space can also be triangulated by regular ideal tetrahedra. We now have 18 non-ideal edges which are in one-to-one correspondence with the tetrahedra in the triangulation.
	
	An interesting question to consider is whether $M_2^*$ is a covering of the figure-8 knot complement $K$. If this were the case, then $M_2^*$ would be a 9-fold cover with one cusp. We first introduce the concept of cusp shape. The torus-shaped boundary of a neighborhood of a cusp in $M_2^*$ inherits a Euclidean structure from the hyperbolic structure of our manifold $M_2^*$. Up to scaling, Euclidean structure on the torus boundary is known as the \emph{cusp shape}. This cusp shape is described by a single complex number. A Euclidean torus tiles the complex plane. We can describe the shape of this torus by two vectors. Letting one of those vectors be the vector \textbf{1}, the complex number describing the second vector is then the cusp shape.
		
	We know that $K$ has a cusp shape of $2\sqrt{3}$. If $M_2^*$ is a covering of $K$, then the cusp shape of $M_2^*$ would have to be an index 9 subgroup of $2\sqrt{3}$. $M_2^*$ has the cusp shape in Figure \ref{24cusp}, that is $\frac{1}{2}+\frac{\sqrt{3}}{2}i$. Unfortunately, $\frac{1}{2}+\frac{\sqrt{3}}{2}i$ is not an index 9 subgroup of $2\sqrt{3}$.
	
	The fact that $M_2^*$ is not a covering of $K$ does not imply that $UM_2$ or $M_2$ are not coverings of $K$. It only shows that if they were coverings of $K$, then they would have to be direct coverings that do not go through the intermediate step $M_2^*$.
	\end{subsection}
\end{section}


\newpage
\begin{section}{The Relationship}\label{relationship}
%%[HERE ADD HOW THE TWO ARE COMMENSURABLE, MORE STUFF ON THE COLORED GRAPHS, FURTHER STUDY]
	A link is a collection of circles embedded in $S^3$, much like knots but allowing multiple components. We would like to note that neither $M_1$ nor $M_2$ are link complements. The cusps of $M_1$ and $M_2$ have torus links. Therefore, we can fill them in with solid tori. However, conning off the cusps results in $D_3(K_7)$ and $D_3(K_{4,4})$ respectively. These two spaces have nontrivial fundamental group, but $S^3$ does have trivial fundamental group. Conning off cusps kills the fundamental group generators on the cusps, so if conning off does not trivialize the fundamental groups, neither can filling the cusps with solid tori.

	We have seen in Sections \ref{endK7} and \ref{endK44} that both $M_1$ and $M_2$ are commensurable with the figure-8 knot complement $K$. In particular, this means that $M_1$ and $M_2$ are commensurable with each other. An interesting question we can ask is whether there is a finite simple graph $G$ whose discretized configuration space, away from the vertices, is related to both $M_1$ and $M_2$ in some special way. Also, we could find a large manifold that covers both $M_1$ and $M_2$ and directly show how the two of these are commensurable.
	
\end{section}


\newpage
\begin{thebibliography}{1}
\bibitem{Abrams} A Abrams, 2000: \textit{Configuration Spaces and Braid Groups of Graphs}, PhD thesis, UC Berkeley. 

\bibitem{Abrams Ghrist} A Abrams and R Ghrist, 2002: Finding Topology in a Factory: Configuration Spaces, \textit{American Mathematics Monthly}, \textbf{109}, 140-150.

\bibitem{Volume} D Derevnin and A Mednykh, 2005: A formula for the volume of a hyperbolic tetrahedron, \textit{Russian Math. Surveys}, \textbf{60}, 2:346–348.

\bibitem{Dummit} D. Dummit and R. Foote, 2004: \textit{Abstract Algebra}, 3rd ed. John Wiley and Sons.

\bibitem{Hatcher} A. Hatcher, 2001: \textit{Algebraic Topology}, Cambridge University Press.

\bibitem{Thurston} W. Thurston, 1997: \textit{Three-Dimensional Geometry and Topology}. Vol. 1. Princeton University Press.

\bibitem{MathOverflow} \textit{Detecting a cover of the figure-8 knot complement},  2011, available at 
\small{\texttt{http://mathoverflow.net/questions/52291/detecting-a-cover-of-the-figure-8-}}
\small{\texttt{knot-complement}}.

\end{thebibliography}

\end{document}