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

From EtoneWiki
Jump to: navigation, search

Problem 1

Let and consist of sets of size at most , i.e. , it holds that .

Show that if is an antichain then .

Problem 2

(Due to Frankl 1986)

Let be a -uniform set family satisfying that for any .

Show that .

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

Problem 3

Let and be such a -uniform set family that for all .

How large can be at most?

Hint: Use Erdos-Ko-Rado theorem. Consider how to construct an intersecting family out of .

Problem 4

An -player tournament (竞赛图) is said to be transitive, if there exists a permutation of such that for every .

Show that for any , there exists an such that every tournament of players contains a transitive sub-tournament of players.

Hint: Use Ramsey Theorem.