\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 4}{Due Thurs, Apr 6, 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{\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 Let $G$ be a $t$-vertex $m$-edge graph with $m\ge 2$.  Show that $\ex(n, G) \ge cn^{2-\frac{t-2}{m-1}}$.  Compare this lower bound in the case that $G=C_{2k}$ with the Bondy--Simonovits theorem.

\item \emph{Turán number of $C_6$.}
\begin{enumerate}
	\item Prove that if $G$ is an $m$-edge graph with no $6$-cycle, then $G$ has a subgraph with at least $m/4$ edges and girth at least $8$.
	\item Use part (a) to show that $\ex(n,C_6)\le cn^{4/3}$ for some constant $c$.
\end{enumerate}
 
\item \emph{The diamond poset Turán problem.}
\begin{enumerate}
\item Let $\F \subseteq 2^{[n]}$ be nonempty.  For each $A\in \F$, let $I_A$ be the number of times that a random chain from $A$ to $[n]$ meets $\F$.  (Note that since $A\in \F$, always $I_A \ge 1$.)  Show that there exists $A\in \F$ such that $\EX(I_A) \ge \ell(\F)$.
\item Prove that if $\ell(\F) > 2.5$, then $\F$ weakly contains the diamond poset $2^{[2]}$.  Conclude that $\La(n,2^{[2]}) \le 2.5\binom{n}{n/2}$.
\end{enumerate}

\item The $t$-dimensional hypercube, denoted $Q_t$, has vertex set $\{0,1\}^t$ with vertices adjacent if and only if they disagree in exactly one coordinate.  Prove that there exists a constant $c$ such that $R(Q_t,Q_t) \le 2^{ct}$ for all $t$.  (Hint: given a $2$-edge-coloring of $K_n$, apply a modified the dependent random choice lemma to a monochromatic subgraph with density at least $1/2$.) 

\item In a hypergraph, the \emph{degree} of a set of vertices $S$, denoted $d(S)$, is the number of edges containing $S$.  Let $n\ge 5$ and let $G$ be an $n$-vertex $3$-uniform hypergraph such that $d(S) = d(S') > 0$ when $|S| = |S'| = 2$.  Prove that $\chi(G) > 2$.

\item Let $G$ be the $3$-uniform complete $3$-partite graph with $t$ vertices in each part.  
\begin{enumerate}
	\item Let $H$ be an $n$-vertex $3$-uniform graph.  For a set $S\subseteq V(H)$, let $d(S)$ be the number of edges in $H$ that contain $S$.  Prove that if $\sum_{S\in\binom{V(H)}{2}} \binom{d(S)}{t} > \ex(n,K_{t,t}) \binom{n}{t}$, then $G\subseteq H$.
	\item Prove that $\ex(n,G) \le c_tn^{3-\frac{1}{t^2}}$ for some constant $c_t$.
\end{enumerate}


\end{enumerate}
\end{document}
