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

|≤─── |B| 显然有

2K² ϵ

|N(α)∩N(α′)|＜──

────── 2K²

𝔼α，α′∈A𝕀[(α，α′)∈Ω] |B|

反过来就是

1 |N(α)∩N(α′)|

𝔼α，α′∈A(1−─ϵ𝕀[(α，α′)∈Ω])──────

ϵ |B|

1

≥──

2K²

左边按照 b∈B 重新排列得到

1

𝔼b∈B───

|A|² 1 1

∑α，α′∈N(b)(1−─ 𝕀[(α，α′)∈Ω])≥──

ϵ 2K²

所以必然存在 b∈B 使得

1

──

|A|² 1 1

∑α，α′∈N(b)(1−─ 𝕀[(α，α′)∈Ω])≥──

ϵ 2K²

此时 |N(b)|≥|A|

──

√2K 而且 |(α，α′)∈N(b)：(α，α′)∈Ω|≤ϵ|N(b)|²

，这很显然，因为左边求和非负值

于是我们只要令 A′：＝N(b) 命题便成立

注意我们其实把 A 缩减很多，甚至都缩减到某个 b 的邻域 N(b) ，但是只要是常数倍的缩减就都在一个数量级上，变化仍然不大

引理2 3 路径的估计

给定 |E|≥|A||B|/K，K≥1 的二分图 G(A，B，E) ，存在满足 |A′|≥|A|

──

4√2K 和 |B′|≥|B|

──的

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