\documentclass{article}
\usepackage{amssymb}
\usepackage{multicol}
\usepackage{graphicx}
\usepackage{color}
\usepackage{amsthm}
\usepackage{hyperref}
\usepackage{amsmath}
\usepackage{verbatim}
\usepackage{caption}
\usepackage{subcaption}
\usepackage{amsmath, epsfig}
\setlength{\parskip}{8pt}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
%\theoremstyle{Remark}
%\newtheorem{remark}
\renewcommand{\today}{}
\newcommand{\abs}[1]{\left| #1\right|}
\newcommand{\Lap}[1]{\mathcal{L}\left\{#1\right\}}


\addtolength{\topmargin}{-.875in}
\addtolength{\textheight}{1.75in}

\newcommand{\solution}[1]{
\color{red}\begin{quote}Solution:\quad 
\color{black} #1
\end{quote}\color{black}
}
\newcommand{\ba}{\backslash}
\newcommand{\Ber}{\hbox{Ber}}
\newcommand{\p}[1]{\mathbb{P}\left(#1\right)}
\newcommand{\e}[1]{\mathbb{E}(#1)}
\newcommand{\Po}[1]{\hbox{Po}(#1)}
\newcommand{\var}[1]{\hbox{Var}(#1)}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\floor}[1]{\left\lfloor #1\right\rfloor}
\newcommand{\C}{\mathbb{C}}
\DeclareMathOperator{\Diam}{diam}
\newcommand{\diam}[1]{\Diam\left(#1\right)}


\begin{document}
\title{Math 301 Homework}
\author{Mary Radcliffe}
\date{Due 13 October 2017}
\maketitle

Complete the following problems. Fully justify each response.

\begin{enumerate}

\item Prove the following generalized Local Lemma. Let $A_1, A_2, \dots, A_n$ be events in a probability space, and let $G$ be a dependency graph on the $A_i$. Suppose there exists a sequence of numbers $x_1, x_2, \dots, x_n\in[0, 1)$ such that for all $i$,
\[\p{A_i} \leq x_i\prod_{A_i\sim A_j} (1-x_j).\]
Then \[\p{\bigcap A_i^c}\geq \prod_{i=1}^n (1-x_i)>0.\]

\item Let $G$ be a graph. A proper coloring of $G$ is called $\beta$-frugal if for every vertex $v\in V(G)$, no color is used more than $\beta$ times to color $N(v)$.

In this problem, we will use the generalized Lovasz Local Lemma to show that if the maximum degree $\Delta$ in $G$ satisfies $\Delta \leq \beta^\beta$, then $G$ has a $\beta$-frugal coloring using at most $C=16\Delta^{1+1/\beta}$ colors. This problem is difficult so I have here broken it up into steps to help you along.

Randomly color the vertices of $G$ with $C$ colors.
\begin{enumerate}
\item  For $u\sim v$, define $A_{uv} = \{u, v\hbox{ have the same color}\}$. Show that $\p{A_{uv}} = \frac{1}{C}$.
\item For $x_1, x_2, \dots, x_{\beta+1}$ a set of vertices having a common neighbor, define $B_{x_1, \dots, x_{\beta+1}}$ to be the event that $x_1, x_2, \dots, x_{\beta+1}$ are all the same color. Show that $\p{B_{x_1, \dots, x_{\beta+1}}}\leq \frac{1}{C^\beta}$.
\item Explain why it is sufficient to show that
\[\p{\left(\bigcap A_{uv}^c\right)\cap \left(\bigcap B_{x_1, \dots, x_{\beta+1}}^c\right)}>0\]
in order to resolve the claim.
\end{enumerate}

We will use the structure of the generalized local lemma here. We have two types of events to consider: $A$-type events and $B$-type events. Notice, then, in the dependency graph, that we will have two different kinds of degrees to consider, since these two types of events will give us different intersections.

\begin{enumerate}
\item[(d)] Explain why we can take the edges in the dependency graph precisely to be between two events whose corresponding vertex sets intersect.
\item[(e)] Show that an $A$-type event is adjacent to at most  $2\Delta$ other $A$-type events, and at most $2\Delta{\Delta\choose \beta}$ $B$-type events. Call these values $d_{AA}$ and $d_{AB}$, respectively.
\item[(f)] Show that a $B$-type event is adjacent to at most $(\beta+1)\Delta$ $A$-type events, and at most $(\beta+1)\Delta{\Delta\choose \beta}$ other $B$-type events. Call these values $d_{BA}$ and $d_{BB}$, respectively.
\end{enumerate}
 Using the notation in problem 1, note that for every event here we need to find a corresponding $x$ value. Our strategy will be to choose the $x$-value to be the same for all the $A$-type events, and all the $B$-type events. That is to say, we will pick two numbers $x_A$ and $x_B$, to satisfy the condition. 
\begin{enumerate}
\item[(g)] Explain why the following two criteria are sufficient to resolve the theorem:
\[ \p{A_{uv}} \leq x_A (1-x_A)^{d_{AA}}(1-x_B)^{d_{AB}},\]
and 
\[ \p{B_{x_1, \dots, x_{\beta+1}}} \leq x_B (1-x_A)^{d_{BA}}(1-x_B)^{d_{BB}}.\]
\item[(h)] Show that choosing $x_A=\frac{2}{C}$ and $x_B = \frac{2}{C^\beta}$ satisfies these inequalities. 
\item[(i)] Notice that you are done. I mean it. Look at the work you've completed, and notice that it is sufficient to solve the problem. Spend at least 10-15 minutes thinking carefully about what's going on here.
\end{enumerate}

\item Let $G=G(n, p)$ be a random graph such that each edge is included independently and with probability $p$, where $p$ is a constant. Note that the expected degree of each vertex is $np$. Let $\delta$ be the minimum degree in $G$. Prove that for any constant $c>1$, 
\[\lim_{n\to\infty} \p{\delta<np-c\sqrt{n\log n}} = 0.\]

That is to say, the probability that $\delta > np-c\sqrt{n\log n}=np(1-o(1))$ tends to 1 as $n\to \infty$.


\end{enumerate}
\end{document}