Quasi-randomness and The Regularity Lemma

准随机性和规律性引理

• 批准号: 0071261
• 负责人: Vojtech Rodl
• 金额: $ 15.46万
• 依托单位: Emory University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2000
• 资助国家: 美国
• 起止时间: 2000-08-01 至 2003-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0071261&HistoricalAwards=false
• 关键词: Quasi; randomness; Regularity; Lemma

The probabilistic method pioneered and chiefly developed by Paul Erdos has become one of the most powerful tools in combinatorics. Extensive research has been carried out in the study of random graphs and other combinatorial structures, often motivated by applications requiring the proof of existence of certain combinatorial objects. This project is oriented to this vigorously developing area in which probabilistic reasoning plays a crucial role in the proof of deterministic statements. One of the most notable examples is the Regularity Lemma of Szemeredi. This lemma allows one to decompose any graph into components whose quasi-randomness ensures the existence of certain substructures, as though they were random objects. Proof methods based on the Regularity Lemma already have numerous applications in graph theory and theoretical computer science. Recently, some of these techniques have been extended to sparse graphs (to which the original regularity lemma could not be applied) as well as to some set systems. The Principal Investigator plans systematic study of such techniques.

由 Paul Erdos 首创并主要发展的概率方法已成为组合学中最强大的工具之一。在随机图和其他组合结构的研究中已经进行了广泛的研究，通常是由需要证明某些组合对象的存在的应用程序推动的。该项目面向这个蓬勃发展的领域，其中概率推理在确定性陈述的证明中发挥着至关重要的作用。最值得注意的例子之一是 Szemeredi 的正则引理。这个引理允许人们将任何图分解为组件，这些组件的准随机性确保了某些子结构的存在，就好像它们是随机对象一样。基于正则引理的证明方法已经在图论和理论计算机科学中得到了广泛的应用。最近，其中一些技术已扩展到稀疏图（原始正则引理无法应用到稀疏图）以及某些集合系统。首席研究员计划对此类技术进行系统研究。