Combinatorics (Fall 2010)/Problem set 4: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
imported>WikiSysop
imported>WikiSysop
Line 3: Line 3:


#一万条边的图,最多可以包含多少个三角形(<math>K_3</math> 完全子图)?给出证明。
#一万条边的图,最多可以包含多少个三角形(<math>K_3</math> 完全子图)?给出证明。
#推广:一个图有 <math>m</math> 条边,最多可以包含多少个 <math>K_k</math>?
#推广:一个图有 <math>m</math> 条边,最多可以包含多少个 <math>K_k</math>(<math>k</math> 点完全子图)


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

Revision as of 08:55, 17 November 2010

Problem 1

(D. E. Knuth)

  1. 一万条边的图,最多可以包含多少个三角形([math]\displaystyle{ K_3 }[/math] 完全子图)?给出证明。
  2. 推广:一个图有 [math]\displaystyle{ m }[/math] 条边,最多可以包含多少个 [math]\displaystyle{ K_k }[/math]([math]\displaystyle{ k }[/math] 点完全子图)?

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

Problem 2

Problem 3

大挑战 (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].

证明该定理。