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

From EtoneWiki
Jump to: navigation, search

Problem 1

为任意长为 的整数序列。

证明:存在 满足 使得 可被 整除。

Problem 2

Attention:这道题目我上课之前临时改了一下,现在发现改错了,于是又改回去了。请同学们相互转告。

一个无向图 的切 (cut) 被某个点集 定义,为 ,即那些一头在 中另一头在 的补中的边。求一个图的最大切 (maximum cut) 是 Karp 的21个NP完全问题之一

证明:任意一个有 条边的无向图都存在一个不 的切。

Problem 3

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

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