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

From TCS Wiki
Jump to navigation Jump to search
imported>WikiSysop
imported>WikiSysop
m Protected "Combinatorics (Fall 2010)/Problem set 4" ([edit=sysop] (indefinite) [move=sysop] (indefinite))
 
(14 intermediate revisions by 2 users not shown)
Line 2: Line 2:
(D. E. Knuth)
(D. E. Knuth)


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


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


==Problem 2 ==
==Problem 2 ==
我们称一个[http://en.wikipedia.org/wiki/Tournament_(graph_theory) '''竞赛图'''] <math>T([n],E)</math> 是[http://en.wikipedia.org/wiki/Tournament_(graph_theory)#Transitivity 传递(transitive)]的,如果存在一个 <math>[n]</math> 的全排列 <math>\pi</math> 使得 <math>(i,j)\in E</math> 当且仅当 <math>\pi_i<\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 ==
==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)==
== 大挑战 (Lovász's simplified version of the Kruskal-Katona theorem)==

Latest revision as of 09:08, 12 January 2011

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 2

我们称一个竞赛图 [math]\displaystyle{ T([n],E) }[/math]传递(transitive)的,如果存在一个 [math]\displaystyle{ [n] }[/math] 的全排列 [math]\displaystyle{ \pi }[/math] 使得 [math]\displaystyle{ (i,j)\in E }[/math] 当且仅当 [math]\displaystyle{ \pi_i\lt \pi_j }[/math],即该竞赛图 [math]\displaystyle{ T([n],E) }[/math] 的边的方向符合传递性。

证明:对任何 [math]\displaystyle{ k\ge 3 }[/math],存在 [math]\displaystyle{ N(k) }[/math],对任何的 [math]\displaystyle{ n\ge N(k) }[/math] 个点的竞赛图,都存在一个 [math]\displaystyle{ k }[/math] 个点的子竞赛图满足传递性。

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].

证明该定理。