组合数学 (Spring 2013)/Problem Set 3

From EtoneWiki
Jump to: navigation, search

Problem 1

一个-超图 (-uniform hypergraph) blocking set 是这样一个集合 ,使每一个超边 (hyper-edge) 都有

注:当 的时候, 就是一个图,而 blocking set 就是这个图的顶点覆盖(vertex cover)。因此,blocking set 就是顶点覆盖在超图(hypergraph)上的推广。我们知道最小定点覆盖(minimum vertex cover)问题是 NP-hard 问题,因此求最小 blocking set 也是难的。

证明:任何 , ,都存在一个不大于 的 blocking set。

第一题做小小改动。为了防止的极端情况。

Problem 2

一个图 支配集 (dominating set) 是一个顶点集合 ,使得每个顶点 要么属于 要么有邻居属于 。最小支配集 (minimum dominating set) 是 NP-hard问题。

证明:任何一个 个顶点的 -regular 图(每个顶点恰好有 个邻居),必然存在一个不大于 的支配集。

Problem 3

为一个图, 为一个整数。已知存在一个图 不包含 子图。

证明:对于 ,存在一个对 结点完全图)的 着色,没有单色(monocharomatic)的

注:令 的边集为 ,“对 的边的 着色",就是一个映射 。 即,每个边选择 种颜色之一进行着色,可以任意着色,无需考虑相邻的边是否同色。

Problem 4

为一个 -uniform -regular hypergraph,即 ,刚好有 个不同的 满足

假设 。证明:存在一个对 的 2着色 使得 中不存在单色的集合

Problem 5

一个图 的 independence number 中最大的独立集 (independent set) 的大小。证明Turán定理的对偶(dual)版本:

定理
如果图 个结点, 条边,,则

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

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