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

Problem 1

一个set family [math]\displaystyle{ \mathcal{F}\subset{[n]\choose k} }[/math] 的 blocking set 是这样一个集合 [math]\displaystyle{ T\subseteq[n] }[/math]，使每一个 member set [math]\displaystyle{ A\in\mathcal{F} }[/math] 都有 [math]\displaystyle{ T\cap A\neq\emptyset }[/math]。当 [math]\displaystyle{ k=2 }[/math] 的时候，[math]\displaystyle{ \mathcal{F} }[/math] 就是一个图，而 blocking set [math]\displaystyle{ T }[/math] 就是这个图的顶点覆盖（vertex cover）。因此，blocking set 就是顶点覆盖在超图（hypergraph）上的推广。我们知道最小定点覆盖（minimum vertex cover）问题是 NP-hard 问题，因此求最小 blocking set 也是难的。

证明：任何 [math]\displaystyle{ \mathcal{F}\subset{[n]\choose k} }[/math], [math]\displaystyle{ |\mathcal{F}|=m }[/math]，都存在一个不大于 [math]\displaystyle{ \left\lceil\frac{n\ln m}{k}\right\rceil }[/math] 的 blocking set。

Problem 2

一个图 [math]\displaystyle{ G(V,E) }[/math] 的支配集 (dominating set) 是一个顶点集合 [math]\displaystyle{ D\subseteq V }[/math]，使得每个顶点 [math]\displaystyle{ v\in V }[/math] 要么属于 [math]\displaystyle{ D }[/math] 要么有邻居属于 [math]\displaystyle{ D }[/math]。最小支配集 (minimum dominating set) 是 NP-hard问题。

证明：任何一个 [math]\displaystyle{ n }[/math] 个顶点的 [math]\displaystyle{ d }[/math]-regular 图（每个顶点恰好有 [math]\displaystyle{ d }[/math] 个邻居），必然存在一个不大于 [math]\displaystyle{ \frac{n(1+\ln(d+1))}{d+1} }[/math] 的支配集。

Problem 3

一个图[math]\displaystyle{ G }[/math] 的 independence number [math]\displaystyle{ \alpha(G) }[/math] 为 [math]\displaystyle{ G }[/math] 中最大的独立集 (independent set) 的大小。证明Turán定理的对偶（dual）版本：

定理

如果图 [math]\displaystyle{ G }[/math] 有 [math]\displaystyle{ n }[/math] 个结点，[math]\displaystyle{ \frac{nk}{2} }[/math] 条边，[math]\displaystyle{ k\ge 1 }[/math]，则 [math]\displaystyle{ \alpha(G)\ge\frac{n}{k+1} }[/math]。

要求至少给出两个版本的证明：

1. 用概率法证明。
2. 用Turán定理直接证明。

Problem 4

[math]\displaystyle{ H(W,F)\, }[/math] 为一个图，[math]\displaystyle{ n\gt |W|\, }[/math] 为一个整数。已知存在一个图 [math]\displaystyle{ G(V,E)\, }[/math] 有 [math]\displaystyle{ |V|=n, |E|=m\, }[/math] 且不包含 [math]\displaystyle{ H\, }[/math] 子图。

证明：对于 [math]\displaystyle{ k\gt \frac{n^2\ln n}{m} }[/math]，存在一个对 [math]\displaystyle{ K_n\, }[/math]（[math]\displaystyle{ n }[/math]结点完全图）的边的 [math]\displaystyle{ k }[/math] 着色，没有单色（monocharomatic）的[math]\displaystyle{ H\, }[/math]。

注：令 [math]\displaystyle{ K_n }[/math] 的边集为 [math]\displaystyle{ E={V\choose 2} }[/math]，“对 [math]\displaystyle{ K_n }[/math] 的边的 [math]\displaystyle{ k }[/math] 着色"，就是一个映射 [math]\displaystyle{ f: E\rightarrow [k] }[/math]。 即，每个边选择 [math]\displaystyle{ k }[/math] 种颜色之一进行着色，可以任意着色，无需考虑相邻的边是否同色。

Problem 5

我们称一个竞赛图 [math]\displaystyle{ T([n],E) }[/math] 是传递(transitive)的，如果存在一个 [math]\displaystyle{ [n] }[/math] 的全排列 [math]\displaystyle{ \pi }[/math] 使得 [math]\displaystyle{ (i,j)\in E }[/math] 当且仅当 [math]\displaystyle{ \pi_i\lt \pi_j }[/math]，即该竞赛图 [math]\displaystyle{ T([n],E) }[/math] 的边的方向符合传递性。

证明：对任何 [math]\displaystyle{ k\ge 3 }[/math]，存在 [math]\displaystyle{ N(k) }[/math]，对任何的 [math]\displaystyle{ n\ge N(k) }[/math] 个点的竞赛图，都存在一个 [math]\displaystyle{ k }[/math] 个点的子竞赛图满足传递性。