View source for 组合数学 (Spring 2013)/Problem Set 4

==Problem 1==
Let <math>k\le\frac{n}{2}</math> and <math>\mathcal{F}\subset 2^{[n]}</math> consist of sets of size at most <math>k</math>, i.e. <math>\forall S\in\mathcal{F}</math>, it holds that <math>|S|\le k</math>.

Show that if <math>\mathcal{F}</math> is an antichain then <math>|\mathcal{F}|\le{n\choose k}</math>.

==Problem 2==
(Due to Frankl 1986)

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

Show that <math>|\mathcal{F}|\le1+{k\choose\lfloor k/2\rfloor}</math>.

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

== Problem 3==
Let <math>n\le 2k</math> and <math>\mathcal{F}\subseteq{[n]\choose k}</math> be such a <math>k</math>-uniform set family that <math>S\cup T\neq [n]</math> for all <math>S,T\in\mathcal{F}</math>.

How large can <math>|\mathcal{F}|</math> be at most?

Hint: Use Erdos-Ko-Rado theorem. Consider how to construct an intersecting family out of <math>\mathcal{F}</math>.

==Problem 4 ==
An <math>n</math>-player tournament (竞赛图) <math>T([n],E)</math> is said to be transitive, if there exists a permutation <math>\pi</math> of <math>[n]</math> such that <math>\pi_i<\pi_j</math> for every <math>(i,j)\in E</math>.

Show that for any <math>k\ge 3</math>, there exists an <math>N(k)</math> such that every tournament of <math>n\ge N(k)</math> players contains a transitive sub-tournament of <math>k</math> players.

Hint: Use Ramsey Theorem.