塞迈雷迪正则性引理

数学上，塞迈雷迪正则性引理（Szemerédi regularity lemma）断言，给定任意一个足够大的图，都可以将其顶点集划分成若干个差不多一样大的子集，使得几乎每两个不同的子集之间的边，都具有随机二部图的性质。塞迈雷迪于 1975 年引入了该引理较弱的版本，其只适用于二部图，用作证明塞迈雷迪定理[1]，后来再于 1978 年证明了完整的版本[2]。 Vojtěch Rödl（英语：Vojtěch Rödl） 及其合作者[3][4][5]和高尔斯[6][7]将正则性方法推广到超图上。

定义和引理叙述

塞迈雷迪正则性引理的严格叙述须用到下列定义。设 G 为一幅图，而 V 为其顶点集。

密度

设 X, Y 为 V 的两个互斥子集。定义 (X, Y) 的密度为

 

其中 E(X, Y) 为一个顶点在 X 中，而另一个顶点在 Y 中的边的集合。

ε-正则

对于 ε > 0, 称两个由顶点组成的集合 X 和 Y 为 ε-正则，若对任意满足|A| ≥ ε|X| 和 |B| ≥ ε|Y| 的子集 A ⊆ X 和 B ⊆ Y, 都有

 

ε-正则划分

设 V1, ...,  Vk 为将 V 分成 k 份的划分。其称为 ε-正则划分，若：

  • 对每个 i, j 都有 Vi 与 Vj 的大小至多相差 1.
  • 除了至多 εk2 对满足 i < j 的 Vi, Vj 以外，其他的每一对都 ε-正则。

利用上述定义，可以写出引理的严格叙述。

正则性引理

对任意的 ε > 0 和正整数 m, 存在整数 M, 其满足：若 G 为至少有 M 个顶点的图，则存在整数 k 满足 m ≤ k ≤ M, 和一个 ε-正则划分将 G 的顶点集分成 k 份。

引理的证明所给出的 M 的上界极大，比如 m 的 O(ε−5) 次迭代幂次。若实际的上界并非如此大，而是 exp(ε -β) 的形式的话，则其可应用在其他地方。然而，高尔斯于 1997 年找到了一些图作为例子，证明 M 确实可以增长得极快，比如至少为 m 的 ε−1/16 次迭代幂次。由此可见，最佳的上界必定位于 Grzegorczyk 分层（英语：Grzegorczyk hierarchy）中的第 4 层，因此不属初等递归函数[8]。

推广

János Komlós（英语：János Komlós）、Gábor Sárközy（英语：Gábor Sárközy）和塞迈雷迪·安德烈其后（于 1997 年）证明了blow-up 引理[9][10] ，其断言塞迈雷迪正则性引理中的正则对，在特定意义下与完全二部图具有同样的性质。若考虑将大而疏的图，嵌入到一个稠密的图中，则适用 blow-up 引理来深入研究该嵌入的性质。

陶哲轩以概率方法证明了一条不等式，其推广了塞迈雷迪正则性引理[11]。

注意，不可能在塞迈雷迪正则性引理中，证明“所有”对都正则。原因是，一些图（比如半图（英语：Half graph））确实需要划分中有若干对顶点集非正则，尽管按照正则性引理，这样的对只占很小一部分。[12]

参考文献

  1. ^ Szemerédi, Endre, On sets of integers containing no k elements in arithmetic progression, Polska Akademia Nauk. Instytut Matematyczny. Acta Arithmetica, 1975, 27: 199–245 [2018-12-02], MR 0369312, （原始内容存档于2012-02-05） .
  2. ^ Szemerédi, Endre, Regular partitions of graphs, Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), Colloq. Internat. CNRS 260, Paris: CNRS: 399–401, 1978, MR 0540024 .
  3. ^ Frankl, Peter; Rödl, Vojtěch, Extremal problems on set systems, Random Structures & Algorithms, 2002, 20 (2): 131–164, MR 1884430, doi:10.1002/rsa.10017.abs .
  4. ^ Rödl, Vojtěch; Skokan, Jozef, Regularity lemma for k-uniform hypergraphs, Random Structures & Algorithms, 2004, 25 (1): 1–42, MR 2069663, doi:10.1002/rsa.20017 .
  5. ^ Nagle, Brendan; Rödl, Vojtěch; Schacht, Mathias, The counting lemma for regular k-uniform hypergraphs, Random Structures & Algorithms, 2006, 28 (2): 113–179, MR 2198495, doi:10.1002/rsa.20117 .
  6. ^ Gowers, W. T., Quasirandomness, counting and regularity for 3-uniform hypergraphs, Combinatorics, Probability and Computing, 2006, 15 (1-2): 143–184, MR 2195580, doi:10.1017/S0963548305007236 .
  7. ^ Gowers, W. T., Hypergraph regularity and the multidimensional Szemerédi theorem, Annals of Mathematics, Second Series, 2007, 166 (3): 897–946, MR 2373376, arXiv:0710.3032  , doi:10.4007/annals.2007.166.897 .
  8. ^ Gowers, W. T., Lower bounds of tower type for Szemerédi's uniformity lemma, Geometric and Functional Analysis, 1997, 7 (2): 322–337, MR 1445389, doi:10.1007/PL00001621 .
  9. ^ Komlós, János; Sárközy, Gábor N.; Szemerédi, Endre, Blow-up lemma, Combinatorica, 1997, 17 (1): 109–123, MR 1466579, doi:10.1007/BF01196135 
  10. ^ Komlós, János; Sárközy, Gábor N.; Szemerédi, Endre, An algorithmic version of the blow-up lemma, Random Structures & Algorithms, 1998, 12 (3): 297–312, MR 1635264, arXiv:math/9612213  , doi:10.1002/(SICI)1098-2418(199805)12:3<297::AID-RSA5>3.3.CO;2-W 
  11. ^ Tao, Terence, Szemerédi's regularity lemma revisited, Contributions to Discrete Mathematics, 2006, 1 (1): 8–28, Bibcode:2005math......4472T, MR 2212136, arXiv:math/0504472   .
  12. ^ Conlon, David; Fox, Jacob, Bounds for graph regularity and removal lemmas, Geometric and Functional Analysis, 2012, 22 (5): 1191–1256, MR 2989432, arXiv:1107.4829  , doi:10.1007/s00039-012-0171-x 

参见

  • Komlós, J.; Simonovits, M., Szemerédi's regularity lemma and its applications in graph theory, Combinatorics, Paul Erdős is eighty, Vol. 2 (Keszthely, 1993), Bolyai Soc. Math. Stud. 2, János Bolyai Math. Soc., Budapest: 295–352, 1996, MR 1395865 .
  • Komlós, J.; Shokoufandeh, Ali; Simonovits, Miklós; Szemerédi, Endre, The regularity lemma and its applications in graph theory, Theoretical aspects of computer science (Tehran, 2000), Lecture Notes in Computer Science 2292, Springer, Berlin: 84–112, 2002, MR 1966181, doi:10.1007/3-540-45878-6_3 .