# 组合数学 (Spring 2013)/Problem Set 4

## Problem 1

Let ${\displaystyle k\leq {\frac {n}{2}}}$ and ${\displaystyle {\mathcal {F}}\subset 2^{[n]}}$ consist of sets of size at most ${\displaystyle k}$, i.e. ${\displaystyle \forall S\in {\mathcal {F}}}$, it holds that ${\displaystyle |S|\leq k}$.

Show that if ${\displaystyle {\mathcal {F}}}$ is an antichain then ${\displaystyle |{\mathcal {F}}|\leq {n \choose k}}$.

## Problem 2

(Due to Frankl 1986)

Let ${\displaystyle {\mathcal {F}}\subseteq {[n] \choose k}}$ be a ${\displaystyle k}$-uniform set family satisfying that ${\displaystyle A\cap B\not \subset C}$ for any ${\displaystyle A,B,C\in {\mathcal {F}}}$.

Show that ${\displaystyle |{\mathcal {F}}|\leq 1+{k \choose \lfloor k/2\rfloor }}$.

Hint: Use Sperner's theorem. Consider how to construct the antichain.

## Problem 3

Let ${\displaystyle n\leq 2k}$ and ${\displaystyle {\mathcal {F}}\subseteq {[n] \choose k}}$ be such a ${\displaystyle k}$-uniform set family that ${\displaystyle S\cup T\neq [n]}$ for all ${\displaystyle S,T\in {\mathcal {F}}}$.

How large can ${\displaystyle |{\mathcal {F}}|}$ be at most?

Hint: Use Erdos-Ko-Rado theorem. Consider how to construct an intersecting family out of ${\displaystyle {\mathcal {F}}}$.

## Problem 4

An ${\displaystyle n}$-player tournament (竞赛图) ${\displaystyle T([n],E)}$ is said to be transitive, if there exists a permutation ${\displaystyle \pi }$ of ${\displaystyle [n]}$ such that ${\displaystyle \pi _{i}<\pi _{j}}$ for every ${\displaystyle (i,j)\in E}$.

Show that for any ${\displaystyle k\geq 3}$, there exists an ${\displaystyle N(k)}$ such that every tournament of ${\displaystyle n\geq N(k)}$ players contains a transitive sub-tournament of ${\displaystyle k}$ players.

Hint: Use Ramsey Theorem.