\documentclass[12pt,ifthen]{article}
\usepackage{url}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{html}
\usepackage{hyperref}
\newcommand{\spec}{{\rm spec}}
\newcommand{\D}{{\sf D}}
\newcommand{\N}{{\sf N}}
\newcommand{\Z}{{\sf Z}}
\newcommand{\Q}{{\sf Q}}
\newcommand{\into}{{\rightarrow}}
\newcommand{\ceil}[1]{\lceil #1 \rceil}
\newcommand{\COL}{{\rm COL}}
\newtheorem{theorem}{Theorem}

\begin{document}

\centerline{\bf TAKE HOME MIDTERM FOR  CMSC 752}
\centerline{\bf Morally Due April 1}
\centerline{\bf Dead Cat Day April 3}

\bigskip
{\bf Rules} Same as the HW: You can get help but you must understand
and hand in your own work. You can use ChatGPT if you want to hand in
answers that are really bad. 

\bigskip
There are four problems and they add up to 100 points. 

\newpage 

\begin{enumerate}

\item
(25 points) 
Let $L$ be an ordered set.

Let $\COL\colon L\into [d]$.

A set $H$ is {\it $c$-homog (relative to $\COL$)}
if $\COL$ restricted to $H$ takes on $\le c$ values. 


\begin{enumerate}
\item
(15 points) 

Find $c$ such that the following is true:

\begin{itemize}
\item 
For all $d$, 
for all $\COL\colon \Q \into [d]$ there exists 

a $c$-homog set $H\equiv \Q$. 
\item
There exists $\COL\colon \Q \into [c]$ such that there are no $c-1$-homog sets
$H\equiv \Q$. 
\end{itemize}

\item
(10 points) 
Let $L= \Z + \cdots + \Z$ (there are $n$ copies of $\Z$). 

Find $c$ such that the following is true:

\begin{itemize}
\item 
For all $d$, 
for all $\COL\colon L\into [d]$ 

there exists a $c$-homog set $H\equiv L$. 
\item
There exists $\COL\colon L\into [c]$ such that there are no $c-1$-homog sets
$H\equiv L$. 
\end{itemize}
\end{enumerate}

\newpage

\item 
(25 points)
For this problem you may assume the following

$R_a(k)$ is the least $n$ such that every $\COL \colon \binom{[n]}{a}\into[2]$ has a homog 
set of size $k$.

For this problem you may assume the following:

$R_1(k)\le 2k$

$R_2(k)\le 2^{2k}$

$R_3(k)\le 2^{2^{4k}}$. 

(These are not the best known upper bounds but use them as the math will be neater.) 

Fill in the function $XXX(k)$ in the statement below so that the statement is true.
Prove your statement. 
Try to use an $XXX(k)$ that is small.

{\it For all $k$ there exists $n=XXX(k)$ such that, for all 
triples of colorings:

$\COL_1\colon [n] \into [2]$

$\COL_2\colon \binom{[n]}{2} \into [2]$

$\COL_3\colon \binom{[n]}{3} \into [2]$

there exists $H$ of size $k$ such that

$H$ is homog for $\COL_1$ (all elements of $H$ map to same color).

$H$ is homog for $\COL_2$ (all elements of $\binom{H}{2}$ map to the same color).

$H$ is homog for $\COL_3$ (all elements of $\binom{H}{3}$ map to the same color).
}


\newpage


\item 
(30 points) 
This problem has three parts: $a$, $b$, $c$. 

In this problem we will guide you through a proof of a theorem;
however, you will need to fill in the XXX. Here is the theorem:


{\bf Theorem} 
{\it Let $c\ge 2$.
Let $n= XXX(c)$.
For all $\COL\colon \binom{[n]}{2}\into[c]$ 
there exists a monochromatic $C_4$. 
That is, four distinct vertices $a,b,c,d$ such that
$\COL(a,b)=\COL(b,c)=\COL(c,d)=\COL(d,a)$.
($XXX(c)$ will be a polynomial.) 
}

\bigskip 

{\bf Proof} 

{\it Plan} We will find a function $E(n)$ such that any graph with $n$ vertices
and $E(n)$ edges has a $C_4$. We will then find an $n=XXX(c)$ such 
that, for all $\COL\colon \binom{[n]}{2}\into[c]$, some color occurs in $E(n)$
edges. That subgraph must have a $C_4$, which will be the desired monochromatic $C_4$. 

Let $G=(V,E)$ where $V=[n]$.  Assume $G$ does not have $C_4$. (We are not
going towards a contradiction. We will instead get an upper bound on $|E|$.) 

{\it Notation} 

\begin{equation}
e_{ij}=
\begin{cases}
1 & \hbox{ if $(i,j)\in E$}\\
0 & \hbox{ if $(i,j)\notin E$ or $i=j$}\\
\end{cases}
\end{equation}

\begin{enumerate}
\item 
(10 points) 
Let $a,b\in V$. Show that

$$\sum_{i=1}^n e_{ai}e_{ib} \le 1.$$

\newpage 

\item
(10 points) 
Assuming the result of Part 1 we have

$$\sum_{i=1}^n e_{ai}e_{ib} \le 1.$$

We now take a summation over $a$ and over $b\ne a$ on both sides.

$$
\sum_{a=1}^n \quad \sum_{b=1,b\ne a}^n \quad \sum_{i=1}^n e_{ai}e_{ib} \le 
\quad \sum_{a=1}^n\sum_{b=1,b\ne a}^n 1.$$

$$\sum_{i=1}^n \sum_{a=1}^n \quad \sum_{b=1,b\ne a}^n e_{ai}e_{ib} \le n(n-1).$$

$$\sum_{i=1}^n \sum_{a=1}^n e_{ai}\quad  \sum_{b=1,b\ne a}^n e_{ib}\le n(n-1).$$

Note that $\sum_{b=1,b\ne a}^n e_{ib}\in \{\deg(i),\deg(i)-1\}$, so 

$$\sum_{b=1,b\ne a}^n e_{ib}\ge \deg(i)-1.$$

Hence we have

$$\sum_{i=1}^n \sum_{a=1}^n e_{ai} (\deg(i)-1)\le n(n-1).$$

$$\sum_{i=1}^n (\deg(i)-1)\sum_{a=1}^n e_{ai} \le n(n-1).$$

$$(\sum_{i=1}^n (\deg(i)-1))\deg(i) \le n(n-1).$$

$$(\sum_{i=1}^n (\deg(i)-1))\deg(i) \le n(n-1).$$

$$\sum_{i=1}^n \deg(i)^2 - \sum_{i=1}^n \deg(i) \le n(n-1).$$

Finally, here is the problem:

Show that 

$$\sum_{i=1}^n \deg(i) \le 0.5n  + n\sqrt{n-0.75}$$

{\bf Hint} Use the Cauchy-Schwartz Inequality AND the Quadratic Formula.

\newpage

\item 
(10 points) 
We have 

$$\sum_{i=1}^n \deg(i) \le 0.5n + n\sqrt{n-0.75}$$

Since $\sum_{i=1}^n \deg(i) = 2|E|$ we have

$$2|E| \le 0.5n + n\sqrt{n-0.75}$$

$$|E| \le 0.25n  + 0.5n\sqrt{n-0.75}$$

So we have the following:

\bigskip

{\it Let $G=(V,E)$. 

If $G$ has no $C_4$ subgraph then $|E| \le 0.25n  + 0.5n\sqrt{n-0.75}$}

\bigskip

Take the contrapositive:

\bigskip

{\it Let $G=(V,E)$. 

If $|E| > 0.25n  + 0.5n\sqrt{n-0.75}$ then $G$ has a $C_4$ subgraph.}

\bigskip

Finally, here is the problem:

Find a polynomial $XXX(c)$ such that the following is true, and prove it:

{\it Let $c\ge 2$. Let $n=XXX(c)$. Then for all $\COL\colon \binom{[n]}{2}\into[c]$
there exists a monochromatic $C_4$.}

\end{enumerate}

\newpage
\item
(20 points) 
Recall that $5\omega = \omega  + \omega + \omega + \omega + \omega$. 

Let $\COL\colon \binom{5\omega}{3} \into [10^{10}]$. 

A set $H$ is {\it $c$-homog (relative to COL)} if $\COL$ restricted to
$\binom{H}{3}$ takes only $c$ colors. 

Find a number $c$ such that the following is true, and prove both statements.

\begin{itemize}
\item
For all $\COL\colon \binom{5\omega}{3} \into [10^{10}]$ there exists a
$c$-homog set $H\equiv 5\omega$. 
\item
There exists $\COL\colon \binom{5\omega}{3} \into [c]$ there is no
$c-1$-homog set $H\equiv 5\omega$. 
\end{itemize}

A student asked if I allow you to use the result for 
$\binom{5\omega}{2}$ from the HW.

I said YES.

Then the student said {\it WAIT! That doesn't work!}

My verdict: You can use it but it might not help. 


\end{enumerate}


\end{document}

