\documentclass[12pt,ifthen]{article}
\usepackage{amsmath}
\usepackage{amssymb}
%\usepackage{html}
\usepackage{hyperref}
\newcommand{\N}{{\sf N}}
\newcommand{\into}{{\rightarrow}}
\newcommand{\ceil}[1]{\lceil #1 \rceil}

\usepackage{amsthm}
\newtheorem{theorem}{Theorem}

\begin{document}

\centerline{\bf Homework 1, Morally Due Tue Feb 11, 2020}

COURSE WEBSITE:

\url{http://www.cs.umd.edu/~gasarch/COURSES/858/S20/index.html}

(The symbol before gasarch is a tilde.)

\begin{enumerate}

\item
(0 points but if you do miss the midterm and don't tell Prof Gasarch about it ahead of time, it is $-100$ points)
What is your name?  Write it clearly.
Staple your HW. 
When is the midterm tentatively scheduled (give Date and Time)?
If you cannot make it in that day/time see me ASAP.

\item
(20 points)
\begin{enumerate}
\item
(10 points)
Prove that for every $c$, for every $c$ coloring of
$\binom{\N}{2}$, there is a homogenous set USING a proof
similar to what I did in class.
\item
(10 points)
Prove that for every $c$, for every $c$ coloring of
$\binom{\N}{2}$, there is an infinite  homogenous set USING induction on $c$.
\item
(0 points)
Which proof do you like better?
Which one do you think gives better bound when you
finitize it?
\end{enumerate}

\item (30 points) Prove the following theorem rigorously (this is the
  infinite $c$-color $a$-ary Ramsey Theorem):
  \begin{theorem}
    For all $a\ge 1$, for all $c\ge 1$, and for all $c$-colorings of
    $\binom{\mathbb{N}}{a}$, there exists an infinite set
    $A\subseteq \mathbb{N}$ such that $\binom{A}{a}$ is monochromatic
    ($A$ is an infinite homogeneous set).
  \end{theorem}
The proof should be by induction on $a$ with the base case being $a=1$.

\item
(25 points)
State and prove a theorem with the XXX filled in.

For every coloring (any number of colors) of $XXX(n)$ points there is EITHER:
(a) a set of $n$ that are all colored the same, or
(b) a set of $n$ points that are all colored differently.
However!- there IS a coloring of $XXX(n)-1$ points such that
there is NEITHER:
(a) a set of $n$ that are all colored the same, or
(b) a set of $n$ points that are all colored differently.

\centerline{\textbf{THERE IS A PROBLEM ON THE NEXT PAGE}}

\item
  (25 points)

  Suppose $x_{1},x_{2},x_{3},\dots$ be an infinite increasing sequence
  of natural numbers. Let $p(y_{1},y_{2},\dots,y_{k})$ be any function
  on natural numbers, and let $q(z)$ be an increasing and unbounded
  function on the naturals.

  Prove that there exists an infinite subsequence $y_{1},y_{2},\dots$
  such that for all $y_{i_{1}}< y_{i_{2}}< \dots<y_{i_{k}}<y_{i_{k+1}}$,
  $p(y_{i_{1}},\dots,y_{i_{k}}) < q(y_{i_{k+1}})$.

\end{enumerate}

\end{document}

%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End: