塞迈雷迪正则性引理

✍ dations ◷ 2025-10-15 16:07:37 #图论,组合数学,信息论,引理

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

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

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

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

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

1, ...,  为将 分成 份的划分。其称为 -正则划分,若:

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

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

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

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

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

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

相关

  • 螺旋CTCT可指:
  • 悬雍垂悬雍垂(palatine uvula,又名腭垂,俗称“小舌”、“吊钟”)是人体口腔器官,悬挂于软颚正中间的末端。悬雍垂的功能是在饮食时上升堵住食物通过鼻腔进入气管的通道,从而使食物进入食
  • 大君主作战(1944年-1945年)霸王行动(英语:Operation Overlord)为诺曼底战役的代号,是盟军于第二次世界大战期间成功夺回德占西欧的军事行动。1944年6月6日诺曼底登陆开始(海王星行动,Operation
  • 安平六角头安平六角头为台湾旧安平地区的六个聚落,分别为海头社、港仔尾社、王城西社、灰窑尾社、十二宫社和囝仔宫社。其中“角头”(kak-thâu)为台语,教育部台湾闽南语常用词辞典的定义
  • 任何事任何事(英语:Anything)是艾迪塔·歌娳娅的第二张专辑和第一张国际专辑艾迪塔的第四支派台单曲。 这首歌由Pam Sheyne 和 Will Mowat 作曲及填词,Christopher Neil制作,而单曲封
  • 吕底亚语吕底亚语是一种在安那托利亚西部的吕底亚地区语言,在今土耳其境内,隶属于印欧语系的安那托利亚语族。尽管被分类在安那托利亚语族内,吕底亚语的地位独特且有疑问。首先,了解这种
  • 飞·奇幻世界万时红 刘成树 姚海军 《飞·奇幻世界》(Fantasy World,缩写FW)是总部位于中华人民共和国四川省成都市的中文月刊,创刊于2003年,前身是科幻世界杂志社的《科幻世界少年版》。《飞
  • 蔡斯·阿特利蔡斯·卡麦隆·厄特利(Chase Cameron Utley,1978年12月17日-),出生在加利福尼亚州的帕萨迪纳。阿特利是属于左打右投的选手,自从成为费城人队的固定先发二垒手以后,阿特利的表现证
  • 必比登必比登(法语:Bibendum)是米其林公司的吉祥物,是该公司的创始人是阿里斯蒂德·巴比尔和爱德华·道布里两个堂兄弟,在1832年于法国克莱蒙费朗成立的农用机械和橡胶工厂。最初主要制
  • 欧洲冬青欧洲冬青(学名)是一种原产于西欧及南欧、西北非洲及西南亚洲的冬青。欧洲冬青是常绿树,高达10-25米,树干直径40-80厘米阔,树皮呈灰色及光滑。叶子长5-12厘米及阔2-6厘米,形状各有