\documentclass[11pt]{article}
\pagestyle{empty}
\begin{document}
\newcommand{\ben}{\begin{enumerate}}
\newcommand{\een}{\end{enumerate}}
\newcommand{\lam}{\lambda}
\newcommand{\eps}{\epsilon}
\newcommand{\gam}{\gamma}
\newcommand{\ah}{\alpha}
\newcommand{\del}{\delta}
\newcommand{\sig}{\sigma}
\newcommand{\ra}{\rightarrow}
\begin{center} \Large\bf{Random Graphs G22.3033-007\\
Assignment 1. Due Monday, January 30,2006}\end{center}
\ben
\item
The Bipartite Ramsey Number $BR(k)$ is the least $n$ so that if
$A,B$ are disjoint with $|A|=|B|=n$ and $A\times B$ is two colored
there exist $A_1\subseteq A, B_1\subseteq B$ with $|A_1|=|B_1|=k$ and
$A_1\times B_1$ monochromatic. Find and prove
a theorem which gives a lower bound for $BR(k)$ and
explore the asymptotics.
\item
Let $f(k)$ be the maximal $n$ for which there exists $p$ with $0\leq p\leq 1$
such that
\[ n^kp^{k^2/2} + n^{2k}(1-p)^{2k^2} \leq 1 \]
Let $U(k)$ be the maximal $n$ for which there exists such $p$ with
$n^kp^{k^2/2}\leq 1$ and $n^{2k}(1-p)^{2k^2}\leq 1$. Let $L(k)$ be the
maximal $n$ for which there exists such $p$ with $n^kp^{k^2/2}\leq \frac{1}{2}$
and $n^{2k}(1-p)^{2k^2}\leq \frac{1}{2}$.
\ben
\item Argue that $L(k)\leq f(k)\leq U(k)$
\item Find the asymptotics of $U(k)$. (Warning: Do {\em not} assume $p=o(1)$
because the optimal $p$ isn't!) Partial credit for $\lim_k U(k)^{1/k}$.
\item Find the asymptotics of $L(k)$, showing that it is the same as that
of $U(k)$. (That is, changing $1$ to $\frac{1}{2}$ had an asymptotically
negligible effect.)
\item Deduce the asymptotics of $f(k)$
\een
\item
Find asymptotic lower bounds on the Ramsey function $R(k,2k)$. That is, set
$g(k)$ to be
the maximal $n$ for which there exists $p$ with
$0\leq p\leq 1$ such that
\[ {n\choose k}p^{{k\choose 2}} + {n\choose{2k}}(1-p)^{{{2k}\choose 2}} < 1
\]
Find an asymptotic formula for $g(k)$.
(Note: You'll want to use the ideas of the previous problem. Still,
this is not an easy problem. Full marks for $\lim_k g(k)^{1/k}$ -- its
the same as $\lim_k f(k)^{1/k}$ but you have to prove this. The full asymptotics
are if you enjoy a challenge.)
\item
Find $m=m(n)$ as large as you can so that the following holds: Let
$A_1,\ldots,A_m\subseteq \{1,\ldots,4n\}$ with all $|A_i|=n$. Then
there exists a two coloring of $\{1,\ldots,4n\}$ such that none of
the $A_i$ are monochromatic. Use a random equicoloring of
$\{1,\ldots,4n\}$. Express your answer as an asymptotic function of
$n$.
\een
\end{document}