Combinatorics (Fall 2010)/Problem set 2

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

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] 种颜色之一进行着色，可以任意着色，无需考虑相邻的边是否同色（这种情况称为"proper“ coloring）。

(提示：概率法。)

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]。