\documentclass[11pt]{article}
\usepackage{fullpage}
\usepackage{url}
\usepackage{amsmath}
\usepackage{comment}

% This is a file of macros and definitions that may come up in
% ANY LATEX paper.  Typically I'll use this file and some other file in the
% directory of the paper, this one for general math things, that one for
% things specific to that paper.
%
% font's used and general paper things.
\font\tenrm=cmr10
\font\ninerm=cmr9
\font\eightrm=cmr8
\font\sevenrm=cmr7
% \font\title=cmbx10 scaled \magstep1 % extra big title font
\font\ss=cmss10 % used by \proof
\font\smallcaps=cmcsc10 % used to label Theorems, etc.
% imhibit black bars on overflows
%
\overfullrule=0pt
%
% today's date
%
%
% English words that I always italizice in papers.
% Some words that appear in math mode alot that I wasn roman
%

\newcommand{\R}{\rm  R} 
\newcommand{\B}{\rm  B} 
\newcommand{\G}{\rm  G} 
\newcommand{\Y}{\rm  P} 

\newcommand{\IO}{\exists^\infty}
\newcommand{\ceil}[1]{\left\lceil {#1}\right\rceil}
\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}

\newcommand{\into}{{\rightarrow}}
\newcommand{\D}{{\sf D}}
\newcommand{\N}{{\sf N}}
\newcommand{\Z}{{\sf Z}}
\newcommand{\Q}{{\sf Q}}
\newcommand{\reals}{{\sf R}}
\newcommand{\qd}{{\rm qd}}
\newcommand{\GE}[1]{{\equiv^{G}_{#1}}}
\newcommand{\TE}[1]{{\equiv^{T}_{#1}}}
\newcommand{\TES}[1]{{\equiv^{T}_{#1,{\rm S}}}}
\newcommand{\TEB}[1]{{\equiv^{T}_{#1,{\rm BOOL(S)}}}}
\newcommand{\LL}{{\cal{L}}}
\newcommand{\onepe}{1+\epsilon}
\newcommand{\oneme}{1-\epsilon}
\newcommand{\cool}{cool}
\newcommand{\nze}{numzeros}
\newcommand{\non}{numones}
\newcommand{\LR}[2]{ {\rm LR}_{{#2}}({#1})}
\newcommand{\LH}[2]{ {\rm LH}({#1};{#2})}
\newcommand{\bbb}{{\gamma}}
\newcommand{\COL}{{\rm COL}}
\newcommand{\card}[1]{\#(#1)}
\newcommand{\st}{\mathrel{:}}
\newcommand{\fhat}{{\hat{f}}}
\newcommand{\Ahat}{{\hat{A}}}

\begin{document}

\centerline{\bf Homework 03, Morally Due 12:30PM, Tue Feb 17,  2026}


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

\begin{enumerate}

\item
(0 points) What is your name? 

\bigskip

\vfill\eject 

\item
(20 points) 
\begin{enumerate}
\item 
(0 points) 

Look at the slide packet {\it Infinite Ramsey Thm For Graphs}.

Look at Slides 102-119. 

Slide 102 is titled {\it Formal Construction}.

Slide 119 is titled {\it Some Color Appears Infinitely Often}.

READ and UNDERSTAND the construction and how it captures
the intuitive construction I presented in that slide packet. 

\item
(20 points)

Look at the slide packet {\it Infinite Ram on Z}

Look at Slides 70-100. 

Slide 70 is titled {\it $c\le 2$} 

Slide 100 is titled {\it We Are Done}

Write up the construction formally, similar
to what you read and understood in Part 1 of this question.

\end{enumerate}

\vfill

\centerline{\bf GO TO NEXT PAGE}

\eject

\item
(20 point) 
Look at the slide packet {\it Inf Can Ram}

Look at Slides 87--94, the first one titled {\it Step 3}

\begin{enumerate}
\item
(10 points) 
Describe how to process $x_3$. 
\item 
(10 points) 
Describe how to process $x_n$. 
\end{enumerate}

\vfill\eject


\item 
(20 point) 
Look at the slide packet {\it Inf Can Ram}.

Look at Slide 139-149. The first one is titled {\it Is $H_1$ Max-Homog?}

Prove that $H_1$ is Max-Homog. 

\vfill\eject

\item 
(20 points)
Look at the slide packet {\it Inf Can Ram}.

Look at Slides 168--177. The first one is  titled {\it Need to do More To Get Rainbow Set.}

Prove the theorem on slide 177:

{\it Let $X$ be infinite. Let $\COL \colon \binom{X}{2}\into \omega$. Assume that,
for all $c\in\omega$, $\deg_c(x)\le 2$. Then there exists an infinite rainbow $X_1\subseteq X$. 
}


\vfill\eject

\item
(20 points) 
Let $A=\{p_1,p_2,\ldots\}$ be a sequence of distinct points in the plane.
Let $d(p_i,p_j)$ be the usual Euclidean distance from $p_i$ to $p_j$. 

Let $\COL \colon \binom{\N}{2} \into \reals$ be the coloring

$$\COL(i,j)=d(x_i,x_j).$$

Apply the Can Ramsey Theorem to this coloring to get an infinite set $H$. 

\begin{enumerate}
\item
(3 points)
Prove that $H$ is not homog.
\item
(3 points)
Prove that $H$ is not min-homog.
\item
(3 points)
Prove that $H$ is not max-homog.
\item
(11 points) 
So $H$ is Rainbow. You just proved a theorem! I'll begin the statement
and then you need to FILL IN the part that says FILL IN.

{\it Let $A=\{p_1,p_2,\ldots\}$ be a sequence of distinct points in the plane.
There is an infinite $B\subseteq A$ such that FILL IN.}

\item 
(0 points and not extra credit, but for your own personal enlightenment)
Think about the following variants of this problem: 

\begin{itemize}
\item 
Use a different definition of distance, E.g., {\it the Manhattan Metric (look it up)}.
\item
Do the problem in $\reals^3$ with both the Euclidean distance and others. 
\item
To quote {\it The Bolzano Weierstrass rap}:

{\bf 
Well I am out of here, because my rap is at its end,

But I'll leave you with this exercise, to do it in $\reals^n$!
}
\end{itemize}
\end{enumerate}


\vfill

\centerline{\bf GO TO NEXT PAGE}

\newpage

\item
(0 points but you must do it)

\begin{enumerate}
\item
Listen to as much of {\it The Bolzano Weierstrass Rap} as you can stand.
Here it is:

\url{https://www.youtube.com/watch?v=eM3S74kchoM&list=FLllaX0oj-4_KcE1C4JF72gw}

\item
I feel a moral obligation to present you with math songs that are better than the BW Rap
(hmmm, that would be all math songs). 

Here is a link to my collection of math songs:

\url{https://www.cs.umd.edu/~gasarch/FUN/mathsongs.html}

Pick 5 using any criteria you like (e.g., You are a Swiftie so you want to listen to the linear algebra song {\it $u$ belongs to $V$}), 
listen to them, and give me your opinion of some of them as you see fit. 
\end{enumerate}

\vfill

\centerline{\bf GO TO NEXT PAGE}

\newpage

\item
Extra Credit (0 points). 
This problem does not use any of the techniques in the course.
I will be asking this this to my Honors Discrete Math class and
see who does better, them or you (I would bet on you).

{\it Def} An {\it honest $c$-coloring} is a coloring that uses all $c$ colors. 

{\it Def} Let $\COL\colon \reals^n \into [c]$. Let $b\le c$. 

A {\it $b$-rainbow line} is a line that has at least $b$ colors on it. 

A {\it $b$-rainbow plane} is a plane that has at least $b$ colors on it. 

\begin{enumerate}

\item
Let $A$ be the set of all pairs $(b,c)$ such that $b\le c$ and 
the following is true:

\smallskip

\centerline{\it For all honest $c$-colorings of $\reals^2$ there is a $b$-rainbow line.} 

\smallskip

Give a simple description of the set $A$ 
(e.g., 
{\it $A$ is the set of all $(b,c)$ such that $1\le b^2 \le c$}).
Prove the your descriptions is correct---that is, all $(b,c)$ that fit
your description have the property, and all $(b,c)$ that satisfy the property fit your
description.


\item
Let $B$ be the set of all pairs $(b,c)$ such that $b\le c$ and 
the following is true:

\medskip

\centerline{\it For all honest $c$-colorings of $\reals^3$ there is a $b$-rainbow line.} 

\medskip

Give a simple description of the set $B$, for example

\smallskip

\centerline{\it $B$ is the set $\{ (1,2), (1,3), (2,3) \}$ }

\smallskip


Prove the your descriptions is correct---that is, all $(b,c)$ that fit
your description have the property, and all $(b,c)$ that satisfy the property fit your
description.


\item

Let $C$ be the set of all ordered pairs $(b,c)$ such that $b\le c$ and 
the following is true:

\medskip

\centerline{\it For all honest $c$-colorings of $\reals^3$ there is a $b$-rainbow plane.} 

\medskip

Give a simple description of the set $C$, for example 

\smallskip

\centerline{\it $C$ is the set of all $(b,c)$ such that $b$ is prime and $c$ is the product of two primes}

\smallskip

Prove the your descriptions is correct---that is, all $(b,c)$ that fit
your description have the property, and all $(b,c)$ that satisfy the property fit your
description.

\end{enumerate}








\end{enumerate}


\end{document}

