\documentclass[12pt]{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{graphicx}
\providecommand{\abs}[1]{\lvert#1\rvert}
\providecommand{\norm}[1]{\lVert#1\rVert}

\newtheorem{thm}{Theorem}
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{fact}[thm]{Fact}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{eg}{Example}
\newtheorem{ex}{Exercise}
\newtheorem{defi}{Definition}
\newtheorem{hw}{Problem}
\newenvironment{sol}
  {\par\vspace{3mm}\noindent{\it Solution}.}
  {\qed}

\newcommand{\ov}{\overline}
\newcommand{\cb}{{\cal B}}
\newcommand{\cc}{{\cal C}}
\newcommand{\cd}{{\cal D}}
\newcommand{\ce}{{\cal E}}
\newcommand{\cf}{{\cal F}}
\newcommand{\ch}{{\cal H}}
\newcommand{\cl}{{\cal L}}
\newcommand{\cm}{{\cal M}}
\newcommand{\cp}{{\cal P}}
\newcommand{\cz}{{\cal Z}}
\newcommand{\eps}{\varepsilon}
\newcommand{\ra}{\rightarrow}
\newcommand{\la}{\leftarrow}
\newcommand{\Ra}{\Rightarrow}
\newcommand{\dist}{\mbox{\rm dist}}
\newcommand{\bn}{{\mathbf N}}
\newcommand{\br}{{\mathbf R}}
\newcommand{\bz}{{\mathbf Z}}
\newcommand{\expe}{{\mathsf E}}
\newcommand{\prob}{{\mathsf{Pr}}}

\setlength{\parindent}{0pt}
%\setlength{\parskip}{2ex}
\newenvironment{proofof}[1]{\bigskip\noindent{\itshape #1. }}{\hfill$\Box$\medskip}

\begin{document}

$\;$\hfill Due: 2012/11/07 before class

\begin{center}
{\LARGE\bf Homework 7}
\end{center}

\begin{hw}
For each $n$, define the set of points in the plane
\[A_n = \{(x, y) : x, y \in \bz, 1 \leq x, y \leq n \}. \]

Prove that, for any integer $c>0$, there exists $N = N(c)$, such that
no matter how we $c$-color $A_N$, there are 4 points in $A_N$ with the same
color and form an axis-parallel rectangle.
\end{hw}

\begin{hw}
For any positive integers $c$ and $r$, there exists $N = N(c, r)$,
such that no matter how we $c$-color $[N]$, there are $r+1$ distinct positive
numbers $x$, $y_1$, $y_2$, ..., $y_r$ such that all the $2^r$ sums
\[ x + \sum_{i \in S} y_i : S \subseteq [r]\]
are not bigger than $N$, and have the same color.
(This lemma is perhaps the first Ramsey type result in the hisotry, due to
David Hilbert, 1892.)
\end{hw}

{\em Note.} The problem above follows easily from van der Waerden theorem (why?).
But try to prove it without v.d.W.

\begin{hw}
Prove the stronger version of Schur's theorem:
For any positive integer $c$, there exists $S^*(c)$ such that
no matter how we color $[S^*(c)]$ by $c$ colors, there are {\em distinct}
$x, y, z \in [S(c)]$ of the same color such that $x + y = z$.
(Hint: Prove that $S^*(c) \leq N_{2c}(3;2)$.)
\end{hw}

\begin{hw} (V Chv\'atal)

(a) Prove that, for any $n$, one can color the edges of the cube $Q_n$ with
Y and B such that there are no monochromatic copies of $Q_2$ (or call it $C_4$ if you like).

(b) Let $T_1$ and $T_2$ be two trees, discuss when it is true that, no matter how we
color the edges of $T_1$ with Y and B, there is always a monochromatic copy of $T_2$.
\end{hw}

To be more precise, describe a simple (polynomial time) algorithm, given
$T_1$ and $T_2$, decide if the above property holds. Prove the correctness of your algorithm.

\end{document}
