组合数学 (Spring 2013)/Counting and existence and 组合数学 (Spring 2013)/Problem Set 3: Difference between pages
imported>Etone |
imported>Etone |
||
| Line 1: | Line 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>\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。 | |||
== Problem 2== | |||
一个图 <math>G(V,E)</math> 的'''支配集''' (dominating set) 是一个顶点集合 <math>D\subseteq V</math>，使得每个顶点 <math>v\in V</math> 要么属于 <math>D</math> 要么有邻居属于 <math>D</math>。最小支配集 (minimum dominating set) 是 NP-hard问题。 | |||
证明：任何一个 <math>n</math> 个顶点的 <math>d</math>-regular 图（每个顶点恰好有 <math>d</math> 个邻居），必然存在一个不大于 <math>\frac{n(1+\ln(d+1))}{d+1}</math> 的支配集。 | |||
== Problem 3 == | |||
<math>H(W,F)\,</math> 为一个图，<math>n>|W|\,</math> 为一个整数。已知存在一个图 <math>G(V,E)\,</math> 有 <math>|V|=n, |E|=m\,</math> 且<font color=red>不包含</font> <math>H\,</math> 子图。 | |||
证明：对于 <math>k>\frac{n^2\ln n}{m}</math>，存在一个对 <math>K_n\,</math>（<math>n</math>结点完全图）的<font color=red>边</font>的 <math>k</math> 着色，没有单色（monocharomatic）的<math>H\,</math>。 | |||
注：令 <math>K_n</math> 的边集为 <math>E={V\choose 2}</math>，“对 <math>K_n</math> 的边的 <math>k</math> 着色"，就是一个映射 <math>f: E\rightarrow [k]</math>。 | |||
即，每个边选择 <math>k</math> 种颜色之一进行着色，可以任意着色，无需考虑相邻的边是否同色。 | |||
== Problem 4 == | |||
令 <math>\mathcal{H}\subseteq{[n]\choose k}</math> 为一个 <math>k</math>-uniform <math>k</math>-regular hypergraph，即 <math>\forall i\in[n]</math>，刚好有 <math>k</math> 个不同的 <math>S\in\mathcal{H}</math> 满足 <math>i\in S</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 == | |||
我们称一个[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>k\ge 3</math>，存在 <math>N(k)</math>，对任何的 <math>n\ge N(k)</math> 个点的竞赛图，都存在一个 <math>k</math> 个点的子竞赛图满足传递性。 | |||
Revision as of 15:14, 8 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{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{ 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{ 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] 个点的子竞赛图满足传递性。