\documentclass[11pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[czech, english]{babel}
\usepackage[left=1.5cm,right=1.5cm,top=1.5cm,bottom=1.5cm]{geometry}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{mathtools}
\usepackage{hyperref}
\usepackage{stmaryrd}
\usepackage{tikz}
\usepackage{verbatim}
\usetikzlibrary{shapes.geometric}
\usetikzlibrary{shapes.multipart}
\usetikzlibrary{arrows}
\usetikzlibrary{calc}



\usepackage{hyperref}
\usepackage[
    type={CC},
    modifier={by-nc-sa},
    version={4.0},
]{doclicense}
%\begin{document}
% \doclicenseIcon
%\end{document}



\newtheorem{theorem}{Theorem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{claim}[theorem]{Claim}

\newcommand{\vc}[1]{\ensuremath{\vcenter{\hbox{#1}}}}

% Fancy footnote....
\usepackage{fancyhdr}
\pagestyle{fancy}
\usepackage{lastpage}
\rfoot{ \hfill Math 608 - page \thepage/\pageref{LastPage}}
\lfoot{ \doclicenseIcon Due April 19 2018, submit PDF and TeX on Canvas.}
\cfoot{}
\rhead{}
\lhead{}
\renewcommand{\headrulewidth}{0pt}
\renewcommand{\footrulewidth}{0pt}


% Itemize environment with small skips
\newenvironment{packeditemize}{
\begin{itemize}
  \setlength{\itemsep}{1pt}
  \setlength{\parskip}{0pt}
  \setlength{\parsep}{0pt}
}{\end{itemize}}


% Itemize environment with small skips
\newenvironment{packedenumerate}{
\begin{enumerate}
  \setlength{\itemsep}{1pt}
  \setlength{\parskip}{0pt}
  \setlength{\parsep}{0pt}
}{\end{enumerate}}



\makeatletter
\newcommand*\bigcdot{\mathpalette\bigcdot@{.8}}
\newcommand*\bigcdot@[2]{\mathbin{\vcenter{\hbox{\scalebox{#2}{$\m@th#1\bullet$}}}}}
\makeatother


\newif\ifshowsolutions


\showsolutionstrue
%\showsolutionsfalse


% toggle between macros for showing and/or hiding solutions
\ifshowsolutions
	\definecolor{SOLUTION}{RGB}{0,128,255}								%custom color
	\newcommand\hide[1]{{\color{SOLUTION}{#1}}}
	\newenvironment{solution}% environment name 
	{% begin code 
	\vskip 0em\Large\color{SOLUTION}\noindent\textbf{Solution:} 
	}% 
	{\vskip 0em}% end code
\else
	\definecolor{SOLUTION}{rgb}{255,255,255}	                    %enable to hide solutions (colors them white)
	\newcommand\hide[1]{{\color{SOLUTION}\phantom{#1}}}
	\newenvironment{solution}{\comment}{\endcomment}
\fi

											

\newcounter{excounter}
\setcounter{excounter}{1}
%\newcommand\question[2]{\vskip 0.1em  \noindent\textbf{\arabic{excounter}\addtocounter{excounter}{1}:} \emph{#1} \noindent#2}
%\newcommand\solution[1]{{\vskip 0em{\Large \color{SOLUTION}\noindent\textbf{Solution:} #1 }}}


\newenvironment{exercise}% environment name 
{% begin code 
\vskip 0.1em  \noindent\textbf{\arabic{excounter}\addtocounter{excounter}{1}:}
}% 
{}% end code

\newenvironment{hint}% environment name 
{% begin code 
\vskip 0em\noindent\textbf{Hint:} 
}% 
{\vskip 0em}% end code





\newcommand\ex{\ensuremath{\mathrm{ex}}}
\newcommand\rt{\ensuremath{\mathrm{\bf RT}}}
\newcommand\E{\ensuremath{\mathrm{\mathbb{E}}}}
\newcommand\pr{\ensuremath{\mathrm{\mathbb{P}r}}}



\setlength{\parindent}{0cm}
\setlength{\parskip}{0.25cm}

\begin{document} 
\centerline{\large \textbf{Homework 3}}

\begin{exercise}
Show that there exists a graph $F$ of chromatic number $3$ and constant $C$ (depending on $F$) such that
$$\ex(n,F) \geq \frac{1}{4}n^2 + Cn^{1.99}.$$

\begin{hint}
Prove instead $\ex(n,F) \geq \frac{1}{4}n^2 + Cn^{2-2/t}$ for any $t$. Let $F$ be the complete tripartite graph with classes of size $t$.
\end{hint}

\begin{solution}

\end{solution}

\end{exercise}




\begin{exercise}
	Let $Q_d$ be the graph of the $d$-dimensional hypercube. Show that the Ramsey number of $Q_d$ is
	$$R(Q_d,Q_d) \leq 2^{3d}.$$
	
	\begin{hint}
		Use dependent random choice on the graph spanned by the more common color.
	\end{hint}
	
\begin{solution}

\end{solution}
	
\end{exercise}



\begin{exercise}
Find another extremal graph for the path on $k$ vertices (that is not $n/(k-1)$ copies of $K_{k-1}$) and confirm that it has the maximal number of edges.
\begin{hint}
The construction is connected and has a large independent set.
 \end{hint} 

\begin{solution}

\end{solution} 
\end{exercise}





\begin{exercise}[Half Graph]
Let $H$ be a bipartite graph with classes $A=[n]$ and $B=[n]$. A pair of vertices $a \in A$ and $b \in B$ form an edge if and only if $a \geq b$. 

\begin{enumerate}
\item[(a)] Find an explicit $\epsilon$-regular partition of $H$ into $r$ parts where $ 3 \leq r \leq 10/\epsilon$.

\item[(b)] Show that for $\epsilon >0$ small enough there exists $c>0$ such that any $\epsilon$-regular equipartition of $H$ into $r$ classes has at least $cr$ many pairs of classes that are not $\epsilon$-regular. 
\end{enumerate}

\begin{solution}

\end{solution}

\end{exercise}

\begin{exercise}
Use the regularity lemma to prove the following alternate version:

Given $\epsilon >0$ and $m\geq 1$, there exists a constant $M = M(\epsilon,m)$ such that for every graph on $n$ vertices (for $n$ large enough) has a partition into $r+1$ parts $V_0,V_1,V_2\dots V_r$ such that $|V_0| \leq \epsilon n$ and $|V_1|=|V_2| = \cdots = |V_r|$ and all but at most $\epsilon r^2$ pairs of classes from $V_1,V_2,\dots, V_r$ are $\epsilon$-regular and $m \leq r <M$.

\begin{hint}
Use regularity lemma from class to get an $\epsilon/2$-regular partition and trim the too-big partition classes.
\end{hint}

\begin{solution}


\end{solution}
\end{exercise}



\begin{exercise}
\begin{theorem}[Solymosi, 2001]\label{solymosi}
For any $\alpha > 0$, there exists $N$ such that if $A$ is a set of $\geq \alpha N^2$ many points on the $N \times N$ integer lattice, then $A$ contains three distinct points of the following form $(x,y), (x+d,y), (x,y+d)$, i.e., an isosceles right triangle.
\end{theorem}

\begin{proof}
Consider the collection of vertical lines, horizontal lines and $45^{\circ}$ diagonal (left to right) lines in the $N \times N$ lattice.

Construct a $3$-partite graph $G$ with classes $X,Y,Z$ such that
$X$ is the set of vertical lines,  $Y$ is the set of horizontal lines, and $Z$ is the set of
diagonal lines.

Two vertices (lines) in this graph are connected by an edge if the intersection of the two lines is an element of $A$. Therefore, for each element $a \in A$, the three lines intersecting in $a$ form a triangle in $G$.


\emph{Finish the proof by looking at triangles.}
\begin{solution}


\end{solution}
\end{proof}
\end{exercise}


\begin{exercise}
Let $G$ be a graph on $n$ vertices that consists of the union of $n$ induced matchings. 
Show that $e(G) = o(n^2)$.

\begin{hint}
Suppose for contradiction that $G$ has at least $\delta n^2$ edges.
Use regularity lemma. 
In the clan up, for each matching $M$ also remove edges of $M$ incident to $V_i$ if there are less than $\epsilon |V_i|$ many of these edges. What happens if some edges remain? Final contradiction can be obtained that some matching is not induced.
\end{hint}

\begin{solution}

\end{solution}

\end{exercise}

\end{document}
