\documentclass{article}%
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}%
\setcounter{MaxMatrixCols}{30}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.00.0.2552}
%TCIDATA{CSTFile=40 LaTeX article.cst}
%TCIDATA{Created=Monday, November 10, 2008 13:20:00}
%TCIDATA{LastRevised=Saturday, November 29, 2014 22:00:18}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{<META NAME="DocumentShell" CONTENT="Standard LaTeX\Blank - Standard LaTeX Article">}
\newtheorem{theorem}{Theorem}
\newtheorem{acknowledgement}[theorem]{Acknowledgement}
\newtheorem{algorithm}[theorem]{Algorithm}
\newtheorem{axiom}[theorem]{Axiom}
\newtheorem{case}[theorem]{Case}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{conclusion}[theorem]{Conclusion}
\newtheorem{condition}[theorem]{Condition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{criterion}[theorem]{Criterion}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{solution}[theorem]{Solution}
\newtheorem{summary}[theorem]{Summary}
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\begin{document}

\title{Problems on small world}
\maketitle

1) A 3D grid is the graph consisting of vertices at points $\left(
x,y,z\right)  ,$ where each of these are integers, say all between $0$ and
$n,$ and two vertices are connected by an edge if ONE of their coordinates
differ by 1 and the others are the same (so there is an edge between $\left(
0,0,1\right)  $ and $\left(  0,1,1\right)  $). This is the obvious 3D
\textquotedblleft cube wireframe\textquotedblright\ analogy to the 2D grids we
considered. Suppose we add in one random edge to each vertex $v$ which goes to
another vertex $u$ with probability proportional to $d\left(  u,v\right)
^{-q}.$ Fix $v$ and let $R_{d}$ be the ring of vertices a distance at least
$d$ from $v$ and at most $2d$ from $v.$ What value should $q$ have so that the
probability that the random edge from $v$ jumps into $R$ can be bound by a
number independent of $d$ (and hence independent of the choice of ring $R_{d}%
$)? Justify your answer.

2) Go to wikipedia.com and try to find a short path from "Lynah Faithful" to
"Zona Zoo" using only links on each page. It may be helpful to know that
"Lynah Faithful" refers to hockey fans at Cornell University in Ithaca, NY,
and "Zona Zoo" refers to University of Arizona student fans. What is your strategy?

3) Consider the complete graph $K_{n}$, the path with $n$ vertices $P_{n},$
and the cycle with $n$ vertices. Compute the characteristic path length and
the clustering coefficient.

4) On the 2D grid, show that there are no more than $4i$ vertices a distance
$i$ from a given vertex, and no less than $i+1$ vertices a distance $i$ from a
given vertex.

5) Show that there are no more than $2^{2j+2}$ vertices in $B_{j}.$

In the next few questions, we see why our argument for decentralized search
does not work for $q\neq2.$ (Note that Kleinberg shows that you expect it to
take longer, but we are only seeing why our argument did not show these have
short paths.) We will consider the situation in the notes.

6) Show the estimates:

\ \ \ \ a)
\[
\sum_{w\neq v}d\left(  w,v\right)  ^{-q}\leq c
\]
for some constant $c$ if $q>2$ (hint: p-series converge for $p>1$!) and

\ \ \ \ b)
\[
\sum_{w\neq v}d\left(  w,v\right)  ^{-q}\leq\frac{1}{2-q}\left(  2n\right)
^{2-q}%
\]
if $q<2.$

7) If $q>2,$ show that the probability $P_{j}$ that a message in stage $j$
(i.e., the message is currently in $B_{j+1}$ but not $B_{j}$) enters $B_{j}$
after one step satisfies
\[
P_{j}\geq\frac{1}{c2^{2q+1}2^{\left(  q-2\right)  j}}%
\]
for the $c$ in problem 6.

8) If $q>2,$ show that our bound for the expected number of steps in phase $j$
is les than or equal to
\[
\sum_{i=1}^{\infty}\left(  1-\frac{1}{2^{\left(  q-2\right)  j}2^{2q+1}%
c}\right)  ^{i}\leq c2^{2q+1}2^{\left(  q-2\right)  j}%
\]
and so the expected number of steps $E$ in the myopic search is%
\begin{align*}
E  &  \leq2^{2q+1}c\sum_{j=1}^{\log_{2}n}2^{\left(  q-2\right)  j}\\
&  =2^{2q+1}c\left[  \frac{2^{\left(  q-2\right)  \left(  \log_{2}n+1\right)
}-1}{2^{\left(  q-2\right)  }-1}-1\right] \\
&  \leq Cn^{q-2}%
\end{align*}
for some $C$ depending only on $q.$ (Technically, this is only if $\log_{2}n$
is an integer, but this estimate is good enough.){}So the expected number of
steps is $n$ to a positive power.

9) If $q<2,$ show that the probablility $P_{j}$ that a message in stage $j$
(i.e., the message is currently in $B_{j+1}$ but not $B_{j}$) enters $B_{j}$
after one step satisfies
\[
P_{j}\geq\frac{\left(  2-q\right)  2^{\left(  2-q\right)  j}}{2^{2q+1}\left(
2n\right)  ^{2-q}}=C\frac{2^{\left(  2-q\right)  j}}{n^{2-q}}%
\]
for appropriate $C$ depending on $q$ but not on $j$ or $n.$

10) If $q<2,$ show that our bound for the expected number of steps in phase
$j$ is less than or equal to
\[
\sum_{i=1}^{\infty}\left(  1-C\frac{2^{\left(  2-q\right)  j}}{n^{2-q}%
}\right)  ^{i}\leq\frac{n^{2-q}}{C2^{\left(  2-q\right)  j}}-1
\]
and so the expected number of steps $E$ in the myopic search is%
\begin{align*}
E  &  \leq\sum_{j=1}^{\log_{2}n}\frac{n^{2-q}}{C2^{\left(  2-q\right)  j}}\\
&  \leq\frac{n^{2-q}}{C}\left[  \sum_{j=1}^{\infty}2^{-\left(  2-q\right)
j}\right] \\
&  =\left(  \frac{1}{C}\frac{2^{-\left(  2-q\right)  }}{1-2^{-\left(
2-q\right)  }}\right)  n^{2-q}\\
&  =C^{\prime}n^{2-q}%
\end{align*}
for some constant $C^{\prime}$ depending only on $q.$ So again it grows like
$n$ to a power.


\end{document}