\documentclass[12pt,ifthen]{article}
\usepackage{amsmath,amssymb}
%\usepackage{html}
%\usepackage{url}
\usepackage{hyperref}
\newcommand{\spec}{\rm spec}
\newcommand{\R}{\mathbb{R}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\into}{{\rightarrow}}
\newcommand{\st}{\mathrel{:}}
\newcommand{\finv}{f^{-1}}
\newcommand{\COL}{\mathrm{COL}}
\newcommand{\lf}{\left\lfloor}
\newcommand{\rf}{\right\rfloor}
\newcommand{\lc}{\left\lceil}
\newcommand{\rc}{\right\rceil}
\newcommand{\ceil}[1]{\left\lceil {#1}\right\rceil}
\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\degg}{{\rm deg}}

\begin{document}

\centerline{\bf Homework 10, DUE DUE  Tue May 12, 2020, 3:30PM}

\centerline{\bf NEED it done by Tue May 12 so can go over it on the last day}

COURSE WEBSITE: \url{http://www.cs.umd.edu/~gasarch/858/S18.html}

\newif{\ifshowsoln}
\showsolntrue % comment out to NOT show solution inside \ifshowsoln and \fi blocks.


\bigskip

\begin{enumerate}
\item
(0 points)
What is your name?  Write it clearly.

\item
(30 points)
Show that Szemeredi's Theorem implies VDW's Theorem.

\item
(30 points) Prove or disprove. You may assume VDW's theorem.
\begin{enumerate}
\item
(15 points)
For all $COL:\N\into[c]$ there exists, for all $k$, a mono $k$-AP AND 
the 3-AP, the 4-AP, the 5-AP, etc are all disjoint.
\item
(15 points)
For all $COL:\N\into[c]$ there exists a mono $\omega$-AP
(e.g., 10,15,20,$\ldots$ all the same color).
\end{enumerate}


\item
(40 points) %VDW
A set $A$ is {\it 4-free set} if it does not have any arithmetic sequence of size 4.

For this problem assume that, for all $P$, there is a 4-free set $A\subseteq [P]$ of
size $Pe^{-(\log P)^{2/3}}$.

Alice, Bob, Carol, and Donna each have a string of length $n$ on their foreheads
The strings are $a,b,c,d$. Give a protocol for them to used such that
\begin{itemize}
\item
At the end they all know if $a+b+c+d=2^{n+1}-1$.
\item
The number if bits communicated is $\ll n$.
\item
Assume that your reader is a student in this class who MISSED the lecture on 
multiparty Communication (but she saw all of the prior lectures).
\end{itemize}



\end{enumerate}

\end{document}