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

% 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{\ALG}{{\rm ALG}}
\newcommand{\ACK}{{\rm ACK}}
\newcommand{\VC}{{\rm VC}}
\newcommand{\AC}{{\rm AC}}
\newcommand{\ZL}{{\rm ZL}}
\newcommand{\WOP}{{\rm WOP}}
\newcommand{\tree}{{\rm tree}}
\newcommand{\SUBSEQ}{{\rm SUBSEQ}}
\newcommand{\minor}{{\preceq_m}}
\newcommand{\minorp}{{\preceq_m'}}
\newcommand{\cminor}{{\preceq_{\rm c\hbox{-}m}}}
\newcommand{\GM}{{\rm  GM}}
\newcommand{\TREE}{{\rm  TREE}}
\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 07, Morally Due 12:30PM, Tue Mar 24  2026}


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

\begin{enumerate}

\item
(0 points) What is your name? 


\vfill

\centerline{\bf GO TO NEXT PAGE}

\newpage


\item
(35 points)
Prove the infinite 4-ary Ramsey theorem:

{\it For all $\COL \colon \binom{\N}{4}\into [2]$ there exists an infinite homog set.} 

Do the proof where at every stage you use the infinite 3-ary Ramsey Theorem
(so you use the infinite 3-ary Ramsey Theorem infinitely often) 
and then at the end you use the 1-ary Ramsey Theorem once.


\vfill

\centerline{\bf GO TO NEXT PAGE}

\newpage

\item
(30 points) 
Prove the finite 4-ary Ramsey theorem:

{\it $\forall k)(\exists n)$ such that $\forall)$ $\COL \colon \binom{[n]}{4}\into [2]$ there exists a homog set, size $k$.}

Also give an upper bound on $n$ as a function of $k$.
The bound should be reasonable (e.g., NOT the TOWER function). 

You may use the following approximation of the finite 3-ary Ramsey Theorem:

{\it $\forall)$ $\COL \colon \binom{[n]}{3}\into [2]$ there exists a homog set
of size $\ge \log(\log(n)$.}

\vfill

\centerline{\bf GO TO NEXT PAGE}

\newpage

\item
(35 points) 
\begin{enumerate}
\item 
THIS IS NOW EXTRA CREDIT SINCE THE PROOF I HAD IN MIND DOES NOT WORK.

Find XXX such that the following is true, and prove it.

\bigskip

{\it Let $\COL' \colon \binom{\N}{2} \times \N \into [10^{100}]$. 
Show that there exists infinite sets $A,B\subseteq \N$ such that
$\COL'$ restricted to $\binom{A}{2}\times B$ only uses XXX colors.}

\bigskip

\item
Find $c$ such that the following is true, and prove it.

\bigskip

{\it Let $\COL \binom{\omega+\omega}{3} \into [10^{100}]$. 
Show that Then there exists an infinite  $c$-homogenous set.} that is order equivalent to
$\omega+\omega$. 

ADDED LATER: $c$ CAN BE A FUNCTION OF XXX FROM PART 1. FOR EXAMPLE YOU CAN SAY
$c=XXX^2$. 

(Hint: Use Part a. Thats why its there!)

\bigskip 

\end{enumerate}

\vfill

\centerline{\bf GO TO NEXT PAGE}

\newpage

\item
(0 points, but you must answer it)

As I told you in class, I wrote {\it I can see for miles and miles}
as a song about the infinite hat game, but then sold it to {\it The Who}
who changed the lyrics.

My lyrics are part of these slides:

\url{https://www.cs.umd.edu/~gasarch/COURSES/752/S26/slides/miles.pdf}

Their lyrics are in this youtube video of the Who singing it:

\url{https://www.youtube.com/watch?v=FWt1adCTnd4}

Listen to their version and my version as sung by {\it Bad Sequence}.

Whose version to you prefer?

Consider: 

\begin{itemize}
\item 
{\bf My version} is about the infinite hat game. 
\item
{\bf The Who's} version has the viewpoint of a guy who thinks his girlfriend is cheating
on him but warns her that he knows since, as he puts it, 
{\it I can see for miles and miles$\ldots$}.
\end{itemize}

\begin{itemize}
\item 
{\bf The Who} played for the Superbowl halftime show in 2010. The past. 
\item
{\bf Bad Sequence} will play for the Superbowl halftime show in 2027. The future!
\end{itemize}

\begin{itemize}
\item 
{\bf The Who} has great backup singers, and had musical accompaniment. 
\item
{\bf My version} had neither of those.
\end{itemize}


\vfill

\centerline{\bf GO TO NEXT PAGE}

\newpage

\item
(0 points, but you must answer it)

I got the idea for the skit, where Amedeo is confused about the rock band being {\it The Who} 
from a famous (or is it?) comedy routine called {\it Who's on first} 
It was performed by the comedy duo Abbott and Costello.

Here it is on You Tube

\url{https://www.youtube.com/watch?v=5FsJe4DScDs}

\noindent
a) Listen to it. (I am NOT going to ask what's better theirs or mine, since it's MUCH better,
and they were first, unlike the song {\it I can see for miles and $\ldots$} where I was first). 

\noindent
b) Name all of the players that are mentioned in the routine. 

\noindent
c) Here is my question: Have you heard it before? Also include if you've lived in
America since you were 10 (see comment below for why I want to know). 

I ask since it was, at one time, {\it Who's on First} 
was the most famous comedy routine in America. I suspect it has long faded. 
I am curious to get data on that, and also correlate with people living in 
America for a long or short time. 

\end{enumerate}

\end{document}