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



\begin{itemize}
\item The due is on Thursday, Nov. 26 (UNUSUAL date!), at beginning of the class.
\end{itemize}




\noindent{\bf 1.} For any point $p\in R^d$ in $d$-dimension, write $p=(p_1,p_2,...,p_d)$.
A set $\mathcal{P}$ of points in $R^d$ is called {\it good}, if for each $i\in [d]$, the $i^{th}$ coordinates of these points are distinct.
Given two points $p,q\in R^d$,
define $box(p,q):=\{x\in R^d: \min\{p_i,q_i\}\le x_i\le \max\{p_i,q_i\} \text{ for each } i\}$ as the box determined by points $p,q$.

Prove that in any good set $\mathcal{P}$ of $2^{2^{d-1}}+1$ points of $R^d$, there is a point $x\in \mathcal{P}$ which is in the box determined by two of the other points in $\mathcal{P}$.


\bigskip

\noindent{\bf 2.} For any integers $k,\ell\ge 1$, construct a sequence of $k\ell$ distinct integers with no increasing
subsequence of length $k + 1$ and with no decreasing subsequence of length $\ell + 1$.


\bigskip

\noindent{\bf 3.} Let $P=(X,\prec)$ be a finite partial ordered set. Show that $X$ can be expressed as a disjoint union of at most $\alpha(P)$ chains.

Hint: by induction on $|X|$.

\bigskip

\noindent {\bf 4.} Construct an explicit 2-edge-coloring of $K_{k\ell}$ to show that $R(k+1,\ell+1)\ge k\ell+1$.


\bigskip


\noindent{\bf 5.} Use Ramsey's theorem to prove: for every integer $k\ge 2$, there is an integer $n$ such that
every sequence of $n$ distinct real numbers contains a monotone subsequence of $k$ real numbers.

(You must use Ramsey's theorem and cannot use the Erd\H{o}s-Szekeres theorem.)

\bigskip


\noindent{\bf 6.} For integers $k\ge 2$ and $s_1,s_2,...,s_k\ge 2$, the {\it Ramsey number} $R_k(s_1,s_2,...,s_k)$ is the least
number of integer $n$ such that any $k$-edge-coloring of $K_n$ has a monochromatic clique $K_{s_i}$ in color $i$.
Prove that for any integers $s_1,s_2,...,s_k\ge 2$, the Ramsey Number $$R_k(s_1,s_2,...,s_k)<+\infty.$$

\bigskip


\noindent{\bf 7.} Prove that $2^k\le R_k(3,3,...,3)\le (k+1)!$

\end{document}
