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



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

\item  Solve all problems. 
\end{itemize}



\noindent{\bf 1.} Find the maximum number of line segments that a Hasse diagram of poset $(X,\prec)$ with $|X|=n$ can have.
Then define a poset which achieves this maximum number and draw its Hasse diagram.


\bigskip


\noindent{\bf 2.} For two natural numbers $a,b$, the symbol $a|b$ means that ``$a$ divides $b$". In other words, there exists a natural number $c$ such that $b=ac$.
First verify that the relation ``$|$" is a partial ordering on the set $\mathbf{N}$ of natural numbers.
Then prove that every finite poset can be embedded into $(\mathbf{N},|)$.

\bigskip

\noindent{\bf 3.} 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 4.} For any integers $k,l\ge 1$, construct a sequence of $kl$ distinct integers with no increasing
subsequence of length $k + 1$ and with no decreasing subsequence of length $l + 1$.


\bigskip

\noindent{\bf 5.} 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 6.} Construct an explicit 2-edge-coloring of $K_{kl}$ to show that $R(k+1,l+1)\ge kl+1$.


\bigskip


\noindent{\bf 7.} 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 8.} 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 9.} Prove that $2^k\le R_k(3,3,...,3)\le (k+1)!$

\end{document}
