\pdfoutput=1 %arXiv addition for pdflatex, permits no file extensions.
%Must go on first line!
\documentclass[]{article}
\usepackage{url,float}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{latexsym}
%\input{/home/orourke/tex/mac}
%\withcomplaints
\newcommand{\hide}[1]{}
\newcommand{\ABox}{
\raisebox{3pt}{\framebox[6pt]{\rule{6pt}{0pt}}}
}
\newenvironment{proof}{{\bf Proof:}}{\hfill\ABox}
%\newenvironment{pf}{{\bf Proof:}}{\hfill\ABox}
\newtheorem{theorem}{{\bf Theorem}}
\newtheorem{corollary}{Corollary}
\newtheorem{lemma}{Lemma}
%Zip\newtheorem{lemma}[theorem]{Lemma}
%\newtheorem{conjecture}[theorem]{Conjecture}
%\newtheorem{definition}[theorem]{Definition}
%For labels of items.
\newcommand{\lemlab}[1]{\label{lemma:#1}}
\newcommand{\thmlab}[1]{\label{thm:#1}}
%\newcommand{\eqlab}[1]{\label{eq:#1}}
\newcommand{\corlab}[1]{\label{cor:#1}}
\newcommand{\deflab}[1]{\label{def:#1}}
\newcommand{\tablab}[1]{\label{tab:#1}}
\newcommand{\figlab}[1]{\label{fig:#1}}
\newcommand{\seclab}[1]{\label{sec:#1}}
%\newcommand{\chaplab}[1]{\label{chap:#1}}
\newcommand{\lemref}[1]{\ref{lemma:#1}}
\newcommand{\thmref}[1]{\ref{thm:#1}}
\newcommand{\corref}[1]{\ref{cor:#1}}
\newcommand{\defref}[1]{\ref{def:#1}}
%\newcommand{\chapref}[1]{\ref{chap:#1}}
\newcommand{\secref}[1]{\ref{sec:#1}}
%\newcommand{\eqref}[1]{\ref{eq:#1}}
\newcommand{\figref}[1]{\ref{fig:#1}}
\newcommand{\tabref}[1]{\ref{tab:#1}}
%\floatstyle{ruled}
%\newfloat{algorithm}{htbp}{loa}
%\floatname{algorithm}{Algorithm}
%From Erik Demaine:
% Complex \xxx for making notes of things to do. Use \xxx{...} for general
% notes, and \xxx[who]{...} if you want to blame someone in particular.
% Puts text in brackets and in bold font, and normally adds a marginpar
% with the text `xxx'' so that it is easy to find. On the other hand, if
% the comment is in a minipage, figure, or caption, the xxx goes in the text,
% because marginpars are not possible in these situations.
{\makeatletter
\gdef\xxxmark{%
\expandafter\ifx\csname @mpargs\endcsname\relax % in minipage?
\expandafter\ifx\csname @captype\endcsname\relax % in figure/caption?
\marginpar{xxx}% not in a caption or minipage, can use marginpar
\else
xxx % notice trailing space
\fi
\else
xxx % notice trailing space
\fi}
\gdef\xxx{\@ifnextchar[\xxx@lab\xxx@nolab}
\long\gdef\xxx@lab[#1]#2{{\bf [\xxxmark #2 ---{\sc #1}]}}
\long\gdef\xxx@nolab#1{{\bf [\xxxmark #1]}}
% This turns them off:
%\long\gdef\xxx@lab[#1]#2{}\long\gdef\xxx@nolab#1{}%
\gdef\turnoffxxx{\long\gdef\xxx@lab[##1]##2{}\long\gdef\xxx@nolab##1{}}%
}
% Blackboard R for real numbers, S for sphere (\S taken someplace, so \Sph).
% \def\P{{\mathcal P}}
% \def\r{{\rho}}
% \def\s{{\sigma}}
% \def\S{{\Sigma}}
\def\C{{\mathcal C}}
% \def\X{{\mathcal X}}
% \def\G{{\Gamma}}
% \def\g{{\gamma}}
% \def\l{{\lambda}}
% \def\L{{\Lambda}}
% \def\k{{\kappa}}
% \def\o{{\omega}}
% \def\O{{\Omega}}
% \def\d{{\delta}}
% \def\e{{\varepsilon}}
% \def\a{{\alpha}}
% \def\b{{\beta}}
% \def\t{{\theta}}
% \def\hull{\mathop{\rm hull}\nolimits}
% \def\sp{\mathop{\rm sp}\nolimits}
%Special, problematical symbols:
%\def\polyh{{\mathcal P}}
%\def\p{{P}}
%\def\p*{{P^*}}%\def\p1{{P_1}}
%\def\p2{{P_2}}
% \def\bP{{\partial P}}
% \def\bX{{\partial X}}
% \def\bD{{\partial D}}
% \def\bU{{\partial U}}
% \def\bM{{\partial M}}
\def\R{{\mathbb{R}}}
\def\D{{\Delta}}
\def\c{{\chi}}
\def\s{{\sigma}}
\newcommand{\squeezelist}{\setlength{\itemsep}{0pt}}
%\newcounter{abc}
\title{%
Thickness-2 Box Complexes\\
are 3-Colorable
} %title
\author{%
\emph{The Coloring~Clique}:
\and
Lily, Jessica, Micaela, Emily, Joe,
Victoria, Rawia, Stephanie%
\thanks{Department of Mathematics and of Computer Science, Smith College, Northampton, MA
01063, USA.}
}%author
\begin{document}
\maketitle
\begin{abstract}
First draft of proof. Only a sketch so far. Needs many figures.
\end{abstract}
\section{Definitions}
\seclab{Definitions}
This proof only works on a restricted class of objects built from
boxes.
First we will define the class of objects.
\paragraph{The Objects.}
Each element of the object is a rectangular box.
The boxes are glued together whole-face-to-whole-face to form a
\emph{box complex}.
We do not allow two boxes sharing only part of a face.
However, it is possible for two boxes to share just part of an edge, or
share only one vertex.
In two dimensions, the analogous object is a \emph{rectangle complex};
Figure~\figref{RectComplex}(a).
In this proof, we will need a relaxation of the
whole-edge-to-whole-edge
gluing in a rectangle complex, to permit two rectangles to share just
part of an edge.
Let us call this looser conglomeration a \emph{rectangle collection};
Figure~\figref{RectComplex}(b).
In all these objects, the rectangles or box edges are parallel to
orthogonal $xyz$
Cartesian axes, and all vertices have integer
coordinates,
i.e., all corners lie on the integer lattice, $\mathbb{Z}^2$ or
$\mathbb{Z}^3$
respectively.
%see Figure~\figref{RectComplex}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure Begin
\begin{figure}[htbp]
\centering
\includegraphics[width=0.95\linewidth]{Figures/RectComplex}
%\fbox{RectComplex}
\caption{(a)~A rectangle complex and its dual graph.
(b)~A rectangle collection and its dual graph.}
\figlab{RectComplex}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure End
\paragraph{Dual Graph.}
Each object has an associated dual graph that forms the basis of
coloring rules.
For a rectangle complex, the nodes of the dual graph are rectangles,
and there is an arc between each pair of rectangles that share a
(whole) edge (and they can only share a whole edge in a rectangle
complex).
For a rectangle collection, the nodes of the dual graph are rectangles,
and again there is an arc between each pair of rectangles that share a
whole edge. Note that none of the partial-edge contacts, which are
permitted in
a rectangle collection, result in an arc in the dual graph.
Finally, the dual graph of a box complex has a node for each box,
and an arc between each pair of boxes that share a (whole) face
(and they can only share a whole face in a box
complex). Two boxes that share a whole edge, or part of an edge, or
just one vertex, but not a face, are not
connected by an arc in the dual graph.
See again Figure~\figref{RectComplex}.
\paragraph{Coloring.}
An object is \emph{solid-colored} by coloring the nodes of the dual
graph so that no two adjacent nodes are assigned the same color.
Thus abutting rectangles or boxes must get different colors.
We call it ``solid''-coloring because the entire solid box is given a color,
which must be different from any other box that shares a face with it.
A class of objects is said to be \emph{$k$-colorable} if $k$ colors always
suffice
for any object in that class. Our goal is to prove sharp colorability
results of the form: a certain class of objects is $k$-colorable, and
sometimes $k$ colors are needed.
\section{2D Theorems}
\seclab{Theorems}
\begin{theorem}
A rectangle complex is 3-colorable, and sometimes 3 colors are needed.
\thmlab{rect.complex}
\end{theorem}
\begin{proof}
By induction. \xxx{Proof to be added later.}
\end{proof}
\begin{theorem}
A rectangle collection is 3-colorable, and sometimes 3 colors are
needed.
\thmlab{rect.collection}
\end{theorem}
\begin{proof}
Almost the same as the previous proof. \xxx{Proof to be added later.}
\end{proof}
\section{Thickness-2 Theorem}
Say that a box complex has \emph{thickness-$t$} if its height in one
of the three directions (which we take to be the $z$-direction) is
$\le t$, i.e., it lies between two parallel planes separated by
distance at most $t$, and it does not lie between closer parallel planes.
A box complex of thickness-1 has the same dual graph as a rectangle
complex:
because we restrict all coordinates to integers, boxes must be at
least one-unit in thickness, so the rectangle bases of the boxes has
the same dual graph as the boxes themselves.
Thus a box complex of thickness-1 is 3-colorable by
Theorem~\thmref{rect.complex}.
The first interesting case is thickness-2:
\begin{theorem}
A box complex of thickness-2 is 3-colorable, and sometimes 3 colors are needed.
\end{theorem}
\begin{proof}
Sketch. \xxx{Full details to be added later.}
That 3 colors are sometimes needed is immediate, because a box complex
of
thickness-1 sometimes needs 3 colors, and such a complex
could be stretched
by a factor of 2 in the $z$-direction.
Let $\C$ be the rectangle complex, and $G$ its dual graph.
Call a box \emph{tall} if it has $z$-height 2.
First notice that the set of tall boxes forms a separate component of
$G$,
call it $G_2$. This is because no box of height 1 can be adjacent to
a tall box.
Just as we argued above (for thickness-1 complexes), $G_2$ is the same
as the dual graph of the rectangles that form the bases of all the
tall boxes. Thus $G_2$ is 3-colorable by
Theorem~\thmref{rect.complex}.
Henceforth we concentrate solely on the box complex $\C_1$ consisting
of all the boxes of height 1, and its dual graph $G_1$.
Although the boxes have $z$-height 1, they can have any (integer) size in
the $x$ and $y$ dimensions.
Without loss of generality, assume all the boxes in $\C_1$ lie between
$z=0$ and $z=2$.
Call the collection of boxes that touch $z=0$ to be in \emph{layer 1}
and those that touch $z=2$ to be in \emph{layer 2}.
Finally, say that a box in layer 2 that has no box beneath it in layer
1,
is \emph{suspended}.
The proof now takes four steps:
\begin{enumerate}
\squeezelist
\item Under every suspended box in layer 2, add an identical
\emph{imaginary} box in layer 1.
\item Argue that the boxes of $\C_1$ in layer 1, plus the imaginary
boxes, form a box collection $\C'_1$.
\item Apply Theorem~\thmref{rect.collection} to conclude that $\C'_1$
is 3-colorable.
\item Color every box in layer 2 with color $c+1 (\mathrm{mod} 3)$ if the box
of
$\C'_1$ underneath it is colored $c$.
\end{enumerate}
Now we detail these four steps.
\begin{enumerate}
%\squeezelist
\item Add imaginary boxes in layer 1 under every suspended box in layer 2.
Note that by our definition of a box complex, it is not possible for,
say,
a large box in layer 2 to have a small box underneath it, because then
we would have two boxes touching in a part of rather than in a whole face.
So every box $b_2$ in layer 2 either has an identical box $b_1$ beneath it in
layer 1, or it has nothing beneath it at all.
In the former case, we do nothing. In the latter case, we add
a ``imaginary'' box $b'_1$ underneath it. $b_2$ and $b'_1$ share a
face,
and so are adjacent in $G_1$.
\item Let $\C'_1$ be the set of boxes from $\C_1$ in layer 1, plus
all the imaginary boxes added in Step~1.
We now argue that $\C'_1$ is a collection of boxes, as defined
previously.
(In fact, the definition of a collection of boxes was designed
precisely
to capture $\C'_1$.)
\xxx{Argument unfinished. Needs illustration!}
\item $\C'_1$ is 3-colorable.
This follows immediately from Theorem~\thmref{rect.collection}
\item Let the colors used to solid-color $C'_1$ be $c \in \{0,1,2\}$.
Let $b_2$ be a box in layer 2. Note that it must have a box of
$\C'_1$
beneath it, either a box of $\C_1$ or an imaginary box.
Call that box $b_1$. It was colored in Step~3.
If $b_1$ is assigned color $c$, then color $b_2$ with
color $c+1 (\mathrm{mod} 3)$.
\xxx{Argument unfinished.}
\end{enumerate}
\end{proof}
% \paragraph{Acknowledgments.}
\bibliographystyle{alpha}
%\bibliographystyle{plain}
\bibliography{/Users/orourke/bib/geom/geom}
\end{document}
%%%% EDIT HERE %%%%
see Figure~\figref{X}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure Begin
\begin{figure}[htbp]
\centering
\includegraphics[width=0.75\linewidth]{Figures/X}
%\fbox{X}
\caption{X}
\figlab{X}
\end{figure}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Figure End
\begin{lemma}
\lemlab{vve}
\end{lemma}
\begin{proof}
\end{proof}
\begin{theorem}
\thmlab{Convex}
\end{theorem}
\begin{proof}
\end{proof}
\begin{description}
\item[Case 1.]
\item[Case 2.]
\item[Case 3.]
\end{description}