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

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

\DeclareMathOperator{\ord}{ord}

\begin{document}
\headers{Math773}{Homework 3}{Due Thurs, Mar 16, 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}}
\newcommand{\Rind}{R^{\star}}
\makeatletter
\def\@oddfoot{}
\makeatother

\noindent
\textbf{Directions:} Solve 4 of the first 5 problems, plus problem number 6.  See the course syllabus and the Homework Webpage on the course website for general directions and guidelines.

\begin{enumerate}

\item For an integer $m$ and a graph $G$, we use $mG$ to denote the disjoint union of $m$ copies of $G$.  Prove that $R(mK_2,mK_2) = 3m-1$.

\item Let $S$ be a set of $R^{(3)}(m,m)$ points in the plane with no three on a line.  Prove that $S$ contains $m$ points that form a convex $m$-gon.  (Hint: assign to each triple $\{p,q,r\}\in \binom{S}{3}$ one of two colors that encodes appropriate information about their arrangement in the plane.)

\item Given graphs $G_1$ and $G_2$, the \emph{induced Ramsey number}, denoted $\Rind(G_1, G_2)$, is the minimum number of vertices in a host graph $H$ such that every red/blue edge-coloring of $H$ contains an induced copy of $G_1$ that is all red or an induced copy of $G_2$ that is all blue.  
\begin{enumerate}
	\item Determine $\Rind(P_3,P_3)$, where $P_3$ denotes the path on $3$ vertices.
	\item Prove that if $G$ is an $n$-vertex graph with $m$ edges, then $\Rind(P_3,G) \le n+m$.
\end{enumerate}
Comment: it is not obvious that $\Rind(G_1,G_2)$ exists, since the requirement that our target graphs $G_1$ and $G_2$ be induced prevents using a large complete graph for $H$.  The induced Ramsey theorem was discovered in the 1970's independently by several groups.

\item Use Behrend's construction to show that for some constant $c$ and all sufficiently large $n$, there exists a subgraph $G$ of $K_{n,n}$ with at least $n^{2-\frac{c}{\sqrt{\ln n}}}$ edges that is the union of at most $2n-1$ induced matchings.  (Hint: first obtain a relatively large subset of $[n]^2$ with no three points of the form $(x,y), (x+d,y), (x,y+d)$ with $d\ne 0$.)

\item \emph{Turán Theorem stability for $K_4$-free graphs}.  Let $G$ be an $n$-vertex $K_4$-free graph with $m$ edges.  For each edge $e\in E(G)$, let $f(e)$ be the number of vertices that complete a triangle with $e$.  Let $t$ be the number of triangles in $G$, and let $k$ be the number of copies of $K_4^-$ in $G$.  (Here, $K_4^-$ denotes the graph obtained from $K_4$ by deleting an edge.)
\begin{enumerate}
	\item   Prove that $3t = \sum_{e\in E(G)} f(e)$ and $k = \sum_{e\in E(G)} \binom{f(e)}{2}$.
	\item Prove that $2k \ge \frac{9t^2}{m} - 3t$.
	\item Let $B$ be the $(X,Y)$-bigraph where $X$ is the set of triangles in $G$ and $Y = |V(G)|$ with $T\in X$ and $y\in Y$ adjacent if and only if $T$ and $y$ together form a copy of $K_4^-$ in $G$.  Prove that there exists $T\in X$ such that $T$ has at least $\frac{9t}{m} - 3$ neighbors.
	\item Prove that for every $\varepsilon > 0$, there exists $\delta > 0$ such that every $n$-vertex $K_4$-free graph with at least $(\frac{1}{3} - \delta)n^2$ edges can be made $3$-colorable by deleting at most $\varepsilon n$ vertices.  (Hint: regularity is not needed.  You may find our lower bound on $t$ from HW1 useful.)
\end{enumerate}

\item {} \textbf{[Required problem]} Prove that for each $\varepsilon > 0$, there exists a constant $C$ such that if $G$ is an $n$-vertex triangle-free graph with $\delta(G) \ge (\frac{1}{3} + \varepsilon)n$, then $\chi(G) \le C$.  (Hint: choose an appropriate $\alpha$ in terms of $\varepsilon$ and let $\{X_1, \ldots, X_M\}$ be an $\alpha$-regular equipartition of $V(G)$.  Show that for each vertex $v\in V(G)$, there is a part $X_i$ such that $v$ has more than $\frac{1}{2} |X_i|$ neighbors in $X_i$.)


\end{enumerate}
\end{document}
