\documentclass{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{listings}
\usepackage{enumitem}
\usepackage{hyperref}
\usepackage{algorithmicx,algorithm}
\usepackage{algpseudocode}
\usepackage{float}

\usepackage{etoolbox}
\usepackage{url}
\usepackage[most]{tcolorbox}
\usepackage{xcolor}
% 0.0in to center
\setlength{\topmargin}{-.53in}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{0.0in}
\setlength{\evensidemargin}{0.0in}
\setlength{\textheight}{9in}
%\setlength{\parskip}{\medskipamount}
\setlength{\marginparwidth}{1.2in}
%\renewcommand{\baselinestretch}{1.3}

\lstset{
  language=Python,
  showstringspaces=false,
  formfeed=newpage,
  tabsize=4,
  commentstyle=itshape,
  morekeywords={models, lambda, forms}
}

\newcommand{\eps}{\epsilon}
\newcommand{\E}{\textbf{E}}
\newtheorem{theorem}                {Theorem}
\newtheorem{lemma}      [theorem]   {Lemma}
\newtheorem{remark}     [theorem]   {Remark}
\newtheorem{fact}       [theorem]   {Fact}
\newtheorem{claim}      [theorem]   {Claim}
\newtheorem{corollary}      [theorem]   {Corollary}
\newtheorem{definition}     [theorem]   {Definition}
\newtheorem{prop}       [theorem]   {Proposition}
\newtheorem{warning}        [theorem]   {Warning}

\def\proof{\rm \trivlist \item[\hskip \labelsep{\bf Proof. }]}
\def\endproof{\hfill $\rule{1.3ex}{1.3ex}$ \endtrivlist}

\newcommand{\ip}[2]{
{\langle {#1} , {#2} \rangle}
}
\newcommand{\n}[1]{
{\| {#1} \|}
}
\newcommand{\ns}[1]{
{\| {#1} \|^2}
}

\providetoggle{solution}
\settoggle{solution}{false}

\def\prop{{\em Proposition: }}
\def\L{\mathcal{L}}
\def\N{\mathcal{N}}
\def\C{\mathcal{C}}
\def\Z{\mathcal{Z}}
\def\Q{\mathcal{Q}}
\def\R{\mathcal{R}}
\def\P{\mathcal{P}}
\def\M{\mathcal{M}}
\def\B{\mathcal{B}}
\def\TV{$T \in \mathcal{L}(V)$ }
\def\pf{\noindent {\bf Proof Sketch: }}
%\def\limsup{\overline{\lim}}
%\def\liminf{\underline{\lim}}
\def\sm{\setminus}
\newtheorem{Alg}{Algorithm}
\newcommand{\myalg}[3]{
\medskip
\begin{footnotesize}
\fbox{
\parbox{6.2in}{\begin{Alg}\label{#1}{\textsc{ #2}}\\
{\texttt{ #3}}\end{Alg}
}}
\medskip
\end{footnotesize}}


\newcommand{\bfx}{{\bf x}}
\newcommand{\bfy}{{\bf y}}

\begin{document}

\begin{center}
{\Large CS265/CME309, Problem Set 6}

\begin{tabular}{rl}
SUNet ID(s): & \\
Name(s): & \\
\end{tabular}
\end{center}

By turning in this assignment, I agree by the Stanford honor code and declare that all of the writing is the work of my partner and I (discussion in larger groups is permissible).


\begin{center}
{\large Due by 11:59 PM on \textbf{Tuesday}, November 5th.}
\end{center}



\begin{enumerate}

\item (Probabilistic Method Practice)  Suppose we are investigating the social habits in a group of $n$ chimpanzees, and after months of observations, for some pairs of chimpanzees $A$ and $B$, we know whether $A$ has spent more time grooming $B$ or whether $B$ has spent more time grooming $A$.   We wish to aggregate these results into a single ranking of the 'altruism' of each chimpanzee that minimizes the number of ``inconsistent pairs'', where a pair $A,B$ is inconsistent/violated if $A$ is above $B$ in the ranking but has spent less time grooming $B$ than $B$ spent grooming $A$.
\begin{enumerate}
\item (4 points) Prove that there exists a ranking that violates at most half the pairwise relationships.  

\medskip

SOLUTION: XXX

\medskip

\item (4 points) Prove that for sufficiently large $n$, there exists a set of grooming habits such that for \emph{every} ranking, at least $49 \%$ of the pairwise relationships would be violated.  [Hint: probabilistic method---choose a distribution over the grooming habits, then argue that the probability a random ranking violates significantly less than half the pairwise relationships is so small, that there is a good chance you picked a set of grooming habits with the property that no 'good' ranking exists.] 

\medskip

SOLUTION: XXX

\medskip

\item (1 point) Prove that there exists a ranking that violates strictly less than half the pairwise relationships.

\medskip

SOLUTION: XXX

\medskip

\end{enumerate}

\item An \emph{edge coloring} of an (undirected) graph $G=(V,E)$ assigns exactly one color to each edge of the graph.  We say that a colored path in the graph is \emph{symmetric} if the path has an even number of edges, and the second half of the path is colored identically to the first half of the path (i.e. the sequence of colors in the second half of the path is the same sequence as in the first half).   [Throughout this problem, by ``path'' we refer only to simple paths---ie paths that do not re-use any edges.]

\begin{enumerate}
\item (4 points) Prove that for any graph whose maximum degree is $d$, there exists a coloring using $10 \cdot d^2$ colors such that there are no ``symmetric'' paths of length $4$ (i.e. no repeating paths consisting of 4 distinct edges). [Hint: Lovasz Local Lemma!] 
 \item (4 points) Given the setup in the previous part, give an algorithm that will find such a coloring in expected time polynomial in the size of the graph, and justify the runtime.  
\item (4 points)  Prove that there is some constant $C$ such that for any graph whose maximum degree is $d$, there exists a coloring using $C \cdot d^2$ colors such that there are no ``symmetric'' paths (of any length).
\end{enumerate}



\item Consider a set of equations over variables $x_1,\ldots,x_n$, where each equation has the form $a_1x_{i_1}+a_2x_{i_2}+\ldots + a_rx_{i_r} \equiv a_{r+1} \mod 17,$ for some $r$ (that might vary from equation to equation) and set of coefficients $a_1,\ldots,a_{r} \in \{1,2,\ldots,16\},$ and $a_{r+1} \in \{0,\ldots,16\}.$    Additionally, suppose that each variable, $x_i$, occurs in at most 4 equations.
\begin{enumerate}
\item (6 points) Prove that there exists an assignment to the variables such the \emph{none} of the equations are satisfied.
\item (2 points) Would your proof above continue to hold if the equations were modulo 18 rather than modulo 17?  Explain why or why not?
\end{enumerate}

\item Tightness of the Lovasz Local Lemma:  One version of the LLL that we saw asserts that for any set of events $A_1,\ldots,A_n$, such that for each $i$, $A_i$ is mutually independent of all but at most $d$ events, then as long as $Pr[A_i] \le \frac{1}{e(d+1)},$  then there is a nonzero chance of all events being simultaneously avoided.
\begin{enumerate}
\item (4 points) Define a set of events over a probability space such that each event is mutually independent of all but at most $d$ other events, and $Pr[A_i] \le 1/(d+1)$ for all $i$, but the probability of simultaneously avoiding all events $A_i$ is 0.  This shows that the constant $e$ in the statement of the LLL cannot be replaced by $1$.
\item (4 bonus points) For some constant $c>1$, prove that the constant $e$ in the LLL cannot be replaced by $c$.
\end{enumerate}
\end{enumerate}

\end{document}