特殊篇章（数学定理）二 (6-3)

4K A′⊆A， B′⊆B ，使得对任何 α∈A′，b∈B′ 至少有 |A||B|

───条 3 路径相连

2¹² K⁵

大体上我们要使用引理1，不过需要一点准备

证明

首先我们要缩减 A

从 A 中移除那些度小于 |B|/2K 的点剩下的就是 A~ ，因为从 G 到 G~ 最多移除 |A||B|/2K 条边， G~ 中至少还有|A||B| |A~||B|

───＝───＝

2K 2K|A~|/|A|

|A~||B| |A~||B|

───＝───

2K/L K′

条边，对此时的图 G~＝G~(A~，B，E~) 应用引理1，我们选择 ϵ：＝1

──

16K ，可得到子集 A~′⊆A~

|A~| |A|

|A~′|≥|A~|≥ ───＝───

── √2(2K/L) 2√2K

√2K′

1

满足条件至少有比例 1−─

16K 的配对(α，α′)∈A~′×A~′被至少 ϵ

─ |B| L²|B|

2K′²|B|＝───＝───

16K⋅2⋅(2K/L)² 128K³ 条 G~ 中的 2 路径相连

反过来最多有比例 1

─

16K 的配对(α，α′)∈A~′×A~′ 它们被少于 L²|B|

───

128K³ 条 G~ 中的 2 路径相连，我们称之为坏的配对

我们选取那些最多有 1

─

数学联邦政治世界观提示您：看后求收藏（同人小说网http://tongren.me），接着再看更方便。