Combinatorics (Fall 2010)/Problem set 3
Problem 1
- 用König-Egerváry定理推出Hall定理。
- 用Dilworth定理推出König-Egerváry定理。
Problem 2
- 令 [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
- [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年才得到这个证明）