\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{\RED}{{\rm RED}} \newcommand{\BLUE}{{\rm BLUE}} \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 Ramsey Theory Project. Morally Due 12:30PM May 5, 2026} \begin{enumerate} \item (0 points) What is your name? \vfill \centerline{\bf GO TO NEXT PAGE} \newpage \item (10 points) For this problem you can assume that $R(k)=2^k$. \begin{enumerate} \item Fill in the following sentence and prove it: \bigskip {\it Let $k\in\N$. If $n$ satisfies condition $XXX(k)$ then, for all $\COL \colon \binom{[n]}{2}\into [2]$, there exists at least 3 mono $K_k$'s. \bigskip Your proof should use a similar technique used in class for $K_4$. } \item (0 point and don't hand in but this will help you with Part 3) Write a program that will, given $L$, find the least $n$ that satisfies $XXX(L)$. \item (5 points) Run the program for $k=4$ to 7 give us a table of the following form (I only give the first three rows and the numbers are made up.) \[ \begin{array}{|r|l|} \hline k & \hbox{least n} \cr \hline 4 & 22 \cr 5 & 27 \cr 6 & 37 \cr 7 & 47 \cr \hline \end{array} \] \item (5 points) Based on your data, come up with a conjecture for what $n$ is as a function of $k$. \end{enumerate} \vfill \centerline{\bf GO TO NEXT PAGE} \newpage \item (20 points) For this problem you may use the following theorem we proved in class: \noindent $\forall$ $\COL\colon \N\times\N \into [10^{100}]$ $\exists$ infinite $A,B\subseteq \N$ such that $\COL \colon A\times B \into [10^{100}]$ only uses $2$ colors. \bigskip Fill in the $c$ and prove the resulting theorem: (By `prove' I mean show me the first few steps of the construction and hand-wave the rest.) \bigskip {\it \noindent 1) $\forall$ $\COL\colon \N\times\N\times \N \into [10^{100}]$ $\exists$ infinite $A,B,C\subseteq \N$ such that $\COL \colon A\times B\times C \into [10^{100}]$ only uses $c$ colors. \bigskip \noindent 2) $\exists$ $\COL\colon \N\times\N\times\N \into [c]$ such that there is no infinite $A,B,C\subseteq\N$ such that $\COL \colon A\times B\times C \into [c]$ only uses $c-1$ colors. } \vfill \centerline{\bf GO TO NEXT PAGE} \newpage \item (20 points) Prove that the following function exists: \bigskip $f(n)$ is the least $m$ such that there for every sequence of graphs $$G_1,G_2,\ldots,G_m$$ where the number of vertices in $G_i$ is $\le i+n$ there is an $i