\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]{
\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 4}
\author{Mary Radcliffe}
\date{due 5 Oct 2015}
\maketitle

Complete the following problems. Fully justify each response.

\begin{enumerate}

\item Let $A$ be an $n\times n$ array, in which the numbers $1$ through $n$ appear exactly $n$ times each. Prove that there exists either a row or column in $A$ in which appear at least $\sqrt{n}$ distinct numbers.

\item Prove Sperner's Theorem: If $\mathcal{F}$ is a collection of subsets of $[n]$, 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 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 the $V(G)\backslash N[v]$ contains at most $m-\frac{4m^2}{n^2}$ edges\footnote{Note that the average degree in $G$ is $\frac{2m}{n}$, so a subgraph containing $m-(\frac{2m}{n})^2$ edges must be substantially sparser than the graph $G$ itself.}. 


\end{enumerate}

\end{document}