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



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


\noindent{\bf 1.} Let $V$ be a finite set and $r\ge 3$ be an integer. An {\it $r$-uniform hypergraph} is a pair $(V,E)$, where $E\subseteq \binom{V}{r}$.
And $K_n^{(r)}$ denotes the complete $r$-uniform hypergraph on $n$ vertices, i.e., $K_n^{(r)}=(V, \binom{V}{r})$ for $|V|=n$.
Let {\it hypergraph Ramsey number} $R^{(r)}(s,t)$ be the least integer $n$ such that any 2-edge-coloring of $K^{(r)}_n$ has a blue $K_s^{(r)}$ or a red $K_t^{(r)}$.

Prove that for any $s,t\ge r$, $R^{(r)}(s,t)< \infty$.

\bigskip

\noindent{\bf 2.} (a). A fixed point of a permutation $\pi$ is an integer $i$ such that $\pi(i)=i$. Let $X_{\pi}$ be the number of fixed points of permutation $\pi$. What is the expectation $E[X_{\pi}]$ for a random permutation $\pi$ chosen from the set $S_n$? (Recall that $S_n$ is the set of all permutations of $[n]$.)

(b). We toss a fair coin $n$ times. What is the expected number of ``runs"? ``Runs" are consecutive tosses with the same result. For example, the sequence ``TTTHHHHTT" has 3 runs, where `T' means `tail' and `H' means `Head'.

\bigskip


\noindent{\bf 3.} Let $n\ge 6$. We color the edges of complete graph $K_n$ with colors blue and red in such a way that each edge is in at most one blue triangle. Let $X$ be a maximal subset of the vertices with the property that $X$ does not contain a blue triangle. Then
\begin{itemize}
\item [(a)] show that $X$ contains at least $|X|/2$ red edges, and
\item [(b)] show that $|X|\ge \sqrt{2n}$.
\end{itemize}

\bigskip


\noindent{\bf 4.} Let $k\ge 4$ be an integer and $\mathcal{F}\subseteq \binom{X}{k}$ be a $k$-family defined on the ground set $X$.
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 all 4 colors are represented in every subset of family $\mathcal{F}$.




\end{document}
