\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}




\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 - HW 2 page \thepage/\pageref{LastPage}}
\lfoot{} % \doclicenseIcon Bernard Lidick\'y, mixed from Cory Palmer's notes.}
\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}



\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} 

This HW is due Mar 22 BEFORE the class starts. Submit electronically to the instructor. Choose your number, priority of numbers first come first served.

\centerline{\large \textbf{Homework 2}}

\centerline{\large \textbf{Participant number XXXX}}



\begin{exercise}
Find the extremal number (with error term allowed) of the graph  the icosahedron and of the Peterson graph.
\begin{hint}
Just need the chromatic number.
 \end{hint} 
\end{exercise}
\begin{solution}

\end{solution}


\begin{exercise}
Let $\ex(n,F_1,F_2,\dots,F_t)$ be the maximum number of edges in an $n$-vertex graph containing no copy of any graph $F_i$. Determine the asymptotically sharp upper bound for $\ex(n,F_1,F_2,\dots,F_t)$.
\begin{solution}

\end{solution}
\end{exercise}




\begin{exercise}\label{ex-monotone}
For a fixed graph $F$, show that the following function is decreasing as $n$ increases
$$\frac{\ex(n,F)}{\binom{n}{2}}.$$
\begin{solution}

\end{solution}
\end{exercise}



\begin{theorem}[F\"uredi, 2015]\label{mini-stability}
Suppose $G$ is an $n$-vertex $K_{k+1}$-free graph with $e(G) = e(T_k(n)) - t$. Then $G$ can be obtained from a complete $k$-partite graph (on $n$ vertices) by adding and removing at most $3t$  total edges.
\end{theorem}

\begin{exercise}
Prove Theorem~\ref{mini-stability}.
\begin{hint}
We had some Lemma that might be useful.
\end{hint} 
\begin{solution}

\end{solution}
\end{exercise}

\vskip 2em


\begin{theorem}[Erd\H os; K\H ovari-S\'os-Tur\'an, 1954]
For any naturals $s \leq t$ we have
$$\ex(n,K_{s,t}) \leq \frac{1}{2}(t-1)^{1/s} n^{2-{1/s}}+O(n).$$
\end{theorem}

\begin{exercise}
Prove KST Theorem. 
\begin{hint}
Let $G$ be an $n$-vertex graph with no $K_{s,t}$ subgraph. Count the pairs $(v,S)$ where $v$ is a vertex and $S$ is a set of $s$ vertices in the neighborhood of $v$.
Use this to finish the proof.
\end{hint}
\begin{solution}



\end{solution}
\end{exercise}



\begin{exercise}
Let $S$ be a set of $n$ points in the plane. Show that there are at most $O(n^{3/2})$ pairs of points that are of unit distance from each 
other\footnote{The best known upper bound is $O(n^{4/3})$ and is conjectured to be $n^{1+o(1)}$.}.

\begin{hint} Consider a graph on the given points and connect two vertices by an edge if they are at distance $1$.
\end{hint} 
\end{exercise}
\begin{solution}

\end{solution}


\begin{exercise}
Let $A \subset [n]$ be a set of integers such that no element divides the product of any other two elements. Prove that $|A| \leq \pi(n) + n^{2/3}$ where $\pi(n)$ is the number of primes not exceeding $n$.

\begin{hint}
Look at Bollob\'{a}s \emph{Modern Graph Theory}, exercises in the extremal chapter.
\end{hint}
\begin{solution}



\end{solution}
\end{exercise}





\end{document}
