\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 9. Due Monday, Apr 10,2006}
\end{center}
\noi {\tt Note:} NO CLASS Monday, April 24. LAST CLASS Monday, May 1
\ben
\item Let $D$ denote the unit disk in the plane with center $\vec{0}=(0,0)$.
Let $\vec{P}$ be at distance $1-s$ from the $\vec{0}$, $s\in (0,1)$. Let
$L$ be the line through $\vec{P}$ perpendicular to the line from $\vec{0}$
to $\vec{P}$. Then $L$ splits $D$ into two parts. Let $f(s)$ denote the
area of the smaller part.
\ben
\item Find $f(s)$ precisely.
\item Give an asymptotic formula $f(s)\sim As^B$ as
$s\ra 0^+$.
\item Let $\vec{P}_1,\ldots,\vec{P}_n$ be chosen uniformly and independently
from $D$. Call $\vec{P}_i$ {\em extremal} if, splitting $D$ by a line through
$\vec{P}_i$ as defined above, all the $\vec{P}_j$, $j\neq i$, lie in the
larger part. Find an exact formula (as an integral) for the expected number
of extremal points.
\item Find an asymptotic formula (as $n\ra\infty$) for the above formula.
(Note: The main term will be when $s$ is ``small" but finding the right
parametrization for $s$ in terms of $n$ is the key to the problem.)
(Remark: The convex hull of $n$ randomly chosen points has been the object
of much study.
Extremal points are necessarily on the convex hull, though the
converse is not true.)
\een
\item By a {\em dumbbell} we mean two cycles joined by a path.
Let $r,s$ denote the cycle lengths and $t$ the number of interior
points of the path so that the dumbbell has $k=r+s+t$ points.
\ben
\item Find the number of dumbbells with parameters $r,s,t$ on $n$ vertices.
\item Find an exact expression $A=A(n,p)$ for the expected number
of dumbbells in $G(n,p)$. The expression should be a sum over $k$ as above.
\item
Let $c<1$ be fixed and let $G\sim G(n,p)$ with $p=\frac{c}{n}$.
Prove (by showing $A(n,p)\ra 0$)
that almost surely $G$ does not contain a dumbbell.
\item (*) Let $p=\frac{1}{n}+\lam n^{-4/3}$ where $\lam=\lam(n)\ra -\infty$.
(This is known as the {\em subcritical} range.)
Prove (by showing $A(n,p)\ra 0$)
that almost surely $G$ does not contain a dumbbell.
[Note: Connected components of $G$ which are neither trees nor unicyclic are
called {\em complex}. Complex components either contain dumbbells or
something similar. Extending this analysis one can show that
complex components do not appear in the subcritical range.]
\een
\item Consider a branching process beginning with root Eve in which each
node independently has number of children given by a Poisson distribution
with mean one. List all possible outcomes (trees) for which the family
(including Eve) has precisely five nodes. For each give the probability
of obtaining that outcome. What is the total probability of getting a
family of size precisely five?
\item Consider a branching process beginning with root Eve in which each
node independently has number of children given by a Poisson distribution
with mean $c$.
\ben
\item What is the probability Eve has precisely two children?
\item What is the probability Eve has no children with precisely two
children?
\item Draw the family tree (including males) with root your maternal
grandmother. [If you'd rather not, just make one up or use your
officemate's grandmother.]
\item True or false: she had no children that had no children that
had no children.
\item With the branching process defined for Eve what is the probability
that she has no children that have no children that have no children?
\een
\item For $1\leq i0$ arbitrary and
asymptotics as $n\ra\infty$. Let $f(t)$ be the probability that
$1,2$ don't lie in the same component of $G(n,t)$ (with no conditioning).
Argue that $f^-(t)=f(t)+o(1)$. (This is part of a very general
principle that conditioning on an almost sure event changes a
probability by $o(1)$.)
\item (The meat of the problem.) Find the limiting value of $f(t)$
as a function $g(c)$. (There will be two cases and $g(c)$ may be
given implicitly. The key is to look at the almost sure picture of $G(t)$
given in class.)
\item For $K>0$ let $E_K[T]$ denote the sum of the lengths of the minimal
spanning tree, counting only lengths that are at most $K/n$. Express
$\lim_{n\ra\infty}E_K[T]$ as an integral.
\item It can be shown that $\lim_{n\ra\infty}E[T] =
\lim_{K\ra\infty}\lim_{n\ra\infty}E_K[T]$ and lets assume that.
(But I hope you see that this is {\em not} obvious. If, for example,
most of the weight from the minimal spanning tree came from
edges of weight between $n^{-1/2}$ and $2n^{-1/2}$ then it wouldn't
be true.) Given this assumption find $\lim_{n\ra\infty}E[T]$
as an integral. Evaluate the integral numerically.
\item (*) Express $\lim_{n\ra\infty}E[T]$ in a nice form which
overlaps the name of a movie star.
\een
\een
\begin{quote}
I think that it is a relatively good approximation to truth - which is
much too complicated to allow anything but approximations - that
mathematical ideas originate in empirics, although the genealogy is
sometime long and obscure. But, once they are so conceived, the subject
begins to live a particular life of its own and it is better compared
to a creative one, governed by almost entirely aesthetical motivations,
than to anything else and, in particular, to an empirical science.
\\ -- John von Neumann
\end{quote}
\end{document}