The Regularity Method for Sparse Graphs and Hypergraphs

稀疏图和超图的正则方法

• 批准号: 5443326
• 负责人: Professor Dr. Mathias Schacht
• 金额: --
• 依托单位: Forschungsschwerpunkt Diskrete Mathematik
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2005
• 资助国家: 德国
• 起止时间: 2004-12-31 至 2007-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/5443326?language=en
• 关键词: Regularity; Method; Sparse; Graphs; Hypergraphs

This proposal seeks further development and understanding of the Regularity Method, which has had a series of successes in Discrete Mathematics. The Regularity Lemma of E. Szemerédi for graphs asserts that every dense graph can be decomposed into relatively few random-like subgraphs. This random-like behavior enables one to find and enumerate subgraphs of a given isomorphism type. This observation is called Counting Lemma. The interplay of Szemerédi's Regularity Lemma and the Counting Lemma, referred to as the Regularity Method for dense graphs, has many applications in the area ot extremal graph theory. Since random graphs of a given edge-density are usually easier to analyze than arbitrary graphs of the same edge-density, the Regularity Method enables us to transfer some methods applicable to random graphs to the class of all graphs. In recent years the Regularity Method was partly expanded to new types of discrete structures: sparse graphs and k-uniform hypergraphs. In particular, analogues of the Regularity Lemma for these combinatorial objects were established. In the proposed program, we seek a deeper understanding of the random-like behavior guaranteed by those Regularity Lemmas. Furthermore, we focus on applications of these novel techniques in the area of extremal combinatorics.

该建议寻求进一步的发展和理解规律方法，该方法在离散数学方面取得了一系列成功。图形E.szemerédi的规律引理断言，每个密集的图都可以分解为相对较少的随机样子图。这种随机行为使人们能够找到并枚举给定同构类型的子图。该观察结果称为计数引理。 Szemerédi的规律性引理和计数引理的相互作用（称为密集图的规则性方法）在极端图理论的区域中有许多应用。由于给定边缘密度的随机图通常比相同边缘密度的任意图更容易分析，因此规则性方法使我们能够将适用于随机图的某些方法传输到所有图的类别。近年来，规律性方法部分扩展到新的离散结构类型：稀疏图和K-均匀的超图。特别是，建立了这些组合物体的规则性引理的类似物。在拟议的计划中，我们寻求对这些规律性引理保证的随机行为的更深入的了解。此外，我们专注于这些新技术在极端组合技术领域的应用。