Combinatorics (Fall 2010)/Problem set 2: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
imported>WikiSysop
imported>WikiSysop
 
(12 intermediate revisions by the same user not shown)
Line 1: Line 1:
<font color=red size=3>第一题原说法有歧义,现在改成更精确的说法了。</font>
== Problem 1 ==
== Problem 1 ==
( Due to Karger )
( Due to Karger )


8种颜色的小球,每种20只,放到6个盒子里。证明无论怎么放,一定有一个盒子包含两对不同颜色的球。
8种颜色的小球,每种20只,放到6个盒子里。证明无论怎么放,一定有一个盒子包含两对不同的小球 <math>\{a,b\}</math> 和 <math>\{�c,d\}</math>:每对小球的颜色都相同(即 <math>\{a,b\}</math> 颜色相同,<math>\{�c,d\}</math> 颜色相同),但两对球具有不同颜色(即 <math>\{a,b\}</math> 的颜色和 <math>\{c,d\}</math> 不同)。


尝试推广到一般情况(自己设计如何推广)。
尝试推广到一般情况(自己设计如何推广)。


提示:用鸽笼原理。
(提示:用鸽笼原理。)


== Problem 2 ==
== Problem 2 ==
Line 18: Line 20:


证明:对于 <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>\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> 种颜色之一进行着色,可以任意着色,无需考虑相邻的边是否同色。


(提示:概率法。)
(提示:概率法。)
Line 25: Line 30:
# 定义图性质<math>P</math>为:包含一个k个点的树的子图。性质P是否有threshold;如果有的话,threshold是什么?为什么?
# 定义图性质<math>P</math>为:包含一个k个点的树的子图。性质P是否有threshold;如果有的话,threshold是什么?为什么?


== 大挑战 ==
== 大挑战 (Zarankiewicz's problem) ==
对 <math>a\ge 2</math>,令 <math>Z_a(n)</math> 为符合如下条件的最小的 <math>k</math>:所有包含多于 <math>k</math> 个 1 的 <math>n\times n</math> 的 0-1 矩阵都必有<math>a\times a</math> 的全1的子矩阵。
对 <math>a\ge 2</math>,令 <math>Z_a(n)</math> 为符合如下条件的最小的 <math>k</math>:所有包含多于 <math>k</math> 个 1 的 <math>n\times n</math> 的 0-1 矩阵都必有<math>a\times a</math> 的全1的子矩阵(行、列未必连续)。


# 证明:如果一个二分图(bipartite graph)<math>G(V_1,V_2,E)</math> 有 <math>|V_1|=|V_2|=n</math>(即左、右两边各<math>n</math>个点)且不包含子图 <math>K_{a,a}</math>(左、右两边各<math>a</math>个点的完全二分图),则 <math>|E|\le Z_a(n)</math>。
# 证明:如果一个二分图(bipartite graph)<math>G(V_1,V_2,E)</math> 有 <math>|V_1|=|V_2|=n</math>(即左、右两边各<math>n</math>个点)且不包含子图 <math>K_{a,a}</math>(左、右两边各<math>a</math>个点的完全二分图),则 <math>|E|\le Z_a(n)</math>。
# 证明:<math>Z_a(n)=\Omega(n^{2-2/a})\,</math>。
# (due to Erdős-Spencer) 证明:<math>Z_a(n)=\Omega(n^{2-2/a})\,</math>。

Latest revision as of 02:23, 24 October 2010

第一题原说法有歧义,现在改成更精确的说法了。

Problem 1

( Due to Karger )

8种颜色的小球,每种20只,放到6个盒子里。证明无论怎么放,一定有一个盒子包含两对不同的小球 [math]\displaystyle{ \{a,b\} }[/math][math]\displaystyle{ \{�c,d\} }[/math]:每对小球的颜色都相同(即 [math]\displaystyle{ \{a,b\} }[/math] 颜色相同,[math]\displaystyle{ \{�c,d\} }[/math] 颜色相同),但两对球具有不同颜色(即 [math]\displaystyle{ \{a,b\} }[/math] 的颜色和 [math]\displaystyle{ \{c,d\} }[/math] 不同)。

尝试推广到一般情况(自己设计如何推广)。

(提示:用鸽笼原理。)

Problem 2

一个图[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]

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

  1. 证明:如果 [math]\displaystyle{ G(n,p) }[/math] "almost always" 具有property [math]\displaystyle{ P_1 }[/math],并且 [math]\displaystyle{ G(n,p) }[/math] "almost always" 具有property [math]\displaystyle{ P_2 }[/math],则 [math]\displaystyle{ G(n,p) }[/math] "almost always" 同时具有property [math]\displaystyle{ P_1 }[/math][math]\displaystyle{ P_2 }[/math]
  2. 定义图性质[math]\displaystyle{ P }[/math]为:包含一个k个点的树的子图。性质P是否有threshold;如果有的话,threshold是什么?为什么?

大挑战 (Zarankiewicz's problem)

[math]\displaystyle{ a\ge 2 }[/math],令 [math]\displaystyle{ Z_a(n) }[/math] 为符合如下条件的最小的 [math]\displaystyle{ k }[/math]:所有包含多于 [math]\displaystyle{ k }[/math] 个 1 的 [math]\displaystyle{ n\times n }[/math] 的 0-1 矩阵都必有[math]\displaystyle{ a\times a }[/math] 的全1的子矩阵(行、列未必连续)。

  1. 证明:如果一个二分图(bipartite graph)[math]\displaystyle{ G(V_1,V_2,E) }[/math][math]\displaystyle{ |V_1|=|V_2|=n }[/math](即左、右两边各[math]\displaystyle{ n }[/math]个点)且不包含子图 [math]\displaystyle{ K_{a,a} }[/math](左、右两边各[math]\displaystyle{ a }[/math]个点的完全二分图),则 [math]\displaystyle{ |E|\le Z_a(n) }[/math]
  2. (due to Erdős-Spencer) 证明:[math]\displaystyle{ Z_a(n)=\Omega(n^{2-2/a})\, }[/math]