Combinatorics (Fall 2010)/Problem set 2

From TCS Wiki
Revision as of 00:31, 15 October 2010 by imported>WikiSysop
Jump to navigation Jump to search

Problem 1

( Due to Karger )

8种颜色的小球,每种20只,放到6个盒子里。证明无论怎么放,一定有一个盒子包含两对不同颜色的球。

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

提示:用鸽笼原理。

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

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是什么?为什么?

大挑战

[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. 证明:[math]\displaystyle{ Z_a(n)=\Omega(n^{2-2/a})\, }[/math]