\documentclass[12pt,ifthen]{article}
\usepackage{amsmath}
\usepackage{hyperref}
\usepackage{url}
\newcommand{\R}{{\sf R}}
\newcommand{\N}{{\sf N}}
\newcommand{\Q}{{\sf Q}}
\newcommand{\Z}{{\sf Z}}
\newcommand{\into}{{\rightarrow}}
\newcommand{\st}{\mathrel{:}}
\newcommand{\finv}{f^{-1}}
\newcommand{\COL}{\mathrm{COL}}

\begin{document}

\centerline{\bf Homework 4, Morally Due Tue Feb 27, 2018}

COURSE WEBSITE: \url{http://www.cs.umd.edu/~gasarch/COURSES/858/S20/index.html}

\begin{enumerate}
\item (0 points) What is your name? When is the midterm? By what day
  must you tell Dr.\ Gasarch you can't make the midterm? (While this
  problem is 0 points, if you miss the midterm and do not tell Dr.\
  Gasarch, you will get $-100$ on every single homework problem
  1). When is the final?

\item (40 points) Recall the second proof of the infinite can Ramsey
  theorem that used 3-ary, 4-color Ramsey and a maximal set
  argument. Finitize it. Give a bound on $\mathrm{CR}_{2}(k)$, where
  you can have a Big-Oh in the exponent. 

  (Note: You will learn how to do this in the Thurs Feb 27 lecture)

\item
(40 points)
The $n\times m$ grid is the set of points 
\[
\{(a,b) \st 1\le a\le n \hbox{ and } 1\le b\le m \}.
\]

In this problem we will be coloring these points.

A {\it monochromatic rectangle} is when there are FOUR points that
are the corners of a rectangle that are all the same color.
Example would be
\[
\{ (3,4), (3,8), (7,4), (7,8) \}.
\]
For which values of $m$ can the $4\times m$ grid be 3-colored without
having a monochromatic rectangle? Prove your result.

\centerline{\bf THERE IS ANOTHER PAGE TO THIS HW}

\newpage

\item
(20 points)
Complete the following statement of a theorem so that it is correct and then prove it:

\emph{For all $\mathrm{COL}\colon \binom{\N}{3} \to \omega$, there exists an infinite set $H$ such that either:
BLAH, or BLAH, or ..., or BLAH.}

\item
(0 points but you must do this so we can discuss)
Here is a book review of a book on the Banach-Tarski Paradox:

\url{http://www.cs.umd.edu/~gasarch/BLOGPAPERS/pea.pdf}

Read the review. Be prepared to discuss if you think the BT paradox is TRUE or FALSE or
SOMETHING ELSE. There is no right answer here but I want to know what you think.

\item
(0 points)
Compare and contrast the following parodies of Billy Joel's \emph{The Longest Time}:
\begin{itemize}
\item ``The Longest Path'' \url{https://www.youtube.com/watch?v=a3ww0gwEszo} 
\item ``Entropic Time'' \url{https://www.youtube.com/watch?v=i6rVHr6OwjI} (does the singer look like anybody you know?)
\item ``Graduate on Time'' \url{https://www.youtube.com/watch?v=Vw6h6epNS5k}
\item ``Polynomial Time'' \url{https://www.youtube.com/watch?v=oO9nFOo8q_c}
\end{itemize}

For reference, here is the original: \url{https://www.youtube.com/watch?v=a_XgQhMPeEQ}


\end{enumerate}

\end{document}