Combinatorics (Fall 2010)/Problem set 4

From EtoneWiki
Jump to: navigation, search

Problem 1

(D. E. Knuth)

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

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

Problem 2

我们称一个竞赛图 传递(transitive)的,如果存在一个 的全排列 使得 当且仅当 ,即该竞赛图 的边的方向符合传递性。

证明:对任何 ,存在 ,对任何的 个点的竞赛图,都存在一个 个点的子竞赛图满足传递性。

Problem 3

为一个 -regular family,即 ,刚好有 个不同的 满足

假设 。证明:存在一个对 的 2着色 使得 中不存在单色的集合

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

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

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

Theorem (Lovász)
Let with , and suppose that for some real number . Then
.

证明该定理。