Combinatorics (Fall 2010)/Problem set 2

From EtoneWiki
Jump to: navigation, search

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

Problem 1

( Due to Karger )

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

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

(提示:用鸽笼原理。)

Problem 2

一个图 的 independence number 中最大的独立集 (independent set) 的大小。证明Turán定理的对偶(dual)版本:

定理
如果图 个结点, 条边,,则

Problem 3

为一个图, 为一个整数。已知存在一个图 不包含 子图。

证明:对于 ,存在一个对 结点完全图)的 着色,没有单色(monocharomatic)的

注:令 的边集为 ,“对 的边的 着色",就是一个映射 。 即,每个边选择 种颜色之一进行着色,可以任意着色,无需考虑相邻的边是否同色。

(提示:概率法。)

Problem 4

  1. 证明:如果 "almost always" 具有property ,并且 "almost always" 具有property ,则 "almost always" 同时具有property
  2. 定义图性质为:包含一个k个点的树的子图。性质P是否有threshold;如果有的话,threshold是什么?为什么?

大挑战 (Zarankiewicz's problem)

,令 为符合如下条件的最小的 :所有包含多于 个 1 的 的 0-1 矩阵都必有 的全1的子矩阵(行、列未必连续)。

  1. 证明:如果一个二分图(bipartite graph)(即左、右两边各个点)且不包含子图 (左、右两边各个点的完全二分图),则
  2. (due to Erdős-Spencer) 证明: