\documentstyle[11pt]{article}
\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}
\pagestyle{empty}
\begin{document}
\begin{center} \Large\bf{Random Graphs G22.3033-007\\
Assignment 2. Due Monday, February 6,2006}\end{center}
\ben
\item
Suppose $n \geq 2$ and let $A_1,\ldots,A_m\subseteq\Omega$ all have
size $n$. Suppose $m< 4^{n-1}$.
Show that there is a coloring of $\Omega$ by
$4$ colors so that no edge is monochromatic.
\item
Suppose $n \geq 4$ and let $A _1,\ldots,A_m\subseteq\Omega$ all have
size $n$. Suppose $m< \frac{4^{n-1}}{3^{n}}$.
Prove that there is a coloring of
$\Omega$ by $4$ colors so that in every edge all $4$
colors are represented.
\item
The expected number of isolated trees [just take this as a fact]
on $k$ vertices in $G(n,p)$ is given by $f(n,k,p):= {n\choose k}
k^{k-2}p^{k-1}(1-p)^B$ with $B=k(n-k)+{k\choose 2}-k+1$. Set
$p=\frac{1}{n}$. Let $c$ be a positive constant. Find the
asymptotics of $f(n,k,p)$ when $k\sim cn^{2/3}$. (*) Express
the limit as $n\ra\infty$ of the sum of $f(n,k,p)$ for
$n^{2/3}\leq k < 2n^{2/3}$ as a definite integral and use
a computer package to evaluate the integral numerically.
\item
Consider Boolean expressions on atoms $x_1,\ldots,x_n$. By
a $k$-clause $C$ we mean an expression of the form $y_{i_1}\vee \ldots
\vee y_{i_k}$ where each $y_{i_j}$ is either $x_{i_j}$ or
$\overline{x}_{i_j}$. Prove a theorem of the following form
[you fill in the $m=m(k)$] by the
probabilistic method: For any $m$ $k$-clauses $C_1,\ldots,C_m$ there
is a truth assignment such that $C_1\wedge\ldots\wedge C_m$ is satisfied.
\een
\begin{quote}
Working with Paul Erd\H{o}s was like taking a walk in the hills.
Every time when I thought that we had achieved our goal and
deserved a rest, Paul pointed to the top of another hill and
off we would go.
\\ -- Fan Chung
\end{quote}
\end{document}