\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{multicol}
\usepackage{latexsym}
\usepackage[pdftex]{graphicx}
\usepackage{url}
\usepackage{mathrsfs}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}

\def\zero{\multicolumn{1}{>{\columncolor{white}}c}{0}}
\def\colCell#1#2{\multicolumn{1}{>{\columncolor{#1}}c}{#2}}

\input{preamble.tex}

\begin{document}
\homework{12: Ramsey Theory}{Due Friday, Week 8}



Do \textbf{three} of the six problems listed here!  Have fun, prove all of your claims, and let me know if you have any questions!  

\begin{enumerate}
\item Take the graph $K_7$.  Color each of the edges of $K_7$ either green or blue.  We know, by Ramsey's theorem, that there is at least one triangle in this graph with edges all the same color, because $R(3,3) = 6 < 7$.  Prove that there are actually at least \textbf{four} triangles in this graph such that each triangle's edges are all the same color.

\item In class, we mentioned that finding $R(3,3)$ can be thought of as a game:
\begin{itemize}
\item There are two players, Red and Blue.  Their gameboard consists of six points drawn on a plane.  Players alternate turns, and Red starts first. 
\item On a given player's turn, they must connect two points that do not have a line drawn between them yet, with a line of their given color.
\item The game ends when a monochromatic triangle is drawn on the board, in which case that player loses.
\end{itemize}
We proved in class that this game always ends with one player losing (i.e.\ no draws are possible), because $R(3,3) = 6$.  Assuming that both players play optimally, which player always wins: red or blue?  (Warning: hard!) 

\item Suppose you play the game above on a gameboard with just \textbf{five} points.  Prove that with optimal play from both players, this game will always end in a draw.

\item We defined the \textbf{tri-color Ramsey number} $R(k,k,k)$ to be the smallest natural number $n$ such that in any (red, green, blue)-coloring of $K_n$, there is a monochromatic $K_k$ of some color.  For any $k \geq 3$, prove that
\begin{align*}
R(k,k,k) \geq \lfloor 3^{k/2} \rfloor_.
\end{align*}

\item \begin{enumerate}
\item Show that for any graph $G$ on at least $5\cdot n$ vertices, either $G$ or $\overline{G}$ must contain $n$ disjoint triangles, for any $n \geq 3$.
\item For any $n$, find a graph $G$ on $5n-1$ vertices such that neither $G$ or $\overline{G}$ contain $n$ disjoint triangles, for any $n \geq 3$.
\end{enumerate}

\item 
\begin{enumerate}
\item Draw any five points in the plane, so that no three line on a single line.  Prove that there is a subset consisting of four of these points, such that they are the vertices of a convex quadrilateral.
\item Prove the following theorem:
\begin{thm}
For any $m$, there is some value $N_m$ such that the following holds: suppose that we draw any set of $N_m$ points in the plane, so that no three line on a single line.  Then there is a subset consisting of $m$ of these points, such that they are the vertices of a convex $m$-gon.
\end{thm}
\end{enumerate}
\end{enumerate}



\end{document}