\documentclass[12pt,ifthen]{article}
\usepackage{amsmath}
\usepackage{hyperref}
\usepackage{comment}
\newcommand{\N}{{\sf N}}
\newcommand{\Q}{{\sf Q}}
\newcommand{\Z}{{\sf Z}}
\newcommand{\into}{{\rightarrow}}
\newcommand{\st}{\mathrel{:}}
\newcommand{\IO}{\exists^\infty}
\newcommand{\COL}{\mathrm{COL}}
\newcommand{\lf}{\left\lfloor}
\newcommand{\rf}{\right\rfloor}
\newcommand{\lc}{\left\lceil}
\newcommand{\rc}{\right\rceil}
\newcommand{\Ceil}[1]{\left\lceil {#1}\right\rceil}
\newcommand{\ceil}[1]{\left\lceil {#1}\right\rceil}
\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}

\newcommand{\nth}{n^{th}}

\begin{document}

\centerline{\bf Take Home Final}
\centerline{\bf Due May 20 at 7:00AM. No Extensions}


\newif{\ifshowsoln}
% \showsolntrue % comment out to NOT show solution inside \ifshowsoln and \fi blocks.

\centerline{\bf THIS EXAM IS THREE PAGES!!!!!!!!!!!!!!!}


\begin{enumerate}

\item
(0 points)
What is your name?  Write it clearly.

\item (20 points) % Ramsey
A coloring $COL:\binom{\N}{2}\into \N$ is {\it Dhruv} if, for all $x<y$,

% $$x\le f(x,y) \le y.$$
$$x\le COL(x,y) \le y.$$

\begin{enumerate}
\item
Either give an example of a Dhruv coloring $COL:\binom{\N}{2}\into \N$ that has
an infinite homog set OR prove there cannot be one.

\item
Either give an example of a Dhruv coloring $COL:\binom{\N}{2}\into \N$ that has
an infinite min-homog set OR prove there cannot be one.

\item
Either give an example of a Dhruv coloring $COL:\binom{\N}{2}\into \N$ that has
an infinite max-homog set OR prove there cannot be one.

\item
Either give an example of a Dhruv coloring $COL:\binom{\N}{2}\into \N$ that has
an infinite rainbow set OR prove there cannot be one.


\end{enumerate}


\centerline{\bf GO TO NEXT PAGE}

\newpage


\item
(40 points) % VDW-Lower Bound
The following is a known theorem that we will refer to in two (very different)
questions:

{\bf Theorem USETHIS} For all $k$ there exists $G$ such that for all $COL:[G]\times[G]\into [2]$
there exists $a,b,d$ such that all the elements of

$\{a, a+d, \ldots, a+(k-1)d \} \times \{b, b+d, \ldots, b+(k-1)d \}$ is monochromatic

($k=2$ is the square theorem. $k=3$ would be a regular $3\times 3$ grid being mono.)

\begin{enumerate}
\item
(20 point)
Find a lower bound on $G$ from {\bf Theorem USETHIS} using the Prob Method.




\item %VDW
(20 points)
(You may and should use the {\bf Theorem USETHIS}.)
Show that there exists $M$ such that, for all 2-colorings of 

$$[M]\times[M]\times[M].$$

there exists four points that are the same color of the following form:

$(x,y,z)$

$(x+d,y,z)$

$(x,y+d,z)$

$(x,y,z+d)$

(Feel quite free to use pictures in your solution.)

\noindent
where $x,y,z\in [M]$ and $d\ge 1$.

\end{enumerate}

\centerline{\bf GOTO NEXT PAGE}

\newpage



\item
(20 points)  Recall that

$LR_2(k)$ is the least $n$ such that any 2-coloring of $\binom{\{k,\ldots,n\}}{2}$ has a large homog set $H$
where large means that $|H|>\min(H)$ (note the strict inequality).
In class we showed $LR_2(2)\le 13$ and there are now slides on that on the course websites.

Prove that $LR_2(2)\le 12$.

\item
(20 points) % VDW
For this problem you MAY NOT assume Rado's theorem. You will essentially be proving
it in a particular case.

Fill in an $A\ge 1$ and a $B\ge 1$ such that the following 2-part theorem is true, and prove both parts.
\begin{enumerate}
\item
There exists a $c$ and a $c$-coloring of $\N$ such that the equation
$$w+2x+5y-Az=0$$
has NO mono solution.
Try to make $A$ as small as possible.
\item
For every $c$ there exists $n$ such that for all $c$-colorings of $[n]$ 
there is a mono solution to the equation
$$w+2x+5y-Bz=0$$
with $w,x,y,z$ ALL DIFFERENT.
Try to make $B$ as large as possible.
(YES I know that for this part I said ALL DIFFERENT and for Part a I did not.
This is NOT a mistake.)
\end{enumerate}


\end{enumerate}


\end{document}




\end{enumerate}


\end{document}