\documentclass[11pt]{article}

\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amsthm}

\newtheorem{claim}{Claim}

\addtolength{\topmargin}{-2cm}
\addtolength{\textheight}{4cm}
\addtolength{\textwidth}{2cm}
\addtolength{\oddsidemargin}{-1cm}
\addtolength{\evensidemargin}{-1cm}

\newcommand{\E}{\mathbb{E}}
\renewcommand{\Pr}{\mathbb{P}}

\newcounter{saveenum}
\begin{document}

\noindent 
\begin{tabular*}{\textwidth}{@{\extracolsep{\fill}}lr}
{\large \textbf{18.434 Assignment 3}} & Due Monday 21 March, before class\\
\end{tabular*}
\vspace{0.2cm}
\hrule
\vspace{0.3cm}

\noindent Name all your collaborators. You must write your own solutions. Assignments must be done in LaTeX. Hand in electronically as a .pdf file to \texttt{olver@math.mit.edu}, using your first name as the filename.

\medskip

\begin{enumerate}
	\item \emph{(Ex 6.3)} Given an $n$-vertex undirected graph $G=(V,E)$, consider the following method of generating an independent set.
		Given a permutation $\sigma$ of the vertices, define a subset $S(\sigma)$ of the vertices as follows: for each vertex $i$, $i \in S(\sigma)$ if and only if no neighbour $j$ of $i$ precedes $i$ in this permutation $\sigma$.

		Write $d_i$ for the degree of vertex $i$, and $n=|V|$.

		\begin{enumerate}
			\item Show that for any permutation $\sigma$, $S(\sigma)$ is an independent set in $G$.
			\item Suggest a natural randomized algorithm to produce a random $\sigma$ and hence $S(\sigma)$, so that you can show
				\[ \E(|S(\sigma)|) \geq \sum_{i=1}^n \frac{1}{d_i+1}. \]
			\item Hence deduce that any $G$ has an independent set of size at least $\sum_{i=1}^n \frac{1}{d_i+1}$. 
		\end{enumerate}

	\item Recall the random graph model $G_{n,p}$ that we saw in class. Let $c$ be a positive constant, and choose $p=\frac{c\ln n}{n}$.
		\begin{enumerate}
			\item \emph{(Ex 6.13)} If $c < 1$, show (using the second moment method) that with high probability, $G_{n,p}$ has an isolated vertex, i.e., a vertex with no adjacent edges.
				In other words: for any $n$, let $I_n$ be the event that $G_{n,p}$ (with $p = \frac{c\ln n}{n}$) has an isolated vertex; show that
		\[ \Pr(I_n) \rightarrow 1 \qquad \text{as}\qquad n \rightarrow \infty. \]
	\item \emph{(Variation of Ex. 5.18)} Now show that for $c$ large enough (but constant), then with high probability, $G_{n,p}$ is \emph{connected} (there is a path from any vertex to any other vertex). (Note that this is \emph{not} the same as not having any isolated vertices, it is a much stronger property.) In other words, let $C_n$ be the event that $G_{n,p}$ is connected ($p$ as before); show that
		\[ \Pr(C_n) \rightarrow 1 \qquad \text{as}\qquad n \rightarrow \infty. \]
		\emph{I've put a hint for this question on the website. Also, if you prefer to do this with $G_{n,M}$ with $M=c\ln n$ (i.e., a random graph with exactly $M$ edges), as stated in Ex. 5.18, that's fine too.}
\end{enumerate}
In fact more is true: for b), only $c > 1$ is needed (but is harder to prove). This is yet another example of a threshold in random graphs.

\item Consider the following model of a distributed server system.
  There are $n$ machines.  At time zero $n$ jobs arrive and each chooses
  a random machine. Each round, a machine can only process a single job that has been assigned to it.
  The unprocessed jobs remain to be processed in future rounds.  We are interested in the number of rounds needed to
  process all the jobs. 
  \begin{enumerate}
	  \item Assume that each job stays on the machine it initially chose. 
		  With high probability, and within a constant factor, how many rounds are needed to complete all the jobs? 

	\setcounter{saveenum}{\value{enumii}}
  \end{enumerate}

  Now suppose that instead, at the beginning of each round, all remaining jobs randomly pick a machine to move to, uniformly at random. (The job could pick the machine it's currently assigned, in which case it won't move). 
  We will show that the number of rounds will be much less than in (a); it will be $O(\log \log n)$ with high probability.

  \begin{enumerate}
		  \setcounter{enumii}{\value{saveenum}}
	  \item Argue that if $\alpha n$ remaining jobs begin the round (with $\alpha n \geq \log n)$, then for some constant $c < 2$, the
  probability that more than  $\alpha^2/c n$ unprocessed jobs will remain at the end of the round is exponentially small.

	\item Using this, show the number of rounds is $O(\log\log n)$ with high probability.
	\end{enumerate}

	\emph{We will have a discussion about this question in the class on Wednesday, but I expect you to have spent some time thinking about it before then! There is an easier version of this problem as Ex. 5.11 in the book, you could also think about that.}
\end{enumerate}
\end{document}