
\documentclass[12pt]{article}
\usepackage{amssymb}
\usepackage{mathrsfs}
\addtolength{\topmargin}{-.5in} \addtolength{\textheight}{1in}
\addtolength{\oddsidemargin}{-.6in}
\addtolength{\evensidemargin}{-.6in} \addtolength{\textwidth}{1.2in}
\usepackage{latexsym,amsmath,amssymb,amsfonts,epsfig,graphicx,cite,psfrag}
\usepackage{eepic,color,colordvi,amscd}


\def\qed{\hfill \rule{4pt}{7pt}}

\def\pf{\noindent {\it Proof. }}




\pagestyle{plain}


\begin{document}
\begin{center}
    \large{Combinatorics, 2016 Fall, USTC} \\
    {Homework 11}
\end{center}



\begin{itemize}
\item The due is on {\bf Tuesday}, Dec. 13, at beginning of the class.

\item  Solve all  problems.
\end{itemize}





\noindent{\bf 1.} Using the corollary proved in lecture on Dec 6, prove the approximate version of Tur\'an's Theorem:
For any $n$-vertex $K_{r+1}$-free graph $G$, we have $e(G)\le \frac{r-1}{2r}n^2.$


\bigskip

\noindent{\bf 2.} Prove the exact version of Tur\'an's Theorem: For any $n$-vertex $K_{r+1}$-free graph $G$, $$e(G)\le e(T_r(n))$$ with equality if and only if $G$ is the Tur\'an graph $T_r(n)$. (Hint: by induction on $r$.)


\bigskip

\noindent{\bf 3.} Let $\mathcal{F}$ be an independent system of $[n]$. Let $\pi\in S_n$ be a random permutation of $[n]$.
By considering the set $$X=\left\{i: \{\pi(1),\pi(2),...,\pi(i)\} \in \mathcal{F}\right\},$$
give a new proof of that $$|\mathcal{F}|\le \binom{n}{\lfloor n/2\rfloor}.$$

\bigskip



\noindent{\bf 4.} Given a graph $G$ with $\chi(G)=n$ and a proper coloring $f:V(G)\to [n]$, prove that
for any color $i\in [n]$, there exists a vertex of color $i$ adjacent to a vertex of every other color.


\bigskip


\noindent{\bf 5.} Let $H$ be the graph obtained from $K_4$ by deleting one edge. Prove that for infinity many integers $n$, 
there exists an $n$-vertex $H$-free graphs with at least $c\cdot n^{6/5}$ edges for some absolute constant $c>0$. 








\end{document}
