组合数学 (Spring 2013)/Problem Set 3: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
imported>Etone
imported>Etone
 
(5 intermediate revisions by the same user not shown)
Line 1: Line 1:
== Problem 1==
== Problem 1==
一个<math>k</math>-超图 (<math>k</math>-uniform hypergraph) <math>\mathcal{H}\subset{[n]\choose k}</math> 的 '''blocking set''' 是这样一个集合 <math>T\subseteq[n]</math>,使每一个超边 (hyper-edge) <math>S\in\mathcal{H}</math> 都有 <math>T\cap S\neq\emptyset</math>。当 <math>k=2</math> 的时候,<math>\mathcal{H}</math> 就是一个图,而 blocking set <math>T</math> 就是这个图的顶点覆盖(vertex cover)。因此,blocking set 就是顶点覆盖在超图(hypergraph)上的推广。我们知道最小定点覆盖(minimum vertex cover)问题是 NP-hard 问题,因此求最小 blocking set 也是难的。
一个<math>k</math>-超图 (<math>k</math>-uniform hypergraph) <math>\mathcal{H}\subset{[n]\choose k}</math> 的 '''blocking set''' 是这样一个集合 <math>T\subseteq[n]</math>,使每一个超边 (hyper-edge) <math>S\in\mathcal{H}</math> 都有 <math>T\cap S\neq\emptyset</math>


证明:任何 <math>\mathcal{F}\subset{[n]\choose k}</math>, <math>|\mathcal{F}|=m</math>,都存在一个不大于 <math>\left\lceil\frac{n\ln m}{k}\right\rceil</math> 的 blocking set。
注:当 <math>k=2</math> 的时候,<math>\mathcal{H}</math> 就是一个图,而 blocking set <math>T</math> 就是这个图的顶点覆盖(vertex cover)。因此,blocking set 就是顶点覆盖在超图(hypergraph)上的推广。我们知道最小定点覆盖(minimum vertex cover)问题是 NP-hard 问题,因此求最小 blocking set 也是难的。
 
证明:任何 <math>\mathcal{H}\subset{[n]\choose k}</math>, <math>|\mathcal{H}|=m</math>,都存在一个不大于 <math>\left\lceil\frac{n\ln (m{\color{red}+1})}{k}\right\rceil</math> 的 blocking set。
 
<font color=red>第一题做小小改动。为了防止<math>m=1</math>的极端情况。</font>


== Problem 2==
== Problem 2==
Line 22: Line 26:
假设 <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>。
假设 <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>。


==Problem 5 ==
== Problem 5 ==
我们称一个[http://en.wikipedia.org/wiki/Tournament_(graph_theory) '''竞赛图'''] <math>T([n],E)</math> 是[http://en.wikipedia.org/wiki/Tournament_(graph_theory)#Transitivity 传递(transitive)]的,如果存在一个 <math>[n]</math> 的全排列 <math>\pi</math> 使得 <math>(i,j)\in E</math> 当且仅当 <math>\pi_i<\pi_j</math>,即该竞赛图 <math>T([n],E)</math> 的边的方向符合传递性。
一个图<math>G</math> 的 independence number <math>\alpha(G)</math> 为 <math>G</math> 中最大的独立集 (independent set) 的大小。证明Turán定理的对偶(dual)版本:
{{Theorem|定理|
:如果图 <math>G</math> <math>n</math> 个结点,<math>\frac{nk}{2}</math> 条边,<math>k\ge 1</math>,则 <math>\alpha(G)\ge\frac{n}{k+1}</math>
}}


证明:对任何 <math>k\ge 3</math>,存在 <math>N(k)</math>,对任何的 <math>n\ge N(k)</math> 个点的竞赛图,都存在一个 <math>k</math> 个点的子竞赛图满足传递性。
要求至少给出两个版本的证明:
#用概率法证明。
#用Turán定理直接证明。

Latest revision as of 08:21, 19 May 2013

Problem 1

一个[math]\displaystyle{ k }[/math]-超图 ([math]\displaystyle{ k }[/math]-uniform hypergraph) [math]\displaystyle{ \mathcal{H}\subset{[n]\choose k} }[/math]blocking set 是这样一个集合 [math]\displaystyle{ T\subseteq[n] }[/math],使每一个超边 (hyper-edge) [math]\displaystyle{ S\in\mathcal{H} }[/math] 都有 [math]\displaystyle{ T\cap S\neq\emptyset }[/math]

注:当 [math]\displaystyle{ k=2 }[/math] 的时候,[math]\displaystyle{ \mathcal{H} }[/math] 就是一个图,而 blocking set [math]\displaystyle{ T }[/math] 就是这个图的顶点覆盖(vertex cover)。因此,blocking set 就是顶点覆盖在超图(hypergraph)上的推广。我们知道最小定点覆盖(minimum vertex cover)问题是 NP-hard 问题,因此求最小 blocking set 也是难的。

证明:任何 [math]\displaystyle{ \mathcal{H}\subset{[n]\choose k} }[/math], [math]\displaystyle{ |\mathcal{H}|=m }[/math],都存在一个不大于 [math]\displaystyle{ \left\lceil\frac{n\ln (m{\color{red}+1})}{k}\right\rceil }[/math] 的 blocking set。

第一题做小小改动。为了防止[math]\displaystyle{ m=1 }[/math]的极端情况。

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{ 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 4

[math]\displaystyle{ \mathcal{H}\subseteq{[n]\choose k} }[/math] 为一个 [math]\displaystyle{ k }[/math]-uniform [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]

Problem 5

一个图[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定理直接证明。