Homework 2 -- CORRECTION

A correction has been made to Problem (6c) on the homework. Thanks to Or for pointing out the mistake and giving the correction. The new statement (which is also in the file on the course home page) is:

c) Suppose we form $G'$ by blowing up each node $v$ in $G$ to a clique of size $2nk + w(v)$; we put either all possible edges or no possible edges between the "$u$-clique" and the "$v$-clique", depending on whether or not $(u,v)$ was an edge in $G$. Let $k' = 2nk^2 + r$, where $r \in [2nk]$ is chosen randomly. Show that if $G$'s maximum clique has size $< k$ then with probability $1$, $G'$ has no $k'$-clique; and, if $G$'s maximum clique has size $k$ then $G'$ has a unique $k'$-clique with probability at least $1/(4nk)$.