\documentclass[11pt]{article}
\usepackage{jeffe,handout,multicol,tikz,kgm}

\newcommand{\kgmcomment}[1]{}
\newcommand{\ZZ}{\mathbb{Z}}
\renewcommand{\gcd}{\mathrm{gcd}}

\DeclareMathOperator{\ord}{ord}

\begin{document}
\headers{Math773}{Homework 2}{Due Thurs, Feb 9, 2017}

%\makeatletter
%\def\@oddfoot{\hfill \tikz \node[draw] {over} ; }
%\makeatother

%\newcommand{\seq}[1]{\left\langle #1\right\rangle}
%



\newcommand{\compicon}%
{%
	\begin{tikzpicture}[scale=0.15]%
		\draw[double] (0,0) rectangle (1,1) ;
		\begin{scope}[yshift=-5pt]
			\draw (-0.5, -0.5) rectangle (1.5, 0) ;
		\end{scope}
	\end{tikzpicture}
}

\newcommand{\RR}{\mathbb{R}}
\newcommand{\msd}{\mathrm{msd}}

\makeatletter
\def\@oddfoot{}
\makeatother

\noindent
\textbf{Directions:} Solve 5 of the following 6 problems.  See the course syllabus and the Homework Webpage on the course website for general directions and guidelines.

\begin{enumerate}

\item For $r\ge 3$, determine the minimum number of vertices in a graph $G$ such that $\chi(G)\ge r$ but $G$ contains no copy of $K_r$.

\item Let $S$ be a set of $n$ points in the plane such that $|p-q|<1$ when $p,q \in S$.  Show that at most $\floor{n^2/3}$ pairs of points in $S$ are at distance at least $1/\sqrt{2}$.  

\item Let $G$ be a copy of $K_n$ in which every edge is colored red or blue.  For $v\in V(G)$, let $r_v$ be the number of red edges incident to $v$ and let $b_v$ be the number of blue edges incident to $v$.
\begin{enumerate}
	\item Find a formula for the number of monochromatic triangles in $G$ in terms of $n$, the red degrees $r_v$, and the blue degrees $b_v$.  (Hint: first count the number of triangles that are not monochromatic.)
	\item Prove that $G$ has at least $n(n-1)(n-5)/24$ monochromatic triangles.
	\item Describe the $2$-edge-colorings of $K_n$ that have exactly $n(n-1)(n-5)/24$ monochromatic triangles.
\end{enumerate}

\item Let $G$ be a graph and let $X,Y\subseteq V(G)$.  Prove that for each $\varepsilon > 0$, there exists $\delta > 0$ such that if $(X,Y)$ is $\delta$-regular, then $(X',Y')$ is $\varepsilon$-regular when $X'\subseteq X$, $Y'\subseteq Y$, $|X'|\ge \varepsilon |X|$, and $|Y'| \ge \varepsilon|Y|$.

\item An \emph{equipartition} is a partition whose parts differ in size by at most $1$.
\begin{enumerate}
	\item Show that for each $\delta > 0$, there exists $\ell$ such that if $X$ is a partition of $V(G)$ into $k$ parts, then there is an equipartition $Y$ of $V(G)$ into $\ell k$ parts such that $\msd(Y) \ge \msd(X) - \delta$.
	\item Describe how to modify the proof of Szemer\'edi's regularity lemma to obtain the following strengthening: for each $\varepsilon > 0$, there exists $M$ such that every graph has an $\varepsilon$-regular equipartition into at most $M$ parts.
\end{enumerate}

\item Prove that for each $\varepsilon > 0$ there exists $\delta > 0$ such that if $G$ is an $n$-vertex graph with $|E(G)| \ge (\frac{1}{4} + \varepsilon)\frac{n^2}{2}$, then either $G$ contains a copy of $K_4$, or $G$ has an independent set of size at least $\delta n$. 

\end{enumerate}
\end{document}
