\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 3. Due Monday, February 13,2006}\end{center}
\ben
\item Let $X_1,\ldots,X_n$ be independent random variables with
$\Pr[X_i=+1]=\Pr[X_i=-1]=\frac{1}{2}$. Set $X=X_1+\ldots+X_n$.
Find $E[X^2]$ precisely. Find $E[X^4]$ precisely. [Idea: Expand
and use linearity of expectation.]
\item Use the alteration method as discussed in class to find a lower
bound to the Ramsey Number $R(3,t)$. [To give you a head start, let the
Red probability be $\epsilon n^{-2/3}$ for some small $\epsilon$,
where $n$ is the number of vertices.]
\item
\ben
\item
Find an asymptotic formula for
\[ \sum_{k=n^{1/2}}^{2n^{1/2}} (n)_kn^{-k} \]
by parametrizing $k=cn^{1/2}$ and turning it into an integral
which can be evaluated numerically.
\item (*)
Find an asymptotic formula for
\[ \sum_{k=1}^n (n)_kn^{-k} \]
(Idea: Show that the sum over $k\leq \eps n^{1/2}$ and over $k\geq Kn^{1/2}$
are (relatively) negligible for $\eps,K$ small and large respectively. The
sum over $\eps n^{1/2}\leq k\leq Kn^{1/2}$ becomes an integral. As $\eps\ra 0$
and $K\ra\infty$ and becomes an integral from $0$ to $\infty$ which has a
nice closed form.)
\een
\item Prove, for $m=m(n)$ as large as you can, the existence of
an $n\times n$ matrix $A$ of zeroes and ones with $m$ ones which does not
contain a $3\times 3$ submatrix of all ones. Use the alteration method:
make each entry one with probability $p$ and then for each such submatrix
change a one to zero. When you optimize [using Calculus!]
your final answer should be of the form $m\sim an^b$ for some
reasonable $a,b$.
\pagebreak
\item Set $X=\sum_{i=1}^n X_i$ where $X_i=\pm 1$ uniformly and independently.
Bound $\Pr[X>\frac{n}{2}]$ as follows.
\ben
\item Find a closed form for $E[e^{\lam X_i}]$.
\item Find a closed form for $E[e^{\lam X}]$.
\item Use the Chernoff Bound $\Pr[X>a] < E[e^{\lam X}]e^{-\lam a}$ with
$a=\frac{n}{2}$. Use
Calculus (this gets a little messy to put in closed form,
full points for numerical answers) to select the the optimal $\lam$.
\item Compare this with the lower bound \[ \Pr[X\geq \frac{n}{2}] \geq
\Pr[X=\frac{n}{2}] = 2^{-n}{n\choose \frac{3n}{4}} \]
showing that the upper and lower bounds have the same main terms.
\een
\een
\begin{quote}
It surprised him that he didn't dance very well. He had danced a lot in
Connecticut, rather than make conversation, yet his finesse had flattened
along one of those hyperbolic curves that computers delight in projecting.
Men had been wrong ever to imagine the universe as a set of circles; in
reality, nothing closes, everything approaches, but never quite touches,
its asymptote.
\\ from {\em I Will Not Let Thee Go, Except Thou Bless Me} by John Updike
\end{quote}
\end{document}