组合数学 (Fall 2011)/Problem set 3

Problem 2

一个图 [math]\displaystyle{ G(V,E) }[/math] 的切 (cut) 是一个边集 [math]\displaystyle{ C\subseteq E }[/math]，使得去掉这些边之后 [math]\displaystyle{ G }[/math] 不再连通。

证明：任意一个有 [math]\displaystyle{ m }[/math] 条边的无向图都存在一个大小为 [math]\displaystyle{ \frac{m}{2} }[/math] 的切。

Problem 3

令 [math]\displaystyle{ \mathcal{F}\subseteq{[n]\choose k} }[/math] 为一个 [math]\displaystyle{ k }[/math]-regular family，即 [math]\displaystyle{ \forall i\in[n] }[/math]，刚好有 [math]\displaystyle{ k }[/math] 个不同的 [math]\displaystyle{ S\in\mathcal{F} }[/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{F} }[/math] 中不存在单色的集合 [math]\displaystyle{ S\in\mathcal{F} }[/math]。