Combinatorics (Fall 2010)/Problem set 3

From TCS Wiki
Revision as of 14:34, 28 October 2010 by imported>WikiSysop (→‎大挑战(Erdős–Ko–Rado theorem))
Jump to navigation Jump to search

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年才得到这个证明)