\documentclass[12pt,ifthen]{article}
\usepackage{amsmath,amssymb}
%\usepackage{html}
%\usepackage{url}
\usepackage{hyperref}
\newcommand{\spec}{\rm spec}
\newcommand{\R}{\mathbb{R}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\into}{{\rightarrow}}
\newcommand{\st}{\mathrel{:}}
\newcommand{\finv}{f^{-1}}
\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{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\degg}{{\rm deg}}

\begin{document}

\centerline{\bf Homework 8, Morally Due Tue April 28, 2020, 3:30PM}

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

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

\centerline{\bf THIS HW IS TWO PAGES LONG!!!!!!!!!!!!}

\bigskip

\noindent
{\bf Note:} In this homework, $R(a,b)$ refers to the 2-ary asymmetric Ramsey
numbers: $R(a,b)$ is the least $n$ such that every $2$-coloring of
$K_{n}$ has a mono RED $K_{a}$ or a mono BLUE $K_{b}$. Similarly,
$R(a,b,c)$ is the 2-ary asymmetric Ramsey with \emph{three} colors:
 $R(a,b,c)$ is the least $n$ such that every $3$-coloring of $K_{n}$
 has a monoc RED $K_{a}$ or a mono BLUE $K_{b}$ or a mono GREEN
 $K_{c}$.

\bigskip

\begin{enumerate}
\item
(0 points)
What is your name?  Write it clearly.

\item
(30 points)
We never defined $R(1,b)$ or $R(a,1)$. Define it so that the inequality
\[
  R(a,b) \le R(a-1,b) + R(a,b-1)
\]
holds. Does the definition also make intuitive sense?


\item
(30 points)
Let $R(a,b,c)$ be the least $n$ such that, for all 3-colorings of 
the edges of $K_n$,
there exists either a RED $K_a$, a BLUE $K_b$, or a GREEN $K_c$.

\begin{enumerate}

\item
Give a bound on $R(2,b,c)$ in terms of $R$ on two variables.


\item
{\bf Recall} In class we proved

$$R(2,b)=b \hbox{ and } R(a,2)=a$$

$$R(a,b) \le R(a-1,b) + R(a,b-1).$$

We used these two relations to get bounds on $R(a,b)$.
We did this by viewing the size of the input $(a,b)$ as $a+b$. With that viewpoint we are
able to get upper bounds on $R(a,b)$ by using upper bounds on smaller pairs.

In this problem you will use this approach for $R(a,b,c)$.

The size of  $(a,b,c)$ is $a+b+c$. 
State and prove an inequality that bounds $R(a,b,c)$ in terms of $R$ on smaller triples.
(for example, it could be
$R(a,b,c) \le R(\floor{\sqrt{a}},b-1,c) + R(\floor{a/2},2,2)$ --- but its not).


\item
  Use parts (a) and (b) to
determine reasonable upper bounds on $R(2,2,2)$, $R(2,2,3)$, $R(2,3,3)$, and $R(3,3,3)$.


\end{enumerate}

\item
(40 points)
The following is a corollary of VDW's theorem that we will cover later in the class

{\bf VDW Theorem} For all $k$ there exists $W=W(k)$ such that for all 2-coloring of
$[W]$ there exists $a,d$ such that

$$a, a+d, \ldots, a+(k-1)d$$

are all the same color.

(This is called a {\it monochromatic arithmetic progression of length $k$}
which we abbreviate {\it mono $k$-AP}.

Use the Prob Method to get a LOWER BOUND on $W(k)$.


\end{enumerate}

\end{document}