\documentclass[12pt,ifthen]{article}
\usepackage{amsmath}
\usepackage{hyperref}
\usepackage{comment}
\newcommand{\N}{{\sf N}}
\newcommand{\Q}{{\sf Q}}
\newcommand{\Z}{{\sf Z}}
\newcommand{\into}{{\rightarrow}}
\newcommand{\st}{\mathrel{:}}
\begin{document}
\centerline{\bf CMSC/MATH 858R Homework 3}
\centerline{\bf Morally Due TUESDAY Feb 25 at 3:30PM.}
\newif{\ifshowsoln}
\showsolntrue % comment out to NOT show solution inside \ifshowsoln and \fi blocks.
\begin{enumerate}
\item
(0 points)
What is your name? When is the midterm? By what day must you tell Dr.\ Gasarch you can't make the
midterm? (While this problem is 0 points, if you miss the midterm and do not tell Dr.\ Gasarch,
you will get $-100$ on every single homework problem 1). When is the final?
\item
(45 points)
Let $(X,\preceq)$ be a well quasi order.
Let $2^{{\rm fin } X}$ be the set of FINITE subsets of $X$.
We DEFINE an order $\preceq_{\mathrm{BILL}}$ on
$2^{{\rm fin } X}$:
$A\preceq_{\mathrm{BILL}} B$ if there is an injection $f$ from $A$ to $B$ such that $x\preceq f(x)$ for all $x$.
($\emptyset \preceq_{\mathrm{BILL}} B$ is always true: use the empty function and the condition holds vacuously.)
Show that $(2^{{\rm fin } X},\preceq_{\mathrm{BILL}})$ is a well quasi order.
(NOTE- You may use the fact, proven in class, that well-quasi orders are closed under cross product)
\item
(45 points)
Let $TREE$
be the set of trees.
We define $T\preceq_{\mathrm{CLYDE}} T'$ if
$T$ is a minor of $T'$
(recall that $T$ is a minor of $T'$ if you can get $T$ by removing vertices, removing edges, and contracting edges from $T'$)
Show that $TREE$ under $\preceq_{\mathrm{CLYDE}}$ is a wqo.
\textbf{HINT:} You will need to use
the theorem you proved in problem 2 of this homework. As an additional
hint, your proof should begin like this:
\emph{Assume, BWOC that the set of trees under minor is NOT a wqo.}
\emph{Let $T_1,T_2,\ldots$ be a MINIMAL BAD SEQUENCE defined in some fashion (you figure it out).}
\emph{None of the trees is the empty tree, so they all have a root.}
\emph{Assume the root of $T_i$ has degree $d_i$.
For each $T_i$ remove the root to obtain $d_i$ trees $T_{i,1},\ldots,T_{i,d_i}$
}
\centerline{\textbf{GO TO NEXT PAGE}}
\newpage
\item (10 points) Listen to the following songs all set to the tune of Coolio's \emph{Gangsta Paradise}
\begin{itemize}
\item
\emph{Gangsta Paradise} (not math): \url{https://www.youtube.com/watch?v=fPO76Jlnz6c}
\item
\emph{Mathematics paradise} by Klein Four: \url{https://www.youtube.com/watch?v=ncUm362M_gc}
LYRICS: \url{https://genius.com/The-klein-four-mathematics-paradise-lyrics}
\item
\emph{Mathematics Paradise} diff song entirely, not by Klein four: \url{https://www.youtube.com/watch?v=nskSfmeCFic}
\item
\emph{Amish Paradise} (not math): \url{https://www.youtube.com/watch?v=lOfZLb33uCg}
\end{itemize}
Which math version is your favorite? Is it better than the other math songs we have heard so far?
\end{enumerate}
\end{document}
%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End: