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