\documentclass[11pt]{article}
% Problem set: do not define TEMPLATE or SOL
% LaTeX template: define TEMPLATE but not SOL
% Solution: define both TEMPLATE and SOL
% \def\sol{1}
\def\template{1}
\usepackage{fullpage,graphicx}
\usepackage{amsmath,amsfonts,amsthm,amssymb,multirow}
\usepackage{algorithmic,comment,url,enumerate}
\usepackage{tikz}
\usepackage{framed}
\usepackage{xcolor}
\usepackage[ruled,vlined,commentsnumbered,titlenotnumbered]{algorithm2e}
\newcommand{\expecting}[1]{\noindent{[\textbf{We are expecting:} \em #1\em]}}
\newcommand{\hint}[1]{\noindent{[\textbf{HINT:} \em #1\em]}}
\newcommand{\fact}[1]{\noindent{\textbf{FACT:} \em #1\em}}
\newcommand{\pts}[1]{\textbf{(#1 pt.)}}
\newcommand{\sgn}{\mathrm{sgn}}
\definecolor{shadecolor}{gray}{0.95}
\newcommand{\clarification}[1]{\noindent{[\textbf{Clarification:} \em #1 \em]}}

\usepackage{mathtools}
\newcommand{\bE}{\ensuremath{\mathbb{E}}}
\newcommand{\bR}{\ensuremath{\mathbb{R}}}
\newcommand{\cE}{\ensuremath{\mathcal{E}}}
\newcommand{\eps}{\ensuremath{\epsilon}}
\newcommand{\rank}{\ensuremath{\mathrm{rank}}}
\newtheorem{theorem}{Theorem}

\begin{document}
\noindent
\textbf{Problem Set 6 \ifdefined\sol Solutions \fi} \hfill CS265, Autumn 2023
\ifdefined\sol\else
\newline
Due: Friday November 10, 11:59pm on Gradescope.
\ifdefined\template
\newline 
Group members: INSERT NAMES HERE
\fi

\vspace{.4cm}\noindent
Please follow the homework policies on the course website.
\fi

\noindent
\rule{\linewidth}{0.4pt}



\noindent\textbf{Note:} In this homework you may find the following inequality useful. When $x \in (0,1)$:
$$\exp\left(-\frac{x}{1 - x}\right) \leq 1 - x \leq \exp(-x).$$
A nice special case is that if $x \in (0, 1/2)$ then $1 - x \geq e^{-2x}$. 
Feel free to use these without proof!


\begin{enumerate}

%%%%%%%%%%%%%%%%%%%%%% Threshold for isolation %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\item \pts{10} \textbf{[Threshold for isolation]}

Recall that $G_{n,p}$ refers to a random graph with $n$ vertices, where each of the $\binom{n}{2}$ possible edges is present independently with probability $p$.

\begin{enumerate}


	\item \pts{2} Suppose that $p = 1.01\frac{\ln n}{n}$. Show that $G_{n, p}$ has an isolated vertex with probability $o(1)$.

	\item \pts{4} Let $X_1, X_2, ..., X_n$ be $0/1$ random variables that are \emph{not} necessarily independent, and \emph{not} necessarily identically distributed, and let $X = \displaystyle\sum_{i = 1}^n X_i$. Prove that
	\vspace{-.6cm}
	$$\bE[X^2] = \sum_{i = 1}^n \Pr[X_i = 1]\cdot\bE[X\mid X_i = 1].$$

	\item \pts{4} Suppose that $p = 0.99\frac{\ln n}{n}$. Show that $G_{n, p}$ has an isolated vertex with probability $1 - o(1)$.

	\hint{Consider using part (b) -- it might make the math simpler.}


\end{enumerate}

\ifdefined\template
\begin{shaded}
	\textbf{SOLUTION:}
	\ifdefined\sol
	\input{solution/isolation.tex}
	\fi
\end{shaded}
\fi

%%%%%%%%%%%%%%%%%%%%%% Echoing paths %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\item \pts{6} \textbf{[Echoing paths]}

\definecolor{colorC}{HTML}{648FFF}
\definecolor{colorA}{HTML}{DC267F}
\definecolor{colorB}{HTML}{FFB000}

\begin{figure}[h!]
\centering
\begin{tikzpicture}[scale=1]
\draw[line width=0.6mm,color=colorC] (2, 4) -- (3, 2);
\node at (2.7,3.1) {\textcolor{colorC}{$c$}};
\draw[line width=0.6mm,color=colorC] (2, 0) -- (3, 2);
\node at (2.3,1.1) {\textcolor{colorC}{$c$}};
\draw[line width=0.6mm,color=colorC] (5, 2) -- (6, 4);
\node at (5.3,3.1) {\textcolor{colorC}{$c$}};
\draw[line width=0.6mm,color=colorA] (0, 4) -- (1, 2);
\node at (0.7,3.1) {\textcolor{colorA}{$a$}};
\draw[line width=0.6mm,color=colorA] (4, 4) -- (3, 2);
\node at (3.3,3.1) {\textcolor{colorA}{$a$}};
\draw[line width=0.6mm,color=colorA] (6, 0) -- (5, 2);
\node at (5.7,1.1) {\textcolor{colorA}{$a$}};
\draw[line width=0.6mm,color=colorB] (1, 2) -- (2, 4);
\node at (1.3,3.1) {\textcolor{colorB}{$b$}};
\draw[line width=0.6mm,color=colorB] (5, 2) -- (4, 4);
\node at (4.7,3.1) {\textcolor{colorB}{$b$}};
\draw[line width=0.6mm,color=colorB] (7, 2) -- (6, 0);
\node at (6.3,1.1) {\textcolor{colorB}{$b$}};
\draw[fill=black] (2, 0) circle (2pt);
\node at (2,-0.3) {$v_4$};
\draw[fill=black] (6, 0) circle (2pt);
\draw[fill=black] (1, 2) circle (2pt);
\draw[fill=black] (3, 2) circle (2pt);
\node at (3.3,1.7) {$v_5$};
\draw[fill=black] (5, 2) circle (2pt);
\draw[fill=black] (7, 2) circle (2pt);
\node at (7,2.3) {$v_6$};
\draw[fill=black] (0, 4) circle (2pt);
\node at (0,4.3) {$v_1$};
\draw[fill=black] (2, 4) circle (2pt);
\node at (2,4.3) {$v_3$};
\draw[fill=black] (4, 4) circle (2pt);
\draw[fill=black] (6, 4) circle (2pt);
\node at (6,4.3) {$v_2$};
\end{tikzpicture}
\caption{An edge coloring of a graph with some echoing paths.}
\label{fig:graph}
\end{figure}

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{echoing} 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). For example, in Figure~\ref{fig:graph}, the paths from $v_1$ and $v_2$, from $v_3$ to $v_4$, and from $v_5$ to $v_6$ are all echoing paths. Edges are colored and labeled $a, b,$ or $c$ corresponding to their color.

Throughout this problem, by ``path'' we refer only to simple paths---i.e. paths that do not re-use any edges.


\begin{enumerate}
\item \pts{4} 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 echoing paths of length $4$ (i.e. no echoing paths consisting of 4 distinct edges, like the path from $v_5$ to $v_6$ in Figure~\ref{fig:graph}).

\hint{Lovasz Local Lemma!}

 \item \pts{2} 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 \pts{0} \textbf{[This problem is optional.]}  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 echoing paths (of any length).
\end{enumerate}


\ifdefined\template
\begin{shaded}
	\textbf{SOLUTION:}
	\ifdefined\sol
	\input{solution/echoing-paths.tex}
	\fi
\end{shaded}
\fi


%%%%%%%%%%%%%%%%%%%%%% Tightness of the Lovasz Local Lemma %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\item \pts{0} \textbf{[Tightness of the Lovasz Local Lemma]} 

\textbf{This whole problem is optional and will not be graded.}

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  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 \textbf{(Challenge!)} For some constant $c \in (1, e)$, prove that the constant $e$ in the LLL cannot be replaced by $c$.
\end{enumerate}


\ifdefined\template
\begin{shaded}
	\textbf{SOLUTION:}
	\ifdefined\sol
	\input{solution/tight-LLL.tex}
	\fi
\end{shaded}
\fi


\end{enumerate}
\end{document}
