\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 7 October 2017}
\maketitle

Complete the following problems. Fully justify each response.

\begin{enumerate}

\item Let $G$ be a triangle-free graph having $n$ vertices and $m$ edges. Given a vertex $v$, define the closed neighborhood \[N[v] = \{ u\in V(G)\ | \ u=v\hbox{ or }u\sim v\}.\] 
Prove that there exists a vertex $v$ such that $V(G)\backslash N[v]$ contains at most $m-\frac{4m^2}{n^2}$ edges.

\item Use the probabilistic method to find a lower bound on $R(4, t)$. (Suggested strategy: color edges red and blue with probability $p$ and $1-p$, respectively. Then choose a nice $p$ later.)

\item Prove Sperner's Theorem: If $\mathcal{F}$ is a collection of subsets of $[m]$, such that no set in $\mathcal{F}$ is contained in any other set in $S$, then $|\mathcal{F}|\leq {m\choose \floor{{m/2}}}$.

\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 $\frac{2^{k-3}}{k}-1$, then $H$ is $2$-colorable.

\end{enumerate}
 

\end{enumerate}
\end{document}