\documentclass[12pt]{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\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{\bz}{{\mathbf Z}}

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

\begin{document}

$\;$\hfill Due: 2011/10/26 before class

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

\begin{hw}
Given two graphs $G$ and $H$, where $V(G)$ and $V(H)$ are disjoint,
their {\em join} is defined to be the graph with a copy of $G$,
a copy of $H$ and additional edges joining all the pairs between $G$
and $H$. Formally,
\[ G \vee H = (V(G) \cup V(H), E(G) \cup E(H) \cup \{uv : u \in V(G), v \in V(H)\} ).\]

Clearly, $K_3 \vee C_5$ does not contain a copy of $K_6$. Prove that,
if its edges are colored Y and B, there is always a monochromatic
$K_3$.
\end{hw}

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

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

\end{document}
