组合数学 (Fall 2011)/Problem set 3: Difference between revisions
imported>Etone |
imported>Etone |
||
Line 7: | Line 7: | ||
==Problem 3 == | ==Problem 3 == | ||
令 <math>\mathcal{H}\subseteq{[n]\choose k}</math> 为一个 <math>k</math>-regular hypergraph,即 <math>\forall i\in[n]</math>,刚好有 <math>k</math> 个不同的 <math>S\in\mathcal{ | 令 <math>\mathcal{H}\subseteq{[n]\choose k}</math> 为一个 <math>k</math>-regular hypergraph,即 <math>\forall i\in[n]</math>,刚好有 <math>k</math> 个不同的 <math>S\in\mathcal{H}</math> 满足 <math>i\in S</math>。 | ||
假设 <math>k\ge 10</math>。证明:存在一个对 <math>[n]</math> 的 2着色 <math>f:[n]\rightarrow\{0,1\}</math> 使得 <math>\mathcal{ | 假设 <math>k\ge 10</math>。证明:存在一个对 <math>[n]</math> 的 2着色 <math>f:[n]\rightarrow\{0,1\}</math> 使得 <math>\mathcal{H}</math> 中不存在单色的集合 <math>S\in\mathcal{H}</math>。 |
Revision as of 17:56, 26 October 2011
Problem 1
Problem 2
一个图 [math]\displaystyle{ G(V,E) }[/math] 的切 (cut) 是一个边集 [math]\displaystyle{ C\subseteq E }[/math],使得去掉这些边之后 [math]\displaystyle{ G }[/math] 不再连通。求一个图的最大切 (maximum cut) 是 Karp 的21个NP完全问题之一。
证明:任意一个有 [math]\displaystyle{ m }[/math] 条边的无向图都存在一个不小于 [math]\displaystyle{ \frac{m}{2} }[/math] 的切。
Problem 3
令 [math]\displaystyle{ \mathcal{H}\subseteq{[n]\choose k} }[/math] 为一个 [math]\displaystyle{ k }[/math]-regular hypergraph,即 [math]\displaystyle{ \forall i\in[n] }[/math],刚好有 [math]\displaystyle{ k }[/math] 个不同的 [math]\displaystyle{ S\in\mathcal{H} }[/math] 满足 [math]\displaystyle{ i\in S }[/math]。
假设 [math]\displaystyle{ k\ge 10 }[/math]。证明:存在一个对 [math]\displaystyle{ [n] }[/math] 的 2着色 [math]\displaystyle{ f:[n]\rightarrow\{0,1\} }[/math] 使得 [math]\displaystyle{ \mathcal{H} }[/math] 中不存在单色的集合 [math]\displaystyle{ S\in\mathcal{H} }[/math]。