Combinatorics (Fall 2010)/Problem set 3

Problem 1

1. 用König-Egerváry定理推出Hall定理。
2. 用Dilworth定理推出König-Egerváry定理。

Problem 2

1. 令 [math]\displaystyle{ G(U,V,E) }[/math] 为一个二分图。令 [math]\displaystyle{ \delta_U }[/math] 为 [math]\displaystyle{ U }[/math] 这一侧的最小度数，[math]\displaystyle{ \Delta_V }[/math] 为 [math]\displaystyle{ V }[/math] 这一侧的最大度数。证明：如果[math]\displaystyle{ \delta_U\ge \Delta_V }[/math]，则存在一个 [math]\displaystyle{ G }[/math] 的匹配（matching）使得 [math]\displaystyle{ U }[/math] 中所有的点都被匹配。

Problem 3

1. [math]\displaystyle{ S_1,S_2,\ldots,S_n }[/math] 为任意n个不同的集合，证明：我们总能找到 [math]\displaystyle{ \mathcal{F}\subseteq \{S_1,S_2,\ldots,S_n\} }[/math] 使得 [math]\displaystyle{ |\mathcal{F}|\ge \lfloor\sqrt{n}\rfloor }[/math]；且对任意不同的 [math]\displaystyle{ A,B,C\in\mathcal{F} }[/math]，有 [math]\displaystyle{ A\cup B\neq C }[/math]。

（提示：用Dilworth定理。）

大挑战（Erdős–Ko–Rado theorem）

我们称一个 [math]\displaystyle{ \mathcal{F}\subseteq{X\choose k} }[/math] 为 [math]\displaystyle{ t }[/math]-相交（[math]\displaystyle{ t }[/math]-intersecting），如果对于任意的 [math]\displaystyle{ S,T\in\mathcal{F} }[/math]，[math]\displaystyle{ |S\cap T|\ge t }[/math]。

证明：令 [math]\displaystyle{ \mathcal{F}\subseteq{X\choose k} }[/math] 且 [math]\displaystyle{ |X|=n }[/math]。如果 [math]\displaystyle{ \mathcal{F} }[/math] 为 [math]\displaystyle{ t }[/math]-相交，那么对于 [math]\displaystyle{ k\gt t\ge 1 }[/math] 且 [math]\displaystyle{ n }[/math] 足够大，有 [math]\displaystyle{ |\mathcal{F}|\le{n-t\choose k-t} }[/math]。

（Erdős, Ko, Rado三人拖了23年才得到这个证明）