1.1 KiB
1.1 KiB
title, created, updated, type, tags, sources
| title | created | updated | type | tags | sources | |||||
|---|---|---|---|---|---|---|---|---|---|---|
| Szemerédi Regularity Lemma | 2026-05-11 | 2026-05-11 | concept |
|
|
Szemerédi Regularity Lemma
定义
Szemerédi 正则性引理（Endre Szemerédi, 1975）断言：任意大图可以分解为有限个"拟随机"的子图结构。具体地，对任意 ε > 0，存在 M(ε)，使得任意图的顶点集可划分为至多 M 个几乎等大的部分，且绝大多数部分对之间构成 ε-正则对。
Ramsey 型精神
引理的证明和大量应用都带有深刻的 Ramsey 型思想：在足够大的结构中，必然存在有序的子结构。它提供了从"完全无序"到"近似有序"的系统化方法。
核心应用
- 三角形移除引理：少量三角形可被移除
- 图同态计数：大图中的子图频率估计
- 超图正则性：高维推广，解决多个长期悬而未决问题