
\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, 2020 Fall, USTC} \\
    {Homework 10}
\end{center}



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

\noindent{\bf 1.} Prove that for all integers $n$ and $p\in [0,1]$, $$R(k,\ell)>n-\binom{n}{k}p^{\binom{k}{2}}-\binom{n}{\ell}(1-p)^{\binom{\ell}{2}}$$
and then show $$R(4,k)\ge c\cdot \left(\frac{k}{\ln k}\right)^2$$ for some absolute constant $c>0$.

\bigskip

\noindent{\bf 2.} Let $\mathcal{F}\subseteq \binom{[n]}{3}$ be a family of $m$ subsets where $m\geq n/3$.
Prove that there exists a subset $A\subseteq [n]$ with
$$|A|\ge \frac{2n^{3/2}}{3\sqrt{3m}}$$ such that none of the sets in $\mathcal{F}$ is contained in $A$.

\bigskip

\noindent{\bf 3.} Using the corollary proved in the beginning of the lecture on Dec 15,
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 4.} 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 5.} 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}.$$


\end{document}
