\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}
\newcommand{\noi}{\noindent}
\pagestyle{empty}
\begin{document}
\begin{center} \Large\bf{Random Graphs G22.3033-007\\
Assignment 7. Due Monday, March 27,2006}\\
\end{center}
\noindent {\tt Note}: Benny Sudakov will give the Math Colloquium
talk on Probabilistic Combinatorics on Monday, March 27,
at 3:45 p.m. in wwh 1302.
\ben
\item Set $\Omega = [n]\times [n]$. Define a random set
$C\subset \Omega$ by
\[ \Pr[(x,y)\in C] = p= \frac{c}{n} \]
the events $(x,y)\in C$ mutually independent. A horozontal
bond is a pair $(x,y),(x+1,y)\in C$ and a vertical bond
is a pair $(x,y),(x,y+1)\in C$. Find the expected number
of bonds. Use Janson's Inequality to bound the probability
there are no bonds in both directions and find the limiting
probability as $n\rightarrow\infty$.
\item Let $G\sim G(n,p)$ with $p=\frac{c}{n}$.
\begin{enumerate}
\item Condition on $12,13,23\in G$. Use Janson's Inequality
to find an asymptotic formula for the probability there are
no {\em other} triangles in $G$.
\item Find an asymptotic formula for the probability that
$G$ contains precisely one triangle.
\end{enumerate}
\item Find a positive constant $c$ so that there exists
a two-coloring of $K_n$ such that every subset of
size $\frac{n}{2}$ has discrepancy less than $(c+o(1))n^{3/2}$.
(The discrepency is the absolute value of the difference
between the number of edges of the two colors.)
Try to make $c$ as small as you can. (Of course, you'll
examine a random coloring!)
\item Let $G\sim G(n,p)$ with $p=cn^{2/3}$ and let $v,w$ be two distinct fixed
vertices of $G$. Use Janson's Inequality to find the limiting probability that
$v,w$ are {\em not} joined by a path of length three.
\een
\begin{quote}
Every Sunday my wife and I took a romantic little walk to
Grandchester, a lovely, lovely little town near Cambridge,
and we ate lunch at a pub there. We would stroll along the
road reciting pi to each other; she would do twenty places,
then I would do twenty and so forth.
\\ -- John Conway
\end{quote}
\end{document}