\magnification=\magstep1 \voffset=-.55truein \advance\vsize
1.56truein \hoffset=-.25truein
%\hsize=7.28truein
%\baselineskip=10.4truept
\nopagenumbers
%\parskip=1pt
\centerline{HOMEWORK SET \#11 / CO1A / Spring 2020} \vskip8mm


\item{1.)}  Let $T_m$ be an arbitrary, but fixed tree of $m$ vertices. Show that $R(T_m,K_n)=1+(m-1)(n-1)\,\,.$ (challenging)
\item{2.)} Prove that  $R_k(3,3, \ldots , 3) \le [e\cdot k!]+1$. (to be solved later)
\item{3.)} Show that  $R_k(3,3, \ldots , 3) \ge 2^k+1$. (to be solved later)
\item{4.)} What is ex$(n,K_3)$ (hint: what is the maximum number of edges of a bipartite graph on $n$ vertices?
\item{5.)}Find the Ramsey number  $R(C_4,C_4)$.
\item{6.)}Find the Ramsey number $R(P_4,C_7)$.

\item{7.)} Let $n>1$ be a positive integer. Prove that $R(n+2,3) >
3n$.

\item{8.)}  Find $R(S_5,S_5)$ where $S_5$ is the star on 5
vertices, that is a vertex of degree 4 joint to 4 other vertices,
each of degree 1.
 \bye
