\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 06, Morally Due 12:30PM, Tue Mar 10  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)
Recall that we proved the following statement:

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

FROM this give a nonconstructive proof of the following:

\bigskip

\centerline{\it For all $k$ there exists $n$ such that for all $\COL \colon \binom{[n]}{2} \into [2]$}

\centerline{\it  there exists a homog set of size $k$.}

\bigskip

The proof should begin with 

\bigskip

\centerline{\it Assume not. Then there exists $k$ such that, for all $n$,}

\centerline{\it there exists $\COL_n \colon \binom{[n]}{2}\into [2]$ with no homog set of size $k$.}

\bigskip

\smallskip
{\bf Hint:} The proof is similar to the proof that $\tree(n)$ exists.

\smallskip
{\bf Warning:} If you go to the web or AI you will probably find a CONSTRUCTIVE proof that
$n$ exists and $n\le 2^{2k}$ or even lower. This is NOT what I want. 
(I will do that proof later in the term.) 


\vfill

\centerline{\bf GO TO NEXT PAGE}

\newpage

\item
(35 points) 
Consider the following algorithm for $\VC_k$:

{\bf BEGIN}

ALG4($G,k$) (Note that we call it ALG4. We use this terminology later.) 

Input $G,k$

If $k=0$ and $G$ has at least one edge then output NO.
This take $n$ steps. 

Look for a vertex of degree $\ge 3$. 

\begin{itemize}
\item
If none exists then every vertex has degree $\le 2$. 
This graph is just a collection of lines and cycles.
Finding if there is a VC of size $k$ takes $n$ steps.
\item
There exists a vertex $v$ of degree $\ge 3$. 
Consider the two cases of either USING $v$ IN THE VC or NOT USING $v$ IN THE VC.
\begin{itemize} 
\item
Use $v$. If $\ALG4(G-\{v\},k-1)$ says YES then output YES.
\item
Do not use $v$. {\it Then you must use all of its neighbors!}. 
Let $N(v)$ be the neighbors of $v$. 
If $\ALG4(G-(N(v) \cup \{v\}),k-|N(v)|)$ says YES then output YES.
\item
Output NO.
\end{itemize}
\end{itemize}

{\bf END} 

\begin{enumerate}
\item 
(15 points) 
Write a recurrence that bounds $T(n,k)$. 
For example it could be (but it's NOT)

$T(n,0)=\ACK(n,n)$. 

$T(n,k) \le T(n-\ceil{\log n}, k- \ceil{\sqrt{k}}) + k2^n$.

\item
(0 points but you need to do this.) Write a program that computes an
upper bound on $T(n,k)$ using Part $a$. 
(You do not hand anything in for this part.) 

{\it Note} You need to have done Part $a$ to do this part.
If you are having trouble with Part $a$1 you have permission
(more than usual) to get help on it since I really want you to
do Part $c$. 

\item 
(10 points) 
We think that $T(n,k)$ is bounded by an expression of the form $\alpha^k n$. 

Do empirical studies to find a good value for $\alpha$. 

Give a good value for $\alpha$ and describe why your empirical evidence gives you
that value. 

\item
(10 points)
Consider the following algorithm: Run Buss's algorithm except,
at the last step, instead of using ALG2, use ALG4.
What is the run time? Express in terms of $\alpha,k,n$ and you can use O-of 
(so it could be, but its not $O(\ACK(\alpha,k)k^n n^k)$.
\end{enumerate}

\vfill

\centerline{\bf GO TO NEXT PAGE}

\newpage

\item
(30 points)
In class I STATED that the following are equivalent:
Axiom of Choice (AC), Zorn's Lemma (ZL), and The Well Ordering Principle (WOP).

Prove one of the following (you can go to the web or AI for help but
you must put it in your own words). 

$AC\implies ZL$

$ZL\implies AC$

$AC\implies WOP$

$WOP\implies AC$

$ZL\implies WOP$

$WOP\implies ZL$

\vfill

\centerline{\bf GO TO NEXT PAGE}

\newpage

\item
(Extra Credit- 0 points) 
Give a analytic proof of a good bound on $T(n,k)$ in Problem 2. 
The proof should be complete and well written so that I can easily
make it into slides and present it to the class.
(I am not sure if I will do this, but I want to be able to.)

\end{enumerate}

\end{document}