Combinatorics (Fall 2010)/Problem set 3

From EtoneWiki
Jump to: navigation, search

Problem 1

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

Problem 2

为一个二分图。令 这一侧的最小度数, 这一侧的最大度数。证明:如果,则存在一个 的匹配(matching)使得 中所有的点都被匹配。

Problem 3

为任意n个不同的集合,证明:我们总能找到 使得 ;且对任意不同的 ,有

(提示:用Dilworth定理。)

大挑战(Erdős–Ko–Rado theorem)

我们称一个 -相交(-intersecting),如果对于任意的

证明:令 。对于 足够大,如果 -相交,则必有