Combinatorics (Fall 2010)/Problem set 4

From EtoneWiki
Jump to: navigation, search

Problem 1

(D. E. Knuth)

  1. 一万条边的图,最多可以包含多少个三角形([math]K_3[/math] 完全子图)?给出证明。
  2. 推广:一个图有 [math]m[/math] 条边,最多可以包含多少个 [math]k[/math]-clique ([math]k[/math] 点完全子图)?(不需要closed form)

(提示:一个词——"shadow")

Problem 2

我们称一个竞赛图 [math]T([n],E)[/math]传递(transitive)的,如果存在一个 [math][n][/math] 的全排列 [math]\pi[/math] 使得 [math](i,j)\in E[/math] 当且仅当 [math]\pi_i\lt \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] 个点的子竞赛图满足传递性。

Problem 3

[math]\mathcal{F}\subseteq{[n]\choose k}[/math] 为一个 [math]k[/math]-regular family,即 [math]\forall i\in[n][/math],刚好有 [math]k[/math] 个不同的 [math]S\in\mathcal{F}[/math] 满足 [math]i\in S[/math]

假设 [math]k\ge 10[/math]。证明:存在一个对 [math][n][/math] 的 2着色 [math]f:[n]\rightarrow\{0,1\}[/math] 使得 [math]\mathcal{F}[/math] 中不存在单色的集合 [math]S\in\mathcal{F}[/math]

大挑战 (Lovász's simplified version of the Kruskal-Katona theorem)

虽然 Kruskal-Katona theorem 很强大,但由于其陈述比较复杂,导致其应用受到很多限制。为此,Lovász 建议如下的简化版本:

对于任意得实数 [math]x[/math],我们可以定义广义二项式系数(generalized binomial coefficient) 如下:

[math]{x\choose k}=\frac{x(x-1)\cdots(x-k+1)}{k!}[/math]
Theorem (Lovász)
Let [math]\mathcal{F}\subseteq {X\choose k}[/math] with [math]|\mathcal{F}|=m[/math], and suppose that [math]m={x\choose k}[/math] for some real number [math]x\ge k[/math]. Then
[math]|\Delta\mathcal{F}|\ge {x\choose k-1}[/math].

证明该定理。