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