\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{\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{\ACK}{{\rm ACK}} \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 752 Final for Spring 2026} \bigskip {\bf Exam START TIME:} 12:00PM (Noon) May 15 \bigskip {\bf Exam END TIME:} 6:00PM May 15 \bigskip {\bf My Expectation:} The exam should take between 2 and 3 hours, but feel free to take all 6. \bigskip {\bf Rules:} \begin{itemize} \item You CAN use your slides, notes, HW, and your brain. \item You CAN ask me a question of clarity by email. I may also be on zoom part of the day. \item You CANNOT use anything else. \item How will I enforce the rules? I am counting on your integrity and fine character. \item The exam is one 0-point problem (what is your name) and then four 20-point problems. So the totals to 80 points. The other 20 points are from the take-home part of the final. \item Exam starts on the next page. \end{itemize} \vfill \centerline{\bf GO TO NEXT PAGE} \newpage \begin{enumerate} \item (0 points) What is your name \vfill \centerline{\bf GO TO NEXT PAGE} \newpage \item If $X$ is a finite subset of $\N$ then $\min(X)$ is the smallest element of $X$. Recall that $\ACK$ is a very fast growing function of two variables. We want a fast growing function on one variable. Let $f(n)=\ACK(n,n)$. Note that $f$ is a fast growing function on one variable. \bigskip {\bf Def} Let $X$ be a finite subset of $\N$. $X$ is {\it superlarge} if $|X|> f(\min(X))$. Prove the following: {\it For every $k\in\N$ there exists $n$ such that, for every $\COL\colon \binom{k,k+1,\ldots,k+n}{3}\into [2]$ there exists a superlarge homog set.} \vfill \centerline{\bf NEXT PAGE IS BLANK IF YOU NEED IT} \newpage \vfill \centerline{\bf BLANK PAGE} \vfill \centerline{\bf GO TO NEXT PAGE} \newpage \item (20 points) Recall that infinite $a$-ary Ramsey Theorem: {\it For all $a\in\N$, for all $\COL\colon \binom{\N}{a}\into[2]$ there exists an infinite homog set.} We denote the above statement as $a$-ary IRT (Infinite Ramsey Theorem). Assume that you already know the 1-ary IRT, 2-ary IRT, $\ldots$, 99-ary IRT. Prove the 100-ary IRT. (Hint: There are many different proofs depending on which $a$-IRT you want to use infinitely often and which one at the end. Do the easiest one which is NOT the one that gives the best bounds when made finite.) \vfill \centerline{\bf GO TO NEXT PAGE} \newpage \item (20 points) Let $E$ be the equation $$x_1 + 2x_2 + 4x_3 - 8x_4 = 0$$ Give a finite coloring of $\N$ that has no mono solution in $\N$. Prove your coloring has no mono solution. (For this problem 0 is NOT an element of $\N$.) \vfill \centerline{\bf NEXT PAGE IS BLANK IF YOU NEED IT} \newpage \centerline{\bf BLANK PAGE} \vfill \centerline{\bf GO TO NEXT PAGE} \newpage \item (20 points) Recall that $W(k,2)$ is {\it the least $n$ such that, for all $\COL\colon [n]\into [2]$, there is a mono $k$-AP.} Use the probabilistic method to obtain a lower bound on $W(k,2)$. \vfill \centerline{\bf NEXT PAGE IS BLANK IF YOU NEED IT} \newpage \centerline{\bf BLANK PAGE} \vfill \centerline{\bf GO TO NEXT PAGE} \newpage \centerline{\bf NEXT TWO PAGES ARE SCRATCH PAPER FOR ANY PROBLEM} \vfill \centerline{\bf BLANK PAGE} \newpage \vfill \centerline{\bf NEXT PAGE IS SCRATCH PAPER FOR ANY PROBLEM} \newpage \centerline{\bf BLANK PAGE} \vfill \centerline{\bf THIS IS THE LAST PAGE} \end{enumerate} \end{document}