Combinatorics (Fall 2010)/Problem set 4

Problem 1

(D. E. Knuth)

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

（提示：一个词——"shadow"）

Problem 3

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

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

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

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

对于任意得实数 [math]\displaystyle{ x }[/math]，我们可以定义广义二项式系数(generalized binomial coefficient) 如下：

[math]\displaystyle{ {x\choose k}=\frac{x(x-1)\cdots(x-k+1)}{k!} }[/math]

Theorem (Lovász)

Let [math]\displaystyle{ \mathcal{F}\subseteq {X\choose k} }[/math] with [math]\displaystyle{ |\mathcal{F}|=m }[/math], and suppose that [math]\displaystyle{ m={x\choose k} }[/math] for some real number [math]\displaystyle{ x\ge k }[/math]. Then [math]\displaystyle{ |\Delta\mathcal{F}|\ge {x\choose k-1} }[/math].

证明该定理。