\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{\AREA}{{\rm AREA}}
\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 10, Morally Due 12:30PM, Tue Apr 21  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) 
For this problem assume $R(5)=43$ (this is widely believed). 
Hence the following is true:

{\it For all $\COL \colon \binom{[43]}{2}\into [2]$, 
there exists at least ONE mono $K_5$.} 

\begin{enumerate}
\item 
(20 points) 
Fill in the following sentence and prove it:

{\it Let $L\in\N$.  Think of $L$ as SMALL (like $L=2,3,4,5$.) 
If $n$ satisfies condition $XXX(L)$ then,  for all $\COL \colon \binom{[n]}{2}\into [2]$, 
there exists at least $L$ mono $K_5$'s. This should use a similar technique 
to what I did in class with $K_4$. 
(NOTE: DO NOT do the following: for $L=2$, use $n=2\times 43$, for $L=3$, use
$n=3\times 43$.)
}

\item 
(0 point and don't hand in but this will help you with Part c)
Write a program that will, given $L$, find the least $n$ that satisfies $XXX(L)$. 


\item
(15 points) 
Run the program for $L=1$ to 20 and give us a table of the following form
(I only give the first three rows

\[
\begin{array}{|r|l|}
\hline
L & \hbox{least n} \cr 
\hline
1 & 43 \cr
2 & 50 \cr
3 & 57 \cr
\hline
\end{array}
\] 

\item
(0 points) Using the data from the last problem, try to get a function
that approximates $n$ as a function of $L$. 

\end{enumerate} 


\vfill 

\centerline{\bf GO TO NEXT PAGE}

\newpage


\item
(35 points) 

\noindent
{\bf Def} Let $X$ be a finite set. Let $\COL \colon X \into \omega$.
Let $Y\subseteq X$. $Y$ is {\it homog} if all the elements of $Y$ are the
same color. $Y$ is {\it rainbow} if all the elements of $Y$ are different colors. 

The following is the 1-ary Large Can Ramsey:

{\it For all $k$ there exists $n=LCR(k)$ such that, 

for all $\COL \colon \{k,k+1,\ldots,k+n\}\into \omega$ either there exists
a large homog set or a large rainbow set.}

\begin{enumerate}
\item
(35 points) 
Prove the 1-dim large can Ramsey theorem.
\item
(0 points but you must do) 
Does your prove give a bound on $LCR(k)$ (perhaps in terms of large Ramsey numbers of
a higher arity).? 
\end{enumerate} 

\vfill 

\centerline{\bf GO TO NEXT PAGE}

\newpage

\item 
(30 points) 
Let $a,b,c\ge 2$. 
Let $R(a,b,c)$ be the least $n$ such that, for all $\COL\colon \binom{[n]}{2}\into [3]$
there exists either a RED $K_a$ or a BLUE $K_b$ or a GREEN $K_c$. 
(So $R(k,k,k)$ is the Ramsey Number for 3-coloring a graph and looking seeking
a homog set of size $k$.) 

\begin{enumerate}
\item 
(0 points but you should do it)
Show that 

$R(2,b,c)=R(b,c)$

$R(a,2,c)=R(a,c)$

$R(a,b,2)=R(a,b)$. 

\item
(20 points) 
Show that

$R(a,b,c) \le R(a-1,b,c) + R(a,b-1,c) + R(a,b,c-1)-1$. 

\item 
(0 points) 
Write a program that will, on input $a,b$, outputs an upper bound on $R(a,b)$. 
Use the recurrence-inequality we had for $R(a,b)$ and also the trick 
where if the  bounds on $R(a,b-1)$ and $R(a-1,b)$ are even
then the bound on $R(a,b)$ is $R(a-1,b)+R(a,b-1)-1$. 
(We will be running it on small enough values that doing it by
recursion will be fine.) 

\item 
(0 points) 
Write a program that will, on input $a,b,c$, outputs an upper bound on $R(a,b,c)$. 
(We will be running it on small enough values that doing it by
recursion will be fine. This program will use the $R(a,b)$ program.)
(I do not think there is a trick to lower the number by 1.) 

\item 
(10 points) 
Use your program to find upper bounds on $R(a,b,c)$ for $2\le a,b,c\le 6$. 
DO NOT report all of these values. Since Megan ONLY cares about the symmetric
case, JUST output the bounds on $R(2,2,2)$, $R(3,3,3)$, $\ldots$ $R(8,8,8)$.

So I want a table like the one below (the numbers are made up)

\begin{tabular}{|c|c|}
\hline
$k$ & bound on $R(k,k,k)$ \cr 
\hline
2  &7 \cr
3  & 100 \cr
4 & 1000\cr
5 & 2000 \cr
6 & 3000 \cr
7 & 4000 \cr
8 & 5000 \cr
\hline
\end{tabular}

\item
(0 points) Using the data try to come up with a function $f$ which is
$R(k,k,k)$ as a function of $k$. 

\end{enumerate}
\end{enumerate}

\end{document}

