% To print single-sided: delete ",twoside" below
\documentclass[11pt,twoside]{article}

% Some very basic packages. Feel free to add your favorites!
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{fancyhdr}
\usepackage{graphicx}

% Set up the page correctly
\addtolength{\oddsidemargin}{-.54in}
\addtolength{\evensidemargin}{-1.2in}
\addtolength{\textwidth}{1.75in}
\addtolength{\topmargin}{-.875in}
\addtolength{\textheight}{1.75in}
\setlength{\parindent}{0pt}
\setlength{\parskip}{5pt plus 1pt}

% Some nifty commands. Thanks Adam Blank!
\newcommand{\question}[2] {\vspace{.25in} \hrule\vspace{0.5em}
\noindent{{\bf #1:} #2} \vspace{0.5em}
\hrule \vspace{.10in}}
\renewcommand{\part}[1] {\vspace{.10in} {\bf (#1)}}

% Add an image centered on the page.
% The first parameter is a scale factor (set to 1 for no scale)
% The second parameter is the image file. Make sure it is in the same folder as your .tex file!
\newcommand{\centergfx}[2]{\begin{center}\includegraphics[scale = #1]{#2}\end{center}}

% Command to insert a minus sign with a dot over it. Stolen from
% http://www.cs.miami.edu/~burt/learning/Math688.931/Other/errata.tex
\newcommand{\monus}{\stackrel{{}^{\scriptstyle .}}{\smash{-}}}

%%%%%%%%%%%%%%%%%%%%%
%		Replace "Name" and                 %
%		   "andrewid" below                   %
%%%%%%%%%%%%%%%%%%%%%
\newcommand{\myname}{Name}
\newcommand{\myandrew}{(andrewid)}
\newcommand{\mysection}{ - X}
\newcommand{\myhwnum}{10}
\newcommand{\myclass}{21-484 Graph Theory}

% Set up the nice header
\pagestyle{fancyplain}
\lhead{\fancyplain{}{\textbf{HW\myhwnum}}}
\rhead{\fancyplain{}{\myname \ \myandrew \ \mysection}}
\chead{\fancyplain{}{\myclass}}

\begin{document}

\question{1, Diestel 9.3}{An \emph{arithmetic progression} is an increasing sequence of numbers of the form $a, a+d, a+2d, a+3d \ldots$. \emph{Van der Waerden's theorem} says that no matter how we partition the natural numbers into two classes, one of these classes will contain arbitrarily long arithmetic progressions. Must there even be an infinite arithmetic progression in one of the classes?}

\cleardoublepage

\question{2}{i) Find, with proof, a 2-coloring of the edges of $K^6 - e$ such that no $K^3$ subgraph is monochromatic (has all of its edges colored with one color).

\noindent
ii) Show that it is possible to remove 5 edges from $K^{10}$ and 2-color the remaining 40 edges without introducing a monochromatic $K^3$.

\noindent
iii) Show that removing 4 (or fewer) edges from $K^{10}$ and 2-coloring the remaining edges will always introduce a monochromatic $K^3$.}

\cleardoublepage

\question{3, Diestel 9.9}{Prove the following result of Schur: for every $k \in \mathbb{N}$ there is an $n \in \mathbb{N}$ such that, for every partition of $\{1, \ldots, n\}$ into $k$ sets, at least one of the subsets contains numbers $x, y, z$ such that $x + y = z$.}

\cleardoublepage

\question{4, Diestel 9.13}{Let $m, n \in \mathbb{N}$, and assume that $m - 1$ divides $n - 1$. Show that every tree $T$ of order $m$ satisfies $R(T, K_{1,n}) = m + n - 1$.}

\cleardoublepage

\question{5, Diestel 9.16}{Show that given any two graphs $H_1$ and $H_2$, there exists a graph $G = G(H_1, H_2)$ such that, for every edge-coloring of $G$ with colors 1 and 2, there is either an induced copy of $H_1$ colored 1 or an induced copy of $H_2$ colored 2 in $G$.}

\cleardoublepage

\question{6}{Let $V_n$ be the set of all binary n-tuples.

The hamming distance between a pair of n-tuples is the number of coordinates in which they differ. A right triangle is a set of 3 n-tuples such that the hamming distance between some pair is equal to the sum of the hamming distances between the other two pairs. Find, with proof, the smallest value of $n$ such that every 2-coloring of the edges of the complete graph on $V_n$ contains a right triangle with all three edges of the same color.}


\end{document}
