Combinatorics (Fall 2010)/Problem set 3: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
imported>WikiSysop
imported>WikiSysop
 
(4 intermediate revisions by the same user not shown)
Line 4: Line 4:


== Problem 2 ==
== Problem 2 ==
# 令 <math>G(U,V,E)</math> 为一个二分图。令 <math>\delta_U</math> 为 <math>U</math> 这一侧的最小度数,<math>\Delta_V</math> 为 <math>V</math> 这一侧的最大度数。证明:如果<math>\delta_U\ge \Delta_V</math>,则存在一个 <math>G</math> 的匹配(matching)使得 <math>U</math> 中所有的点都被匹配。
令 <math>G(U,V,E)</math> 为一个二分图。令 <math>\delta_U</math> 为 <math>U</math> 这一侧的最小度数,<math>\Delta_V</math> 为 <math>V</math> 这一侧的最大度数。证明:如果<math>\delta_U\ge \Delta_V</math>,则存在一个 <math>G</math> 的匹配(matching)使得 <math>U</math> 中所有的点都被匹配。


== Problem 3 ==
== Problem 3 ==
# <math>S_1,S_2,\ldots,S_n</math> 为任意n个不同的集合,证明:我们总能找到 <math>\mathcal{F}\subseteq \{S_1,S_2,\ldots,S_n\}</math> 使得 <math>|\mathcal{F}|\ge \lfloor\sqrt{n}\rfloor</math>;且对任意不同的 <math>A,B,C\in\mathcal{F}</math>,有 <math>A\cup B\neq C</math>。
<math>S_1,S_2,\ldots,S_n</math> 为任意n个不同的集合,证明:我们总能找到 <math>\mathcal{F}\subseteq \{S_1,S_2,\ldots,S_n\}</math> 使得 <math>|\mathcal{F}|\ge \lfloor\sqrt{n}\rfloor</math>;且对任意不同的 <math>A,B,C\in\mathcal{F}</math>,有 <math>A\cup B\neq C</math>。


(提示:用Dilworth定理。)
(提示:用Dilworth定理。)
Line 14: Line 14:
我们称一个 <math>\mathcal{F}\subseteq{X\choose k}</math> 为 <math>t</math>-相交('''<math>t</math>-intersecting'''),如果对于任意的 <math>S,T\in\mathcal{F}</math>,<math>|S\cap T|\ge t</math>。
我们称一个 <math>\mathcal{F}\subseteq{X\choose k}</math> 为 <math>t</math>-相交('''<math>t</math>-intersecting'''),如果对于任意的 <math>S,T\in\mathcal{F}</math>,<math>|S\cap T|\ge t</math>。


证明:令 <math>\mathcal{F}\subseteq{X\choose k}</math> 且 <math>|X|=n</math>。如果 <math>\mathcal{F}</math> <math>t</math>-相交,那么对于 <math>k>t\ge 1</math> <math>n</math> 足够大,有 <math>|\mathcal{F}|\le{n-t\choose k-t}</math>。
证明:令 <math>\mathcal{F}\subseteq{X\choose k}</math> 且 <math>|X|=n</math>。对于 <math>k>t\ge 1</math> <math>n</math> 足够大,如果 <math>\mathcal{F}</math> <math>t</math>-相交,则必有 <math>|\mathcal{F}|\le{n-t\choose k-t}</math>。
 
(注:Erdős, Ko, Rado三人拖了23年才得到这个证明。)

Latest revision as of 11:34, 7 November 2010

Problem 1

  1. 用König-Egerváry定理推出Hall定理。
  2. 用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{ k\gt t\ge 1 }[/math][math]\displaystyle{ n }[/math] 足够大,如果 [math]\displaystyle{ \mathcal{F} }[/math][math]\displaystyle{ t }[/math]-相交,则必有 [math]\displaystyle{ |\mathcal{F}|\le{n-t\choose k-t} }[/math]