\documentclass[11pt]{article}
\usepackage{fullpage}
\usepackage{amsmath}

\newtheorem{fact}{Fact}
\newcommand{\deq}{:=}

\begin{document}
\begin{center}
{\huge \textbf{CS49/Math59 Lab 4} }
\end{center}
\vspace{0.2in} This lab assignment is due {\bf before the start of
  class} on Wednesday, October 21.  Homework handed in during class
but after I begin the lecture will be counted as late submissions.
Some things to note:
\begin{itemize}
\item This is a \textbf{one week lab}.  It is due the Wednesday after
  break.  While you are welcome to work over break, you shouldn't need
  to, \textbf{assuming you start early.}
\item I encourage you to write your solution using \LaTeX, but you are not
required to.
\item You may have one partner for this assignment, but are not required to.
If you work with a partner, submit just one writeup.
%
\item Aside from your partner, you should not discuss problems in detail
with anyone.  It's OK to discuss approaches at a high level.  In fact,
I encourage you to discuss general strategies.  However, you should
not reveal specific details of a solution, nor should you show your
written solution to anyone else.
\end{itemize}
Make sure your names are on your submission, and show your work to
maximize partial credit.
\begin{enumerate}
\item \textbf{Variance.} 

  \textbf{(Shoup 8.24)} Let $X \in \{0,1\}$ be a random variable.
  Show that $Var[X] \leq 1/4$.

\item \textbf{(Alon/Spencer 1.5)} Let $G = (V,E)$ be a graph on $n
  \geq 10$ vertices, and suppose that if we add to $G$ any edge not in
  $G$, the number of cliques on ten vertices increases.  Show that the
  number of edges in $G$ is at least $8n-36$.

  \textbf{Hint:} Use the Set Systems problem from lab.  Let the
  elements that compose sets come from $\Omega \deq V$.  For each
  non-edge $(i,j)$ create a pair of sets $(A_i,B_i)$.  You'll need to
  choose $A_i,B_i$ cleverly, so that for any $i$ $A_i,B_i$ are
  disjoint, but for $i\neq j$, the sets $A_i,B_j$ intersect.  Then
  appeal to the set systems theorem to show that there cannot be too
  many non-edges.

\item \textbf{(Alon/Spencer 2.9)} Let $G = (V,E)$ be a bipartite graph
  with $n$ vertices, and for each $v \in V$, let $S(v)$ be a list of
  \textbf{more than} $\log_2 n$ colors.  Prove there is a proper coloring\footnote{a
    ``proper coloring'' of $G$ is a coloring of the vertices so that
    no edge has endpoints colored the same.} of $V$ such that each
  vertex $v$ is colored some color from $S(v)$.

  \textbf{Hint:} Let $L,R$ be the two sides of the bipartite graph
  (i.e. $V = L \cup R$, and the only edges connect vertices in $L$ to
  vertices in $R$).  Try to cleverly assign the colors to $L$ and $R$
  so that no color is used on vertices both in $L$ and in $R$.  As
  long as every vertex in $L$ has some color in their list that's been
  assigned to $L$, argue that you're safe to use this color.

\item \textbf{Attribution.}  Did you get assistance on any of the
  problems on this assignment from anyone aside from me and/or your
  lab partner?  For example, did you discuss any problems at a high
  level with other students?  Did you accidentally stumble on
  solutions while doing a websearch on related material?  If so,
  descibe the nature of the assistance here.  (e.g. ``We briefly
  discussed problem 1 with X,Y, and Z'' or ``We saw a solution on
  $\langle$this website$\rangle$ before finding our own solution'') If you (and your
  partner) worked alone, please say so here.
\item \textbf{Lab Questionnaire.} (None of these questions will have
  an impact on your grade, this is to help provide the feedback I need
  to make the course the best it can be)
  \begin{enumerate}
  \item Approximately how many hours per partner did you spend on this
    lab?
  \item How difficult did you find this lab?  (enter a number 1-5,
    with 5 being very difficult and 1 being very easy)
  \item Describe the biggest challenge you faced on this lab.
  \end{enumerate}
\end{enumerate}
\end{document}
