\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 5. Due Monday, March 6,2006}\end{center}
\ben
\item
Show that the complete graph on $k$ vertices is strictly balanced. Show
that all trees are strictly balanced.
\item Let $X$ be the number of {\em isolated} triangles in $G(n,p)$ with
$p=\frac{c}{n}$. Last assignment you computed $E[X]$. Now find a good
upper bound on $Var[X]$ (Hint: The contribution from the covariances
will be negligible and you'll only need coarse upper bounds there.) Use Chebyschev's Inequality to deduce that
$X$ becomes sharply concentrated about its mean as $c$ gets large.
More precisely, letting
$\mu$ denote the mean, show $\lim_{c\ra\infty}\Pr[|X=\mu|>\eps\mu]\ra 0]$.
\item Let $x$ be chosen uniformly from $\{1,\ldots,n\}$. Set $m=n^{1/10}$.
For $p$ prime, $p\leq m$ let $X_p$ be the indicator random variable for
$p$ dividing $x$. Let $X=\sum X_p$, the sum over all primes $p\leq m$.
Set $\mu_p=E[X_p]$ and $\mu=E[X]$.
\ben
\item Show
$E[(X-\mu)^4] \sim 3(\ln\ln n)^2$.
[This is one of the steps toward the Erd\H{o}s-Kac theorem. Use as a
fact that $\sum_{p\leq m}p^{-1} \sim \ln\ln m \sim \ln\ln n$. You'll
want, similarly to a previous assignment, to expand the fourth power and
consider the different cross terms. The main term shall come from
$\sum_{p\neq q} E[(X_p-\mu_p)^2(X_q-\mu_q)^2]$ -- for the other terms
one can get away with rougher upper bounds, as long as you show the
contribution is $o((\ln\ln n)^2)$.]
\item The Turan Theorem can be written in the following way: For any
positive $\lambda$ the number of $x$ with $1\leq x\leq n$ with
$|v(x)-\ln\ln n| > \lambda (\ln\ln n)^{1/2}$ is at most
$\lambda^{-2}n$. This comes from Chebyschev but lets see it
directly: Each such $x$ would contribute $\frac{1}{n}\lambda^2\ln\ln n$
to $E[(X-E[X])^2]$ (the $\frac{1}{n}$ being the probability of
selecting $x$) so since, as we showed, $E[(X-E[X])^2]\sim \ln\ln n$
this can only happen at most $\lambda^{-2}n +o(n)$ times.
Now for the problem:
Use the result of the first part to find a new bound on the number
of $x$ with $1\leq x\leq n$ with $|v(x)-\ln\ln n|>\lambda(\ln\ln n)^{1/2}$.
Your bound should be better than the Turan bound for $\lambda$
appropriately large.
\een
\item Consider a drawing (in the intuitive sense) of a graph $G$ on the plane
with $v$ vertices, $e$ edges and $\kappa$ crossings. [When $P,Q,R,S$ are
distinct vertices and the edges $PQ,RS$ cross that counts as one crossing.]
In this exercise we find a lower bound for $\kappa$ as a function of $v,e$.
If you don't get part $i$ please assume it and go on to part $i+1$.
\ben
\item Show that if $\kappa=0$ then $e\leq 3v-6$. (A classic result,
involving no probability.)
\item Show that $\kappa\geq e-(3v-6)$. (Easy once you see it.)
\item Take a random subset $U$ of the vertices, where for each vertex $P$
$\Pr[P\in U] = p$ (for the moment, a parameter) and these events are
mutually independent. Let $X,Y,Z$ be the expected number of vertices,
edges and crossings respectively in the restriction of the drawing to $U$.
Show $E[X]=vp$, $E[Y]=ep^2$ and $E[Z]=\kappa p^4$.
\item From parts two and three give a condition on $\kappa$ of the form:
For all $p\in [0,1]$ yadda yadda yadda.
\item For technical convenience replace part two by $\kappa\geq e-3v$ and
make the appropriate replacement in part four. Now use your calculus
skills to derive a theorem in the form
\begin{center} If $e$ is at least blip blip blip then $\kappa$ is at
least blah blah blah \end{center}
The blip blip blip condition will simply reflect that $p$ must lie in
$[0,1]$.
\een
\een
\begin{quote}
Dear Sir,
\par I beg to introduce myself to you as a clerk in the Accounts Department
of the Port Trust Office at Madras on a salary of only \pounds 20 per
annum. I am now about 25 years of age. I have no University education but
I have undergone the ordinary school course. After leaving school I have
been employing the spare time at my disposal to work at Mathematics\ldots
I am striking out a new path for myself. I have made a special investigation
of divergent series in general and the results I get are termed
by the local mathematicians as ``startling" \\ -- Ramanujan
\end{quote}
\end{document}