\documentclass[11pt]{article}

\usepackage{amsmath, amssymb, amsthm}

\theoremstyle{plain}
\newtheorem{thm}{Theorem}[section]
\newtheorem{prop}[thm]{Proposition}
\newtheorem{lem}[thm]{Lemma}
\newtheorem*{lem*}{Lemma}
\newtheorem{defn}[thm]{Definition}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{claim}[thm]{Claim}
\newtheorem{conj}[thm]{Conjecture}

\theoremstyle{remark}
\newtheorem{rem}{Remark}
\newtheorem*{rem*}{Remark}
\newtheorem*{ques*}{Question}
\newtheorem{ques}{Question}
\newtheorem{example}{Example}


\oddsidemargin  20pt
\evensidemargin 20pt
\marginparwidth 40pt
\marginparsep 10pt
\topmargin 0pt
\headsep 10pt
\textheight 8.0in
\textwidth 6.2in
\renewcommand{\baselinestretch}{1.1}


\title{The Lov{\'a}sz Local Lemma and Applications} 

\author{John Doe}

\begin{document}

\maketitle

\begin{abstract}
A true gem in the probabilistic method is the Lov{\'a}sz Local Lemma, which for
a set of bad events $A_1,\ldots,A_m$ with bounded dependence degree can guarantee 
that the event $\bar{A}_1 \wedge \ldots \wedge \bar{A}_m$ has positive probability. 
In this paper we give a proof of the generalized form and show surprising applications of this powerful method to 
Ramsey theory, hypergraph coloring and the satisfiability problem.
\end{abstract}

\section{Introduction}

One of the fundamental techniques in combinatorics is the probabilistic method. 
To show the existence of a desired object, for example an $n$-node graph 
without any $4\log n$-size clique or anti-clique, one considers a suitable random
experiment to show it's existence.  . . .  

The first application of this technique can be found in . . ., where it was used
to show. . . The method was also used in the groundbreaking work of Leighton, Maggs and
Rao~\cite{LeightonMaggsRao94} in the context of 
packet routing.
For a more detailed overview, we refer to the excellent book of Alon and Spencer~\cite{AlSp}.

The local lemma is essentially an existential result and does not give an efficient algorithm
by itself. However, recently, Moser proved a general algorithmic local lemma that can be 
applied to numerous situations to give a randomized algorithm of finding
an instance that satisfies  $\bar{A}_1 \wedge \ldots \wedge \bar{A}_m$.

In this paper, I will first state the local lemma and present its proof. Then I will
review several applications of the local lemma. Finally, I will conclude with the proof
of Moser's result.



\section{Local Lemma}

State local lemma and present its proof

\begin{thm}
Let $A_1, A_2, \cdots, A_n$ be events in an arbitrary probability space.
A directed graph $D=(V,E)$ on the set of vertices $V=[n]$
is called a dependency digraph for the events $A_1, \ldots, A_n$
if for each $i \in [n]$, the event $A_i$ is mutually independent of
all the events $\{A_j\,:\,(i,j)\notin E\}$. Suppose that $D=(V,E)$
is a dependency digraph for the above events and suppose that there are
real numbers $x_1,\ldots,x_n$ such that $0 \le x_i < 1$ and
\[ 
	\mathbf{P}(A_i) \le x_i \prod_{(i,j)\in E} (1-x_j) \forall i \in [n].
\]
Then with $\mathbf{P}(\bigwedge_{i=1}^{n} \overline{A_i}) \ge \prod_{i=1}^{n}(1-x_i)$.
In particular, with positive probability no event $A_i$ holds.
\end{thm}




\section{Applications of local lemma}

\subsection{Application I}

First application is the original application of Erd\H{o}s and Lov\'asz. I will
study $k$-coloring of natural numbers.

\begin{thm}
State theorem
\end{thm}

\subsection{Application II}

Second application is the work of Leighton, Maggs and Rao \cite{LeightonMaggsRao94}.

\begin{thm}
State theorem
\end{thm}


\subsection{Application III}

Third application is property B of hypergraphs.

\begin{thm}
State theorem
\end{thm}


\section{Algorithmic local lemma}

I will study the result of Moser; algorithmic version of the local lemma.

\begin{thm}
State theorem
\end{thm}



\begin{thebibliography}{100}

\bibitem{AlSp}
Noga Alon and Joel~H. Spencer, \textit{The probabilistic method}, 3rd ed.,
  Wiley, New York (2008).

\bibitem{LeightonMaggsRao94}
Frank T. Leighton, Bruce M. Maggs, Satish B. Rao,
Packet routing and job-shop scheduling in O(congestion+ dilation) steps, 
{\it Combinatorica} {\bf 14} (1994), 167--186.


\end{thebibliography}

\end{document}