极值图论
极值图论旨在探究在避免特定子结构的情况下，图可以有多大或多稠密，并识别出极值构型。
用 PaperMind 寻找选题即将推出Find papers & topics
Tools & resources
Learn & explore
视频即将推出
Definition
研究图参数（例如边的数量）的最大值或最小值，但需满足结构约束，例如不存在固定的子图。
Scope
本主题围绕图兰型问题展开——即在没有给定子图的情况下，图中边的最大数量。它始于曼特尔定理和图兰定理，并扩展到埃尔德什-斯通定理，该定理确定了任何被禁止子图的渐近极值密度。它介绍了密度、结构和塞迈雷迪正则性方法之间的相互作用。
Core questions
- 在n个顶点的图中，若不包含给定子图的副本，则其最大边数是多少？
- 哪些图能达到这些极值边界？
- 被禁止子图的色数如何决定渐近解？
- 正则性方法如何将稠密图简化为有界结构？
Key concepts
- 禁止子图
- 图兰图
- 曼特尔定理
- 极值数（图兰数）
- 埃尔德什-斯通定理
- 塞迈雷迪正则性引理
Key theories
- 图兰定理
- 在所有n个顶点的图中，若不包含r+1个顶点的完全子图，则平衡的完全r部图拥有最多的边，这推广了曼特尔的无三角形图边界，并奠定了极值图论的基础。
- 埃尔德什-斯通定理
- 对于任何固定的禁止子图H，无H图的最大边密度渐近地由H的色数决定，统一了图兰型极值结果。
Clinical relevance
极值密度结果限制了大型网络和约束系统的结构，而在此领域发展起来的正则性方法在属性测试、理论计算机科学和加性组合学中都有应用。
History
曼特尔1907年关于无三角形图的边界和图兰1941年的推广开启了该领域；埃尔德什-斯通-西蒙诺维茨理论和塞迈雷迪正则性引理使其成为现代组合学的核心支柱。
Key figures
- Paul Turan
- Paul Erdos
- Endre Szemeredi
Related topics
Seminal works
- bollobas1998
- diestel2017
Frequently asked questions
- 什么是图兰型问题？
- 它询问一个图在避免固定子图的情况下可以拥有的最大边数；典型的例子是无三角形图中的最大边数。
- 极值图论与拉姆齐理论有何关系？
- 两者都研究不可避免的结构，但极值理论固定一个禁止子图并使边数最大化，而拉姆齐理论则保证一旦图足够大，就会出现单色结构。