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

Problem 1

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

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

Problem 2

(Due to Frankl 1986)

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

Show that [math]\displaystyle{ |\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]\displaystyle{ n\le 2k }[/math] and [math]\displaystyle{ \mathcal{F}\subseteq{[n]\choose k} }[/math] be such a [math]\displaystyle{ k }[/math]-uniform set family that [math]\displaystyle{ S\cup T\neq [n] }[/math] for all [math]\displaystyle{ S,T\in\mathcal{F} }[/math].

How large can [math]\displaystyle{ |\mathcal{F}| }[/math] be at most?

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

Problem 4

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

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

Hint: Use Ramsey Theorem.