\documentclass[11pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage{amsfonts,amsmath,amssymb,amsthm}
\PassOptionsToPackage{obeyspaces}{url}
\usepackage[colorlinks=true,citecolor=blue,urlcolor=blue,linkcolor=blue,bookmarksopen=true]{hyperref}
\usepackage{tikz}
\usepackage{enumitem}
\setlist{itemsep=0.5em}
%% header definitions
\def\course{MATH 314}
\def\courselink{https://mathematicaster.org/teaching/graphs2022}
\def\assign{HW \#13}
\def\assignlink{hw13.tex}
\def\due{May 3}
\def\doctype{This homework is from}
%% environments
% theorem style
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{defn}[theorem]{Definition}
% definition style
\theoremstyle{definition}
\newtheorem{problem}{Problem}
% custom
\newenvironment{solution}{\paragraph{Solution.}}{\qed}
%% custom commands
\newcommand*{\arXiv}[1]{\href{http://arxiv.org/pdf/#1}{arXiv:#1}} % arXiv link
\newcommand*{\eqdef}{\stackrel{\mbox{\normalfont\tiny{def}}}{=}} % definition by equality
\newcommand*{\abs}[1]{\lvert #1\rvert} % absolute values, cardinality
\newcommand*{\eps}{\varepsilon} % prettier epsilon
\newcommand*{\R}{\mathbb{R}} % real numbers
\newcommand*{\C}{\mathbb{C}} % complex numbers
\newcommand*{\Q}{\mathbb{Q}} % rational numbers
\newcommand*{\Z}{\mathbb{Z}} % integers
\newcommand*{\N}{\mathbb{N}} % natural numbers
\newcommand*{\F}{\mathbb{F}} % field
\newcommand*{\family}{\mathcal{F}} % family
\newcommand*{\GL}{\mathbf{GL}} % general linear group
\newcommand*{\what}[1]{\widehat{#1}} % wider hat
\newcommand*{\wbar}[1]{\overline{#1}} % wider bar
\newcommand*{\mcal}[1]{\mathcal{#1}} % mathcal
\newcommand*{\mbf}[1]{\mathbf{#1}} % mathbf
\newcommand*{\mbb}[1]{\mathbb{#1}} % mathbb
% operators
\let\Pr\relax\DeclareMathOperator*{\Pr}{\mathbf{Pr}} % probability
\DeclareMathOperator*{\E}{\mathbb{E}} % expectation
\DeclareMathOperator*{\Var}{\mathbf{Var}} % variance
\DeclareMathOperator*{\Span}{span} % span
\DeclareMathOperator{\tr}{tr} % trace
\DeclareMathOperator{\rank}{rank} % rank
\DeclareMathOperator{\supp}{supp} % support
\DeclareMathOperator{\diam}{diam}
\DeclareMathOperator{\Aut}{Aut}
\DeclareMathOperator{\disc}{disc}
\DeclareMathOperator{\comp}{comp}
\DeclareMathOperator{\len}{len}
\begin{document}
\pagestyle{empty}
\noindent
\begin{minipage}{.33\textwidth}
\flushleft {\bf \course}
\end{minipage}
\begin{minipage}{.33\textwidth}
\centering {\bf \assign}
\end{minipage}
\begin{minipage}{.33\textwidth}
\flushright {\bf \due}
\end{minipage}
\vskip3pt
\hrule\hrule\hrule
\vskip5pt
\noindent {\footnotesize \doctype\ \url{\courselink/\assignlink}}
\vskip10pt
\noindent {\small Unless explicitly requested by a problem, do not include sketches as part of your proof.
You are free to use the result from any problem on this (or previous) assignment as a part of your solution to a different problem even if you have not solved the former problem.
}
\vskip20pt
\begin{problem}[2pts]
The 3-color Ramsey number $R(m,n,p)$ is the smallest integer $N$ such that every 3-coloring of $E(K_N)$ (say with colors red, blue and green) contains either a red copy of $K_m$, a blue copy of $K_n$ or a green copy of $K_p$.
\vskip5pt
Prove that $R(3,3,3)\leq 17$.
\vskip5pt
N.b.\ It turns out that $R(3,3,3)=17$, but I'm not asking you to prove the lower bound.
\end{problem}
\begin{problem}[2pts]
Prove that $R(3,n)\leq n^2$ for every positive integer $n$.
(Hint: It's probably best if you just think about $G$ vs $\wbar G$ instead of red,blue-colorings here.)
(Hint: Review the \emph{silly} upper and lower bounds that we proved on chromatic numbers on 04-05.)
\end{problem}
\begin{problem}[2pts]
Consider coloring the numbers in $[17]$ red and blue, i.e.\ we have a function $f\colon[17]\to\{\text{red},\text{blue}\}$.
Prove that there exist $a\neq b\in[17]$ such that $f(a)=f(b)=f(a+b)$.
(Note that no integers outside of $[17]$ receive any color, so it must be the case that also $a+b\in[17]$ in order for this to happen.)
(Hint: Create a red,blue-coloring of $E(K_{18})$ (thinking of $V(K_{18})=[18]$) based on the differences between the points.)
(Hint: $(x-y)+(z-x)=z-y$.)
\vskip5pt
\textbf{You can receive 1.25pts/2 if you prove a simplified version of the claim where you allow $a=b$.} (such a proof could completely ignore the hint if you so choose and can also be accomplished when $17$ replaced by $5$, but you don't have to)
\vskip5pt
I'm not schur if 17 is the smallest integer for which the claim is true.
I'll hand out \textbf{1 bonus point} if you can determine (with proof) the smallest integer for which the claim is still true.
\end{problem}
\begin{problem}[2 + 2 pts]
Let $n$ be a positive integer and set $N=3n-1$.
\begin{enumerate}
\item Prove that every red,blue-coloring of $E(K_N)$ contains a monochromatic matching with $n$ edges.\footnote{
Fun fact (if you care).
Suppose that the red,blue-coloring of $E(K_N)$ was initially hidden from you and, one by one, you're allowed to ask about the color of whichever edges you desire.
How many edges do you have to ask about in order to actually find a monochromatic matching with $n$ edges?
Of course, you can find the matching by asking about about the color of all ${N\choose 2}$ edges thanks to this problem; however, you can do much, much better.
It turns out that you can actually get away with asking about only $N-1$ of the edges!
The general case (more than two colors) is still open, though, if you care to think about it :)
The relevant papers are \url{https://arxiv.org/abs/1904.00246} and \url{https://arxiv.org/abs/2010.04113}.}
(Hint: Show that there exists an incident red- and blue-edge unless every edge gets the same color)
\item Construct a red,blue-coloring of $E(K_{N-1})$ which \emph{does not} contain a monochromatic matching with $n$ edges.
(Hint: Break $V(K_{N-1})$ into two pieces, one of size $2n-1$ and the other of size $n-1$, and color the edges based on how they intersect these two pieces)
\end{enumerate}
\end{problem}
\end{document}