\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{\oddsidemargin}{-.8in}
\addtolength{\textwidth}{1.6in}
\addtolength{\textheight}{1.75in}


\newcommand{\solution}[1]{
\begin{quote}\color{red}Solution:\quad 
\color{black}\end{quote}
}
\newcommand{\Ber}{\hbox{Ber}}
\newcommand{\p}[1]{\mathbb{P}(#1)}
\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}

\begin{document}
\title{Math 301: Homework 5}
\author{Mary Radcliffe}
\date{due 12 Oct 2015}
\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 Use the Lovasz Local Lemma to find a lower bound on $R(3, k)$.

\item A hypergraph $H=(V, E)$ is defined as
\begin{itemize}
\item a finite set $V$, called vertices, and 
\item $E$ is a collection of subsets of $V$, called edges.
\end{itemize}

A hypergraph is called $k$-uniform if $|e|=k$ for all $e\in E$, that is, every edge contains exactly $k$ vertices. In this setting, a typical graph is just a $2$-uniform hypergraph. The degree of a vertex in $H$ is the number of edges of which it is a member.

A hypergraph is called $2$-colorable if we can assign two colors to the vertices in such a way that every edge includes vertices of both colors. That is, no edge is monochromatic.

\begin{enumerate}
\item Use the standard probabilistic method to show that if $H$ is a $k$-uniform hypergraph having at most $2^{k-1}-1$ edges, then $H$ is $2$-colorable.
\item Use the Lovasz Local Lemma to prove the stronger statement that if $H$ is a $k$-uniform hypergraph having maximum degree at most $2^{k-3}-1$, then $H$ is $2$-colorable.
\end{enumerate}
\end{enumerate}

The following is NOT part of the homework set. Just interesting information.

The Lovasz Local Lemma gives us a probabilistic technique for proving the existence of a sometimes rare object. An open question is whether the local lemma actually gives a hint as to a constructive technique; sometimes, you can use the structure of the lemma and its proof to actually construct the rare object. So here is an open question, perhaps simplified a bit.

\noindent \textbf{Open Problem.} Let $S$ be a set, and let $S_1, S_2, \dots, S_n$ be subsets of $S$. Suppose we wish to color $S$ so that no $S_i$ is monochromatic (many of the problems we study here can be reduced to a problem of this form), and the Lovasz Local Lemma tells us that it is possible to do so with $k$ colors. Is there a {\it polynomial time} algorithm for finding such a coloring?

Some partial answers to this question are known (see the work of J. Beck and others).


\end{document}