\documentclass[11pt]{article}
\usepackage{fullpage}
\usepackage{amsmath,amsthm}
%\usepackage{clrscode3e}

\newtheorem{theorem}{Theorem}
\newtheorem{fact}[theorem]{Fact}

\newcommand{\deq}{:=}

\begin{document}
\begin{center}
{\huge \textbf{CS49/Math59 Lab 3} }
\end{center}
\vspace{0.2in} This lab assignment is due {\bf before the start of
  class} on Wednesday, October 7.  Homework handed in during class
but after I begin the lecture will be counted as late submissions.
Some things to note:
\begin{itemize}
\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.
\item In this problem set, you might need an estimate for $n!$.  The
  following asymptotic estimate is called \emph{Stirling's
    Formula.}
  $$n! \sim \sqrt{2\pi n} \left(\frac{n}{e}\right)^n\ .$$ Note: it
  will likely be easier to use a cruder, less accurate bound than
  Stirling's approximation.  For example, from Stirling's Formula, it
  is easy to see that $n! > (n/e)^n$ for all large $n$.
\end{itemize}
Make sure your names are on your submission, and show your work to
maximize partial credit.
\begin{enumerate}
\item \textbf{Analysis.} 
  In class, we saw that if ${n \choose k}\left(1-2^{-k}\right)^{n-k} <
  1$, then there is a tournament on $n$ players with property $S_k$.
  (i.e. for each group of $k$ players, there is another player that
  beats them all.)

  Let $f(k)$ be the least $n$ that satisfies property $S_k$.  Use the
  probabilistic method result to show that $f(k) = O(k^2 2^k)$.  In
  other words, show that there is an $n = ck^22^k$ for some constant
  $c$ such that the inequality holds.

\item \textbf{Increasing Sequences, Decreasing Sequences.}  A
  \emph{subsequence} of a sequence $a = (a_1,\ldots, a_n)$ is a sequence
  that can be obtained from $a$ by deleting items without reordering.
  For example, $a_3a_4a_n$ is a subsequence of $a$, and $bdek$ is a
  subsequence of $abcdefghijk$.

  For a sequence of numbers, an \emph{increasing} subsequence is a
  subsequence which is sorted in ascending order.  For example,
  $1,3,7,8$ is an increasing subsequence of $2,1,9,3,7,4,8,12$.
  Similarly, a \emph{decreasing} subsequence is a subsequence which is
  sorted in descending order.  For some applications, it is useful to
  try to \emph{avoid} long increasing or decreasing subsequences.

  Let $[n]$ denote the set of integers $\{1,\ldots, n\}$.  Show there
  is a constant $c$ and a way to permute $[n]$ so that the longest
  increasing or decreasing subsequence in the permuted sequence is
  less than $k$, for $k = c\sqrt{n}$.  For example, we can permute
  $[4]$ to get the sequence $(2,4,1,3)$, which has no increasing or
  decreasing sequence of length $3$.

  Try to find the smallest possible constant $c$.

\item \textbf{3sum-free Integers} A set of integers $A$ is is called
  \emph{3sum-free} if there are no $a_1,a_2,a_3,a_4 \in A$ such that
  $a_1+a_2+a_3 = a_4$.  Show that there is a constant $c>0$ such
  that every set $B$ of $n$ nonzero integers contains a
  \emph{3sum-free} set $A$ of size $|A|>cn$.  Try to find the largest
  possible constant $c$.

\item \textbf{Sparse Graphs with Near-Cliques.} 

  On a future lab assignment, you will solve the following problem:

  \textbf{(Alon and Spencer, problem 1.5)} Let $G$ 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$.

  For this lab, you will try to build some intuition.  Say $(i,j)$ is
  a \emph{non-edge} if $(i,j) \not\in G$.  Call a set of ten vertices
  $S$ a \emph{near-clique} if it contains exactly one non-edge.  Say
  that a nonedge $(i,j)$ belongs to a near-clique $S$ if $i,j \in S$.
  Call a graph $G$ ``near-clique-full'' if every non-edge belongs to
  at least one near-clique.

  The Alon/Spencer problem above asks you to show that any
  near-clique-full graph has at least $8n-36$ edges.
  \begin{enumerate}
  \item Consider a near-clique-full graph on $10$ vertices.  How many
    edges does it have?
  \item Describe a near-clique-full graph on $n$ vertices with exactly
    $8n-36$ edges.
  \item Suppose $G$ contains non-edges $(i,j)$ and $(i',j')$ that
    belong to near-cliques $S$ and $S'$ respectively.  What is the
    most number of edges that can belong to both $S$ and $S'$?  What
    is the least number of edges that belong to $S$ and $S'$?
  \end{enumerate}
\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}
