\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 5}{Due Thurs, Apr 27, 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

\newcommand{\HJ}{\mathrm{HJ}}
\newcommand{\F}{\mathcal{F}}
\newcommand{\ex}{\mathrm{ex}}
\newcommand{\La}{\mathrm{La}}
\newcommand{\EX}{\mathbb{E}}

\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 \emph{Hales--Jewett extension.}  Let $\tau \in ([t] \cup \{\star_1, \ldots, \star_m\})^n$, where each $\star_j$ appears in at least one coordinate of $\tau$.  For $x\in [t]^m$, let $\tau(x) \in [t]^n$ be the vector obtained from $\tau$ by replacing each occurrence of $\star_j$ in $\tau$ with $x_j$.  For example, with $\tau = 2\star_2 5\star_1 8\:2 \star_2 3$, we have $\tau(4,1) = 21548213$.  The \emph{combinatorial $m$-space rooted at $\tau$} is $\{\tau(x)\st x \in [t]^m\}$.  Let $\HJ_m(r,t)$ be the minimum $n$ such that every $r$-coloring of $[t]^n$ contains a monochromatic combinatorial $m$-space.  Prove that $\HJ_m(r,t) \le m[\HJ(r,t^m)]$.

\item \emph{Nearly spanning cycles.}  Show that there exists a constant $c$ such that for all positive $\alpha$ and $\varepsilon$ with $\alpha>\varepsilon$, there exists $n_0$ such that the following holds for $n\ge n_0$.  Every $\varepsilon$-regular pair with disjoint vertex sets $X$ and $Y$ of size $n$ with density $\alpha$ has a cycle through all but at most $c\cdot \frac{\varepsilon}{\alpha-\varepsilon} n$ vertices.

\item \emph{Sharpness example for Corrádi--Hajnal.}  Prove that for every positive $\varepsilon$, there is an infinite family of graphs $G$ such that $\delta(G) \ge (\frac{2}{3} - \varepsilon)|V(G)|$ but every subgraph of $G$ with a triangle tiling has at most $(1-6\varepsilon)|V(G)|$ vertices.

\item \emph{Tiling threshold for $P_3$.}  Determine the least $\alpha$ such that if $G$ is an $n$-vertex graph such that $3$ divides $n$ and $\delta(G) \ge \alpha n$, then $G$ has a $P_3$-tiling.  (Note: this requires a proof that $\delta(G) \ge \alpha n$ implies that $G$ has a $P_3$-tiling, and also a construction of a sequence of graphs $G_1, G_2, \ldots$ such that $G_k$ is a $3k$-vertex graph and $\delta(G) \ge (\alpha - o(1))3k$ but still $G$ has no $P_3$-tiling.)

\item \emph{Nearly spanning tiling threshold for $P_3$.}  
\begin{enumerate}
	\item Prove that for each $\varepsilon > 0$, there exists $n_0$ such that if $G$ is an $n$-vertex graph with $n\ge n_0$ and $\delta(G) \ge \frac{1}{3} n$, then $G$ has a $P_3$-tiling subgraph with at least $(1-\varepsilon)n$ vertices.
	\item Give a family of examples that shows that the constant $1/3$ in part (b) is sharp.
\end{enumerate}

\item An $n$-vertex graph with density $\rho$ is \emph{$(\delta,\gamma)$-uniform} if $d(X,Y) \le (1+\delta)\rho |X||Y|$ when $X$ and $Y$ are disjoint vertex sets, each of size at least $\gamma n$.  

Let $r$ be an integer, and let $\rho$ and $\delta$ be positive real numbers such that $r\ge 3$ and $\delta<\frac{1}{r-2}$.  Show that there exists $\gamma > 0$ and $n_0$ such that if $G$ is an $n$-vertex $m$-edge $(\delta,\gamma)$-uniform graph with $n\ge n_0$ and $m\ge \rho \frac{n^2}{2}$, then $K_r \subseteq G$.  (Hint 1: first try the case $r=3$.  Hint 2: let $\varepsilon = \varepsilon(r,\rho,\delta)$, and let $\alpha = \frac{1}{2r} \varepsilon^r$.  With $\alpha$ chosen this way, obtain an $\alpha$-regular partition and clean $G$ with respect to a density threshold of $2\varepsilon$.  Then apply the embedding lemma with target graph $K_r$.)

Comment: Turán's theorem states that a graph with density more than $1-\frac{1}{r-1}$ contains a copy of $K_r$.  In this exercise, we show that very small densities force a copy of $K_r$ provided that the edges of $G$ are distributed uniformly.
\end{enumerate}
\end{document}
