
\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 10}
\end{center}



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

\item  Solve all problems.
\end{itemize}

\noindent{\bf 1.} We toss a fair coin $n$ times and let $X$ be the number of heads appearing. Compute the expectation of $X$.

\bigskip

\noindent{\bf 2.} Let $k\ge 4$ be an integer and $\mathcal{F}\subset \binom{X}{k}$ be a $k$-family.
Prove that if $$|\mathcal{F}|<\frac{4^{k-1}}{3^k},$$ then there is a coloring of elements of $X$ with 4 colors such that in any set of family $\mathcal{F}$ all 4 colors are represented.

\bigskip

\noindent{\bf 3.} Prove that if there is a real $p\in [0,1]$ such that $$\binom{n}{k}\cdot p^{\binom{k}{2}}+\binom{n}{t}\cdot (1-p)^{\binom{t}{2}}<1,$$ then Ramsey number $R(k,t)> n$.
Using this, show that $R(4,t)\ge c\cdot \left(\frac{t}{\ln t}\right)^{3/2}$ for some constant $c>0$.
\bigskip

\bigskip

\noindent{\bf 4.}  Prove that there exists an absolute constant $c>0$ with the following property.
Let $A$ be an $n$ by $n$ matrix with pairwise distinct entries. Then there is a permutation of the rows of $A$
so that no column in the permuted matrix contains an increasing subsequence of length at least $c\sqrt{n}$.


\bigskip

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

\bigskip

\noindent{\bf 6.} For any $\mathcal{F}\subseteq \binom{[n]}{3}$ with $m:=|\mathcal{F}|\ge 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 7.}  Recall the definition of $m(k)$. Given the following result: if there exists $p\in [0,1]$ with $t(1-p)^k+t^2p<1$, then $m(k)>2^{k-1}t$.
Prove that $$m(k)\ge c\cdot 2^k \left(\frac{k}{\ln k}\right)^{1/2}$$ for some constant $c>0$.





\end{document}
