\documentclass[11pt]{article}
\usepackage{handout2e}
\usepackage{url}
\begin{document}
\input{macros}
\input{courseMacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\head{CS7880}{Network Algorithms and Analysis}{Spring 2012}{27 January 2012}{1}

\begin{center}
\Large{\bf Problem Set 1 (due Friday, Feb 10)}
\end{center}

{\bf Problem 1 (10 points) $\lambda_2$ for Laplacian of $G(n,p)$} 

We have seen in class that the connectivity threshold in the $G(n,p)$
model is $p = \Theta((\ln n)/n)$.  In particular, we had shown that
when $p < (\ln n)/2n$, the graph is disconnected with high probability
(i.e., with probability $1 - o(1)$), and when $p > (4\ln n)/n$, the
graph is connected with high probability.  Note that much tighter
bounds on the connectivity threshold are known.

Give tight (high probability) bounds on the second smallest eigenvalue
of the Laplacian of $G(n,p)$ for the corresponding cases: (a) $p < (\ln
n)/2n$ and (b) $p \ge (4\ln n)/n$.

{\bf Problem 2 (10 points) Eigenvalues of the hypercube} 

The $n$-dimensional hypercube is the graph $G = (V, E)$ with $V = \{0,
1, \ldots, 2^n - 1\}$ and the set $E$ given as follows: $(i,j)$ is in
$E$ if the binary representations of $i$ and $j$ differ in exactly one
bit.  Find all the eigenvalues of the Laplacian of the hypercube
graph.

{\bf Problem 3 (10 points) Graph properties and the Laplacian
  spectrum}

The independence number of a graph $G$ is the size of the largest set
$S$ of vertices such that there are no edges between any two vertices
in $S$.  The chromatic number of a graph $G$ is the smallest number of
colors needed for coloring the vertices such that no two adjacent
vertices are of the same color.  The diameter of the graph is the
maximum pairwise distance in the graph, where the distance between any
two vertices is the length of the shortest path between the vertices.
Below, $\lambda_n$ is the largest eigenvalue and $\lambda_2$ is the
second smallest eigenvalue.

\begin{itemize}
\item[{\bf (a)}] Prove that the independence number of a $d$-regular
graph is at most $N (1 - d/\lambda_n)$.

\item[{\bf (b)}] Prove that the chromatic number is at least
  $\lambda_n/(\lambda_n - d)$.

\item[{\bf (c)}] Prove that the diameter of $G$ is at most $4d (\log
  n)/\lambda_2)$.
\end{itemize}

{\bf Problem 4 (10 points) Laplacian spectrum and $k$-partition}

Let $G = (V,E)$ be an undirected graph and let $V_1, \ldots, V_k$
denote a partition of the vertex set with $|V_i| = n/k$ (assume $n$ is
divisible by $k$).  Let $e_k$ denote the number of edges with
endpoints in two different sets of the partition.  Let $0 = \lambda_1
\le \lambda_2 \le \ldots \le \lambda_n$ denote the eigenvalues of the
Laplacian of $G$.  Prove that 

\[
\frac{n}{k} \sum_{i = 2}^{k} \lambda_i \le 2e_k \le \frac{n}{k}
\sum_{i=n-k+2}^{n} \lambda_i.
\]

{\bf Problem 5 (10 points) PageRank on the Wikipedia dataset}

Write a program for computing the PageRank vector for a given directed
graph, and apply it to the Wikipedia dataset (from 2009) available at

\url{http://haselgrove.id.au/wikipedia.htm}

You do not need to submit your solution to this problem.

\end{document}