\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}}

\begin{document}

\centerline{\bf Take Home Midterm}
\centerline{\bf Morally Due April 7,  Sick Cat Day-April 9}




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

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


\begin{enumerate}

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

\item (30 points) {\bf Definition:} Let $X$ be either $\N$ or some
  $[n]$ or some $\{k,\ldots,n\}$.  A coloring
  $\COL\colon\binom{X}{2}\into\omega$ is {\it Erika} if
  $\COL(x,y) \le \min\{x,y\}.$ (Note that $\omega$ is
  $\{1,2,3,\ldots,\}$, so $COL(1,y)=1$ always.)

Consider the following (true) statement which we call STATEMENT.

{\it 
If $COL$ is an Erika coloring of $\binom{\N}{2}$ then either 
(1) there exists an infinite homog set, or
(2) there exists an infinite min-homog set.
}

\begin{enumerate}
\item
(10 points) 
Prove STATEMENT from the Can Ramsey Theory.

\item
(10 points) 
Prove STATEMENT directly, NOT using the Can Ramsey Theory.

\item
(10 points) 
Formulate a finite version of STATEMENT.
Give a proof based on your answer to part b. Your proof should also give you
bounds on $n$ as a function of $k$.
\end{enumerate}



\item
(25 points)
Prove the following:

{\it For all $k$ 
there exist $n$ such that for all Erika colorings $COL:\binom{\{k,\ldots,n\}}{2}\into \omega$ 
there exist either 
(1) a LARGE homog set, or 
(2) a LARGE min-Homog set.
(You need not get a bound on $n$.)}


\item
(25 points) 
\begin{enumerate}
\item
(15 points)
Prove the following. There exists a function $f$ such that the following holds:

{\it If $T_1,T_2,\ldots,T_{f(k)}$ is a FINITE sequence of trees, where
$T_i$ has at most $2^ki$ nodes, there is an uptick.}

For this problem the trees are ordered as $T_1 \le T_2$ if $T_1$ is a minor of $T_2$.

\item
(10 points)
Is there some function $g(i,k)$ such that if you 
replace the $2^ki$ in the first question with $g(i,k)$.
the theorem is now false?

\end{enumerate}



\centerline{GOTO NEXT PATE}

\newpage

\item 
(20 points)
Let $c_1,c_2,c_3\in\N$. 

Let $\COL_1$ be a $c_1$-coloring of $\binom{\N}{1}$.

Let $\COL_2$ be a $c_2$-coloring of $\binom{\N}{2}$.

Let $\COL_3$ be a $c_3$-coloring of $\binom{\N}{3}$.

A set $H\subseteq \N$ is \emph{Nathan homogeneous} if 

$\COL_1$ restricted to $\binom{H}{1}$ is monochromatic, and

$\COL_2$ restricted to $\binom{H}{2}$ is monochromatic, and

$\COL_3$ restricted to $\binom{H}{3}$ is monochromatic.


\begin{enumerate}
\item (10 points) Show that for %
  all $c_{1},c_{2},c_{3}$, for all $c_{1}$-colorings of
  $\binom{\N}{1}$, $c_{2}$-colorings of $\binom{\N}{2}$, and all
  $c_{3}$-colorings of $\binom{\N}{3}$, %
  there is an infinite Nathan Homogenous set.
\item
(10 points)
State and prove a finite version of part a, with bounds.
(You may use the known bounds on Ramsey Numbers.)
\end{enumerate}


\end{enumerate}

\end{document}