Combinatorics (Fall 2010)/Problem set 3: Difference between revisions
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> 中所有的点都被匹配。 | |||
== 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>。 | |||
（提示：用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}\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>。 | ||
Latest revision as of 11:34, 7 November 2010
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{ 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]。