\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}