\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{multicol}
\usepackage{latexsym}
\usepackage[pdftex]{graphicx}
\usepackage{url}
\usepackage{mathrsfs}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}

\def\zero{\multicolumn{1}{>{\columncolor{white}}c}{0}}
\def\colCell#1#2{\multicolumn{1}{>{\columncolor{#1}}c}{#2}}

\input{preamble.tex}

\begin{document}
\homework{17: Various Odds and Ends (Extra Credit)}{Due Friday, Finals Week}

This set is extra-credit!  If you want to receive said credit for this set, finish it and get it to my office (or my email if you're leaving before then) by 11:30am on Friday.  

Also this set is fun!  (Recall from previous sets the relative difficulty level of ``fun''.)  Do as many as you want; credit will be given for up to three correct answers.

\begin{enumerate}
\item Prove that the chromatic number of space is at least 5.  (By ``space,'' we mean $\mathbb{R}^3$, where we connect two points with an edge if and only if they are distance one apart.
\item (Do not do this problem if you haven't done problem 1 yet!)  Read the paper ``On the space chromatic number,'' by Oren Nechustan:
\begin{center}
\href{http://www.sciencedirect.com/science/article/pii/S0012365X00004064}{http://www.sciencedirect.com/science/article/pii/S0012365X00004064}
\end{center}
Summarize its proof (i.e. give a writeup that you would use for a lecture to your peers) that $\chi(\mathbb{R}^3) \geq 6$.
\item Prove that the chromatic number of space is at most 21.  (By ``space,'' we mean $\mathbb{R}^3$, where we connect two points with an edge if and only if they are distance one apart.

\item Using Zorn's lemma, prove the De Bruijn-Erd\"os Compactness theorem:
\begin{thm}
Suppose that $k$ is a natural number and $G$ is a graph such that every finite subgraph of $G$ can be properly vertex-colored with at most $k$ colors.

Then $G$ itself can be properly vertex-colored with at most $k$ colors.
\end{thm}
\item Take any coloring of the plane $\mathbb{R}^2$, pick any of our colors, and let $C$ be the collection of all points in the plane that are colored that color.  We say that $C$ \textbf{realizes} distance $s$ if there are two points in $C$ that are distance $s$ apart, and say that it \textbf{forbids} distance $s$ otherwise.

We say that a coloring of the plane $\mathbb{R}^2$ is \textbf{polychromatic} if and only if no single color realizes every possible distance.  We define the \textbf{polychromatic number of the plane} as the smallest value $k$ such that there is a $k$-coloring of the plane that is polychromatic, and denote this value as $\chi_p(\mathbb{R}^2)$.
 Prove that $\chi_p(\mathbb{R}^2) \leq \chi 6$.
 
\item Prove that $\chi_p(\mathbb{R}^2) \geq 3$.  (The best known is slightly stronger, that $\chi_p(\mathbb{R}^2) \geq 4$.  I don't know if 3 makes the problem easier yet, but the proof for 4 is certainly doable if difficult.)

\end{enumerate}



\end{document}

